数据结构课件习题2

题2.12,题2.19,题2.22,题2.24,题2.27,题2.30,题2.38,题2.41,题2.20,题2.11,结束放映,Status Insert_Sq( SqList /Insert_Sq,题 2.11,返回,题2.12,已知 A=(a1, a2, , am) B=(b1, b2, , bn) 均为顺序表，试编写一个比较AB大小的算法。,分析：,1. 算法的目标是分析两个表的大小，则算法中不应当破坏原表；,2. 按题意，表的大小指的是“词典次序”，则不应当先比较两个表的长度；,3. 算法中的基本操作为：同步比较两个表中相应的数据元素。,while (iLa.Length & iLb.Length) ,int compare(SqList La, SqList Lb) ,if (La.elemi=Lb.elemi) i+; else if (La.elemiLb.elemi) return -1; else return 1;,i=0;,if ( iLa.length ,else if (iLb.Length) return 1; else return -1;,返回,题2.19,删除有序表中所有其值大于 mink 且小于maxk的数据元素。,首先分析需要删除的结点的特点：,mink,=maxk,pre,q,p,修改指针: pre-next = p;,释放结点: while (q!=p) s=q-next; free(q); q=s; , ,void delete(LinkList &L, int mink, int maxk) / delete,while (p /查找第一个值mink的结点,if (p) / if,q=pre-next; pre-next=p; / 修改指针,while (q!=p) s=q-next; delete q; q=s; / 释放结点空间,p=L-next;,while (p / 查找第一个值 maxk 的结点,返回,此题即为例2-2的第二种算法在单链表中的具体实现。,void purge_L( LinkList La ) / 删除带头结点的单链表 La 中所有多余的结点 if (La-next) / 只需要处理非空表 p = La-next; suc = p-next; while (suc) / 尚有后继未检查完 if (suc-data = p-data) q = suc; suc = suc-next; free q; / 释放值相同的结点空间 else / 链接值不同的结点 p = suc; suc = suc-next; / if /purge_L,题 2.20,返回,题2.22,逆置线性链表,a1,a2,a3,L,p,a1,a2,a3,基本操作：,1）标志后继结点； 2）修改指针（将*p插入在头结点之后）； 3）重置结点*p（p重新指向原表中后继）；,void inverse(LinkList ,返回,题2.24,将两个非递减有序的有序表归并为非递增的有序表（利用原表结点）。,La,Lb,Lc,操作步骤:,1) 建空表 Lc;,2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表中第一个结点之前直至其中一个表变空为止;,3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后;,4) 释放 La 表和 Lb 表的表头结点。,void union( LinkList& Lc, LinkList& La, LinkList& Lb) / 将非递减的有序表 La 和Lb归并为非递增的 / 有序表Lc,归并之后，La和Lb表不再存在。 / 上述三个表均为带头结点的单链表，Lc 表 / 中的结点即为原 La 或 Lb 表中的结点。,Lc = new LNode; Lc-next = NULL; pa = La-next; pb = Lb-next; / 初始化, / 归并,delete La; delete Lb; / 释放La 和 Lb的头结点, / union,返回,while ( pa | pb ) if ( !pa ) q = pb; pb = pb-next; else if ( !pb ) q = pa; pa = pa-next; else (pa-data data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; Lc-next = q; / 插入 ,完成此题用到了题2.24 和题2.20 的解题方法。,首先分析，需插入到 C 表中的元素的特性:,1) 是 A 表中的元素;,2) 在 B 表中有相同值的元素;,3) 在 C 表中尚未有值相同的元素，即该元素的值和 C 表表尾的元素值不等;,由此可见，此题的“控制结构”和题2.24 基本相同。差异仅在于循环体的内部，对只存在于 A 表中或只存在于 B 表中的元素均不予理睬，只需要考虑两表中值相同的元素是否插入C 表。,题 2.27,算法的基本思想:,1) 设 C 表为空表; k=0; i=j=1;,2) while ( A 表不空 ,void Intersect_Sq( SqList /Intersect_Sq,返回,已知A, B和C为三个有序链表，编写算法从A表中删除B表和C表中共有的数据元素。,题2.30,首先分析被删元素的特点为：ai=bj=ck,其它元素则为：,aibj,bjck,ckai,或,或,设三个指针 pa, pb 和 pc 分别指向这三个链表中的相应结点，则算法中的主要操作为：比较这三个结点元素的大小,void Difference_L( LinkList& La, LinkList Lb, LinkList Lc ) / La, Lb 和 Lc 分别为三个非递减有序的单链表 / 的头指针，从 La 表中删除所有的既在 Lb 表 / 中出现，又在 Lc 表中出现的元素结点,pre= La; pa=La-next; pb=Lb-next; pc=Lc-next;,while (pa & pb & pc) / while,/Difference,返回,else if (pb-datadata) pb=pb-next;,else if (pc-datadata) pc=pc-next;,else pre-next=pa-next; delete pa; pa=pre-next; / 删除，注意没有移动 pb 和 pc 才能 / 实现删除所有满足条件的结点,if (pa-datadata) pre=pa; pa=pa-next; ,题2.38,在双向循环链表的结点中，增加一个访问频度的数据域 freq，编写算法实现 LOCATE(L,x)。,注意算法的两个要点：,(1) 算法的基本操作应该是在链表中进行搜索, 直至( p=L | p-data=x )为止;,(2) 在访问频度 freq 增 1 之后，需将该结点调整到适当位置。向前搜索直至找到一个访问频度大于它的结点为止。,访问频度,p=L-next; / L为双向链表的头指针,while (p!=L / 搜索元素值为 x 的结点*p,if (p=L) return NULL;,q=p-priou; while (q!=L /搜索访问频度不小于它的结点*q,将结点 *p 从当前位置上删除; 之后将结点 *p 插入在结点 *q 之后; return p;,返回,题 2.41,void Difference_L( LinkedPoly pa ) / pa 为指向稀疏多项式循环链表的头指针， / 本算法将链表改变为该多项式的导函数 p = pa-next; p