顺序表链表算法应用.pptVIP

* * * * * * * * * * * * * * 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 … ... an 单循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 4、结构体链表合并 【4-1】已知两个单链表的头指针分别为La 和Lb，其中的数据元素均自小至大有序。编写算法将这两个链表归并为一个链表。 （非调用函数实现） 结构体链表合并 【解题分析】 通常容易想到的这个题的做法是，将 Lb 表中的各个结点插入到 La 表中的相应位置中去。即按照有序关系首先查找插入位置，然后修改相应指针。 另一种做法是，试设想新建一个空的链表，然后将已知两个链表中的结点依从小到大的次序逐个插入到这个新的链表中。 单链表合并 【参考算法】　　void MergeList_L(LinkList La, LinkList Lb, LinkList Lc){ //本算法归并La和Lb得到新的单链表Lc pa = La-next; pb = Lb-next; Lc = rc = new LNode; //建空表Lc?　?while (pa pb){　　　if (pa-data = pb-data) { 　　　　 rc-next = pa; rc = pa; pa = pa-next;　　　 }//if 结构体链表合并 else{ //将*pb插入Lc表，指针pb后移　　　　rc-next = pb; rc = pb; pb = pb-next; 　 　} // else } // while? 结构体链表合并 rc-next = pa ? pa : pb; // 插入剩余段　delete(La); delete(Lb); // 释放 La 和 Lb 的头结点　}// MergeList_L  此算法的时间复杂度为O(ListLength(La)+ListLength(Lb)) 结构体链表合并 结构体链表合并 【4-2】已知两个无序单链表的头指针分别为La和Lb。编写算法将这两个链表归并为一个链表。（调用函数实现） 本课结束 * * * * * * * * * * * * * * * * * * * * * * * * 1 删除重复元素 2 元素整体互换 3 单循环链表合并 4 结构体链表合并 顺序表链表算法应用题 1、删除重复元素 【1-1】编写算法删除顺序表中“多余”的数据元素，即使操作之后的表中所有元素的值都不相同。 删除重复元素 举一个例子：有一线性表序列 （5，2，5，3，3，4，2，5，7，5，4，3） 但如果不是从删除而是从插入来考虑问题，这个题的解法就会有不同的结果。 顺序表删除重复1 　 由于问题的实质是删除，因此所谓新表，在存储结构上并非是新建的表，它和原表可以共享存储空间，只须新建一个指针来指示其表尾的当前位置即可。 顺序表删除重复2 删除重复元素 【参考算法1】 void purge_Sq( SqList L ) { 　// 删除顺序表L中的冗余元素，使操作之//后的顺序表中只保留操作之前表中所有//值都不相同的元素 　k = -1;　　　　　// k 指示新表的表尾for (i=0; iL.length; ++i) {　// 顺序考察表中每个元素 删除重复元素 　 j=0; while(j=k L.elem[j]!=L.elem[i])  ++j;　 // 在新表中查询是否存在和 //L.elem[i]相同的元素if ( k==-1 || jk )　 // k=-1 表明当前考察的是第一个元素　L.elem[++k] = L.elem[i]; } // forL.length = k+1;　　// 修改表长 } // purge_Sq 删除重复元素 　　　 此算法的时间复杂度为O (ListLength2(L)) 分析：　　算法中的基本操作为比较，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，比较操作相对于移动操作所需的时间也少。 删除重复元素 1、删除重复元素 【1-2】编写算法删除单链表中“多余”的数据元素，