数据结构(C++）——顺序表

顺序表和链表的比较

　　1.存取方式

　　　　顺序表可以随机访问，而链表只能从表头顺序查找。（因此经常查找顺序表某一个元素时，顺序表更适合）

　　2.逻辑结构与物理结构

　　　　顺序表中，逻辑上相邻的元素，其物理存储位置也相邻。链表中，逻辑相邻的元素，其物理存储位置不相邻。

　　3.查找、插入和删除操作

　　　　按值查找时，顺序表链表时间复杂度都为O(n)。

　　　　按序号查找时，顺序表时间复杂度为O(1)，而链表时间复杂度为O(n)。

　　　　插入和删除元素中，顺序表平均移动半个表的长度，而链表只需要改变一下指针域的值就可以了。

　　　　（因此，当线性表经常进行插入和删除元素时，选链表更合适）

　　4.空间分配

　　　　顺序表在静态存储分配的情形下，存储空间装满了就不能扩充；链表就不存在这个问题。

顺序表结构

#define MaxSize 50  //顺序表的最大长度

typedef char ElemType; //ElemType为数据类型

typedef struct    //顺序表的静态表示 
 {
    ElemType data[MaxSize];
    int length;    
}SqList;

顺序表的初始化

SqList CreateList()  //初始化顺序表 
{
    SqList L;    
    L.length=0;   //初始化要将顺序表的长度初始化为0 

    return L;
}

向顺序表插入元素

bool InsertList(SqList &L,int i,ElemType d){    //插入元素 
    if(i<1||i>L.length+1||i>MaxSize)  //将数据插入在第i个位置 
    {                                    //插入的位置错误，返回false 
        return false;
    } 

    for(int j=L.length;j>=i;j--)  //从后往前，将下标i-1及以后的元素向后移一个位置，为插入的元素腾位置 
    {
        L.data[j]=L.data[j-1];    //插入元素是向后移动 
    }

    L.data[i-1]=d;                //低昂待插入的元素放的要插入的位置 
    L.length++;                   //插入完成后，长度加1 

    return true;                 //操作成功返回true 
}

删除顺序表中的元素

bool DeleteList(SqList &L,int i,ElemType &e){   //删除顺序表中的元素 
    if(i<1||i>L.length){       
        return true;                //下标错误时，返回false 
    }

    e=L.data[i-1];                 //返回待删除的数据 

    for(int j=i;j<L.length;j++){     //从第i个开始向后 
        L.data[j-1]=L.data[j];
    }

    L.length--;                  //删除后长度减短 

    return true;                //操作完成，返回true 
}

查找顺序表中的元素

int FindList(SqList &L,ElemType e){   //返回第一个与e相等的元素的次序号，找不到返回0 
    for(int i=1;i<=L.length;i++){
        if(L.data[i-1]==e){    //判断第i个元素是否等于e 
            return i;           //等于则返回位置 
        }
    }

    return 0;                  //遍历完顺序表还找不到 返回0 
}

显示表内元素

void PrintList(SqList &L){
    for(int i=0;i<L.length;i++)
    {
        cout<<L.data[i]<<' ';
    }
}

原文链接: https://www.cnblogs.com/WP-WangPin/p/12739166.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/343271

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

数据结构(C++）——顺序表

相关推荐