数据结构课程设计要求.docx

《数据结构》课程设计

一、数据结构课程设计要求

学生应认真主动完成课程设计的要求。有问题及时通过各种方式与教师联系沟通。

学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。

课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。上机时带上源程序（自备U盘）、数据结构教材、实验指导书、C语言教材。

第17周收集课程设计报告等文档资料，并进行面试，学生要能够说明自己的设计思路和具体实现方法。

二、 上交相关内容要求

上交的成果的内容必须由以下三部分组成，缺一不可。

源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中），若有必要，请加入程序说明文件；

课程设计报告：要求提交课程设计报告的word文档电子稿和打印稿，word文件名要求按照”学号-姓名-课程设计报告题目”起名，如文件名为"001-张三-利用栈求表达式的值".doc。

课程设计报告内容主要包括：

项目研究背景与意义

需求分析：在该部分中叙述，每个模块的功能要求；

概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图）每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。

详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

调试分析

测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

总结

总结可以包括课程设计过程中的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。

三、 数据结构课程设计题目

1、用单链表实现一个简易通讯录。

基本要求：程序功能包括通讯录的的建立和显示、联系人的插入、删除、修改和查询等几种操作功能。程序应提供菜单界面，主界面的菜单请参考如下形式设计：

*********************************************************************

TOC\o"1-5"\h\z通讯录管理系统 *

1.添加联系人信息 *

2.查询联系人信息 *

3.修改联系人信息 *

4.删除联系人信息 *

0.退出通讯录管理系统 *

*********************************************************************请选择0—4：

2、利用栈求表达式的值

编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：

1） 从键盘上输入表达式。

2） 分析该表达式是否合法：

（1） 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。

（2） 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。

（3） 若是其它字符，则返回错误信息。

3） 若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

3、迷宫问题

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

基本要求：

（1）实现一个栈类型，然后编写一个求解迷宫的程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

（2） 求得迷宫中所有可能的通路；

（3） 以方阵形式输出迷宫及其通路。（选做）

测试数据：

迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。

1 2 3 4 5 6 7 8

00

0

0

1

0

0

0

1

0

0

0

0

0

0

1

1

1

0

0

0

1

0

1

0

0

0

1

1

1

1

1

0

0

1

1

0

0

0

0

1

0

0

0

1

0

1

1

0

1

0

0

1

0

0

0

0

0

0

1

0

1

1

0

0

1

0

1

0

1

0

0

0

0

实现提示：

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于