《数据结构与算法》

课程设计报告

题    目：本科生导师制问题与家族关系查询系统

院 （系）：         信息科学与工程           

专业班级：      计算机应用技术1301班       

学生姓名：           顾      泉            

学    号：          20131201018            

指导教师：           金      兰             

20 14 年 12  月  29  日至20 15 年  1 月  9 日

华中科技大学武昌分校制

数据结构与算法课程设计任务书

目  录

1   本科生导师制问题. 1

1.1需求. 1

1.2总体设计. 1

1.3详细设计及实现. 1

1.4运行结果. 1

2   停车场管理. 2

2.1需求. 2

2.2总体设计. 2

2.3详细设计及实现. 2

2.4运行结果. 2

3   大整数计算器. 3

3.1需求. 3

3.2总体设计. 3

3.3详细设计及实现. 3

3.4运行结果. 3

4   家族关系查询系统. 4

4.1需求. 4

4.2总体设计. 4

4.3详细设计及实现. 4

4.4运行结果. 4

5 地铁建设问题. 5

5.1需求. 5

5.2总体设计. 5

5.3详细设计及实现. 5

5.4运行结果. 5

总结. 6

（目录要求：目录题头用三号黑体字居中书写，隔行书写目录内容。目录中各级题序及题标用小四号黑体字）

（正文要求：一级标题，黑体，三号，居中；二级标题，黑体，小三号；三级标题，黑体，四号；正文，宋体，小四号，1.25倍行距）

1     本科生导师制问题

1.1需求（二级标题用黑体三号，三级标题用黑体四号，下同）

在高校的教学改革中，有很多学校实行了本科生导师制。一个班级的学生被分给几个老师，每个老师带n个学生，如果该老师还带研究生，那么研究生也可直接带本科生。本科生导师制问题中的数据元素具有如下形式：

①导师带研究生

（老师，（（研究生1，（本科生1，…，本科生m₁）），（研究生2，（本科生1，…，本科生m₂））…））

②导师不带研究生：

（老师，（本科生1，…，本科生m））

导师的自然情况只包括姓名、职称；研究生的自然情况只包括姓名、班级；本科生的自然情况只包括姓名、班级。

①建立：建立导师广义表；

②插入：将某位本科生或研究生插入到广义表的相应位置；

③删除：将某本科生或研究生从广义表中删除；

④查询：查询导师、本科生（研究生）的情况；

⑤统计：某导师带了多少个研究生和本科生；

⑥输出：将某导师所带学生情况输出；

⑦退出：程序结束。

……………（正文用小四宋体，行距为单倍行距1.25磅，下同。）

1.2总体设计

1.3详细设计及实现

以下内容要求：

1.数据结构的设计说明；

2.系统包含的主函数和子函数及各函数功能的详细说明；

3.画系统的总体流程图，子函数流程图，要求采用标准流程图图符至少画两个流程图；

4.部分核心源代码。只能使用C语言，源程序编写格式要按照缩进方式，源程序要有详细的注释，使程序容易阅读。源程序编写格式的规范和注释体现程序员的素质。

…………………………………….

1.4运行结果

以下内容要求：

包括输入的数据，输出的结果。

可以将输出的结果以截屏方式呈现到课程设计报告中。

…………………………………….

2     停车场管理

2.1需求（二级标题用黑体三号，三级标题用黑体四号，下同）

  

2.2总体设计

2.3详细设计及实现

2.4运行结果

3     大整数计算器

3.1需求（二级标题用黑体三号，三级标题用黑体四号，下同）

  

3.2总体设计

3.3详细设计及实现

3.4运行结果

4     家族关系查询系统

4.1需求（二级标题用黑体三号，三级标题用黑体四号，下同）

       建立家族关系数据库，实现对家族成员关系的相关查询。

①建立家族关系并能存储到文件中。

②实现家族成员的添加。

③可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。

4.2总体设计

4.3详细设计及实现

4.4运行结果

5 地铁建设问题

5.1需求（二级标题用黑体三号，三级标题用黑体四号，下同）

  

5.2总体设计

5.3详细设计及实现

5.4运行结果

总结

必须真实的说出自己在课程设计中的切身体会。

例如：课程设计如何构思、如何设计、如何编程、如何调试、遇到的主要问题和解决方法，哪些地方使你“痛苦不堪”；创新之处；课程设计中存在的不足，需进一步改进的设想等等。

（要求：一级标题，黑体，三号，居中；二级标题，黑体，小三号；三级标题，黑体，四号；正文，宋体，小四号，1.25倍行距）

 

课程设计成绩评定表

第二篇：迷宫问题z-数据结构与算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2009 ～2010 学年第二学期

课学专指

生业导

名班教

程 称 级 师

数据结构与算法 迷宫问题 韩非 08计本（2）班 王昆仑 张贯虹

课程设计名称

20xx年6月

一、课程设计名称及内容

名称：迷宫问题

内容：生成一个N×M(N行M列)的迷宫，完成迷宫的组织和存储，并实现迷宫路由算法。基本要求1、 N和M是用户可配置的，缺省值为50和50。2、迷宫的入口和出口分别在左上角和右下角。

提示：（1）可以使用二维数组maze[M+2][N+2]表示迷宫，其中M,N为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值为1时表示该点是墙。老鼠在每一点都有4种方向可以走，可以用数组move[4]来表示每一个方向上的横纵坐标的偏移量，可用另一个二维数组mark[M+2][N+2]记录节点的访问情况。（2）可以选用深度优先算法或广度优先算法实行，迷宫可由自动或手动生成。测试用例应该包含有解迷宫和无解迷宫。

二、问题分析

本程序要求实现迷宫问题的相关操作，包括迷宫的组织和存储，并实现迷宫路由算法（即查找迷宫路径）。程序所能达到的：具体包括迷宫的建立，迷宫的存储（迷宫由自动生成或手动生成），迷宫中路径的查找

迷宫是一个矩形区域，迷宫存在一个入口和一个出口，其内部包含了不能穿越的墙或者障碍。迷宫的建立即是建立这样一个迷宫矩阵，用于存储迷宫信息，包括可穿越的路和不可穿越的墙或者障碍，分别用0表示通路，1表示障碍。对于迷宫矩阵，用m×n的矩阵来描述，m和n分别代表迷宫的行数和列数。这样，则迷宫中的每个位置都可以用其行号和列号来指定。从入口到出口的路径是由一组位置构成的。每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的上、下、左、右的邻居。

为了描述迷宫中位置（i ，j）处有无障碍，规定，当位置（i ，j）处有一个障碍时，其值为1，否则为0.这样迷宫就可以用0、1矩阵来描述，在构造矩阵时，为了操作方便会将矩阵四周置为1（不通）。

对于查找迷宫路由问题

首先，考察，迷宫的入口位置，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则，考察其上、下、左、右位置上的邻居是否是障碍，若不是就移动到这个相邻位置上，然后对于这个位置开始搜索通往出口的路径。如果不成功，就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索出现重复，则将已搜索过的位置标记为1。同时为保留过搜索的痕迹，在考察相邻位置之前，将当前位置保存在一个堆栈中，如果所有相邻的非障碍位置均被搜索过，且未能找到通往出口的路径，则表明不存在从入口到出口的路径。且对于此，实现的是深度优先遍历算法，如果查找到路径，则为从入口到出口的路径。 下面实现如何利用堆栈实行深度优先遍历算法进行迷宫最短路径的查找。

以矩阵 1 1 1 1 1 1 1

1 0 0 1 0 1 1

1 1 0 0 1 0 1

1 1 0 0 0 1 1

1 0 0 1 0 0 1

1 1 1 1 1 1 1

首先，将位置（1，1）放入堆栈中，从它开始搜索，标记。由于其只有一个非障碍位置，所以接下来移动到（1，2），防止稍后的搜索再经过这个位置。

从（1，2）移动到（2，2），放入堆栈中，（2，2）存在（2，3）、（3，2）两个可移动位置。标记已被搜索过，对于每一个非障碍位置，它的相邻非障碍节点均入队列，实现了深度优先遍历算法。所以如果存在路径，则从出口处节点的位置，逆序则可以找到其从出口到入口的通路。实现了查找路径。

宫路由算法流程图：

图1迷宫路由算法流程图

1、数据输入形式和输入值的范围：生成迷宫时可选择手动或者自动生成；手动输入迷

宫矩阵时以0 表示无障碍为通路，1 表示该点有障碍为墙。所有输入中，元素的值均为整

数。

2、结果的输出形式：当完成迷宫生成后，会提示输入入口与出口，进入迷宫路由查找

算法，如找到出口，则打印出路径矩阵坐标，并显示显示迷宫生成图形

3、测试数据：

a、进入界面，选择2，自动生成

b、输入入口与出口

c、查看结果

三、概要设计

1、为了实现上述功能，需要：①构造一个二维数组maze[M+2][N+2]用于存储迷宫矩阵,

构造一个二维数组backup[M+2][N+2]用于备份迷宫矩阵；②自动或手动生成迷宫，即为二

维数组maze[M+2][N+2]赋值并备份；③将构造一个堆栈用于存储迷宫路由；④建立迷宫节

点struct Mlink，用于存储迷宫中每个访问过的节点。⑤实现迷宫路由算法，用深度优先遍历实现查找迷宫路径。如找到路径则显示路径，否则提示无通路。同时显示生成迷宫。⑥在屏幕上显示操作菜单。

2、本程序包含6 个函数：

( 1 )主函数 main( )

( 2 )生成迷宫函数 create( )

( 3 )打印迷宫矩阵与图形函数prin( )

( 4 )寻找迷宫路由Mazepath( )

( 5 )输出迷宫通路坐标printonglu1( )

( 6 )输出迷宫生成图形printonglu2( )

各函数之间的关系如下图（图2）所示：

函数关系图：

create( )

prin( )

)

printonglu1( )

printonglu2( )

图 2各函数间关系图

四、详细设计

实现概要设计中定义的所有数据类型，对各个操作给出伪代码算法。对于主程序和各个模块也给出相应的伪代码算法。

1、 节点类型和指针类型

迷宫矩阵类型：

Mlink *stack; 全局变量堆栈，存储迷宫通路

int abc[M+2][N+2] 辅助数组

int maze[M+2][N+2]; 迷宫矩阵

int backup[M+2][N+2]; 备份矩阵，便于操作，定义为全局变量 迷宫中节点类型及队列类型：

struct Mlink { int row ,col ; struct node * next;} Mlink;

2、 迷宫的操作

(1)生成迷宫

void create(int maze[][N+2])

{定义变量i,j,flag;

srand( (unsigned)time( NULL ) ) 以时间产生随机种子

利用for初始化迷宫矩阵与备份矩阵，包括边界全置为1

利用for将迷宫置为0

选择迷宫生成方式1为手动生成，2为自动生成，输入值并赋给flag

flag=1{

以i , j 控制迷宫中行列数的循环输入

以0 表示通路，以1 表示障碍,给maze[i][j]赋值，不包括边界。

循环结束，完成迷宫生成}

flag=2{

定义变量i1，j1用以接收随机值

以i , j 控制迷宫中行列数的循环赋值操作

以0 表示通路，以1 表示障碍

用for(c=1;c<=M*N;c++){

i1=(int)(rand()%M)+1; j1=(int)(rand()%N)+1; maze[i1][j1]=int(rand()%2); }随机定位矩阵一点，给maze[i1][j1]赋一个随机值，这样可以增加迷宫通路的概率，循环结束，完成迷宫生成}

以i , j 控制迷宫中行列数的循环赋值操作，将maze[][]备份到backup[][];}

(2)打印迷宫矩阵与字符图形

void prin(int maze[][N+2]){

此函数主要用于将迷宫矩阵显示出来

定义变量i，j，z；

for(z=1;z<=N;z++)

{if(z<10) printf("%d ",z); else printf("%d",z);

} 此语句用来标明列号

用 for 控制循环 在第一重循环里，使用语句{

printf("\n");

if(i<10) printf("%d ",i);

else printf("%d",i);}以此用来标明行号

以 i, j 控制迷宫中行列数的循环操作，将maze[i][j]显示出来

并用字符□，■分别代表可通与不可通}

（3）迷宫求解路由求解操作{

Mlink *p;用以操作堆栈

①入口若不通，return（0）否则下一步

②将其入栈

③未找到出口并且堆栈不空{

1）栈顶位置以下是否可通，可通则返回②，否则2），

2）栈顶位置以上是否可通，可通则返回②，否则3)，

3）栈顶位置以右是否可通，可通则返回②，否则4)，

4）栈顶位置以左是否可通，可通则返回②，否则出栈并返回，}

④如果栈顶为出口，return （1）；否则return （0）；}

（4）打印迷宫通路坐标

void printonglu1(){

Mlink *q;用以操作堆栈

q=stack

q不空{

输出q指向的坐标

q=q->next}

}

(5)输出迷宫通路的字符图形

void printonglu2(){

此函数根据堆栈内栈顶与“次栈顶”的位置关系决定输出字符↑，←，→或↓，其中2=↑，3=←，4=→，5=↓所有的操作都是在备份矩阵backup[][]上。

出口位置输出㊣

int i，z，j；Mlink *p=stack；

p不空{

if(p->row>p->next->row) backup[p->next->row][p->next->col]=5; 下一位置在下 else if(p->row<p->next->row) backup[p->next->row][p->next->col]=2;下一位置在上

else if(p->col>p->next->col) backup[p->next->row][p->next->col]=4;下一位置在右

else ;下一位置在左}

利用for循环，i，j为循环控制变量输出备份矩阵backup[][]{

为0是输出“□”

为1是输出“■”

为2是输出“↑”

为3是输出“←”

为4是输出“→”

为5是输出“↓”

为6是输出“㊣”}

另外在输出语句上，与矩阵输出相同，标明了行号与列号（该功能为王教授所要求而后加的） }

3、 主函数

void menu(){

定义迷宫数组矩阵maze[M+2][N+2]

定义辅助数组abc[M+2][N+2] 以用来在可以在第一次产生迷宫中重复选择入口与出口 定义变量k以用来控制循环

定义整型变量 x1，y1 ，用于存储入口。

定义整型变量 x2，y2 ，用于存储出口。

定义整型变量x用于接收mazepash的返回值。

输入入口与出口。

如果x=1则条用函数{

printonglu1();

printonglu2();}

否则提示无通路。}

界面开始会显示：

1,手动建立

2,自动建立

按提示操作，输入入口与出口，回车即会看到结果

五、调试分析

在调试过程中，开始用堆栈实现了路径的查找并调试成功，但输出的结果仅仅只是路径坐标，看起来不形象，于是想到了用字符来表示图形并标出通路，虽然不是太完美，但比之之前好好多了

在实现这一算法过程，注意将访问过的节点进行标记，并且在遍历过程中对矩阵数组是“破坏性”遍历，在算法完成后，矩阵已被破坏，堆栈中会存用路径，为了再原矩阵中用字符图形表示出通路，在建立矩阵后会迷宫矩阵备份一下，当然或许会有更好的处理方法。

六、使用说明

程序名为迷宫.exe，运行环境为DOS，程序执行后显示：

建立迷宫矩阵(选择1或者2)：

1,手动建立

2,自动建立进

请输入您的选择：

在输入选择后输入数字选择执行不同的迷宫建立。按要求输入入口与出口

七、测试结果

1主页面

图3 主页面

2选择自动建立

图4 迷宫自动生成中

3，自动生成迷宫，上面为数组矩阵，其中0可通，1障碍。下面为字符图形，其中白色可通，黑色障碍，

图5 打印出的迷宫矩阵与迷宫图形 4，根据提示输入入口与出口

图6 输入入口与出口 5，回车后输出路径

图7 打印出的迷宫路径 6，输入一个非“0”继续

图8 输入非“0”继续走该迷宫 7，输入入口与出口，无通路

图9 无通路

八、参考文献

[1] 王昆仑，李红.《 数据结构与算法.》 北京：中国铁道出版社，20xx年6月。 附录：

源代码：

#include"iostream"

#include"stdio.h"

#include"time.h"

#include"malloc.h"

#define M 20

#define N 20

typedef struct node//堆栈结构

{

int row; //行

int col; //列

struct node * next;

}Mlink;

Mlink *stack;//定义一个栈

int backup[M+2][N+2]; //备份数组

/*********************************建立迷宫矩阵**************************/

void create(int maze[][N+2])//建立迷宫

{

int i,j,flag; srand( (unsigned)time( NULL ) ); //以时间产生随机种子 for(i=0;i<=M+1;i++) for(j=0;j<=N+1;j++) maze[i][j]=1;//将四周置为1 for(i=1;i<=M;i++) for(j=1;j<=N;j++) { maze[i][j]=0;//初始化矩阵 backup[i][j]=0;//初始化备份矩阵 } printf("建立迷宫矩阵(选择1或者2)：\n1,手动建立\n2,自动建立\n请输入您的选择：\n");

scanf("%d",&flag);

if(flag==2){ //自动建立迷宫 int c,i1,j1; for(c=1;c<=M*N;c++){ //矩阵初始为“0”，随机选择位 if(flag==1)//手动建立迷宫 { printf("手动建立迷宫矩阵(0表示可通1表示障碍):\n"); } for(i=1;i<=M;i++) for(j=1;j<=N;j++) scanf("%d",&maze[i][j]); 置赋予一个随机的0或1，

i1=(int)(rand()%M)+1;

j1=(int)(rand()%N)+1;

maze[i1][j1]=int(rand()%2); //随机矩阵 按照王教授的要求这样可以产生更多的“0”即通路

} printf("自动生成中??\n"); system ("pause"); } for(i=1;i<=M;i++) for(j=1;j<=N;j++) backup[i][j]=maze[i][j];//备份数组矩阵

}

/***************************华丽的分割线*******************************/

/********************************打印迷宫矩阵*****************/

void prin(int maze[][N+2])

{

int i,j; printf("迷宫矩阵如下(0可通)：\n "); int z; for(z=1;z<=N;z++) //在矩阵上方标明列号 {if(z<10) printf("%d ",z); else printf("%d",z); } for(i=1;i<=M;i++) { printf("\n"); if(i<10) printf("%d ",i); //矩阵左方标明行号 else printf("%d",i); for(j=1;j<=N;j++) printf("%d ",maze[i][j]); } printf("\n迷宫图形如下(白色可通)：\n"); printf(" "); for(z=1;z<=N;z++) //在图形上方标明列号 {if(z<10) printf("%d ",z); else printf("%d",z); } for(i=1;i<=M;i++) { printf("\n"); if(i<10) printf("%d ",i); //矩阵左方标明行号 else printf("%d",i);

} for(j=1;j<=N;j++) { } if(maze[i][j]==0) printf("□"); if(maze[i][j]==1) printf("■");

}

/*******************************分割线***************************/

int Mazepath(int maze[][N+2],int x1,int x2,int y1,int y2)

{

Mlink *p; if(maze[x1][y1]==0){ p=(Mlink *)malloc(sizeof(Mlink)); p->row=x1; p->col=y1; p->next=NULL; stack=p; //将入口放入堆栈

maze[stack->row][stack->col]=1;//标志入口已访问

while((!(stack->row==NULL&&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//未找到出口并且堆栈不空

{

if(maze[stack->row][stack->col+1]==0)//下面位置可通 { } p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row; p->col=stack->col+1; p->next=stack; //入栈 stack=p; maze[stack->row][stack->col]=1;//标记已访问 else if(maze[stack->row][stack->col-1]==0)//上面可通 { } p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row; p->col=stack->col-1; p->next=stack; //入栈 stack=p; maze[stack->row][stack->col]=1;//标记已访问

else if(maze[stack->row+1][stack->col]==0)//右面可通 { } { p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row-1; p->col=stack->col; p->next=stack; //入栈 stack=p; p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row+1; p->col=stack->col; p->next=stack; //入栈 stack=p; maze[stack->row][stack->col]=1;//标记已访问 else if(maze[stack->row-1][stack->col]==0)//左面可通 maze[stack->row][stack->col]=1;//标记已访问 } else //不可通 返回上一点 { if (stack->next!=NULL){//堆栈里布置一个顶点则出栈并返回循环 p=stack; stack=stack->next; //出栈 free(p); //释放空间 }

else //堆栈里只有一个顶点即入口，此时若释放空间出栈会使循环

{ //控制语句无法比较（因为

stack->col,stack->row都已不存在，)

stack->row=NULL;

}

} else return(0); } stack->col=NULL; stack->next=NULL;} } if (stack->row==x2&&stack->col==y2) return (1); else return (0);

/****************************输出坐标通路*******************/

void printonglu1()

{

}

/*******************************分割线**********************/

/**********************输出图形通路**************************/

//2时输出↑，3时输出←，4时输出→，5时输出↓

void printonglu2()

{

printf("图形通路如下：\n"); int z; printf(" "); for(z=1;z<=N;z++) //图形上方标明列号 {if(z<10) printf("%d ",z); else printf("%d",z); } int i,j; Mlink *p; p=stack; backup[p->row][p->col]=6; while (p->next!=NULL) { if(p->next->col!=NULL) { if( p->row > p->next->row ) Mlink *q; printf("其中的一条通道为：\n"); q=stack; printf("出口<--"); while (q!=NULL) { printf("(%d%3d)<--",q->row,q->col); q=q->next; } printf("入口\n");

backup[p->next->row][p->next->col]=5;//下一节点在下

else if(p->row<p->next->row)

backup[p->next->row][p->next->col]=2;//下一节点在上

else if(p->col>p->next->col)

backup[p->next->row][p->next->col]=4;//下一节点在右

else backup[p->next->row][p->next->col]=3;//下一节点在左 } else ; p=p->next; } for(i=1;i<=M;i++) { printf("\n"); if(i<10) printf("%d ",i); //图形左方标明行号 else printf("%d",i); for(j=1;j<=N;j++) { if(backup[i][j]==0) printf("□"); if(backup[i][j]==1) printf("■"); if(backup[i][j]==2) printf("↑"); if(backup[i][j]==3) printf("←"); if(backup[i][j]==4) printf("→"); if(backup[i][j]==5) printf("↓"); if(backup[i][j]==6) printf("㊣"); } }

}

void main()

{

system("color f0"); //背景该为白色

int k=1; int maze[M+2][N+2];//迷宫矩阵 create(maze); //建立迷宫 int abc[M+2][N+2],p,q; //备份数组以重复使用迷宫 for(p=0;p<=M+2;p++) for(q=0;q<=N+2;q++) abc[p][q]=maze[p][q]; while(k!=0){ int x,x1,x2,y1,y2; prin(maze); //打印迷宫矩阵 printf("\n输入迷宫入口：\n"); scanf("%d%d",&x1,&y1); printf("输入迷宫出口：\n"); scanf("%d%d",&x2,&y2); x=Mazepath(maze,x1,x2,y1,y2); if(x==1) //迷宫可通 { printonglu1(); //打印坐标通路

} } printonglu2();//打印图形通路 printf("\n"); } else printf("无通路！\n");//不可通 for(p=0;p<=M+2;p++) for(q=0;q<=N+2;q++){ backup[p][q]=abc[p][q]; maze[p][q]=abc[p][q]; } printf("输入0结束:\n"); scanf("%d",&k);