吉林工业职业技术学院
（ 数据结构实训任务书 ）
（ 2014 ~ 2015 学年第 1 学期）
实践班级： 计算机3131 实践时间： 2014.12.15 ~ 2014.12.26 实践天数： 10天 指导教师： 张君楠、刘文宏 专业教研室： 计算机应用技术
自动化 系（部） 系（部）主任：
吉林工业职业技术学院 数据结构实训
数据结构实训任务书
计算机3131班同学：
根据教学计划，你们将在第17-18周进行为期2周的数据结构实训，现将实训题目及要求下达给你们，请你们在规定的时间内完成此项任务。
一、实训题目 （一）单项题目 1、练习打字游戏
【问题描述】 学生自己设置3个文本文件（.txt），文件名为：file1.txt，file2.tx，file3.txt。每个文件内含1000个左右字符（英文字母或其他字符都可以）。实现从用户指定文件随机抽取100个字符并显示在屏幕上供用户参照打字的功能。
【要 求】程序运行后，屏幕显示菜单界面供用户选择练习方式及退出，进行相应选择。根据提示的文本内容，用户可以同步输入练习内容，最后在屏幕上显示得分、录入速度、正确率。使用c语言文件函数。用到头文件：#include
2、表达式求值
【问题描述】求一个数学表达式的值：用户输入一个包含正整数、括号、和算术运算符（＋、－、*、/、^）的算术表达式，计算其结果。
【要 求】输入的表达式为中缀表达式，将其转换成后缀表达式，然后对后缀表达式进行求值。程序运行后，键盘输入中缀表达式，然后显示中缀表达式，再显示后缀表达式，最后输出运算结果。
3、万年历
【问题描述】编写一个万年历的程序。输入年份和月份的值后，即可将对应的12个月的日历打印出来。附加功能：判断是否为闰年。
【要 求】分屏输出月份的信息，每季度（3个月）在一个屏幕内显示出来，然后停止，之后按任意键继续显示下一屏幕信息。
4、二叉树遍历
【问题描述】 建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。
2
吉林工业职业技术学院 数据结构实训
【要 求】编写菜单程序。能够输入二叉树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数；输出中序遍历序列的函数；输出后序遍历序列的函数；输出层序遍历序列的函数。
5、八皇后问题
【问题描述】8个皇后在一个8*8的棋盘上下棋，一个皇后放入一个棋子后，另一个皇后所放的棋子不能与前一个皇后所放的棋子在同一行、同一列（在每一横列竖列斜列只有一个皇后），将所有可能的棋子放法求出来。
【要 求】采用如下方式之一输出棋盘：（1）以数组的形式输出棋盘；（2）以图形方式输出棋盘。
6、图的深度和广度优先搜索遍历
【问题描述】 给定一个无向图，利用邻接矩阵或邻接表进行存储，然后按照深度和广度进行遍历。
【要 求】以吉林省的城市：白城、松原、长春、公主岭、四平、辽源、吉林市、通化、白山、延吉所构成的地理图为无向图。求以吉林市为出发点深度和广度优先搜索遍历序列。
7、全屏幕模拟时钟
【问题描述】 用C语言模拟时钟的运行。
【要 求】 时钟要求有时针、分针、秒针（既能按机械表行走，又能按电子表显示时间和日期）。用到头文件：#include
8、二分法查找演示
【问题描述】 用箭头表示指针，模拟出二分法查找的指针变化过程。
【要 求】 给定一组数据。可以动态地显示二分法查找的过程。用到函数：setcolor(WHITE)－画颜色，line(x1,y1,x2,y2)－画直线;，bar(x1,y1,x2,y2)－画矩形，settextstyle(0,0,2)－字体大小，outtextxy(x,y,变量或常量)－输出内容; initgraph(&gd,&gm,\－tc所在目录的路径，setfillstyle(SOLID_FILL,0)－每次演示的时候先将下面显示的文字给去处掉，等等。
3
closegraph();
吉林工业职业技术学院 数据结构实训
9、排序算法
【问题描述】实现各种常用排序（直接插入排序、二分法排序、直接选择排序、冒泡排序、希尔排序、快速排序）算法。
【要 求】编写菜单程序，按照升序排序。输入数据元素的个数任意，输入数据元素的值任意（正整数），输出排序前、排序后的数据元素。
10、约瑟夫环
【问题描述】：编号是1，2，??,n的n（n>0）个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。开始时任选一个正整数作为报数上限值m，从第一个开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
【要 求】：利用单循环链表存储结构解决此问题，按照出列的顺序输出各个人的编号。键盘输入m、n的初值和每个人的密码（密码也可以利用随机函数产生）。 （二）综合题目 1、迷宫探险
【问题描述】小人在迷宫的左上角进入迷宫，从右下角走出迷宫，在行走过程中不走回头路，即不重复经过同一点，将走过的路径表示出来。
【要 求】可以输入一个任意大小的迷宫数据，用非递归或递归的方法求出一条走出迷宫的路径，并将路径输出。迷宫大小为〔m×n〕，用数组〔0..m+1,0..n+1〕表示，四周有墙，用0表示有路，用1表示墙。（1）假设小人在迷宫中有8个方向可选。
2、物业管理系统
【问题描述】建立一个物业管理信息文件，包括门牌号（num）、户主（name）、住宅面积（area）、物业费（expense）、交费情况（flag）、电话（phone）等。
【要 求】编写菜单程序，功能包括：建立户主记录、插入记录，删除记录、修改记录、按照门牌号或户主姓名查询记录、显示记录、保存文件。定义物业结构体名称为administer。门牌号（num）、户主（name）、交费情况（flag）、电话（phone）均
4
吉林工业职业技术学院 数据结构实训
为字符型数组，长度分别为4、8、1、7。住宅面积（area）、物业费（expense）为单精度型数据。
3、员工管理系统
【问题描述】建立一个员工信息文件，包括工号（num）、姓名（name）、性别（sex）、职务（post）、部门（dpartment）、工龄（years）等。
【要 求】编写菜单程序，功能包括：建立员工记录、插入记录，删除记录、修改记录、按照工号或姓名查询记录、显示记录、保存文件。定义员工结构体名称为staff。工号（num）、姓名（name）、性别（sex）、职务（post）、部门（dpartment）、工龄（years）均为字符型数组，长度分别为2、8、2、12、12、2。
4、通讯录管理系统
【问题描述】建立一个本班学生通讯录文件，包括学号（num）、姓名（name）、性别（sex）、电话（phone）、电子邮箱（email）、住址（addr）。
【要 求】编写菜单程序，功能包括：建立通讯录、插入记录，删除记录、修改记录、按照学号或姓名查询记录、显示记录、保存文件。定义班级学生结构体名称为student。学号（num）、姓名（name）、性别（sex）、电话（phone）、电子邮箱（email）、住址（addr）均为字符型数组，长度分别为2、8、2、11、20、20。
5、学生成绩管理系统
【问题描述】 编写一个学生成绩管理系统，实现计算每个学生的总分、平均分，班级的总分、平均分，按分数高低排序。包含插入、删除、修改、查询、显示模块。 【要 求】成绩包括本学期所开设的课程（数据结构、计算机网络、数据库原理、??），采用菜单程序编写。包含插入、删除、修改、查询、显示模块。
6、图书管理系统
【问题描述】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。
【要 求】编写菜单程序，功能包括：建立图书信息、插入记录，删除记录、修改记录、按照书号或书名查询记录、显示记录、根据图书价格进行排序。定义图书信息结构体名称为book。书号（num）、书名（bookname）、作者（name）、出版社（publish）均为字符型数组。价格（price）为单精度型数据。
附加题目:哈夫曼编码和译码系统
【问题描述】编写一个程序模拟哈夫曼编码通信过程，实现在发送前将要发送的字
5