数据结构实验课.pdf

数据结构实验课--

数据结构课程实验实施方案（2015年）

一、总体设计要求

1、采用C编程语言，应用抽象数据类型的设计，在实现数据结构基本操作
的基础上，完成数据结构的基本应用。
2、程序采用模块化设计思想，划分功能模块结构，确定必要的模块间的联
系，按照基本操作调试、主算法设计与实现、主函数模块调用的步骤进行实验。
3、给出必要的测试用例数据。
4、推荐程序完成必要的界面设计。
5、完成实验题目中规定的基本功能，在完成基本功能的基础上，可以增加
和完善功能。
6、对所完成的实验课题的算法进行必要的时间和空间的性能评价。

二、实验分组要求

1、每个班分成若干个实验课题小组，每组原则上2-3人，个人自愿入组，
采用组长负责制。
2、每个实验给出若干个实验参考题目供课题组选择其中之一。
三、实验题目参考

实验一线性表应用类实验题目参考

1、约瑟夫环问题
【问题描述】
Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整
数m≤n，从第1人开始，沿环计数，第m人出列。这个过程一直进行到所有人
都出列为止。最后出列者为优胜者。全部出列次序定义了1，2，…n的一个排列。
称为（n，m）Josephus排列。例如，（7，3）Josephus排列为3,6,2,7,5,1,4。
【实验要求】
设计求解Josephus排列问题程序。
（1）采用顺序表、单链表等数据结构。
（2）或者，问题转化为“奇数次顺时针轮转，偶数次逆时针轮转”，采用双
向循环链表实现Josephus排列问题。

2、集合的并交差运算
【问题描述】
设计一个能演示集合的并、交、差运算程序。
【实验要求】
（1）采用顺序表或链表等数据结构。

数据结构实验课--
数据结构实验课--

（2）集合的元素限定为数字和小写英文字母。

3、一元多项式运算
【问题描述】
设计一个一元多项式简单计算器。
【实验要求】
（1）采用顺序表或链表等数据结构。
（2）输入并建立多项式。
（3）输出一元多项式加、减运算结果的多项式。

4、学生成绩管理
【问题描述】
对信息学院计算机科学与技术专业的20xx级本科生的学生成绩管理作一个
简单的模拟。
【实验要求】
设计学生成绩管理的模拟程序。
（1）采用顺序表登录学生成绩。
（2）可以登记、查询、插入、删除学生成绩。
（3）将成绩按科目存储到链表中。

5、图书信息管理
【问题描述】
对图书馆的图书信息管理作一个简单的模拟。
【实验要求】
设计图书信息管理的模拟程序。
（1）采用顺序表登录图书成绩。
（2）可以登记、查询、插入、删除图书信息。
（3）将图书信息按类别存储到链表中。

6、运动会竞赛成绩统计
【问题描述】
东北大学第51届运动大会成功举行。共有N个学院的男女代表队参赛。大
会共设M个男子项目和W个女子项目。大会即将闭幕，准备公布成绩。
【实验要求】
设计运动会竞赛成绩统计程序。
（1）采用顺序表或链表等数据结构。
（2）统计各代表队的男女总分和团体总分。
（3）公布各单项成绩的前六名和团体成绩的前三名。
（4）可以查询成绩。

数据结构实验课--
数据结构实验课--

实验二栈和队列应用类实验题目参考

1、算术表达式求值
【问题描述】
由输入的四则算术表达式字符串，动态生成算术表达式所对应的后缀式，通
过后缀式求值并输出。
【实验要求】
设计十进制整数四则运算计算器。
（1）采用顺序栈等数据结构。可以将数据存储在顺序表中。
（2）给定表达式字符串，后缀表达式。
（3）对后缀表达式求值并输出。

2、运动员混合双打组合
【问题描述】
设有M个男羽毛球运动员和N个女羽毛球运动员，现进行男女混合双打组
合K轮配对。男女运动员分别编号排队在等候队列，按顺序依次从男女运动员
中各出队1人组合配对。本轮没成功配对者等待下一轮次配对。
【实验要求】
设计程序模拟完成运动员组合配对过程。
（1）采用队列等数据结构。
（2）输出每轮的配对信息。

3、车厢调度
【问题描述】
假设停在铁路调度入口处的列车编号依次为1,2,…,n。
【实验要求】
设计程序求出所有可能的长度为n的输出车厢序列。
（1）采用栈或队列等数据结构。
（2）输出调度序列。
（3）推荐采用双栈结构求解。

4、八皇后问题
【问题描述】
设一个8×8的棋盘里放置8个皇后，要求在每行、每列、没斜线只允许放
置1个皇后。
【实验要求】
设计实现所有可能解的程序。
（1）采用栈等数据结构。
（2）应用穷举法回溯策略求解。
（3）尝试采用递归和非递归算法求解。

5、简单背包问题
【问题描述】

3

数据结构实验课--
数据结构实验课--

设一个背包所允许的重量是，假设有件物品，物品的重量分别是，
MNWi
可以任意挑选物品，从