前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

顺序存储结构的插入与删除

获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem 操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码:

Status是函数的类型，其值是函数结果状态代码，如OK等

初始条件:顺序线性表L已存在，1≤i≤ListLength(L)

操作结果:用e返回L中第i个数据元素的值

#define OK 1
 #define ERROR 0
 #define TRUE 1
 #define FALSE 0
 typedef int Status;
 Status GetElem (SqList L,int i,ElemType *e)
 {
     if (L.1ength==01I 1<1 11 i>L.length)
         return ERROR;
     *e=L.data[i-1] ;
     return OK;
 }

注意这里返回值类型Status 是-一个整型，返回OK代表1, ERROR代表0。之后代码中出现就不再详述。

插入操作

刚才我们也谈到，这里的时间复杂度为0(1)。 我们现在来考虑，如果我们要实现ListInsert (*L,e),即在线性表L中的第i个位置插入新元素e，应该如何操作?

插入算法的思路:

如果插入位置不合理，抛出异常;

如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;

从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;

将要插入元素填入位置i处;

表长加1。

初始条件:顺序线性表L已存在，1≤i≤ListLength(L)

操作结果:在L中第i个位置之前插入新的数据元素e, L的长度加1

Status ListInsert (SqList *L,int i, ElemType e)
 {
     int k;
     if (L->length==MAXSIZE)     /*顺序线性表已经满*/
         return ERROR;
     if(i<1 || i>L->length+1)    /*当i不在范围内时*/
         return ERROR;
     if (i<=L->length)   /*若插入数据位置不在表尾*/
     {
         for (k=L->length-l;k>=i-1;k--)/*将要插入位置后数据元素向后移动一位*/
             L->data[k+1]-L->data[k];
     }
     L->data[i-1]=e;     /*将新元素插入*/
     L-> length++;
     return OK;
 }

删除操作

书上讲的例子很有意思，哈哈哈哈！！！

删除算法的思路:

如果删除位置不合理，抛出异常;

取出删除元素;

从删除元素 位置开始遍历到最后-一个元素 位置，分别将它们都向前移动一个位置;

表长减1

初始条件:顺序线性表L已存在，1≤i≤ListLength(L)

操作结果:删除在L中第i个数据元素，并用e返回其值, L的长度减1

Status ListDelete(SqList *L,int i, ElemType *e)
 {
     int k;
     if (L->length==0)   /*顺序线性表已经满*/
         return ERROR;
     if(i<1  || i>L->length+1)   /*当i不在范围内时*/
         return ERROR;
     if (i<=L->length)   /*若数据位置不在表尾*/
     {
         for (k = i;k < L->length;k++)/*将要插入位置后数据元素向后移动一位*/
             L->data[k+1]-L->data[k];
     }
     L->data[i-1]=e;     /*将新元素插入*/
     L-> length++;
     return OK;
 }

下面讨论下时间复杂度

当要插入或删除的元素在最后一个位置，那么时间复杂度为O（1），因为不需要移动元素

最坏的情况当然是插入或删除第一个元素，此时所有的元素都要向后移，时间复杂度为O（n）

以上平均下来，为（n-1）/2

通过前面讨论过时间复杂度的推导，可以得出，平均时间复杂度还是0[n)。这说明什么?线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是0(1);而插入或删除时，时间复杂度都是0[n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。 当然，它的优缺点还不只这些....

线性表顺序存储结构的优缺点

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间

可以快速地存取表中任

一位置的元素

缺点

插入和删除操作需要移动大量元素

当线性表长度变化较大时，难以确定存储空间的容量

造成存储空间的“碎片"