线性表的顺序存储结构：

    用一段地址连续的存储单元依次存储线性表中的数据元素

    

1. #define MAXSIZE 20//数组的长度  
2.  
3. typedef int ElemType; 
4. typedef struct{ 
5.     ElemType data[MAXSIZE];//数组来实现  
6.     int length;//线性表的长度  
7. }SqList; 

随机存取：

    LOC(ai)=LOC(a1)+(i-1)*c，对线性表位置的存取是一个常量，存取时间为O(1)     ，我们称这种特性为随机存取结构。

获得元素的操作

    首先，表是否为空，表的自身因素

    其次，i的取值是否合适，范围因素

    最后，执行代码

1. bool getElem(SqList L,int i,ElemType *e){ 
2.     if(L.length == 0 || i<1 || i>L.length){
   //i的取值范围是[i,L.length]  
3.         return false; 
4.     } 
5.     *e = L.data[i-1]; 
6.     return true; 
7. } 

插入操作

    首先，表是否满了

    其次，i的取值是否合适

    接着将代码后移

    将新元素插入

    长度更新

 

1. bool listInsert(SqList *L,int i,ElemType e){ 
2.     int index; 
3.      
4.     if(L->length == MAXSIZE){
   //如果表满了  
5.         return false; 
6.     } 
7.     if(i<1 || i>(L->length+1)){
   //如果插入的位置不合理[1,length+1]，此处理解为插入第i个元素的前面！  
8.         return false; 
9.     } 
10.     for(index=(L->length-1);index>=i-1;index--){
    //后移元素  
11.         L->data[index+1] = L->data[index]; 
12.     } 
13.     L->data[i-1] = e;//插入新元素  
14.     L->length++;//长度增加  
15.     return true; 
16. } 

删除操作

    首先，判断该表是否为空

    其次，判断删除位置i是否合适

    接着，将被删元素赋值给e

    接着，将所有元素前移

    最后更改长度

 

1. bool listDelete(SqList *L,int i,ElemType *e){ 
2.     int index; 
3.      
4.     if(L->length == 0){
   //是否为空  
5.         return false; 
6.     } 
7.     if(i<1 || i>L->length){
   //位置是否合适[1,length]  
8.         return false; 
9.     } 
10.     *e = L->data[i-1];//删除的元素赋值给e  
11.     for(index=i;index<L->length;index++){
    //一次前移  
12.         L->data[i-1] = L->data[i]; 
13.     } 
14.     L->length--;//长度减1  
15.     return true; 
16. } 

时间复杂度分析

    最好情况的插入删除都繁盛在最后的位置，时间复杂度为O(1)

    最坏情况的插入删除都发生在第一个元素，时间复杂度为O(n)

    一般情况也为O(n)

    这说明,顺序存储结构适用于元素个数变化不大，多存取少增删的应用。

优缺点分析