课程设计指导书.doc

数据结构课程设计指导书一、课程设计教学目的及基本要求1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；5. 独立完成，且要有完整可运行的程序；6. 1号到10号学生完成题1或者题8，11号到20号学生完成题2或者题6，21号到30号学生完成题3，31号到40号学生完成题4，41号到52号学生完成题5或者题7；7. 完成时间：2011年3月1日前完成；8提交内容： 打印好的课程设计报告请学习委员收好后交老师办公室（2011年3月8日前，逾期不收）； 电子稿（包括课程设计报告和源程序以“学号姓名”为名打包）提交到网上课堂。二、课程设计步骤1. 问题分析：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）2. 概要设计：对问题描述中涉及的操作对象定义相应的数据结构，并按照以数据结构为中心的原则划分模块，定义主程序模块（函数）和子模块（函数）；并画出各模块（函数）之间的调用关系图；3. 详细设计：对数据结构和基本操作出进一步的求精，写出函数形式的算法框架；4. 程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚；5. 程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6. 编写课程设计报告。三、报告撰写要求（以通讯录管理系统的设计和实现为例）1、 设计题目通讯录管理系统的设计与实现（小四号宋体，单倍行距）2、 设计目的和要求小四号宋体，单倍行距3、 设计内容（包括设计思路、设计实现）3.1问题分析（标题：小四，宋体加粗，正文：五号，宋体，单倍行距）通讯录管理系统一般包括通讯者信息的插入、查询、删除、更新以及通讯录信息的输出等功能。通讯者的信息一般包括编号、姓名、性别、电话以及地址等项。程序运行后显现提示信息，等候用户输入07以进入相应的操作功能。3.2系统设计1、存储结构的设计（说明数据对象及其关系的存储结构）每个通讯录结点采用结构体类型存储，整个通讯录是一个线性表（逻辑结构），采用链表存储的方式（物理结构）。具体结构定义如下：typedef struct2、功能模块（函数）的设计（说明课程设计时要注意模块的划分，不要把所有的内容都写在main中，要分若干函数来完成） （1）通过以下几个函数完成通讯录的管理：LinkList CreateList(void) 建立一个带头结点的通讯录单链表；基本思想：void InserNode(LinkList head ,ListNode *p) 在带头结点的通讯录链表中插入结点；基本思想：ListNode *ListFind(LinkList head) 在带头结点的通讯录链表中查找结点；基本思想：首先输入要查找的通讯者的编号或姓名，从表头顺序访问表中的结点，若查找成功，则返回一个指向查找到的通讯者信息的结点，若查找失败，则返回一个空的指针值NULL。（2）函数间的调用关系图3.3程序编码（把主要的算法程序写上，并且要有必要的解释和说明）参考文献4、 设计小结主要包括程序待改进的地方和本次课程设计的收获（小四号，宋体）四、参考题目1. 【设计题目】通讯录管理系统的设计与实现【问题描述】完成通讯者结点信息的插入、查询、删除、更新以及输出的功能。【实现提示】由键盘输入需要进行的操作，然后调用相应的函数完成功能。可以采用链接存储线性表的方式。2. 【设计题目】表达式求值问题【问题描述】以字符序列的形式从终端输入语法正确的不含变量的整数表达式（只包含基本的四则运算+-*/以及括号），实现表达式的求值。【实现提示】 先把中缀表达式转换成后缀表达式，再计算后缀表达式的值。参考教材给出的程序，利用栈来实现。3. 【设计题目】平衡二叉树的判定问题【问题描述】给定一个二叉树的先（后）序遍历以及中序遍历结果，首先构造二叉树，然后判定其是否为平衡二叉树。【实现提示】首先构造二叉树，然后计算每个结点的平衡度（可设计一个计算树的高度的函数，然后调用它并遍历每个结点求平衡度），计算的同时可判断是否平衡（计算和判断平衡度都可用递归的方法来实现）。4. 【设计题目】哈夫曼编码的应用【问题描述】针对字符集A及其各字符的频率值（可统计获得），给出A中所有字符的哈夫曼编码，并针对一段文本（定义在A上）进行编码，实现一个哈夫曼编码系统。【实现提示】首先建立哈夫曼树（参考教材程序），确立各个字符的编码，然后对给定文本进行哈夫曼编码。5. 【设计题目】校园导航问题【问题描述】设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。【实现提示】 用Dijkstra或Floyd算法实现6. 【设计题目】散列法的实验研究【问题描述】散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。【实现要求】对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。【实现说明】 用顺序存储完成。7. 【设计题目】交通网络的最经济架构问题【问题描述】在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。【实现提示】用Prim算法完成，用邻接矩阵存储图。8. 【设计题目】运动会分数统计的应用【问题描述】参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。每个的项目取前3名积分（或者前5名），积分分别为：5、3、2（或者7、5、3、2、1）；（m=20,n=20）并加以扩展应用。【基本要求】1、 可以输入各个项目的前3名（或