实验一 线性表
- 掌握线性表的逻辑结构定义和各种存储结构的实现。
- 熟练运用线性表的各种存储结构以及各种基本操作。
- 根据实际问题的需要，选择线性表的存储结构解决问题。
- 在教材介绍的顺序表类模板中增加成员函数
max()和min()，它们分别返回顺序表中元素值最大和最小的数据元素序号。 - 修改顺序表类模板中的插入函数。顺序表中的元素从小到大存放，插入元素时根据元素值的大小插入到顺序表的适当位置，保证顺序表的有序性。
- 在（2）的基础上，增加成员函数
deleteRange()，用来删除有序的顺序表中给定值在s和t之间的$(s<t)$所有元素，要求时间复杂度为$O(n)$。 - 在（2）的基础上，增加成员函数
merge()，能在线性阶的时间里完成两个有序表的合并。
（1）定义一个结构体，描述学生信息。学生信息包括：学号、姓名、性别、班级和电话号码等。用描述学生信息的结构体作为线性表的数据元素类型测试带头结点的单链表。 (2)修改带头结点的单链表类模板中的插入函数，插入元素时按元素值从小到大的顺序插入数据元素到链表的适当位置。 （3）在教材介绍的单链表类模板中增加成员函数 reversal()，其功能是对链表中元素结点进行逆置，即将线性表（a1，a2，…，an）逆置为（an，…a2，a1）。 （4）在（2）的基础上，增加函数 merge，能在线性阶的时间里完成两个有序表的合并。
（1）定义一个结构体，描述学生信息。学生信息包括：学号、姓名、性别、班级和电话号码等。用描述学生信息的结构体作为线性表的数据元素类型测试带头结点的双向循环链表。 （2）修改带头结点的双向循环链表类模板中的插入函数，使链表中的结点按元素从大到小的顺序排列。 （3）在教材介绍的双向循环链表类模板中增加成员函数 swap()，其功能是通过修改其中元素最大值和最小值结点的指针，交换两个结点的位置。
仿照教材中带头结点的单链表类模板，设计不带头结点的单循环链表类模板，并且增加成员函数reversal()，其功能是对链表中元素结点进行逆置，即将线性表$(a_1,a_2,\cdots,a_n)$逆置为$(a_n,\cdots,a_2,a_1)$。
模仿教材中带头结点的双向循环链表类模板，设计不带头结点的双向非循环链表类模板。并且增加成员函数swap()，其功能是修改其中元素最大值和最小值的指针，交换它们的位置。
仿照教材中带头结点的单链表类模板，设计带头结点的静态单链表类模板，并实现相应的成员函数。
仿照教材中带头结点的双向循环链表类模板，设计带头结点的双向静态循环链表类模板，并实现相应的成员函数。
某 IT 公司招聘新员工，收到了 N 份简历，人力资源部小 X 和小 Y 负责挑选简历安排面试，他们把 N 份简历排成一个圆圈，按逆时针方向编号为 1～N。开始时小 X 站在 1 号简历前，按逆时针方向数 k 份简历选中；小 Y 站在 N 号简历前，按顺时针方向数 m 份简历选中。两人同时取走所选简历后，分别按逆时针和顺时针走到下一份简历前，再重复如上的方法取简历，直到取走全部简历，如果两人选中同一份简历，则只输出一个编号。
要求输入 3 个数 N、K 和 M，按取走简历的顺序（先甲后乙）输出简历编号。
- 输入样例：
- 10 4 3
- 输出样例：
- 4,8;9,5;3,1;2,6;10,7
对于一元$n$次多项式$P_n(𝑥) = a_1x^{e_1} + a_2x^{e_2}+\cdots+a_mx^{e_m}(n＝e_1>e_2>\cdots>e_m\ge0)$用适当的数据结构表示。并要求对其实现求导、给定$x$值后求多项式的值和四则运算。
要求对一元$n$次多项式进行求导，给定$x$的具体值后求多项式的值，实现两个多项式的相减和相乘运算。为了方便多项式的建立和显示，要求编写独立的函数用于建立多项式和显示多项式。
由读者自己确定。注意测试边界数据，例如，多项式只有一个项为常数项等情况。
用一个线性表模拟电子词典的使用，线性表中每个数据元素记录一个单词及其使用次数（频率）。为了提高查找速度，要求将经常使用的单词存放在线性表的前部。第一次使用的单词（还不在电子词典中）插在线性表的表尾，使用频率为 1；以后每使用（查找）1 次，其使用频率加1，并根据其频率将该单词前移到线性表的相应位置，使线性表中的单词一直以频率为关键字递减排列，频率相同的根据查找的先后顺序排列。
利用双向链表模拟此过程，要求能查找单词、删除单词、显示词典中单词。查找单词时，找到该单词则显示单词的序号、单词、频率，否则在词典末尾插入该单词，并显示插入信息；删除单词时，如果词典中有该单词则先显示单词信息再进行删除，否则显示单词不存在信息；显示词典中单词按照词典中单词的顺序，列出每个单词的序号、单词、频率。
由读者自己确定，可以考虑利用文件初始词典。注意测试边界数据，例如，空词典时进行查找或删除等情况。
在物流系统中，经常需要应用仓库的进货和出货。在系统中，仓库一般需要登记产品的种类编号、产品名称和数量等信息。假设某地有一仓库，可存放 a～z 多种货物，每一种产品最多存放 1000 件。选择适当的数据结构实现物流仓库的管理。
模拟入库、出库和仓库盘点操作。入库时如果库存超出最大限额时系统应及时报警，如果仓库中没有该产品，则需要在仓库中添加新产品，否则只需修改库存数量。出库时如果库存不足时，系统应及时报警，否则需要修改库存，库存减少到 0 时在仓库中删除该产品。仓库盘点需要显示仓库中各产品的数量。
由读者自己确定。注意测试边界数据，例如，仓库中添加、删除产品