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