2014-2015-1数构任务书.doc

吉林工业职业技术学院 数据结构实训吉林工业职业技术学院（ 数据结构实训任务书 ）（ 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 、#include 、#include 、#include 、#include 2、表达式求值【问题描述】求一个数学表达式的值：用户输入一个包含正整数、括号、和算术运算符（、*、/、）的算术表达式，计算其结果。【要 求】输入的表达式为中缀表达式，将其转换成后缀表达式，然后对后缀表达式进行求值。程序运行后，键盘输入中缀表达式，然后显示中缀表达式，再显示后缀表达式，最后输出运算结果。3、万年历【问题描述】编写一个万年历的程序。输入年份和月份的值后，即可将对应的12个月的日历打印出来。附加功能：判断是否为闰年。【要 求】分屏输出月份的信息，每季度（3个月）在一个屏幕内显示出来，然后停止，之后按任意键继续显示下一屏幕信息。4、二叉树遍历【问题描述】 建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。【要 求】编写菜单程序。能够输入二叉树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数；输出中序遍历序列的函数；输出后序遍历序列的函数；输出层序遍历序列的函数。5、八皇后问题【问题描述】8个皇后在一个8*8的棋盘上下棋，一个皇后放入一个棋子后，另一个皇后所放的棋子不能与前一个皇后所放的棋子在同一行、同一列（在每一横列竖列斜列只有一个皇后），将所有可能的棋子放法求出来。【要 求】采用如下方式之一输出棋盘：（1）以数组的形式输出棋盘；（2）以图形方式输出棋盘。6、图的深度和广度优先搜索遍历【问题描述】 给定一个无向图，利用邻接矩阵或邻接表进行存储，然后按照深度和广度进行遍历。【要 求】以吉林省的城市：白城、松原、长春、公主岭、四平、辽源、吉林市、通化、白山、延吉所构成的地理图为无向图。求以吉林市为出发点深度和广度优先搜索遍历序列。7、全屏幕模拟时钟【问题描述】 用C语言模拟时钟的运行。【要 求】 时钟要求有时针、分针、秒针（既能按机械表行走，又能按电子表显示时间和日期）。用到头文件：#include 。sleep(3)；延时二秒观看结果， initgraph(&driver,&mode,a:bgi )；初始化图形模式，circle(x1,y1,r); 使用当前颜色绘制一个闭合图形，setfillstyle(num%12,color1);设置填充方式，floodfill(x1,y1,color1);对闭合图形进行填充，closegraph(); 关闭图形，clrscr(); 清屏，等等。 8、二分法查找演示【问题描述】 用箭头表示指针，模拟出二分法查找的指针变化过程。【要 求】 给定一组数据。可以动态地显示二分法查找的过程。用到函数：setcolor(WHITE)画颜色，line(x1,y1,x2,y2)画直线;，bar(x1,y1,x2,y2)画矩形，settextstyle(0,0,2)字体大小，outtextxy(x,y,变量或常量)输出内容; initgraph(&gd,&gm,c:tc) tc所在目录的路径，setfillstyle(SOLID_FILL,0)每次演示的时候先将下面显示的文字给去处掉，等等。9、排序算法【问题描述】实现各种常用排序（直接插入排序、二分法排序、直接选择排序、冒泡排序、希尔排序、快速排序）算法。【要 求】编写菜单程序，按照升序排序。输入数据元素的个数任意，输入数据元素的值任意（正整数），输出排序前、排序后的数据元素。10、约瑟夫环【问题描述】：编号是1，2，,n的n（n0）个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。开始时任选一个正整数作为报数上限值m，从第一个开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【要 求】：利用单循环链表存储结构解决此问题，按照出列的顺序输出各个人的编号。键盘输入m、n的初值和每个人的密码（密码也可以利用随机函数产生）。（二）综合题目1、迷宫探险【问题描述】小人在迷宫的左上角进入迷宫，从右下角走出迷宫，在行走过程中不走回头路，即不重复经过同一点，将走过的路径表示出来。 【要 求】可以输入一个任意大小的迷宫数据，用非递归或递归的方法求出一条走出迷宫的路径，并将路径输出。迷宫大小为mn，用数组0.m+1,0.n+1表示，四周有墙，用0表示有路，用1表示墙。（1）假设小人在迷宫中有8个方向可选。2、物业管理系统【问题描述】建立一个物业管理信息文件，包括门牌号（num）、户主（name）、住宅面积（area）、物业费（expense）、交费情况（flag）、电话（phone）等。【要 求】编写菜单程序，功能包括：建立户主记录、插入记录，删除记录、修改记录、按照门牌号或户主姓名查询记录、显示记录、保存文件。定义物业结构体名称为administer。门牌号（num）、户主（name）、交费情况（flag）、电话（phone）均为字符型数组，长度分别为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）为单精度型数据。附加题目:哈夫曼编码和译码系统【问题描述】编写一个程序模拟哈夫曼编码通信过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。【要 求】发送功能：输入待传送字符信息；统计字符信息中各字符出现的种类和频率；根据各字符出现的种类和频率建立哈夫曼树；利用该哈夫曼树求出各字符的编码；将字符信息转换成对应的编码信息进行传送。接收功能：接收发送者发来的编码信息；利用哈夫曼树对编码信息进行翻译还原成发送前的字符信息。二、选题方式本次实训共分为16个题目，其中10个单项题目、6个综合题目。单项题目每人1个，每个题目最多有34人选择；综合题目以小组的形式进行，共6组，每4人为一组。附加题目每个人或小组均可以选定。适当根据完成情况适当加分。三、实训报告1. 实训项目：实训题目及问题描述2. 实训目的：通过完成本实训项目，使学生掌握了什么知识，培养了什么能力，得到了什么提高。3. 设计分析：得出解决问题的思路、主要流程、采用的数据结构类型的说明、主要算法的思想。设计方案：采用的数据结构类型的定义、主要算法的描述及说明。4. 详细设计：项目实现的源程序清单，包括自定义函数的详细注释、关键语句说明。5. 用户手册：程序使用说明书，说明如何使用此程序，详细列出每一步的操作步骤。6. 运行调试：例举调试过程中用到的不同的输入数据，以及得到的不同的测试结果。在调试过程中遇到的主要问题及解决方法。7. 实训心得：利用程序设计基础知识和数据结构知识来解决本项目实践的体会，对设计的经验总结及改进思想。四、注意事项1、程序要具有良好的可读性源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。2、涉及多个功能采用菜单程序最后提供的主程序可以像一个应用系统一样有主窗口，通过主菜单和分级菜单调用实训中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能。五、实训结束后应提交的内容1一个报告实训报告：包括实训题目、实训目的、问题描述、设计分析、设计方案、编写程序、调试程序、测试程序、使用说明、实训心得。要求：A4纸，打印稿，页边距：上、下、左、右均为2.5cm，有页码。具体参见样本。2四个文件四个文件：源代码文本文件（*.txt），源代码程序文件（*.c或*. cpp），源代码可执行文件（*.exe），实训报告文件（*.doc）。文件名命名规则：cx.txt，cx.c，cx.exe，bg.doc。cx表示程序，bg表示报告。左侧两个“”表示两位学号（0145），第3个“”表示单项题目还是综合题目（单项为0，综合为1），右侧“”表示题号（0-9）。个人文件放在一个文件夹内，文件夹命名规则：jsj姓名（wl姓名），