发布时间 : 星期四 文章实验一 线性表操作实验题目更新完毕开始阅读
实验一 线性表操作
实验目的：
(1)掌握在顺序、链式存储结构上实现线性表的各种基本运算。 (2)重点掌握单链表的基本操作及应用。
(3)学会综合运用C语言中函数、指针、结构体等知识进行编程。 本次实验中，下列实验项目选做一。
1、顺序表的综合操作
[问题描述]
设计算法，实现线性结构上的顺序表的建立以及元素的查找、插入、删除等操作。
[基本要求及提示]
（1）从键盘输入10个整数，建立顺序表。
（2）从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。
（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。
（4）从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
（5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
2、线性表的逆置
[问题描述]
（1）以顺序存储结构实现线性表的就地逆置。 （2）以链式存储结构实现线性表的就地逆置。
注：线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,?,an）逆置为（an，an-1，?，a2，a1）。
[基本要求及提示]
（1）从键盘输入10个整数，建立顺序表。 （2）实现顺序表逆置，并将结果输出。 （3）从键盘输入10个整数，建立链表。 （4）实现链表逆置，并将结果输出。
（5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。也可以将顺序表和链表上的操作分开，做成两个程序。
3、线性表的元素分类
[问题描述]
已知线性表中元素均为正整数，设计算法将其调整为前后两部分，前边均为奇数，后边均为偶数。即实现线性表的元素的分类。
[基本要求及提示]
（6）从键盘输入10个整数，建立顺序表。
（7）实现顺序表上的元素分类，并输出结果。 （8）从键盘输入10个整数，建立链表。 （9）实现链表的元素分类，并输出结果。
（10）要求程序通过一个主菜单进行控制。也可以将顺序表和链表上的操作分开，做成两个程序。
（11）要求程序的时间复杂度为O(n)，空间复杂度为O(1)。
4、线性表的有序合并
[问题描述]
已知有两个非递减的线性表，设计算法将其有序合并为一个线性表，元素值是非递增排序。
[基本要求及提示]
（1）从键盘输入两个非递减的整数序列，建立两个非递减的顺序表L1,L2。 （2）将顺序表L1,L2有序合并，结果非递增，输出合并后的结果。
（3）从键盘输入两个非递减的整数序列，建立两个非递减的链表L3,L4。
（4）将链表L3,L4有序合并，结果非递增，输出合并后的结果（采用头插法）。 （5）要求程序通过一个主菜单进行控制。也可以将顺序表和链表上的操作分开，做成两个程序。
（6）要求程序的时间复杂度为O(n)，空间复杂度为O(1)。
5、链表的综合操作
[问题描述]
设计算法，实现线性结构上的链表的建立、元素的查找、插入、删除等操作。
[基本要求及提示]
（1）从键盘输入10个字符以$结束，建立链表。
（2）从键盘输入1个序号，在链表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。
（3）从键盘输入1个整数，表示欲插入的位置i，再输入一个字符x，将x插入在i位置上，输出链表所有结点值，观察输出结果。
（4）从键盘输入一个整数，表示欲删除结点的位置，删除该结点，然后输出链表所有结点值，观察输出结果。
（5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
6、在顺序表上删除自第i个开始的k个元素
[问题描述]
建立一个非空的值域为整数的顺序表，从键盘输入i和k的值，编程实现删除自第i个元素开始的k个元素。
[基本要求]
（1） 建立长度至少为10的顺序表；
（2） 从键盘输入两个整数i和k，进行删除运算，删除成功显示“OK”，不成功显
示“ERROR”。注意讨论i和k的合法性。
（3） 显示顺序表的内容；
（4） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调
用各功能函数。
7、在顺序表上删除所有值为item的数据元素
[问题描述]
建立一个非空的值域为整数的顺序表，从键盘输入一个整数item，编程实现删除表中所有值为item的数据元素。
[基本要求]
（1） 建立长度至少为10的顺序表；
（2） 从键盘输入一个整数item，删除表中所有与item相同的元素，删除成功显示
“OK”，不成功显示“ERROR”。
（3） 显示顺序表的内容；
（4） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调
用各功能函数。
8、在顺序表上删除所有值相等的多余元素
[问题描述]
建立一个非空的值域为整数的顺序表，编程实现删除表中值相等的多余元素。
[基本要求]
（1） 建立长度至少为10的顺序表； （2） 删除表中值相等的多余元素。 （3） 显示顺序表的内容；
9、在单链表上，删除所有值在[mink,maxk]内元素
[问题描述]
建立一个非空的值域为整数的表头结点的单链表，从键盘输入两个整数mink，naxk；编程实现删除表中值域大于等于mink，同时小于等于maxk的数据元素。
[基本要求]
（1） （2） （3） （4）
建立长度至少为10的单链表；
删除单链表中表中，值域大于等于mink，同时小于等于maxk的结点。 显示单链表的内容；
要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
10、查找单链表倒数第k个结点
[问题描述]
设有一个值域为整数有头结点的非空单链表，从键盘输入正整数k；在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置的结点，若查找成功，输出该节点的数据域的值，并返回1，否则显示“ERROR”，并返回0。
[基本要求及提示]
（1） 编写非空的值域为整数的单链表的建立函数；
（2） 设工作指针p和q，当p从首节点开始沿链向前走到第k个节点（参考教材
P50-2.8算法）；此时使q指向首节点q=L->next；如此q与p是相距k个节点两个指针；再一同向前走，当p走到表尾时，q即指向倒数第k个结点。
11、在无头结点的循环链表上，删除s结点之前驱结点
[问题描述]
假设有一个循环链表的长度大于1，数据域为整数，且表中既无头结点也无头指针。已知s为指向链表的某一结点的指针，试编写程序在循环链表中删除s的前驱结点。
[基本要求及提示]
（1） 编写建立无头结点循环链表函数，也无头指针，返回该循环链表的某结点的指
针（可以是尾指针）；
（2） 编写删除s结点的前驱结点函数，while(p->next->next!=s)p=p->next; （3） 编写输出链表函数；
（4） 要求程序通过一个主菜单（1.建立；2.删除；3.输出；4.退出）调用各功能函
数。
12、单链表上元素的分类
[问题描述]
已知单链表表示的线性表中含有三类字符（如字母字符、数字字符和其他字符），试编写程序来构造三个以循环链表表示的线性表，使每个表中只含有某一类的字符，且利用原表中的节点空间，作为这三个表的结点空间，头结点可以另辟空间。
[基本要求及提示]
（1） 编写建立无头结点尾指针标识的循环链表函数；
（2） 从键盘输入一个整数key，编写删除链表中值域等于key的结点的前驱结点函
数。
（3） 编写显示单链表的内容函数；
（4） 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调
用各功能函数。
13、双向链表的综合操作
[问题描述]
设计算法，实现双向链表的建立、元素的查找、插入、删除等操作。
[基本要求及提示]
（1）从键盘输入10个整数以-999结束，建立数据域为整数的双向链表。
（2）从键盘输入1个序号，在双向链表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。
（3）从键盘输入两个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在i位置上，输出链表所有结点值，观察输出结果。
（4）从键盘输入一个整数，表示欲删除结点的位置，删除该结点，然后输出链表所有结点值，观察输出结果。
（5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
14、单链表按给定规则合并
[问题描述]
设线性表A=（a1,a2,?，am）,B=（b1,b2,?，bn）,试编写一个按下列规则合并A，B为线性表C的算法，使得
C=（a1,b1,a2,b2,?，am,bm,bm+1,?，bn）或C=（a1,b1,a2,b2,?，an,bn,an+1,?，am）线性表C均以单链表为存储结构，C表利用A，B表的节点空间构成。链表的长度均为显示存储。
[基本要求及提示]
（1）首先编写单链表的初始化函数、单链表创建函数及输出函数。 （2）再编写合并函数。
（3）在主函数中调用其它函数进行调试运行。
15、多项式的奇偶项的分解
[问题描述]
将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅含有奇数项或偶数项，并要求用原链表中的结点空间来构成这两个循环链表。
[基本要求及提示]
（1）首先编写循环链表的初始化函数、循环单链表创建函数（P63-2.21）及输出函数。 （2）再编写分解函数。
（3）在主函数中调用其它函数进行调试运行。
16、给定x值，求多项式P(x)的值
[问题描述]
多项式P(x)采用单链表存储，参见教材的类型定义，写一个算法，对给定x值，求多项式P(x)的值。
[基本要求及提示]
（1）首先编写单链表的初始化函数、单链表创建函数及输出函数。
（2）再编写求值函数，提示求出每一个结点的值，进行累加。提示：结点p的值：p->coef*pow(x,p->exp)。
（3）在主函数中调用其它函数进行调试运行。
17、单链表转换
[问题描述]
已知有单链表（a1,a2,?，an），n为偶数，要求写出一个时间复杂度为O（n），辅助空间为O（1）的算法，将上述单链表转换成（an,an-2,?，a2,a1,a3,?，an-1）。参见教材P75图2.24.
[基本要求及提示]
（1）首先编写单链表的初始化函数、单链表创建函数及输出函数。
（2）再编写转换函数。提示：指针p扫描单链表，依次将第2，4，6?，n结点删除，同时头插到本链表上。
p=L->next;
while(p->next!=NULL)
{s=p->next;p->next=s->next; s->next=L->next;L->next=s; p=p->next;} （3）在主函数中调用其它函数进行调试运行。