数据结构课程设计

1、数据结构课程设计教学目的和任务 1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能 课程设计内容和基本要求1. 在老师指导下，参考数据结构课程设计指导书选定设计题目2.分析题目，查阅相关资料3. 算法设计、数据结构设计4. 编写代码并调试5. 完成课程设计报告课程设计方式与安排数据结构课程设计按照教学要求，总共要上机调试程序20学时。我们初步安排18周进行验收. 课程设

2、计报告的格式（1）问题描述：描述要求编程解决的问题。（2）基本要求：给出程序要达到的具体的要求。（3） 算法思想：描述解决相应问题算法的设计思想。（4） 模块划分：描述所设计程序的各个模块（即函数）功能。（5） 数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。（6） 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。（7） 测试情况：给出程序的测试情况以及运行结果的截图，并分析运行结果 题 目必须从以下5个题目中选2个题目完成：1、生死者游戏2、迷宫的求解3、二叉树的基本操作的实现4、图的基本操作

3、的实现5、二叉排序树的设计与实现以及快速排序算法的实现选 作 题 目1、交通咨询系统设计2、航班信息的查询与检索注意：如果仅仅做了其中的两个题目，最高80分，如果多做会有加分！实 验 内 容与 要 求生死者游戏 有n个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入大海，其余人才能幸免遇难无奈，大家只得同意这种办法，并议定n个人围坐一圈，从1,2,3到n进行编号。由第一个人数起，依次报数，数到第m人，将它扔进大海中，然后再从他的下一个人数起，数到第m人，再将他扔进大海，如此循环进行，直到剩下一半人为止，问哪几个人是将被扔进大海的人。 利用单向循环

4、链表存储结构模拟此过程，输出生者的编号。该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的不带头结点的单循环链表，再给出报数上限值m(假设m1).在链表的首结点开始从1计数，计到m-1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到m-1，再将其下一个结点从单循环链表删除，直到剩下一半结点为止。该问题算法描述如下：建立一个由头指针head指示的有n个结点的约瑟夫单循环链表InitRing。生者与死者的选择： p指向链表第一个结点，初始化i为1； wh

5、ile (idata; 输出所有生者的编号。函数间的调用关系:程序包含以下函数：LinkList InitRing(int n,LinkList R)：初始化一个约瑟夫环。LinkList DeleteDeath(int n,int k,LinkList R)：寻找被扔入大海的人void output(LinkList R)： 输出所有生存者函数图2-12生死者游戏程序结构图mainInitRingDeleteDeathoutput迷宫的求解迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出

6、口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。求解思想：采用回溯法。 回溯法是一种不断试探且及时纠正错误的搜索方法。 本问题可从入口出发，按某一方向向未走过的前方探索，若能走通，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。这也是一种“穷举求解”的方法。求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。需要解

7、决的问题：1、表示迷宫的数据结构2、试探方向3、栈的设计4、防止重复到达某点，避免发生死循环1、表示迷宫的数据结构表示一个m行n列迷宫：用mazemn表示，0im,0jnmazeij = 0 通路mazeij = 1 不通改进：用mazem+2n+2表示且mazeij=1，i=0或m1, j=0或n1入口坐标为（1，1），出口坐标为（m，n） 012345678901111111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111迷宫的定义：#

8、define m 8 /*迷宫的实际行*/#define n 8 /*迷宫的实际列*/int maze m+2n+2 ;2、试探方向表示位置的类型PosType定义如下：typedef struct int x，y; PosType ; 试探顺序规定为：从正东沿顺时针方向与点(x，y)相邻的4个点及坐标(x,y)(x,y+1)(x,y-1)(x+1,y)(x-1,y)3、栈的设计栈中每个元素的组成：通道块在路径上的序号坐标位置前进方向（东为1，南为2，西为3，北为4）栈元素的类型定义： typedef struct int ord; PosType seat; int di;SElemType

9、;4、防止重复到达某点走过不通之处要加以标记（MarkPrint操作）迷宫求解算法:Typedef struct int ord; PosType seat; int di;SElemType;Status MazePath(MazeType maze,PosType start,PosType end) InitStack(S);curpos=start; curstep=1; do if (Pass(curpos) FootPrint (curpos); e=(curstep,curpos,1) Push(S,e); if (curpos=end) return (TRUE); curpo

10、s=NextPos(curpos,1); curstep+; /if else if (!StackEmpty(S) Pop(S,e); while (e.di=4&!StackEmpty(S) MarkPrint(e.seat);Pop(S,e); /while if (e.di4) e.di+;Push(S,e);curPos=NextPos(e.seat,e.di); /if /else while (!StackEmpty(S); return FALSE;二叉树基本操作的实现在主程序中编写一个简单的菜单，将有关二叉树的操作（建立一棵二叉树的存储结构、遍历一棵二叉树、统计二叉树叶子结点

11、的个数、求二叉树的深度）等整合在一起，包括递归算法和非递归算法。图的基本操作的实现在主程序中建立一个菜单，实现图的基本操作，包括：建立图的存储结构，实现图的深度优先搜索遍历，广度优先搜索遍历以及利用图的拓扑排序验证图中是否存在环。二叉排序树的设计与实现以及快速排序算法的实现1、 编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：（1）由4，9，0，1，8，6，3，5，2，7创建一棵bt并以括号表示法输出；（2）判断bt是否为一棵二叉排序树；（3）采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径；（4）分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序树。二叉排序树的设计与实现以及快速排序算法的实现2、编写一个程序，实现对某一张顺序表的快速排序算法。交通咨询系统设计设计一个交通咨询系统，能让旅客咨询从任意一个城市到另一个城市之间的最短路径（里程）或最低花费或最少时间等问题。该设计分成三部分，一建立交通网络图的存储结构，二是解决单源