数据结构第二章线性表.pptVIP

线性表的操作ListDelete_L(L,i,e)在链表中的实现:有序对ai-1,ai和ai,ai+1改变为ai-1,ai+1ai-1aiai+1ai-1在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemTypee){//删除以L为头指针(带头结点)的单链表中第i个结点p=L;j=0;while(p-nextji-1)//寻找第i个结点，并令p指向其前驱{p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放结点e=q-data;free(q);returnOK;}//ListDelete_L算法的时间复杂度为:O(ListLength(L))删除同插入操作不合法判定部分不同空表如何从线性表得到单链表？ 链表是一个动态结构。整个可用存储空间可为多个链表共用，每个链表占用的空间不需预先分配划定，可由系统应需求即时生成。因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。创建带头结点的单链线性表voidCreateList_L(LinkListL,intn){//逆序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带头结点的单链表for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(p-data);//输入元素值p-next=L-next;L-next=p;//插入到表头}}//CreateList_L算法的时间复杂度为:O(Listlength(L))线性表合并将两个有序链表合并为一个有序链表。设立三个指针pa、pb和pc分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到pc所指结点之后，即，让pc指向该元素，然后，修改指针。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。VoidMergeList_L(LinkListLa,LinkListLb,LinkListLc){//已知单链线性表La和Lb的元素按值非递减排列//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列pa=La-next;pb=Lb-next;Lc=pc=La;//用La的头结点作为Lc的头结点While(papb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}//MergeList_L条件赋值变量名＝条件表达式？表达式T：表达式F；if(pa)?

??pc-next?=?pa;?

?else?

??pc-next?=?pb;2538LaLbpapbLcpcpa=La-next;pb=Lb-next;Lc=pc=La;2538LaLbpapbLcpcWhile(papb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}2538LaLbpapbLcpcWhile(papb){