该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

顺序表上实现的基本运算

在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。

注意：

C语言中的数组下标从“0”开始，因此，若L是sqenlist类型的顺序表，则表中第i个元素是L.data[i-1]。

1、插入

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置上，插入一个新结点x，使长度为n的线性表

(a1，…a i-1，ai，…，an)

变成长度为n+1的线性表

(a1，…a i-1，x，ai，…，an)

算法：

int INSERT(sequenlist *L, datatype x, int i)

{

if (((*L).last)>=maxsize-1)

{print(“error”); return NULL;}

else   if ((i<1)||(i>(*L).last+2))

{print(“overflow”); return NULL;}

else

{for (j= (*L).last; j>=i-1; j--)    (该算法的时间主要花费在循环的结点后移语句上，在第i个结点位插入一个结点，执行该语句次数(即移动结点次数)是(n-i+1)。移动结点的次数不仅依赖于表的长度，而且还与插入位置有关)

(*L).data[j+1]=(*L).data[j];

(*L).data[i-1]=x;

(*L).last= (*L).last+1;

}

return(1);

}

当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O(n)。

当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O(n)。

表示算法最讲究的就是时间复杂度和空间复杂度

这个在ACM比赛中甚至都有严格的要求

所以，没个算法的时间复杂度都要熟悉