上机实验题2

1．基础实验题

（1）设计整数顺序表的基本运算程序，并用相关数据进行测试。

（2）设计整数单链表的基本运算程序，并用相关数据进行测试。

（3）设计整数循环单链表的基本运算程序，并用相关数据进行测试。

（4）设计整数双链表的基本运算程序，并用相关数据进行测试。

（5）设计整数循环双链表的基本运算程序，并用相关数据进行测试。

2．应用实验题

（1）假设一个顺序表L中所有元素为整数，设计一个算法调整该顺序表，使其中所有小于零的元素移动到所有大于等于零的元素的前面。并用相关数据进行测试。

（2）有一个整数序列，采用顺序表L存储。设计尽可能高效的算法删除L中最大值的元素（假设这样的元素有多个）。并用相关数据进行测试。

（3）设有一个顺序表L，其元素均为正整数，设计一个算法将L中所有偶数删除并存到另一个顺序表L1中，而顺序表L保留原来的所有奇数。并用相关数据进行测试。

（4）设计一个算法从顺序表中删除重复的元素，多个值相同的元素仅保留第一个。并用相关数据进行测试。

（5）设计一个算法从有序顺序表中删除重复的元素，多个值相同的元素仅保留第一个。并用相关数据进行测试。

（6）采用顺序表来存储非空整数集合（同一个集合中没有相同的元素，两个集合中可能存在相同的元素），设计完成如下功能的算法并用相关数据进行测试。

①求两个集合A、B的并集C。

②求两个集合A、B的差集C。

③求两个集合A、B的交集C。

（7）采用递增有序的顺序表来存储非空整数集合（同一个集合中没有相同的元素，两个集合中可能存在相同的元素），设计完成如下功能的算法并用相关数据进行测试。

①求两个集合A、B的并集C。

②求两个集合A、B的差集C。

③求两个集合A、B的交集C。

（8）有两个递增有序的整数顺序表A、B，设计一个算法将它们中的全部元素放到顺序表C中，要求C中元素是递减有序的。并用相关数据进行测试。

（9）有一个非空整数单链表L，其中可能出现值域重复的结点，设计一个算法删除值重复的结点，多个值相同的结点仅保留第一个。并用相关数据进行测试。

（10）有一个递增有序单链表（可能有值重复的结点），设计一个算法删除值域重复的结点，多个相同值的结点仅保留第一个。并用相关数据进行测试。

（11）有两个整数集合采用递增有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。

（12）有一个整数序列采用带头结点的单链表L存储。设计一个算法，删除单链表L中data值大于等于min且小于等于max的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。并用相关数据进行测试。

（13）令L1=（x1，x2，…，xn），L2=（y1，y2，…，ym）是两个线性表，n≥1，m≥1，采用带头结点的单链表存储，设计一个算法合并L1、L2，结果放在线性表L3中。

L3=（x1，y1，x2，y2，…，xm，ym，xm+1，…，xn）， m≤n

L3=（x1，y1，x2，y2，…，xn，yn，yn+1，…，ym）， m＞n

L3仍采用单链表存储。要求不破坏原有的单链表L1和L2。

（14）有一个带头结点的整数单链表L，设计一个算法实现这样的功能：将所有的负数结点移动到最前面（如果存在这样的结点），中间是为0的结点（如果存在这样的结点），最后是为正数的结点（如果存在这样的结点）。并用相关数据进行测试。

（15）当正整数的位数较多时，采用int或者long变量存储时会发生溢出，可以用一个单链表存储，每一位作为一个结点。设计完成如下功能的算法并用相关数据进行测试。

①由一个数字字符串创建对应的整数单链表。

②输出一个整数单链表表示的正整数。

③实现两个这样的正整数的加法运算。

④实现两个这样的正整数的乘法运算。

（16）有一个带头结点的非空双链表L，假设所有结点值为整数，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被使用之前，其值均初始化为零。每当进行LocateNode（L，x）运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。采用结点移动方式设计符合上述要求的LocateNode运算的算法。并用相关数据进行测试。

（17）有一个含n（n＞3）个整数的数据序列A，另外有一个查找元素的序列S，含m次查找，每次查找都是按元素序号i进行的（1≤i≤n，即每次查找都是成功的查找），如果采用顺序表存储数据序列A，由于顺序表具有随机存取特性，完成S的所有查找恰好需要m次。

但由于n的大小难以事先确定，现在小张采用链表结构存储数据序列A，这样完成S的所有查找需要多次移动结点，小张准备采用不带头结点的循环双链表L存储数据序列A，假设p指针首先指向循环双链表L的首结点，请你编程求出完成S的所有查找p指针移动的总次数。并用相关数据进行测试。