《#2011数据结构课程设计指导书1专业用》由会员分享，可在线阅读，更多相关《#2011数据结构课程设计指导书1专业用（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计指导书计算机科学和控制学院一. 目的通过本课程设计，使学生更加系统地理解和掌握数据结构的基本概念；使学生能自如地根据实际要求，设计相应的数据结构，并运用C+语言实现所设计的算法，编写较大型的程序,分析和解决实际使用问题，为后续其它专业课程的学习和使用打下良好基础。二. 题目根据指导教师的具体要求，从下面题目中选择1个题目来完成1. 二叉树的使用一哈夫曼树（电文的编码和译码）2. 运动会分数统计3. 学生成绩管理系统4. 简易客房管理系统5. 其他类型管理系统的题目 人事档案管理系统 图书管理系统 进销存货物管理系统 职工工资管理系统6. 稀疏矩阵运算器7. 表达式的求值8. 长
2、整数的四则运算9. 校园导游咨询10停车场管理11其余题目：（必须事先得到指导老师允许）二.任务完成形式1. 完整的软件系统最终必须向指导老师提交完整的程序源代码（.c和.cpp以及.h为后缀的文件卜数据文件以及使用说明文件等。源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有8条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。2. 课程设计报告（详细要求请参考附录二）课程设计报告总体上主要包括以下几个部分：1）封面2）目录3）课程设计报告正文4）使用说明5）参考文献四总
3、体要求1每道题目的程序代码总量不少于500行（其中不包括自动生成代码），有合理注释。2课程设计报告正文字数不少于7000字，概念清楚、叙述正确、内容完整、书写规范。3独立完成课程设计，不得抄袭他人。4功能正确、有一定实用性。5尽可能大量使用各种C+语言程序设计技术，尤其在以下几个方面：指针及其运算、结构、指针数组、数组指针、字符数组和字符串、内存空间动态申请和释放、文件访问和操作、合理的常量和全局变量及函数接口变量定义、数据输入和数据格式检查、数据类型转换、错误处理、工程设计技术（整个系统由一个工程文件、若干个程序文件、若干头文件、甚至库文件等组成）。程序界面不做较高要求，但要考虑到用户使用的
4、方便，有较好的交互界面。6可以使用VC编译环境开发程序，但不允许使用现成的数据库如access，SQLServer等完成上面的课程设计题目，否则成绩评定为不及格。7设计时适当考虑程序的可维护性和可扩充性。8提倡积极交流和讨论（同学间、bbs站点）、善于查阅资料、分析和借鉴他人编写的软件。9认真自觉以个人为单位完成自己的任务，代码和课设报告均严禁雷同，否则成绩为不及格。验收时查看代码，并提出若干个跟程序代码有关的问题，并把问题回答情况计入总评成绩。五工作阶段和考核方法大体上可分成五个阶段：1资料查阅准备阶段（15%）2分析设计阶段（35%）3编程调试阶段（40%）4课程设计报告书写阶段（10%）
5、5验收阶段考核方法：只有程序验收通过后，才能按以下方法核定本次课程设计的总成绩，因未能独立完成设计（尤其是抄袭）或概念不清的同学，总成绩将核定为不及格。总成绩由以下几个部分决定：1考勤、纪律、实验室卫生2工作量（代码量、功能多少、难度）3关键技术4实用性、创新5. 代码书写规范性程序界面、新技术引用6. 课程设计报告(叙述、书写规范、字数)动手能力、分析问题解决问题能力六.任务具体要求1、二叉树的使用一哈夫曼树(电文的编码和译码)哈夫曼编码/译码器问题描述：设计一个哈夫曼编码/译码系统，对字符串进行编码/译码基本要求：(1) 从键盘输入字符串，以回车结束；(2) 根据字符串中字符出现的概率进行
6、哈夫曼编码；)(3) 并输出编码结果和编码表；(4)根据编码结果和编码表还原字符串；(5)输出编码过程中构造的哈夫曼树。内容：理解二叉树的基本概念，并在读懂下面详细描述的算法的情况下，编写一个有关二叉树的简单使用程序一电文的编码和译码。具体实验题目和功能要求如下：(1) 电文编码：假如有一份电文中共使用5个字符：a、b、c、d、e,它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码其中：得到的哈夫曼树和哈夫曼编码如下。a:Oilh:10c:00(I:010e:11要求自己编程实现若从键盘输入若干字符
7、，同时并输入它们各自出现的频率，最后能计算并在屏幕上显示出每个字符的代码。(2) 电文译码：给出一段二进制代码的电文，要求根据前面构造的huffman树进行译码。在前面编码的基础上，键盘输入一段电文，则能在屏幕上显示出自动翻译好的电文。比如根据图1显示的哈夫曼树，键盘输入电文如下：1011010,屏幕上能显示自动翻译的结果为bed说明事项：1通过上面的描述本课程设计题目包括（1）电文的编码（2）电文的译码，要求必须用哈夫曼树实现。2.界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。并要明确，只有在使用哈夫曼树进行编码的前提下，才有可能进行译码。3考虑将此程序设计
8、完善，比如可以将编码后的字符代码保存到文件中，将需要翻译的代码保存到另一个文件中，最后把自动翻译后的结果也保存到文本文档中等等。在这个程序中，首先要构造一棵哈夫曼树，然后才能根据这棵哈夫曼树构造编码。因此，步骤一：构造哈夫曼树步骤二：根据哈夫曼树为每个字符编码步骤三：根据步骤二中构造好的哈夫曼树进行译码提示：具体算法见后面的有关哈夫曼树的基础知识介绍部分代码（仅供参考）如下：constintN=5;叶子结点数目constintTREENODENUM=2*N-1;结点总数/huffman树结点的结构typedefchardataType;typedefstructfloatweight;data
9、Typedata;intlchild,rchild,parent;huffmanTreeNode;哈夫曼编码的结构typedefstructcharbitsN;详细的编码，不过是反的，要从ent开始读intcnt;/记录这个字符数由几位bit表示的dataTypedata;/编码要表示的字母codeType;有关哈夫曼树的基础知识介绍（1）哈夫曼树的定义哈夫曼树：设有n个权值：w,W2,.，构造一棵有n个叶子结点的二叉树，每个叶子结点的权值为wi，则wpl最小的二叉树叫哈夫曼树nwpl二wklkk#其中：Wk为权值lk为结点到根到路径长度n为叶子结点数（2）构造Huffman树的方法Huffm
10、an算法构造Huffman树步骤如下： 根据给定的n个权值w1,w2,wn,构造n棵只有根结点的二叉树，令其权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例如：第一步：n棵只有根结点的二叉树，每个结点有相应代表的符号和权值第二步：从中挑出权值最小的合并生成一棵新的树，置新生成的二叉树的根结点第四步：最后完成一棵huffman树1818哈夫曼树结点的存储结构lehilddata结点值weight权值rchildpare
11、nt（3）哈夫曼树使用（哈夫曼编码）哈夫曼树中没有度为1的结点，称为严格的二叉树。哈夫曼编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造哈夫曼树，然后将树中结点引向其左孩子的分支标“0”引向其右孩子的分支标“1”每个字符的编码即为从根到每个叶子到路径上得到到0、1序列例如：要传输到字符集D=C,A,S,T,；字符出现频率w=2,4,2,3,3得到的哈夫曼树和哈夫曼编码为CSCST:00!3()1A:10C:110S:111(4) Huffman编码算法的基本思想从叶子treei出发，利用双亲地址找到双亲结点从叶子treei出发，利用双亲地址找到双
12、亲结点treep，再利用treep的Ichild和rchild指针域判断treei是treep的左孩子还是右孩子，然后决定分配代码是0”还是“1”，然后以treep为出发点继续向上回溯，直到根结点为止(5) Huffman译码算法的基本思想从Huffman树根开始，从待译码电文中逐位取码。若编码是0”，则向左走；若编码是1”,则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束2、运动会分数统计任务:参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目项目编号为男子1m,女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为:7、5、3
13、、2、1，前三名的积分分别为：5、3、2;哪些取前五名或前三名自己设定。(m=20,n=20)功能要求：1可以输出各个项目的前三名或前五名的成绩；2能统计各学校总分；3可以按学校编号、学校总分、男女团体总分排序输出；4可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5键盘输入的比赛成绩信息，保存在文件中，下次运行程序可以直接查询，不需要再次输入成绩信息。实现提示：可以假设n不大于20,m不大于30,w不大于20,姓名长度不超过20个字符。每个项目结束时，将其编号、类型符号(区分取前5名还是前3名)输入，并按名次顺序输入运动员姓名、校名(和成绩)3、学生成绩管理系
14、统问题描述：该系统实现对若干个大学生的学习成绩进行管理。至少包括以下信息：学号、姓名、科目、成绩，学期。学期取值范围可为1-8。功能要求：1使用中文菜单；将学生信息保存在文本文档中，具体对学生信息进行插入删除查询操作时，将保存在文本文档中的学生信息提取出来，保存在链表中，然后再对链表进行操作，所有操作完成，或者在相应的命令后，再将学生信息保存到文本文档中。3具有数据输入功能；4具有数据删除功能；5具有多种查询（如按学号查询、按姓名查询、按成绩查询等）及输出功能；6其它功能（如各种统计）说明：功能各方面越完善越好4、简易客房管理系统问题描述：该系统能简单实现对客栈的住宿情况进行管理。至少包括以下
15、信息：房号、房型、单价（每床）、已住人数；住客姓名、性别、年龄、身份、身份证号码，房号，床号，入住日期、入住时间、离店日期、离店时间。这些信息应存放在两个文件中，分别是客房信息文件、住客信息文件。“房型”可取值1-8，分别表示单人间、双人间.功能要求：1具有建立数据库（客房信息文件、住客信息文件）功能；2具有数据输入功能；3具有数据修改功能4具有数据删除功能；5能查询一些基本信息（如按房号查询、按姓名查询等）；6具有多种统计功能（要求有一定的实用性）（如某客房当前有那些空床、某住客应付多少费用、某天住店总人数和总收入等）5、其他类型管理系统 人事档案管理系统 图书管理系统 进销存货物管理系统 职工工资管理系统基本要求：1上述类型的管理系统题目需要自己作相关的需求分析，设计并完成相应的功能，完成的系统必须具有一定的实用功能。2设计良好的数据结构，代
