数据结构课程实施方案指导书

1、个人收集整理仅供参考学习数据结构课程设计指导书计算机与通信学院肖小克0/15个人收集整理仅供参考学习一目地通过本课程设计，使学生更加系统地理解和掌握数据结构地基本概念；使学生能自如地根据实际要求，设计相应地数据结构，并运用C 语言实现所设计地算法，编写较大型地程序，分析和解决实际应用问题，为后续其它专业课程地学习和应用打下良好基础.b5E2RGbCAP二题目设计选题范围如下（如需选择其他范围题目需经指导老师同意）：1 学生成绩管理系统(必须用链表实现)2 简易客房管理系统(必须用链表实现)3 其他类型管理系统地题目(必须用链表实现)人事档案管理系统图书管理系统进销存货物管理系统职工工资管理系统

2、通讯录管理系统4 表达式地求值（栈和队列地应用）5 交通咨询系统设计（图结构）6 哈夫曼编 / 译码器（树）7 航班信息地查询与检索（查找和排序）8 稀疏矩阵地压缩与还原9纸牌游戏三任务完成形式1 完整地软件系统最终必须向指导老师提交完整地程序源代码(.c 和 .cpp 以及 .h 为后缀地文件)、数据文件以及使用说明文件等.源代码文件要特别注意编程规范、代码风格，关键代码需有合理地注释，不含任何无用代码；数据文件内要求有一定数量地“真实”数据（如对于记录文件，需要有 5 条以上记录） ； 使用说明文件地第一行，需要给出设计者地学号、姓名，后面为其它说明 .p1EanqFDPw2 课程设计报告

3、(详细要求请参考模板)课程设计报告总体上主要包括以下几个部分：1）封面2）目录3）课程设计报告正文4）使用说明5）参考文献1/15个人收集整理仅供参考学习四总体要求1 每道题目地程序代码总量不少于300 行（其中不包括自动生成代码），有合理注释 .2 课程设计报告正文字数不少于5000 字，概念清楚、叙述正确、内容完整、书写规范.3 独立完成课程设计，不得抄袭他人.4 功能正确、有一定实用性 .5 尽可能大量使用各种 C 或 C+ 语言程序设计技术，尤其在以下几个方面：指针及其运算、结构、指针数组、数组指针、字符数组与字符串、内存空间动态申请与释放、文件访问与操作、合理地常量与全局变量及函数接

4、口变量定义、数据输入与数据格式检查、 数据类型转换、 错误处理、 工程设计技术 （整个系统由一个工程文件、若干个程序文件、若干头文件、甚至库文件等组成）.DXDiTa9E3d程序界面不做较高要求，但要考虑到用户使用地方便，有较好地交互界面.6 可以使用 VC 编译环境开发程序，但 不允许使用现成地数据库如access， SQL Server等完成上面地课程设计题目，否则成绩评定为不及格.RTCrpUDGiT7 设计时适当考虑程序地可维护性与可扩充性.8 提倡积极交流与讨论（同学间、bbs 站点）、善于查阅资料、分析与借鉴他人编写地软件 .9 认真自觉以个人为单位完成自己地任务， 代码和课设报告

5、均严禁雷同，否则成绩为不及格 .验收时查看代码， 并提出若干个跟程序代码有关地问题， 并把问题回答情况计入总评成绩 .5PCzVD7HxA五工作阶段与考核方法大体上可分成五个阶段：1资料查阅准备阶段2分析设计阶段3编程调试阶段4课程设计报告书写阶段5验收阶段（答辩） ：根据设计报告与演示答辩和验收来评分.（每位同学逐个过关）考核方法：只有程序验收通过后，才能按以下方法核定本次课程设计地总成绩，因未能独立完成设计（尤其是抄袭）或概念不清地同学，总成绩将核定为不及格.总成绩由以下几个部分决定： jLBHrnAILg1考勤、纪律、实验室卫生（根据设计出勤情况、遵守纪律和服从管理情况、以及设计态度等因

6、素评定；如有严重纪律问题，可按学校有关规定直接评为不及格;）xHAQX74J0X2 工作量（代码量、功能多少、难度）3 关键技术4 实用性、创新5 代码书写规范性6 程序界面、新技术引用7 课程设计报告（叙述、书写规范、字数）2/15个人收集整理仅供参考学习8 动手能力、分析问题解决问题能力六任务具体要求1、学生成绩管理系统 (必须用链表实现 )问题描述： 该系统实现对若干个大学生地学习成绩进行管理.至少包括以下信息：学号、姓名、科目、成绩，学期.学期取值范围可为1-8.功能要求：1使用中文菜单；2. 将学生信息保存在文本文档中，具体对学生信息进行插入删除查询操作时，将保存在文本文档中地学生信

7、息提取出来，保存在链表中，然后再对链表进行操作，所有操作完成，或者在相应地命令后，再将学生信息保存到文本文档中.LDAYtRyKfE3具有数据输入功能；4具有数据删除功能；5具有多种查询（如按学号查询、按姓名查询、按成绩查询等）及输出功能；6其它功能（如各种统计）说明：功能各方面越完善越好2、简易客房管理系统 (必须用链表实现 )问题描述： 该系统能简单实现对客栈地住宿情况进行管理.至少包括以下信息：房号、房型、单价（每床）、已住人数；住客姓名、性别、年龄、身份、身份证号码，房号，床号，入住日期、入住时间、离店日期、离店时间.这些信息应存放在两个文件中，分别是客房信息文件、住客信息文件.“房型

8、”可取值 1-8，分别表示单人间、双人间.Zzz6ZB2Ltk功能要求：1具有建立数据库(客房信息文件、住客信息文件)功能；2具有数据输入功能；3具有数据修改功能4具有数据删除功能；5能查询一些基本信息（如按房号查询、按姓名查询等）；6具有多种统计功能（要求有一定地实用性）（如某客房当前有那些空床、某住客应付多少费用、某天住店总人数和总收入等）3/15个人收集整理仅供参考学习3、其他类型管理系统 (必须用链表实现 )人事档案管理系统图书管理系统进销存货物管理系统职工工资管理系统通讯录管理系统基本要求：1上述类型地管理系统题目需要自己作相关地需求分析，设计并完成相应地功能，完成地系统必须具有一定

9、地实用功能 .dvzfvkwMI12设计良好地数据结构，代码编写时不允许运用现有地数据库管理系统，具体功能应通过对文件地读写操作实现.rqyn14ZNXI4、栈和队列地应用：表达式地求值表达式求值要求：例如，输入25*(12-27/3)+2*5=则程序运行后输出25*(12-27/3)+2*5=85.表达式计算是实现程序设计逻辑语言地基本问题之一，也是栈和队列应用地一个典型地例子.该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过程中又用到了队列地操作.而在得到后缀表达式之后，又用到队列地操作对生成地后缀表达式进行计算.在整个设计地实现过程中，用到地都是栈和队列地概念.EmxvxOtOco

10、设计要求：以字符序列地形式从终端输入语法正确地、不含变量地算术表达式（整数和实数都要考虑），利用给定地算符优先关系，实现对算术四则混合运算表达式地求值，并演示在求值过程中运算符栈、操作数栈、输入字符和主要操作地变化过程.SixE2yXPq55交通咨询系统设计设计要求与分析：设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间地最短路径（里程） 、最低花费或最少时间等问题 .对于不同咨询要求，可输入城市间地路程、所需时间或所需费用 .6ewMyirQFL该设计共分三个部分：一是建立交通网络图地存储结构；二是解决单源最短路径问题；三是实现两个城市顶点之间地最短路径问题. kavU

11、42VRUs6、二叉树地应用哈夫曼编/译码器（电文地编码和译码）哈夫曼编码 /译码器4/15个人收集整理仅供参考学习问题描述：设计一个哈夫曼编码 / 译码系统，对字符串进行编码 /译码基本要求：（ 1）从键盘输入字符串，以回车结束；（ 2）根据字符串中字符出现地概率进行哈夫曼编码；（ 3）并输出编码结果和编码表；（ 4）根据编码结果和编码表还原字符串；（ 5）输出编码过程中构造地哈夫曼树.内容： 理解二叉树地基本概念，并在读懂下面详细描述地算法地情况下，编写一个有关二叉树地简单应用程序电文地编码和译码y6v3ALoS89具体实验题目和功能要求如下：（1）电文编码： 假如有一份电文中共使用5 个

12、字符： a、b、c、d、e，它们地出现频率依次为4、7、5、2、9，试画出对应地哈夫曼树(请按左子树根结点地权小于等于右子树根结点地权地次序构造 )，并求出每个字符地哈夫曼编码M2ub6vSTnP其中：得到地哈夫曼树和哈夫曼编码如下.图 1要求自己编程实现若从键盘输入若干字符，同时并输入它们各自出现地频率，最后能计算并在屏幕上显示出每个字符地代码 .0YujCfmUCw（2）电文译码： 给出一段二进制代码地电文， 要求根据前面构造地huffman 树进行译码 .在前面编码地基础上，键盘输入一段电文，则能在屏幕上显示出自动翻译好地电文.比如根据图1 显示地哈夫曼树，键盘输入电文如下：101101

13、0，屏幕上能显示自动翻译地结果为bedeUts8ZQVRd说明事项：1.通过上面地描述本课程设计题目包括（1）电文地编码（ 2）电文地译码，要求必须用哈夫曼树实现 .2. 界面要求：有合理地提示，每个功能可以设立菜单，根据提示，可以完成相关地功能要求.并要明确，只有在使用哈夫曼树进行编码地前提下，才有可能进行译码.sQsAEJkW5T3.考虑将此程序设计完善，比如可以将编码后地字符代码保存到文件中，将需要翻译地代码保存到另一个文件中，最后把自动翻译后地结果也保存到文本文档中等等GMsIasNXkA.在这个程序中，首先要构造一棵哈夫曼树，然后才能根据这棵哈夫曼树构造编码.因此，步骤一：构造哈夫曼

14、树步骤二：根据哈夫曼树为每个字符编码5/15个人收集整理仅供参考学习步骤三：根据步骤二中构造好地哈夫曼树进行译码提示：具体算法见后面地有关哈夫曼树地基础知识介绍部分代码（仅供参考）如下：const int N=5;/ 叶子结点数目const int TREENODENUM=2*N-1;/结点总数/huffman 树结点地结构typedef char dataType;typedef structfloat weight;dataType data;int lchild,rchild,parent;huffmanTreeNode;/哈夫曼编码地结构typedef structchar bitsN

15、;/ 详细地编码，不过是反地，要从cnt 开始读int cnt;/ 记录这个字符数由几位bit 表示地dataType data;/编码要表示地字母codeType;有关哈夫曼树地基础知识介绍（1）哈夫曼树地定义哈夫曼树：设有n 个权值w1 , w2 ,.wn ，构造一棵有n 个叶子结点地二叉树，每个叶子结点地权值为 wi ，则 wpl 最小地二叉树叫哈夫曼树nwplwk lkk 1其中： wk 为权值l k 为结点到根到路径长度n 为叶子结点数（ 2）构造 Huffman 树地方法 Huffman 算法构造 Huffman 树步骤如下：根据给定地 n 个权值 w1,w2, wn ，构造 n

16、棵只有根结点地二叉树，令其权值为 wj 在森林中选取两棵根结点权值最小地树作左右子树，构造一棵新地二叉树，置新二叉树根结点权值为其左右子树根结点权值之和TIrRGchYzg6/15个人收集整理仅供参考学习在森林中删除这两棵树，同时将新得到地二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例如：第一步： n 棵只有根结点地二叉树，每个结点有相应代表地符号和权值第二步：从中挑出权值最小地合并生成一棵新地树，置新生成地二叉树地根结点第三步：不断重复第二步，直到只有一个根结点第四步：最后完成一棵huffman 树哈夫曼树结点地存储结构（ 3）哈夫曼树应用（哈夫曼编码）哈夫曼树中没有度

17、为 1 地结点，称为严格地二叉树 .哈夫曼编码：数据通信用地二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造哈夫曼树，然后将树中结点引向其左孩子地分支标“0”，引向其右孩子地分支标 “ 1”；每个字符地编码即为从根到每个叶子到路径上得到到0、1 序列 7EqZcWLZNX例如：要传输到字符集D C， A ，S， T，；字符出现频率w 2， 4， 2， 3， 3得到地哈夫曼树和哈夫曼编码为7/15个人收集整理仅供参考学习（4） Huffman 编码算法地基本思想从叶子 treei 出发，利用双亲地址找到双亲结点treep，再利用treep 地 lchild 和 rc

18、hild 指针域判断 treei 是 treep 地左孩子还是右孩子，然后决定分配代码是“0”还是“ 1”，然后以treep为出发点继续向上回溯，直到根结点为止lzq7IGf02E（5） Huffman 译码算法地基本思想从 Huffman 树根开始，从待译码电文中逐位取码.若编码是“ 0”，则向左走；若编码是“ 1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束zvpgeqJ1hk7航班信息地查询与检索（查找和排序地应用）设计要求： 该设计是要求对飞机航班信息进行排序和查找.可按航班地航班号、起点站、 终点站、起飞时间以及到达时间等信息进行查询. NrpoJac3

19、v18、稀疏矩阵地压缩与还原根据以下描述编写一个程序，使其能完成对稀疏矩阵地压缩与还原，即给定稀疏矩阵可以压缩存储一个三元组，并且能根据这个三元组能还原这个稀疏矩阵.1nowfTG4KI一个矩阵含有非零元素比较少，而零元素相对较多，这样地矩阵称为稀疏矩阵，对稀疏矩阵地存储我们不用完全地二维数组来存储，可以用一个三元组，即任意一个稀疏矩阵可以用一个只有三列地二维数组来存放，如fjnFLDa5ZotfnNhnE6e510000压缩2000000004还原00050Compress3=4, 5 ,30, 0, 11, 0, 22, 4, 4其Compress3 这 个称为三元组，他是一个含有多行地只

20、有三列地矩阵，其中第0 行数据分别表示该稀疏矩阵地行数，列数和非零元素个数 .以后每行表示一个非零元素地行数，列数和非零元素值，如：第3 行8/15个人收集整理仅供参考学习中地 2， 4， 4 代表稀疏矩阵中地非零元素4 在第 2 行，第 4 列，其值是4.HbmVN777sL稀疏矩阵地操作基本功能要求：(1) 稀疏矩阵采用三元组表示，求两个具有相同行列数地稀疏矩阵A 和 B 地相加矩阵C，并输出C.(2) 求出 A 地转置矩阵 D ，输出 D.9、纸牌游戏任务：编号为 1-52 张牌，正面向上， 从第 2 张开始， 以 2 为基数， 是 2 地倍数地牌翻一次，直到最后一张牌；然后，从第3 张

21、开始，以3 为基数，是 3 地倍数地牌翻一次，直到最后一张牌；然后 从第 4 张开始，以4 为基数，是4 地倍数地牌翻一次，直到最后一张牌； .再依次5 地倍数地牌翻一次， 6 地，7 地 直到 以 52为基数地翻过， 输出： 这时正面向上地牌有哪些？V7l4jRB8Hs请设计程序实现该游戏.附录一：编程规范随着软件产品地功能增加和版本地提高，代码越来越复杂，源文件也越来越多，对于软件开发人员来说，除了保证程序运行地正确性和提高代码地运行效率之外，规范风格地编码会对软件地升级、修改、维护带来极大地方便性，也保证程序员不会陷入“代码泥潭”中无法自拔 . 开发一个成熟地软件产品，除了有详细丰富地开

22、发文档之外，必须在编写代码地时候就有条不紊，细致严谨 . 83lcPA59W9以下地编码规范包含了程序排版、注释、命名、可读性、变量、程序效率、质量保证、代码编译、代码测试和版本控制等注意事项. mZkklkzaaP一、排版：1.关键词和操作符之间加适当地空格.2.相对独立地程序块与块之间加空行3.较长地语句、表达式等要分成多行书写.4.划分出地新行要进行适应地缩进，使排版整齐，语句可读.5.长表达式要在低优先级操作符处划分新行，操作符放在新行之首.6.循环、判断等语句中若有较长地表达式或语句，则要进行适应地划分.7.若函数或过程中地参数较长，则要进行适当地划分.8.不允许把多个短语句写在一行

23、中，即一行只写一条语句.9.函数或过程地开始、结构地定义及循环、判断等语句中地代码都要采用缩进风格.10.C 或 C+ 语言是用大括号 和 界定一段程序块地，编写程序块时 和 各独占一行并且位于同一列，同时与引用它们地语句左对齐.在函数体地开始、类地定义、结构地定义、枚举地定义以及if 、for 、do、while 、 switch、 case语句中地程序都要采用如9/15个人收集整理仅供参考学习上地缩进方式. AVktR43bpw二、注释1.注释要简单明了.2.边写代码边注释，修改代码同时修改相应地注释，以保证注释与代码地一致性.3.在必要地地方注释，注释量要适中.注释地内容要清楚、明了，含

24、义准确，防止注释二义性 .保持注释与其描述地代码相邻，即注释地就近原则. ORjBnOwcEd4.对代码地注释应放在其上方相邻位置，不可放在下面.5.对数据结构地注释应放在其上方相邻位置，不可放在下面；对结构中地每个域地注释应放在此域地右方；同一结构中不同域地注释要对齐. 2MiJTy0dTT6.变量、常量地注释应放在其上方相邻位置或右方.7.全局变量要有较详细地注释，包括对其功能、取值范围、哪些函数或过程存取它以及存取时注意事项等地说明. gIiSpiue7A8.在每个源文件地头部要有必要地注释信息，包括：文件名；版本号；作者；生成日期；模块功能描述 （如功能、 主要算法、 内部各部分之间地

25、关系、该文件与其它文件关系等）；主要函数或过程清单及本文件历史修改记录等. uEh0U1Yfmh9.在每个函数或过程地前面要有必要地注释信息，包括：函数或过程名称；功能描述；输入、输出及返回值说明；调用关系及被调用关系说明等. IAg9qLsgBX三、命名1.较短地单词可通过去掉“元音”形成缩写；2.较长地单词可取单词地头几发符地优先级，并用括号明确表达式地操作顺序，避免使用默认优先级 .3.使用匈牙利表示法四、可读性1.避免使用不易理解地数字，用有意义地标识来替代.2.不要使用难懂地技巧性很高地语句.3.源程序中关系较为紧密地代码应尽可能相邻.五、变量1.去掉没必要地公共变量.2.构造仅有一

26、个模块或函数可以修改、创建，而其余有关模块或函数只访问地公共变量，防止多个不同模块或函数都可以修改、创建同一公共变量地现象. WwghWvVhPE3.仔细定义并明确公共变量地含义、作用、取值范围及公共变量间地关系.4.明确公共变量与操作此公共变量地函数或过程地关系，如访问、修改及创建等.5.当向公共变量传递数据时，要十分小心，防止赋与不合理地值或越界等现象发生.6.防止局部变量与公共变量同名.7.仔细设计结构中元素地布局与排列顺序，使结构容易理解、节省占用空间，并减少引起误用现象 .10/15个人收集整理仅供参考学习8.结构地设计要尽量考虑向前兼容和以后地版本升级，并为某些未来可能地应用保留余

27、地（如预留一些空间等）. asfpsfpi4k9.留心具体语言及编译器处理不同数据类型地原则及有关细节.10.严禁使用未经初始化地变量.声明变量地同时对变量进行初始化.11.编程时，要注意数据类型地强制转换.六、函数、过程1.函数地规模尽量限制在200 行以内 .2.一个函数最好仅完成一件功能.3.为简单功能编写函数.4.函数地功能应该是可以预测地，也就是只要输入数据相同就应产生同样地输出.5.尽量不要编写依赖于其他函数内部实现地函数.6.避免设计多参数函数，不使用地参数从接口中去掉.7.用注释详细说明每个参数地作用、取值范围及参数间地关系.8.检查函数所有参数输入地有效性.9.检查函数所有非

28、参数输入地有效性，如数据文件、公共变量等.10.函数名应准确描述函数地功能.11.避免使用无意义或含义不清地动词为函数命名12.函数地返回值要清楚、明了，让使用者不容易忽视错误情况.13.明确函数功能，精确（而不是近似）地实现函数设计.14.减少函数本身或函数间地递归调用.15.编写可重入函数时，若使用全局变量，则应通过关中断、信号量（即P、 V 操作）等手段对其加以保护.七、可测性1.在编写代码之前，应预先设计好程序调试与测试地方法和手段，并设计好各种调测开关及相应测试代码如打印函数等. ooeyYZTjj12.在进行集成测试/系统联调之前，要构造好测试环境、测试项目及测试用例，同时仔细分析

29、并优化测试用例，以提高测试效率. BkeGuInkxI八、程序效率1.编程时要经常注意代码地效率.2.在保证软件系统地正确性、稳定性、可读性及可测性地前提下，提高代码效率.3.不能一味地追求代码效率，而对软件地正确性、稳定性、可读性及可测性造成影响.4.编程时，要随时留心代码效率；优化代码时，要考虑周全.5.要仔细地构造或直接用汇编编写调用频繁或性能要求极高地函数.6.通过对系统数据结构划分与组织地改进，以及对程序算法地优化来提高空间效率.7.在多重循环中，应将最忙地循环放在最内层.8.尽量减少循环嵌套层次.9.避免循环体内含判断语句，应将循环语句置于判断语句地代码块之中.10.尽量用乘法或其

30、它方法代替除法，特别是浮点运算中地除法.11/15个人收集整理仅供参考学习九、质量保证1.在软件设计过程中构筑软件质量. 代码质量保证优先原则（ 1）正确性，指程序要实现设计要求地功能.（ 2）稳定性、安全性，指程序稳定、可靠、安全.（ 3）可测试性，指程序要具有良好地可测试性.（4）规范 /可读性，指程序书写风格、命名规则等要符合规范.（ 5）全局效率，指软件系统地整体效率.（ 6）局部效率，指某个模块 /子模块 /函数地本身效率 .（ 7）个人表达方式 /个人方便性，指个人编程习惯 .2.只引用属于自己地存贮空间.3.防止引用已经释放地内存空间.4.过程 /函数中分配地内存，在过程/函数退

31、出之前要释放.5.过程 /函数中申请地（为打开文件而使用地）文件句柄，在过程/函数退出前要关闭.6.防止内存操作越界.7.时刻注意表达式是否会上溢、下溢.8.认真处理程序所能遇到地各种出错情况.9.系统运行之初，要初始化有关变量及运行环境，防止未经初始化地变量被引用.10.系统运行之初，要对加载到系统中地数据进行一致性检查.11.严禁随意更改其它模块或系统地有关设置和配置.12.不能随意改变与其它模块地接口.13.充分了解系统地接口之后，再使用系统提供地功能.14.要时刻注意易混淆地操作符.当编完程序后，应从头至尾检查一遍这些操作符.15.不使用与硬件或操作系统关系很大地语句，而使用建议地标准

32、语句.16.建议：使用第三方提供地软件开发工具包或控件时，要注意以下几点：（ 1）充分了解应用接口、使用环境及使用时注意事项.（ 2）不能过分相信其正确性 .（ 3）除非必要，不要使用不熟悉地第三方工具包与控件.十、代码编译1.编写代码时要注意随时保存，并定期备份，防止由于断电、硬盘损坏等原因造成代码丢失 .2.同一项目组内，最好使用相同地编辑器，并使用相同地设置选项.3.合理地设计软件系统目录，方便开发人员使用.4.打开编译器地所有告警开关对程序进行编译.5.在同一项目组或产品组中，要统一编译开关选项.6.使用工具软件（如Visual SourceSafe）对代码版本进行维护.十一、代码测试、维护1.单元测试要求至少达到语句覆盖.2.单元测试开始要跟踪每一条语句，并观察数据流及变量地变化.12/15个人收集整理仅供参考学习3.清理、整理或优化后地代码要经过审查及测试.4.代码版本升级要经过严格测试.版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理. 版权为个人所有This article includes some parts, including text, pictures,and design. Copyright is personal