《数据结构课程设计》指导大纲。
课程名称：数据结构课程设计。
英文名称：course exercise in data structure
一、课程设计的目的、要求和任务。
本课程设计是为了配合《数据结构》课程而开设的，通过设计完整的大型程序，使学生掌握数据结构的应用、算法的编写、类c语言的算法转换成程序并用上机调试的基本方法。
1.课程的目的。
1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储。
结构和操作实现算法，以及它们在程序中的使用方法。
2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计。
的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基。
本能力；2.课程的基本要求与任务。
1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。（2）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。（3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。
（4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。（5）题目具有足够的工作量。二、课程设计的一般步骤：
1.选题与搜集资料：根据题目的人数要求学生自由分组，并确定组内成员的分工，进。
行课程设计课题的资料搜集。
2.分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的。
数据结构、并在此基础上进行实现程序功能的算法设计。3.程序设计：
运用掌握c/c++语言编写程序，实现各个模块功能。4.调试与测试：
调试程序，并记录测试情况。5.每组成员根据自己的工作各自完成课程设计报告。
6.验收与评分：指导教师对每组同学的开发的系统进行综合验收，并由学院考核小组。
进行随机抽查评分。
三、成绩评定标准。
学生成绩由以下几个方面进行评定：
1.学生编写的实际软件和运行结果，占总成绩40%；2.设计报告，占总成绩40%3.回答问题，占总成绩10%4.出勤，占总成绩10%
四、附：课程设计题目。
1.学生作业管理系统（不超过5人，自行对各功能模块的实现进行分工，，功能模块相对独立，可供其他人调用）
问题描述：设计一个学生作业管理系统，实现对学生作业提交情况的检查、查询、文件名的规范等操作。系统运行要求：
1）“学生信息表”已经存在，初始为教师的教务管理系统中导出的点名表，是excel**，具体**见附件一。
2）学生提交的作业文档已存在，并保存在同一目录下，作业文件名由学号+姓名组成。
系统基本要求：程序采用图形界面下进行交互的工作方式，完成如下功能：
1）规范学生作业文件名。
往往有同学上交的文件没有按照规范命名，这些文件名中可能包含了学号和姓名，但顺序不对；或者除学号、姓名外有其他信息；或者只有学号、只有姓名等；对不规范的命名文件要能够进行重命名，顺序不对的进行调整；信息多余的予以删除；信息不全的则到学生信息表中查找补充；对无法规范的文件名统一管理报告，保存到专门的不规范文件列表文件并能够随时打开显示。能够规范的文件在生成规范的文件名后以新文件名对老的文件名进行修改。（2）多种方式建立学生作业信息。
规范后的每个学生的作业文件放在一个目录下，通过读取这些文件名形成学。
生作业信息表，表中每个节点代表一个学生的作业信息，至少包括学生的学号、姓名、作业文件存放路径，并将作业提交情况信息添加到“学生信息表”保存，在该表中标记已交和未交学生情况；同时将作业信息表保存到。
若在目录中新存入一个文件，则可允许通过手工录入的方式录入作业信息，同。
时更新和“学生信息表”；
也可以导入某个路径下存放学生作业信息的文本文件。（3）检查浏览学生作业提交情况及作业文档。
以列表方式显示所有学生的作业提交信息，区别已交学生和未交学生可选中某一学生，调用word等编辑器打开其作业文档（4）按照学号对所有学生信息进行升序、降序排列，并输出。
可选用冒泡、选择、快速排序等算法；
不仅输出屏幕显示，还可根据需要写入相关信息文件。
5）按姓名、学号等方式，实现对学生作业信息的精确查询、模糊查询，输出屏幕显。
示，并能调用word等编辑器打开选中学生的作业文档。
精确查询结果演示。
查询“姓名是刘梅”同学信息，则输出。
学号姓名作业提交情况作业文件。
2004112011刘梅已交c:\file\2004112011刘梅。doc
查询“作业提交情况是未交”的同学信息，则输出***刘强未交***张计未交***赵冈未交…
模糊查询结果演示。
查询“姓刘”的同学信息，则输出。
学号姓名作业提交情况作业文件。
2004112011刘梅已交c:\file\2004112011刘梅。doc2004112012刘强未交。
2004112013刘星已交c:\file\2004112013刘星。doc
能够实现连续多次查询，并根据用户要求将查询结果保存为文件（6）学生作业信息的插入、删除、修改。
通过插入、删除和修改后，保持所有学生信息的有序性；插入、删除和修改后，对存放所有学生信息的文件及时更新。（7）数据的统计功能。
统计已交学生名单；统计未交学生名单；
将上述统计结果，根据用户需要写入相应文件。
2.个人**号码查询系统（不超过3人，要求其中一人负责系统的主框架，包括实现录入数据、生成链表和统计数据的汇总比较等模块，其他人每人至少完成一种哈希函数和一种冲突解决策略，功能模块相对独立，可供其他人调用）问题描述：设计一个哈希表，实现个人**号码查询系统。
基本要求：
1）设每个记录有下列数据项：**号码、用户名、用户住址；
2）从键盘输入各记录，分别以**号码和用户名为关键字建立哈希表；
a)可根据用户选择使用不同的哈希函数，并输出各自的冲突率；
b)在哈希函数确定的前提下，可提供各种不同类型处理冲突的方法供选择，并统计对应方法的平均查找长度；
c)能统计不同哈希函数的冲突率，及不同冲突处理策略的平均查找长度，列表显示各种不同方法的比较结果；
学号姓名作业提交情况作业文件。
3）查找并显示给定**号码/用户名的记录；
3.实用的小型通讯录（不超过3人，自行对各功能模块的实现进行分工，功能模块相对独立，可供其他人调用）
问题描述：设计一个管理个人通讯录的程序，完成下列基本功能。1）录入和备份通讯录。
a)录入通讯录要求：
采用手工输入方式，建立一个通讯录文件，存放与用户相关的人员通讯信息每条通讯信息由姓名、手机号码、家庭号码、工作单位、家庭住址、与本人关系组成，每个数据项以字符串形式定义。
b)备份通讯录要求：
在默认的c:\backup文件夹中，定期备份通讯录中所有信息。备份文件以“backup当前日期。txt”命名。
2）通讯录管理。
a)通讯录信息浏览要求：
所有通讯信息浏览。
某个类别的通讯信息浏览。其中类别有家庭、朋友、同学、同事和其他四类。b)通讯录信息添加要求：
按照类别添加通讯信息，如果类别缺省，则属于“其他”类中。添加后，需要及时更新通讯录文件。c)通讯录信息删除要求：
删除后，需要及时更新通讯录文件。
d)通讯录信息查询：按照姓名、**号码等字段，进行精确、模糊查询，并在屏幕上。
输出查询结果。查询结果要求参见“1.学生作业管理系统”e)通讯录信息修改要求：
修改后，需要及时更新通讯录文件。f）通讯录类别管理。
类别添加类别删除类别修改要求：
类别删除后，下属的所有通讯信息，应该归为“其他”类中。
4.迷宫问题（1人）
问题描述：用一个字符类型的二维数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（通道）或“1”（阻塞物）。设计一个模拟小老鼠走迷宫的程序，为小老鼠寻找一条从迷宫入口到迷宫出口的途经小方格最少的最短通路。
基本要求：
1）用随机函数设置迷宫；（2）选择合适的数据结构表示迷宫。（3）迷宫入口和出口由键盘或鼠标输入。
4）输出从入口到出口的最短通路（如存在）或不存在通路的信息。（5）设计出友好的图形化界面，做到很好的人机交互。
5.栈与队列结构的操作动画演示系统（不超过4人，自行对各功能模块的实现进行分工，功能模块相对独立，可供其他人调用）
问题描述：设计一个动画演示系统动态演示栈和队列的各种操作，帮助理解这两种数据结构中的插入、删除、向上溢出和向下溢出等概念。特别是关于两个栈共用一块存储空间和循环队列的情况。
基本要求：
1)对单个栈，从键盘或文件中输入入栈数据个数和数据序列，动态演示数据的入栈和。
出栈过程，包括栈顶指针的变化，栈内数据的变化，溢出的情况的演示等，并显示文字说明对该过程进行讲解；
2)对两个栈共用空间的情况，从键盘或文件中输入入栈数据个数和数据序列，动态演。
示数据的入栈过程，包括栈顶指针的变化，栈内数据的变化，溢出的情况的演示等，并显示文字说明对该过程进行讲解；
3)对一般队列，从键盘或文件中输入入队数据个数和数据序列，动态演示入队和出队。
过程，包括队头、队尾指针值的变化，队内数据的变化，溢出的情况的演示等，并显示文字说明对该过程进行讲解；
4)对循环队列，从键盘或文件中输入入队数据个数和数据序列，动态演示入队和出队。
过程，包括队头、队尾指针值的变化，队内数据的变化，特别是队列已满情况的判定条件演示等，并显示文字说明对该过程进行讲解；
6.哈夫曼树编码/译码系统（不超过3人）
问题描述：哈夫曼编码在通讯、网络、数据压缩、图像处理中的得到广泛应用，在一个通讯系统中，采用图形界面设计m叉哈夫曼树(m≥2)，对通讯信息进行编码和解码。基本要求：
1）从终端读入字符文件，统计文件中字符的出现频率作为每个字符的权值，建立m叉哈夫。
曼树，并将哈夫曼树以直观的方式（如树形）显示在终端上，同时将字符及其对应的编码写入文件codeprint中；
2）利用编码结果，对文件中的正文进行编码，然后将结果存入文件codefile中，并输出结。
果，将文件codefile以紧凑格式显示在终端上，每行50个**。
3）将文件codefile中的**进行译码，结果存入文件textfile中，并输出结果。
7.校园导游系统（不超过2人）
问题描述：设计一个校园导游程序，完成校园信息的维护以及为来访的客人提供信息查询等服务功能。基本要求：
1）根据新校区的校园平面图设计带权无向网络，所含景点不少于10个，以图中顶点。
表示校内各景点，顶点的信息包括：景点名称、代号、简介等，以边表示道路，边上信息包括：两点距离、所需时间等相关信息。
（注：数据的输入可以是键盘输入或文件输入两种方式）建立相应的图结构。
2）提供对校园景点信息的编辑（如：添加、删除、修改等）的功能；（3）为来访客人提供图中任意景点相关信息的查询（可提供多种查询方式）；（4）为来访客人提供从校门口到图中任意景点的问路查询（最短路径）；（5）为来访客人提供图中任意景点间的问路查询。
8.最小生成树问题（不超过2人）
问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
现在，我们要选择这样一棵生成树，使总的耗费最小。即构造连通网的最小生成树的问题。基本要求：
1）建立城市交通网的存储结构。（注：数据输入可以是键盘输入或文件输入两种方式）（2）分别用prim算法和kruskal算法构造最小生成树，并输出最小生成树的代价及生成树的边。
（注：结果的输出可以是屏幕输出和文件输出两种方式）
五、备注：1.选题：
1）以上给出的课程设计题目，学生可以从中选择任何一个题目，并做好相关准备；（2）为调动学生的积极性，学生还可参照以上题目，自拟一些具有综合性的题目（工。
作量和难度经指导教师审核通过有效）。
2.功能完成及检测。
1）不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。
2）鼓励同学们充分发挥主观能动性，结合所选课题，独立思考，努力钻研，勤于。
实践，勇于创新，在完成题目的基本要求外，尽量完善程序，提高程序的可读性、健壮性等，完成好的同学，给以适当加分。
六、课程设计报告的规范(详见设计文档要求)
封面：如右图。
课程设计报告要求规范书写，应当包括如下6个部分：1问题描述2基本要求3系统分析与设计4测试数据及结果5总结。
6附录：源程序清单。
文字用小4号宋体，行距20磅；程序和注释用5号字，以班为单位交。
课程设计报告提交电子稿，文件必须是office2003或office2007版本，以”学号+姓名。doc”命名，如“0909080999张三。doc”，最后两次集中上机的时间在机房统一提交，拷贝到老师指定的机器和目录中，过时不候。
日期。数据结构”课程设计。
专业班级学号姓名。
DS课程设计题目
校园导游程序。问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号 名称 简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍 游览路径等问题。基本要求 1 查询各景点的相关信息 2 查询图中任意两个景点间的最短路径。3 查询图中任意两...
DS课程设计题目
1 选题要求 每位同学从ds课程设计题目里任选一题，每道题目的选题人数不得超过15人。2 提交材料 班委收齐每位同学的报告 电子版 后刻成光盘上交给老师。报告需严格按照课程设计报告模板的格式。3 评分细则 报告雷同者，视情节严重程度酌情扣分。原文抄袭网上者，统一按零分处理。课程设计结束时，有演示程序...
DS课程设计大纲
数据结构 课程设计大纲。课程设计名称 数据结构。实验室名称 计算机与信息技术实验室。适用专业 计算机科学与技术 信息管理与信息系统。实验对象 本科生。实验要求 必修。一 课程设计的目的。课程设计是 数据结构 课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机...