实验一 线性表操作实验题目.doc

实验一 线性表操作 实验目的： (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、在顺序表上删除所有值相等的多余元素 [问题描述]