数据结构作业布置
上机题
3-2 针对带表头结点的单链表,试编写下列函数。
(2) 求最大值函数 max:通过一趟遍历在单链表中确定值最大的结点。
(4) 建立函数 create:根据一维数组 a[n]建立一个单链表,使单链表中各元素的次序与
a[n]中各元素的次序相同,要求该程序的时间复杂性为 O(n)。
3-10 试设计一个实现下述要求的 Locate 运算的函数。设有一个带表头结点的双向链表
L,每个结点有 4 个数据成员:指向前驱结点的指针 prior、指向后继结点的指针 next、存放
数据的成员 data 和访问频度 freq。所有结点的 freq 初始时都为 0。每当在链表上进行一次
Locate (x)操作时,令元素值为 x 的结点的访问频度 freq 加 1,并将该结点前移,链接到与
它的访问频度相等的结点后面,使得链表中所有结点保持按访问频度递减的顺序排列,以
使频繁访问的结点总是靠近表头。
思考题
3-1 线性表可用顺序表或链表存储。试问:
(1) 两种存储表示各有哪些主要优缺点?
(2) 如果有 n 个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数
也可能自动改变、在此情况下,应选用哪种存储表示?为什么?
(3) 若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元
素,这时,应采用哪种存储表示?为什么?
3-6 试写出用单链表表示的字符串类及字符串结点类的定义,并依次实现它的构造函
数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等
7 个成员函数。要求每个字符串结点中只存放一个字符。
3-8 设 a 和 b 是两个用带有表头结点的循环链表表示的多项式。试编写一个算法,计算
这两个多项式的乘积 c = a*b,要求计算后多项式 a 与 b 保持原状。如果这两个多项式的项
数分别为 n 与 m, 试说明该算法的执行时间为 O(nm
2
)或 O(n
2
m)。但若 a 和 b 是稠密的, 即其
很少有系数为零的项, 那么试说明该乘积算法的时间代价为 O(nm)。
参考题
1. 设单链表中结点的结构为(data, link)。已知指针 q 所指结点是指针 p 所指结点的直接前
驱,若在*q 与*p 之间插入结点*s,则应执行下列哪一个操作?
(1) s->link = p->link; p->link = s; (2) q->link = s; s->link = p;
(3) p->link = s->link; s-> link = p; (4) p->link = s; s->link = q;
2. 设单链表中结点的结构为(data, link)。已知指针 p 所指结点不是尾结点,若在*p 之后
插入结点*s,则应执行下列哪一个操作?
(1) s->link = p; p->link = s; (2) s->link = p->link; p->link = s;