第二章线性表要点分析.ppt

（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。 算法设计题 (1)Lc指向La (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后 (4) 释放 Lb 表的表头结点 【算法步骤】 12 23 34 45 56 11 32 43 48 54 La Lb Lc ∧ pa pb q pb ∧ q pa q pa q 第（2）题实现过程动态演示 （6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 【算法步骤】类似于求n个数中的最大数 可假设第一个结点最大，用指针pmax指向。 然后用pmax依次和后面的结点进行比较，发现大者则用pmax指向该结点。 这样将链表从头到尾遍历一遍时，pmax所指向的结点就是最大者。 其中的比较语句形式如下： if(p-data pmax-data) pmax=p; 算法设计题 （7）设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转，且仍利用原表的存储空间。　 算法设计题 【算法步骤】从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部 a1 a2 a3 ? L L p ? a1 ? p q a2 p q a3 p 标志后继结点q 修改指针（将p插入在头结点之后） 重置结点p（p重新指向原表中后继） q * * * 有序链表合并（初始化） pa La 1 7 8 2 4 6 8 10 11 Lb pb Lc = pc pa La(Lc ,pc) 1 7 8 2 4 6 8 10 11 Lb pb 有序链表合并( pa-data ＝pb-data ) pc-next = pa; Pa La(Lc) 1 7 8 2 4 6 8 10 11 Lb pb 有序链表合并( pa-data ＝pb-data ) pc-next = pa; pc= pa; 1 Pc La(Lc) 1 7 8 2 4 6 8 10 11 Lb pb 有序链表合并( pa-data ＝pb-data ) pc-next = pa; pc= pa; 1 Pc pa = pa-next; Pa La(Lc) 1 7 8 2 4 6 8 10 11 Lb pb 有序链表合并( pa-data pb-data ) pc-next = pb; 1 Pc pa La(Lc) 1 7 8 2 4 6 8 10 11 Lb pb 有序链表合并( pa-data pb-data ) pc-next = pb; 1 pa Pc pc= pb; 2 La(Lc) 1 7 8 2 4 6 8 10 11 Lb 有序链表合并( pa-data pb-data ) pc-next = pb; 1 pa Pc pc= pb; 2 pb =pb-next; pb La(Lc) 1 2 4 6 7 8 8 10 11 有序链表合并 pc- next=pa?pa:pb; pa(NULL) pb pc La(Lc) 1 2 4 6 7 8 8 10 11 合并后 delete Lb; 有序链表合并 void MergeList_L(LinkList La,LinkList Lb,LinkList Lc){ pa=La-next; pb=Lb-next; pc=Lc=La; //用La的头结点作为Lc的头结点 while(pa pb){ 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; //插入剩余段 delete Lb; //释放Lb的头结点} T(n)= S(n)= O(1) 【算法描述】－有序的链表合并 思考1：要求合并后的表无重复数据，如何实现？ 提示：要单独考虑pa-data = =pb-data La(Lc) 1 2 4 6 7 8 8 10 11 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。 表中允许有重复的数据。 思考2：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？ (1)Lc指向La (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在