辅导stata顺序线性表、线性表数据结构
- 首页 >> OS编程顺序线性表的操作
1.问题描述：
基于线性表的动态顺序存储结构，通过函数分别实现以下操作的算法。
2.实现要求：定义实现以下操作的函数
⑴ 顺序表的建立：通过键盘输入所建立的顺序表的元素个数 n，通过随机
生成的方式生成在[100,100000]之间的整数。
⑵ 输出顺序表的所有元素。
⑶ 求出顺序表中值最小和次小的元素值，要求该算法的时间复杂度为 O(n)，
最小和次小的元素值通过指针变量带回，函数不需要返回值。
⑷ 删除顺序表中值在 S 与 T 之间(S 和 T 的大小关系任意)的所有元素，要求
该算法的时间复杂度为 O(n)，若 S 和 T 不合理或顺序表为空则显示错误信息。
⑸ 删除顺序表中所有值重复的所有元素，使得顺序表中的所有元素两两互
不相同，要求该算法的时间复杂度为 O(n2
)，然后调用函数输出处理之后的顺序
表的所有元素。
⑹ 顺序表的排序，要求该算法的时间复杂度为 O(n ㏒ 2
n
)，然后调用函数输
出处理之后的顺序表.
⑺ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
11 / 43
6. 单链表操作
1.问题描述：
针对带头结点的单循环链表，编写实现以下操作的算法函数。
2.实现要求：
⑴ 单链表建立函数 create：先输入数据到一维数组 A[M]中，然后根据一维
数组 A[M]建立一个单循环链表，使链表中个元素的次序与 A[M]中各元素的次序
相同，要求该函数的时间复杂度为 O(m)；
⑵ 定位查找函数 Locate：在所建立的单循环链表中查找并返回值为 key 的
第 1 个元素的结点指针；若找不到，则返回 NULL；
⑶ 求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为
O(m)，最大和次大的元素值通过指针变量带回，函数不需要返回值；
⑷ 将链表中所有值比 key(值 key 通过形参传入)小的结点作为值为 key 的结
点前驱，所有值比 key 大的结点作为值为 key 的结点后继，并尽量保持原有结点
之间的顺序，要求该算法的时间复杂度为 O(m);
⑸ 设计一个菜单，具有上述处理要求和退出系统功能。
12 / 43
7. 集合运算 (单循环链表)
1.问题描述：
设有两个带头结点的单循环链表存储的集合 A、B，其元素类型为字符或者
整形，且以非递减方式存储，其头结点分别为 ha、hb。要求下面各问题中的结
果集合同样以非递减方式存储，结果集合不影响原集合。
2.实现要求：
⑵ 编写集合元素测试函数 IN_SET，如果元素已经在集合中返回 0，否则返
回 1；
⑶ 编写集合元素输入并插入到单链表中的函数 INSERT_SET，保证所输入
的集合中的元素是唯一且以非递减方式存储在单循环链表中；
⑶ 编写求集合 A、B 的交 C=A∩B 的函数，并输出集合 C 的元素；
⑷ 编写求集合 A、B 的并 D=A∪B 的函数，并输出集合 D 的元素；
⑸ 求集合 A 与 B 的对称差 E=(A-B)∪(B-A) 的函数，并输出集合 D 的元素；
⑹ 设计一个菜单，具有输入集合元素、求集合 A、B 的交 C、求集合 A、B
的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。
3.测试数据：字符型和整形由同学们自定，但集合 A、B 的元素个数不得少于 15
个。
13 / 43
8. 集合运算 (动态顺序表)
1.问题描述：
设有两个动态顺序表存储的集合 A、B，其元素类型为字符或者整形，且以
非递减方式存储。要求下面各问题中的结果集合同样以非递减方式存储，结果集
合不影响原集合。
2.实现要求：
⑴ 编写集合元素测试函数 IN_SET，如果元素已经在集合中返回 0，否则返
回 1；
⑵ 编写集合元素输入并插入到单链表中的函数 INSERT_SET，保证所输入
的集合中的元素是唯一且以非递减方式存储在动态顺序表中；
⑶ 编写求集合 A、B 的交 C=A∩B 的函数，并输出集合 C 的元素；
⑷ 编写求集合 A、B 的并 D=A∪B 的函数，并输出集合 D 的元素；
⑸ 求集合 A 与 B 的对称差 E=(A-B)∪(B-A) 的函数，并输出集合 D 的元素；
⑹ 设计一个菜单，具有输入集合元素、求集合 A、B 的交 C、求集合 A、B
的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。
3.测试数据：由同学们自定，但集合 A、B 的元素个数不得少于 15 个。
14 / 43
9. 双端队列的操作
1.问题描述：
双端队列：双端队列也是一种限制存取位置的顺序存取结构，有 3 种方式：
① 允许在两端进队和出队的双端队列。可看成是栈底连在一起的两个栈，
两个栈的栈顶指针向两端延伸。(两个栈混和)
② 允许一端插入，但允许两端删除的双端队列。可看成是栈底和队尾连在
一起的栈、队混和，栈顶可以插入和删除、队首可以删除。(栈、队混和)
③ 允许两端插入，但只允许一端删除的双端队列。可看成是栈底和队首连
在一起的栈、队混和，栈顶可以插入和删除、队尾可以插入。(栈、队混和)
2.实现要求：
设用不带头结点的双向链表表示双端队列，front 和 rear 分别是指向队首、
队尾的指针，请编写实现双端队列操作的函数。
⑴ 写出分别可以在 front 端和 rear 端进行入队、出队操作的 4 个函数。
⑵ 写出只能在 front 端出队但能在 rear 端进行入队、出队操作的 3 个函数。
⑶ 写出只能在 rear 端出队但能在 front 端进行入队、出队操作的 3 个函数。
15 / 43
10.矩阵的操作
1.问题描述：
给定两个矩阵 A=(aij)m×n，B=(bij)p×q，完成相应的操作。
2.实现要求：
⑴ 编写矩阵输入函数 INPUT_MAT，通过该函数完成矩阵的输入并返回保
存矩阵的数组和对应矩阵的行数、列数。（不能使用全局变量）
⑵ 编写矩阵输出函数 OUTPUT_MAT，通过该函数完成矩阵的输出。
⑶ 求矩阵的转置，矩阵的转置 A
’
=(aji)n×m，转置前输出原矩阵，转置后输
出转置矩阵。
⑷ 求矩阵 A、B 的和。矩阵 A 和 B 能够相加的条件是：m=p，n=q；矩阵 A
和 B 如果不能相加，请给出提示信息；若能够相加，则求和矩阵 C 并输出 C。
C=A+B=(cij)m×n，其中 cij=aij+bij
⑸ 求矩阵 A、B 的积。矩阵 A 和 B 能够相乘的条件是：p=n；矩阵 A 和 B
如果不能相乘，请给出提示信息；若能够相乘，则求积矩阵 D 并输出 D。
D=A×B=(dij)m×q，其中 dij=∑aik×bkj，k=1,2,……,n
⑹ 设计一个菜单，具有求矩阵的转置、求矩阵的和、求矩阵的积、退出等
基本的功能。在求矩阵的和或求矩阵的积时要求能够先提示输入两个矩阵的，然
后再进行相应的操作。