《数据结构》实验题目

《数据结构》实验指导

第一章 实验0 C/C++程序设计 一、 实验基础知识 二、 实验案例 1 学生成绩统计系统 [问题描述]

一个班同学的学号为1-n，输入n位同学的学号、姓名、语文、数学、英语等3门课程成绩，统计每位同学的总分后按成绩从高到低的次序输出。 [基本要求]

实现成绩表的录入、总分统计、总分排序和输出。 [测试数据]

对于10个同学的学号、姓名、语文、数学、英语等3门课程成绩设计实例数据 [实现提示]

1）用结构体设计同学记录，学号、各课程成绩和总分数据域用整型，姓名域采用字符数组；学生成绩表用数组模拟，数组大小根据实际学生数动态申请；学生成绩统计系统通过主菜单形式提供成绩表初始化、学生成绩录入、学生总分统计和排名、成绩表输出等功能。 [提高部分]

1）实现成绩表的文件录入和文件保存 2）实现成绩键盘录入的有效数据限制 2复数计算器 [问题描述]

设计一个能进行复数运算的演示程序。 [基本要求]

实现复数的基本运算：1）由输入的实部和虚部生成一个复数；2）求两个复数的和；3）求两个复数的差；4）求两个复数的乘积；5）求复数的实部；6）求复数的虚部 [测试数据] 0+0=0

3.1,0;4.22,8.9;输出7.32+i8.9 9,8;-9,8;输出i16 9,-8;-9,-8;输出-i16 -9,8;-9,-8;输出-18 9,-7;-9,8;输出i 9,-9;-9,8;输出-i [实现提示]

将复数的实部和虚部组成结构体数据类型，利用实数的操作实现复数的操作。 [提高部分]

1） 实现复数的除法运算；2）求共轭复数 3有理数计算器 [问题描述]

设计一个能进行有理数运算的演示程序。 [基本要求]

实现有理数的基本运算：1）由输入的分子和分母生成一个有理数；2）求两个有理数的和；3）求两个有理数的差；4）求两个有理数的乘积；5）求有理数的分子；6）求有理数的分母

[测试数据] [实现提示]

将有理数的分子和分母组成结构体数据类型，利用整数的操作实现有理数的操作。 [提高部分]

1）实现有理数的除法运算； 第二章 线性表

一、 实验基础知识 二、 实验案例

4顺序表基本操作演示系统 [问题描述]

设计一个能进行顺序表基本运算的演示程序。 [基本要求]

实现顺序表的基本运算：1）顺序表的初始化；2）置空顺序表；3）求表长；4）在指定位置插入新元素；5）查找指定位置元素；6）查找给定值元素；7）删除指定位置元素；8）删除指定值元素 [测试数据]

[实现提示]

[提高部分]

1）实现顺序表中重复元素的删除；2）实现有序顺序表的指定元素的保序插入；3）实现有序顺序表中重复元素的删除；

5单链表基本操作演示系统 [问题描述]

设计一个能进行单链表基本运算的演示程序。 [基本要求]

实现带头结点单链表的基本运算：1）单链表的初始化；2）置空单链表；3）求表长；4）在指定位置插入新元素；5）查找指定位置元素；6）查找给定值元素；7）删除指定位置元素；8）删除指定值元素 [测试数据]

[实现提示]

[提高部分]

1）实现无序单链表中重复元素的删除；2）有序单链表的指定元素的保序插入；2）实现有序顺序表中重复元素的删除；

6集合运算演示系统 [问题描述]

设计一个能进行集合基本运算的演示程序。 [基本要求]

1）限制集合基本元素为小写字母a-z；2）实现集合建立：a）集合的并；b）集合的交；c）集合的差；

[测试数据]

1)Set1=”magzine”,set2=”paper”

set1∪set2=”aeimnprz”,set1∩set2=”ae”,set1-set2=”gimnz” 2)set1=”012per4a6tion89”,set2=”error data”

set1∪set2=”adeinoprt”,set1∩set2=”aeort”,set1-set2=”inp” [实现提示]

以有序单链表表示集合 [提高部分]

1） 集合元素判定和子集判定；2）求集合的补集；

7约瑟夫环问题 [问题描述]

编号为1~n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向从1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出列顺序。 [基本要求]

利用无头结点循环链表存储模拟此过程；每个结点中包含序号、密码和指针域。 [测试数据]

当m初始值为20；n=7,7个人的密码依次为：3，1，7，2，4，8，4；正确的输出序列为6，1，4，7，2，3，5；当m初始值为2；n=1;密码为3；正确的输出序列为1。 [实现提示]

1）扫描指针应指向报数结点的前驱结点以方便出列；2）当表中只有一个结点时，无须报数了，直接出列即行。 [提高部分]

1） 采用带头结点单链表实现；2）采用顺序表实现；

8一元稀疏多项式计算器 [问题描述]

设计一个一元稀疏多项式计算器。 [基本要求]

实现一元稀疏多项式的基本运算：1）输入并建立一元稀疏多项式；2）输出多项式（以指数降序方式输出非零系数项的系数和指数）；3）实现一元稀疏多项式的相加； [测试数据]

[实现提示]

用带头结点的单链表存储多项式，每个结点中包含指数、系数和指针；单链表中结点按指数降序排列。 [提高部分]

1） 实现一元稀疏多项式的相减；2）实现一元稀疏多项式求导；

9仓储管理系统 [问题描述]

设计一个能对商厦商品进行管理的系统。

[基本要求]

实现：1）商品的入库；2）商品的出库；3）商品查询；4）营业前的商品数据恢复；5）营业结束的商品数据保存 [测试数据]

[实现提示]

用有序单链表模拟商品数据表。 [提高部分]

第三章 栈和队列

一、 实验基础知识 二、 实验案例 10顺序栈模拟器 [问题描述]

设计一个实现顺序栈的基本运算的演示程序。 [基本要求]

实现顺序栈的基本运算：1）顺序栈的初始化；2）置空栈；3）元素入栈；4）元素出栈；5）打印栈中元素 [测试数据]

[实现提示]

注意栈的溢出。 [提高部分]

1） 实现两栈共享一连续存储空间的基本运算；2）使用链栈实现栈的基本运算

11队列模拟器 [问题描述]

设计一个实现循环队列的基本运算的演示程序。 [基本要求]

实现循环队列的基本运算：1）循环队列的初始化；2）置空队列；3）元素入队；4）元素出队；5）打印队列中元素 [测试数据]

[实现提示]

1）通过设置队尾指针指向队尾元素，队首指针指向队首前一位置以及模运算方法实现循环队列；2）注意循环队列的溢出。 [提高部分]

1）用队尾指针指向真正队尾、队首指针指向真正队首和附加队列曼/空标记实现循环队列和循环队列的基本操作；2）用队尾指针加表长方式实现循环队列和循环队列的基本操作；3）用循环链表实现队列和队列的基本操作

12表达式括号匹配判断器 [问题描述]

设计一个判断一个表达式中的括号匹配是否配对的演示程序。