数据结构全套配套课件C语言描述第2版李学刚教学课件2-02顺序表的插入.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件2-02顺序表的插入.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2016数据结构Datastructure讲授：简勇顺序表的插入常州信息职业技术学院0203顺序表的插入0.2121．顺序表的初始化将当前表L的表长置为0。可将顺序表作为参数。具体算法：voidInitList(SeqList*L){//将当前表L的表长L->length置为0L->length=0;}2．求顺序表的长度返回当前表L的长度。可将顺序表作为参数。具体算法：intLengthList(SeqList*L){//返回顺序表L的表长L->lengthreturnL->length;}一、顺序表的基本操作04顺序表的插入0.2一、顺序表的基本操作

2、3．取表元返回当前表L第i个结点的值。注意：第i个结点存放在L->data[i-1]中。可将顺序表和整数i作为参数。具体算法：DataTypeGetList(SeqList*L,inti){//返回顺序表L的第i个结点的值L->data[i-1]return05顺序表的插入0.2算法步骤：二、顺序表的插入操作要求：将值为t的新结点插入到当前表L第i个结点的位置上，插入成功返回1，否则返回0。可将顺序表、新结点的值t和插入位置i作为参数。①判断插入位置是否正确，如果不正确，给出提示，返回0，否则，转向②。②判断当前表是否已满，如果已满，给出提示，返回0，

3、否则，转向③。③从最后一个结点开始依次后移，直到第i个结点，转向④。④将t插到第i个结点位置上，并将表长加1，返回1。06顺序表的插入0.2具体算法intInsertList(SeqList*L,DataTypet,inti){//将t插入顺序表L的第i个位置上intj;if(i<1

4、

5、i>L->length+1){puts("插入位置错");return0;}if(L->length>=ListSize){puts("表满不能插入");return0;}for(j=L->length-1;j>=i-1;j--)L->data[j+1]=L->data

6、[j];//结点依次后移L->data[i-1]=t;//插入tL->length++;//表长加1return1;}二、顺序表的插入操作07顺序表的插入0.2二、顺序表的插入操作算法分析显然程序中结点后移的语句执行的频度最高，而对不同的i该语句执行的频度也不相同，因此需要求该语句的平均频度。设顺序表的表长为n，即L->length=n，当i的值为1,2,…,n+1时，该语句的执行频度分别为：n,n-1,…,1,0，所以平均频度为n(n+1)/2/(n+1)=n/2，因此，该算法的时间复杂度为：T(n)=O(n)。THANKS2016.9.18