1、线性表的顺序存储结构

1.1 定义

  • 用一段地址连续的存储单元依次存储线性表的数据元素；
  • 顺序表顺序存储结构必须占用一片连续的存储空间，只要知道某个元素的存储位置就可以知道其他元素的存储位置。


1.2 线性表的顺序存储结构需要封装的三个属性

  • 存储空间的起始位置
  • 线性表的最大存储容量maxsize
  • 线性表的当前长度length


1.3 地址计算方法

  • 假设线性表的每个元素需要c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间的关系满足：LOC（ai+1）=LOC（ai）+c
  • 由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：LOC(ai)=LOC(a1)+(i-1)*c

2 线性表的顺序存储结构中方法的实现

2.1 创建顺序表

  • 顺序表的存储方式与数组类似，所以，我们可以用一维数组表示顺序表，但是我们的数组不能动态分配。所以我们用一个变量表示顺序表的长度属性。
  • 我们可以这样定义： ```c typedef char ElemType;

    define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量

    typedef struct{ ElemType elem[LIST_INIT_SIZE]; //静态分配数组 int length;//当前长度 }SqList;

typedef char ElemType;

define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量

typedef struct{ ElemType *elem;//动态分配数组 int length;//当前长度 }SqList;

//动态分配 SqList L; L.elem=(ElemType)malloc(sizeof(ElemType)LIST_INIT_SIZE);

  2. - 其中：ELemType是你需要用到的数据类型，根据问题进行修改，或者定义。
  4. **
  5. <a name="237Kx"></a>
  6. #### 2.2 线性表的基本操作
  8. - 操作算法中用到的预定义常量和类型
  9. ```c
  10. //函数结果状态代码
  11. #define TRUE 1
  12. #define FALSE 0
  13. #define OK 1
  14. #define ERROR 0
  15. #define INFEASIBLE -1
  16. #define OVERFLOW -2
  18. //Status 是函数的类型。其值是函数结果状态代码
  19. typedef int Status;
  20. typedef char ElemType;
  • 线性表L的初始化（参数用引用） ```c Status InitList_Sq(SqList &L){ //构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem)exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; }
  2. <a name="iI6tp"></a>
  3. #### 2.3 顺序表的插入方法
  5. - 插入算法：线性表的插入运算是指在第i(1<=i<=n+1)个位置上，插入一个新结点e，使长度为n的线性表(a1,…ai-1,ai…an)变成长度为n+1的线性表(a1,…ai-1,e,ai…an)
  7. - **算法思想**
  8.    - 判断插入位置i是否合法
  9.    - 判断顺序表的存储空间是否已满，若满了返回ERROR。
  10.    - 将第n到i位的元素依次向后移动一个位置，空出第i个位置。
  11.    - 将要插入的新元素e放入第i个位置。
  12.    - 将表长度+1，插入成功返回OK
  13. ```c
  14. Status ListInsert_Sq(SqList &L,int i,ElemType e){
  15.     if(i<1||i>L.length+1)return ERROR; //i值不合法
  16.     if(L.length==MAX_SIZE)return ERROR;  //当前存储空间已满    
  17.     for(j=L.length-1;j>=i-1;j--)
  18.     {
  19.         L.elem[j+1]=L.elem[j];    //将i-1之后所有元素后移
  20.     }
  21.     L.elem[i-1]=e;            //将新元素e放入第i个位置
  22.     L.length++;                //表长+1；
  23.     return OK;
  24. }

ASL=1(n-1)+2(n-2)+…+n*0 = (n-1)/2

2.4 顺序表的删除方法

  • 删除算法：线性表的删除运算是指将表的第i(1<=i<=n)个节点删除，使长度为n的线性表(a1,…,ai-1,ai,…,an)变为长度为n-1的线性表(a1…,ai-1,ai+1,…an)

  • 算法思想

    • 判断删除位置i是否合法
    • 将预删除的元素保留在e中。
    • 将第i+1至n位的元素依次向前移动一个位置。
    • 表长-1，删除成功返回OK ```c Status ListDelete_Sq(SqList &L,int i){ if(i<1||i>L.length) return ERROR; //i不合法 for(j=i;j<L.length;j++) {
      1. L.elem[j]=L.elem[j+1]; //被删除元素之后的元素前移一位
      } L.length—; //表长-1 return OK;

}

```

3、小结顺序表的特点

  • 利用数据元素的存储位置表示线性表中相邻数据元素的前后关系，既线性表的逻辑结构与存储结构一致。
  • 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址。因此可以粗略的认为，访问每个元素所花的时间相等。
  • 线性表的顺序存储结构，在存、读数据时，时间复杂度都是O(1)，而在插入删除数据元素时，时间复杂度是O(n)；
  • 线性表适用于，当需要大量存读数据时，可以考虑用顺序存储结构，而经常需要进行插入和删除数据时，顺序存储结构显然不是最好的；

3.1 顺序表的优点

  • 存储密度大(节点本身所占存储量/结点结构所占存储量)
  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速存取表中任意位置的元素


3.2 顺序表的缺点

  • 在插入、删除运算中，需要移动大量元素。
  • 容易造成存储空间的碎片，浪费存储空间
  • 输入静态存储形式，数据元素的个数不能自由扩充