题2.11 题2.19 题2.20 题2.24 题2.38
题2.12 题2.21 题2.27 题2.41
结束放映
题2.22
题2.30
题2.11
顺序表 设顺序表va中的数据元素 递增有序 递增有序。试写一算法，将x插 入到顺序表的适当位置上，以 保持该表的有序性。
题2.12
分析：
已知 A=(a1, a2, …, am) B=(b1, b2, …, bn) 均为顺序表，试编写一个比较 A¸ B大小的算法。
题2.20
同2.19题条件（线性表中的元素以 值递增有序排列，单链表作存储结构。）， 试写一高效的算法，删除表中所有 值相同的多余元素（使得操作后的 线性表中所有元素的值各不相同）， 同时释放被删结点空间，并分析你 算法的时间复杂度。
题2.21
试写一算法，对顺序表 就地逆置 实现就地逆置。
题2.22
题2.19
删除有序表中所有其值大于 mink 且 小于maxk的数据元素。 q
……
首先分析需要删除的结点的特点：
pre p
<=mink
>mink
< next = p;
释放结点: while (q!=p) {s=q->next; free(q); q=s; }
题2.24
La
q
将两个非递减有序的有序表归并为非 递增的有序表（利用原表结点）。
pa q 23 q pb 32 43 48 54 pa pa 34 45 56
12
Lb
q pb 11 ∧
Lc
∧
例 2-2 的第二种算法 在单链表中的具体实现。
q->next = Lc->next; Lc->next = q; // 插入
假设以两个元素值递增有序排列的线性表 A和B分别表示两个集合(同一表中元素值各不 相同),现要求另外开辟空间构成一个线性表C, 其元素为A和B中元素的交集,且C中元素也递增 有序排列,对顺序表完成此算法。 题2.27
对上述的条件做如下修改,在顺序表存储结 构上实现求表C的算法: (1)假设在同一表(A或B)中可能存在值相同的元 素,但要求新生成的表C中的元素各不相同； (2)利用A表空间存放表C。
试写一算法，对单链表 就地逆置 实现就地逆置。
分析 :
逐个把 L 的当前元素 q 插入 新链表头部， p 为新表表头。
题2.24
假设有两个按数据元素值递增 有序排列的线性表A和B，均以单 链表作为存储结构。请编写算法将 A表和B表归并成一个按元素值递 减有序（即非递增有序，允许表中 含有值相同的元素）排列的线性表 C，并要求利用原表（即A表和B表） 结点空间构造C表。
1. 算法的目标是分析两个表的大小，则 算法中不应当破坏原表； 2. 按题意，表的大小指的是“词典次 序”，则不应当先比较两个表的长度； 3. 算法中的基本操作为：同步比较两 个表中相应的数据元素。
题2.19
递增 已知线性表中的元素以值递增 有序 单链表 有序排列，并以单链表作存储结构。 试写一高效的算法，删除表中所有 值大于mink且小于maxk的元素（若 表中存在这样的元素），同时释放 被删结点空间，并分析你的算法的 时间复杂度。 时间复杂度
设有一个双向循环链表,每个结点 中除有prior,data和next三个域外,还增设 了一个访问频度域freq.在链表被起用之 前,频度域freq的值均初始化为零,而每 当对链表进行一次LOCATE(L,x)的操作 后,被访问的结点中的频度域freq的值增 加1,同时调整链表中结点之间的次序, 使其按访问频度非递增的次序顺序排 列, 以便始终保持被频访问的结点总是 靠近表头结点.试编写符合上述要求的 LOCATE操作的算法。
题2.30
已知A，B和C为三个递增的有 序的线性表，现要求对A表做如下 操作：删去那些既在B表中出现又 在C表中出现的元素，试对顺序表 编写实现上述操作的算法，并分析 你的算法的时间复杂度（注意：题 中没有特别指明同一表中的元素值 各不相同）。试对单链表编写算法, 请释放A表中的无用结点空间。
题2.38
题2.41
试以循环链表作为稀疏多项 式的存储结构,编写求其导函数的 算法,要求利用原多项式中的结点 空间存放其导函数(多项式),同时 释放所有无用(被删)结点。