第一篇：数据结构课程设计报告

青岛理工大学

数据结构课程设计报告

题目：宿舍管理查询软件

院（系）：计算机工程学院

学生姓名:谢茂盛

班级：网络121学号: 201207131

起迄日期:2014.07.07-2014.07.20

指导教师:张艳

一、需求分析（所有大标题宋体加粗四号，下同）（小标题宋体加粗小四，下同）

1.问题描述：

以无歧义的陈述详细说明对自己所选题目的解释性描述，可以补充说明该设计中要做的具体任务。强调的是程序要做什么？

2.基本功能

要求分别列出该设计要实现的功能，（每个功能要尽量和概要设计中的模块函数对应起来）。

二、概要设计

1.设计思路：

解决问题的思路概述，拟采用的算法的简介。

2.数据结构设计：

要求分别列出拟采用的数据结构及其定义，分为逻辑结构（线性？树状？图状？）和存储结构（顺序？链式？）。采用该结构的原因，如果有定义的抽象数据类型，可以列出其定义及各种操作。如下为抽象数据类型定义的模板。

定义程序中用到的抽象数据类型；

设计中所用到的数据结构或抽象数据类型的说明，以及在程序中的作用

抽象数据类型线性表的定义如下：

ADT List{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}

数据关系：R1={| ai-1,ai ∈D,i=1,2,3,……，n}

基本操作：

Insert(&L,i,j)

初始条件：线性表L已存在，1≤i≤n+1。

操作结果：在L中第i个位置之前插入新的数据元素j,L的长度加1。

Del(&L,i,j)

初始条件：线性表L已存在，1≤i≤n。

操作结果：删除L的第i个数据元素,L的长度减1

Xg(&L,i,j)

初始条件：线性表L已存在。

操作结果：用新的输入数据项j代替原有的指定要修改的数据项i。

Search(&L,i,e)

初始条件：线性表L已存在。

操作结果：查找指定的某元素i，并将值赋给e,用e 输出。

}

3.软件结构设计：

按需求分析中的功能进行模块划分，建立模块的层次结构及调用关系。

三、详细设计

实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画

出函数和过程的调用关系图。

实现设计中主程序和其他子模块的算法，以流程图的形式表示，需画出函数和过程的调用关系图。

本小节内所有的图均要求用Visio或Word进行绘制，不允许用bmp或其他格式的图片。绘图内文字均采用宋体五号（如果图比较大，排版不好看的话，可以根据需要缩小字体），单倍行间距，段前段后均设置为0行。

1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；

2．主函数和其他函数的伪码算法；

3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。

4.画出函数之间的调用关系图。

四、调试分析

内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析。

1.实际完成的情况说明（完成的功能，支持的数据类型等）；

2.程序的性能分析，包括时空分析；

3.上机过程中出现的问题及其解决方案；

4.程序中可以改进的地方说明；

5.程序中可以扩充的功能及设计实现假想。

五、测试结果

列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。

六、用户手册

说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是Step by Step的。

所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。

七、体会与自我评价

写出本设计的总结思考，收获心得体会，要求不少于600字，不得摘抄网上资料，只能参考。

正文（各标题除外），均采用宋体和Times New Roman字体，小四号字，1.25倍行距。

八、参考文献（列出你参考的书，格式按照下面的例子来写）例如：

[1]严蔚敏．数据结构(C语言)．清华大学出版社，2007

第二篇：数据结构课程设计报告

计算机科学与工程系

数据结构课程设计报告

课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级

专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师

数据结构课程设计

迷宫

题目一

1.设计内容 1.1问题描述

求迷宫从入口到出口的所有路径。1.2设计要求

1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。

1.3开发环境

Visual C++6.0的集成化环境 1.4研究思路

对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。

经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。

2.设计步骤

2.1 需求分析

（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和

1-1数据结构课程设计

迷宫

在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。

2.3 详细设计（1）主菜单伪代码：

while(flag1){

}

{shuru();//输入行列数

printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++)

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数

数据结构课程设计

迷宫

和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。

（2）算法的时空分析：

由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。

链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。

3.用户使用说明

运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。

图数据结构课程设计

迷宫

图1-2

图1-3 退出

5.总结与心得体会

本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。

{ }

mg[i][j]=1;//初始化

矩阵,将最外围置为1

printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2);

}mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量

}

void showplay(int mg[][M+2])//迷宫输出

{

n“);

for(i=1;i<=m;i++){

printf(”n“);for(j=1;j<=n;j++)

printf(”%d “,mg[i][j]);

int i,j;

printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计

迷宫

} } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){

}

printf(”n“);for(j=1;j<=n;j++){

} if(mg[i][j]==0)printf(”

if(mg[i][j]==1)printf(“

if(mg[stack->row][stack->col+1]==

p->next=stack;

stack=p;{

p=(mlink 可通)：n”);0)//下面位置可通

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■

//入栈

mg[stack->row][stack->col]=1;//将

} else

访问过的标记为1 int Mazepath(int mg[][N+2]){

mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p;

//将入口

mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&

if(mg[stack->row][stack->col-1]==0)//上面可通

//入栈

stack=p;

p->next=stack;

{

p=(mlink *)malloc(sizeof(mlink));

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问

&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口

{

mg[stack->row][stack->col]=1;//将

访问过的标记为1

数据结构课程设计

迷宫

void tonglu()//将坐标的顶点输出 {

始化

printf(“(%d%3d)n”,q->row,q->col);

情况

else printf(“□”);//0的 } q=stack;{

} for(i=0;i

for(j=0;jrow-1][q->col-1] q=q->next;

=

while(q!=NULL)//循环条件 q=q->next;for(j=0;j

情况

}

void create(int mg[][N+2])//创建和菜单

{

int i,j,x,choice,flag1=1;chushi();while(flag1){ }

printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件

printf(“

##

printf(”#

n“);

*********选择菜单**********

#n”);

printf(“

##

printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫

{

shuru();

printf(”手动建立for(i=1;i<=m;i++)

n“);

printf(”# 1-手动生成迷

宫

2-自动生成迷宫

3-退出

#n“);0;//将路径中的点赋给辅助数组a 形的界面输出

迷宫矩阵(0表示可通1表示障碍):n”);

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);

数据结构课程设计

航班信息查询与检索系统

题目二

1.设计内容 1.1问题描述

设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。

1.2设计要求

（1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能：  创建

 修改（插入、添加、删除、更新） 查询  浏览  退出管理系统（3）航班信息包括：

 航班号：字符序列，具体字符表达的意思上网查询  起点站和终点站：字符串  班期：指一周中哪些天有航班

 起飞时间：可将时间定义成一个时、分组成的序列  到达时间：可将时间定义成一个时、分组成的序列  机型：字符序列，具体字符表达的意思上网查询  票价：整型数，具体值可上网查询

（4）创建是指从文件中读取数据，并存入所定义的顺序表中。

（5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。

（6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。

（7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。

数据结构课程设计

航班信息查询与检索系统

typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane {

};（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数：

do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”);

printf(“*

1.创建

2.修改

3.查询

4.浏览

5.表长

6.文件

0.退出

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”);

scanf(“%d”,&opt);switch(opt){

case 1:Initlist(L);break;

case 2:handle(L);break;

case 3:search(L);break;

case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break;

数据结构课程设计

航班信息查询与检索系统

} }while(opt!=0);}

（4）文件操作： void File(Sqlist &L){

int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“*

*n”);

printf(“* 1.保存信息到文件

2.从文件读取信息

0 退出 *n”);

printf(“*

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“请输入选项n”);

scanf(“%d”,&ch);

switch(ch)

{

case 1:SaveList(L);break;

} }while(ch!=0);case 2:ReadList(L);break;

case 0:printf(“退出！n”);break;}

（5）浏览信息：就是循环使用输出函数，在此就不必多说了

2.4 调试分析

（1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。

（2）算法中有许多不是很优化的地方。3.用户使用说明

程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打

数据结构课程设计

航班信息查询与检索系统

图2-2 查询信息

图2-3插入

图2-4删除

数据结构课程设计

航班信息查询与检索系统

时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。

6.附录

#include #include #include typedef struct time { int hour;int min;

{ }

void search_key(Sqlist L)//按航班号查找

{ 号：“);

Time rh;Time lv;

scanf(”%s“,n);int i;

printf(”此航班的航班号，起点char n[20];

printf(“请输入要查找的航班

printf(”%dn“,L.length);//表长

}Time;typedef struct node {

}Pnode;struct Plane {

};typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;

终点，班期，起飞时间，到达时间，票价：n”);

if(strcmp(L.plane[i].key,n)==0)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length;

plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

0数据结构课程设计

航班信息查询与检索系统

printf(“此航班的航班号，起点

ted，{ 终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].lv.hour<=hour)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s

L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

}

void search(Sqlist L){

int i;do {

printf(“* * * * * * * * * * * }

} printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane

} void search_rh(Sqlist L){

int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price);

* * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

printf(“* 1.航班号查询

2.起点终点查询

3.班期查询 4.起飞时间查询

5.到达时间查询

0.退出

*n”);

printf(“* * * * * * * * * *

* * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

scanf(“%d”,&i);

switch(i)

{

case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){

1:search_key(L);break;

2数据结构课程设计

航班信息查询与检索系统

n“);

} else { } printf(”查找不成功。

i--;if(i==0)

{

char c[20];

printf(“输入修改后的scanf(”%s“,c);

内容：”);

strcpy(L.plane[i].sche,c);

printf(“修改成功！n”);}break;{

int a,b;

printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1:

printf(”修改成功！n“);printf(”修改成功！n“);{

char a[10];printf(”输入修改后的scanf(“%s”,a);

case 4:

内容：“);

char b[20];printf(”请输入修改后scanf(“%s”,b);

scanf(“%d:%d”,&a,&b);

L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“);

}break;{

int a,b;

printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{

case 5: case 2:

内容：“);

scanf(”%d:%d“,&a,&b);

L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break;

}break;{

int a;

case 6: case 3:

4数据结构课程设计

航班信息查询与检索系统

*n“);

printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“);

printf(”请输入选项n“);

scanf(”%d“,&ch);

switch(ch)

{

case 1:SaveList(L);break;case 2:ReadList(L);break;

L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane

[i].rh.hour,&L.plane[i].rh.min,&L.pl

}

void delet_Sq1(Sqlist &L){

char n[10];int i,j;

printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){

printf(“没有选项！n”);for(i=0;i

L.length++;

ane[i].price);

case 0:printf(“退出！n”);break;

}

void Initlist(Sqlist &L)//插入存储 {

“);

容：”);价n“);

scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i

班期

起飞时间

到达时间

票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内

int i,n;printf(“输入表中航班的数量：

} }while(ch!=0);

班号：”);

if(strcmp(L.plane[i].key,n)==0)

{

printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”);

printf(“n航班号

起点终点

printf(”%s %s %s %d:%d %d:%

d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

6数据结构课程设计

航班信息查询与检索系统

n”);} printf(“无法打开文件！}

}while(opt!=0);

void insert_Sq(Sqlist &L){ 数量

价n”);

for(i=0;i

printf(“* * * * * * * * * * *

scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[

{

int a=get_Sq(L);

printf(”请输入要添加班机的scanf(“%d”,&n);

printf(“请输入要添加的班机printf(”n航班号

起点终点

int i,n;

//n表示添加的fprintf(fp,“航班号：%sn起点站：%s

终点站：%sn班期：%dn起飞时间：%d:%d

到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi

n“);} void delet_Sq(Sqlist &L){

int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price);

数量：“);

信息：n”);

班期

起飞时间

到达时间

票* * * * * * * * * *n“);

printf(”* 1.航班号删除

printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除

0.退出

*n”);* * * * * * * * * * *n“);

scanf(”%d“,&opt);

switch(opt){

case 1:delet_Sq1(L);break;

case 2:delet_Sq2(L);break;

case 0:printf(”退出。}

L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan

e[L.length].rh.min,&L.plane[L.length].price);

}

void handle(Sqlist &L){

}

L.length++;

n");break;

第三篇：数据结构课程设计报告

《数据结构》课程设计

哈希表实现电话号码查询系统一目的

利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

二需求分析

1、程序的功能

1)读取数据

① 读取原电话本存储的电话信息。

② 读取系统随机新建电话本存储的电话信息。2)查找信息

① 根据电话号码查询用户信息。② 根据姓名查询用户信息。3)存储信息

查询无记录的结果存入记录文档。

2、输出形式

1)数据文件“old.txt”存放原始电话号码数据。

2)数据文件“new.txt”存放有系统随机生成的电话号码文件。3)数据文件“out.txt”存放未查找到的电话信息。4)查找到相关信息时显示姓名、地址、电话号码。

3、初步测试计划

1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中。

2)分别采用伪随机探测再散列法和再哈希法解决冲突。3)根据姓名查找时显示给定姓名用户的记录。4)根据电话号码查找时显示给定电话号码的用户记录。

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 1

《数据结构》课程设计

5)将没有查找的结果保存到结果文件Out.txt中。

6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。

三概要设计

1、子函数功能

int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突

void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表

int Collision_Rehash(int key,string str)//再哈希法处理冲突

void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表 void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 void Outhash(int key)//输出哈希表中的记录 void Rafile()//随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表

int Search_by_name(string name)//根据姓名查找哈希表中的记录 int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 2

《数据结构》课程设计

2、函数调用图

main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 3

《数据结构》课程设计

四详细设计

1、主函数流程图

开始选择数据来源21建“new.txt”选择查找方式12姓名查找电话号码查找12021输入姓名显示哈希表0显示哈希表输入电话号码无此记录显示信息无此记录显示信息0写入“out.txt”写入“out.txt”结束

2、“伪随机探测再散列处理冲突”伪代码

若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%哈希表长。若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到合适的位置。

3、“再哈希法处理冲突”伪代码

用“折叠法”将电话号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。

再用“除留余数法”求的新的关键字=原关键字%哈希表长。

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

4、“以姓名为关键字建立哈希表”伪代码

用“除留余数法”将姓名的ASCII码值定义为关键字。

若对应位置上存在其他数据，则调用伪随机处理冲突，然后将数据存入哈希表。

5、“以电话号码为关键字建立哈希表”伪代码

用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。

五调试分析

1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常打开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。

2、创建“new.txt”内容用子函数来实现，但是原数据是从“old.txt”文件中读取的，刚开始不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。

3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解

六测试结果

1、根据姓名查找

1)姓名查找成功

2)姓名查找失败

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 5

《数据结构》课程设计

3)哈希表

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 6

《数据结构》课程设计

2、根据电话号码查找

1)电话号码输入错误

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 7

《数据结构》课程设计

2)电话号码查询成功

3)电话号码查询失败

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 8

《数据结构》课程设计

4)哈希表

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 9

《数据结构》课程设计

七用户使用说明

1、选择数据来源

根据提示信息进行操作，选择已存在的“old.txt”文件中的数据或系统当前自动生成的“new.txt”文件。

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 10

《数据结构》课程设计

2、选择查找方式

根据提示信息进行操作，选择“根据姓名查找”或“根据电话号码查找”两种查找方式。

3、选择功能

根据提示信息进行操作，选择输入已知信息或查看哈希表。

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 11

《数据结构》课程设计

4、显示结果

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 13

《数据结构》课程设计

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 14

《数据结构》课程设计

5、查看文件

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 15

《数据结构》课程设计

八课程设计总结

1、收获

学会了C++的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创建和熟练运用。

2、心得体会

在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 16

《数据结构》课程设计

学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

附录：源程序

#include #include #include

using namespace std;

ifstream in_file;ofstream out_file;

int D[10]={1,3,5,8,13,15,17,21,27,34};//伪随机数序列 int count;//当前数据元素个数 int sizeindex;//哈希表的长度 char *sign;//冲突的标志

struct Data { string name;string phone;string address;};Data *intermediate_data;

int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突{ int Re_key;if(sign[key]=='1'){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 18

《数据结构》课程设计

} Re_key=(key+D[i])%sizeindex;return Re_key;//归回新的要害码

return-1;}

void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表

{ int i=0;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){

} if(key==-1)exit(1);key=Collision_Random(key,i+1);count++;intermediate_data[key].name=name;//将数据存入哈希表

intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//设置冲突标志 }

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 19

《数据结构》课程设计

int Collision_Rehash(int key,string str)//再哈希法处理冲突 { int Re_key;int num1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');int num2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0');int num3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;}

void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表

{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){

} count++;intermediate_data[key].name=name;intermediate_data[key].address=address;intermediate_data[key].phone=phone;key=Collision_Rehash(key,phone);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 20

《数据结构》课程设计

sign[key]='1';}

void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中

{ if((key==-1)||(sign[key]=='0')){

out_file.open(“out.txt”);

if(out_file.fail())

{

cout<<“n”<<“文件打开失败！!n”<

exit(1);

}

out_file<

out_file.close();} }

void Outhash(int key)//输出哈希表中的记录 { unsigned i;if((key==-1)||(sign[key]=='0')){

cout<<“n”<<“无此记录！!n”<

} else xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 21

《数据结构》课程设计

{

for(i=0;i

cout<

for(i=0;i<8;i++)

cout<<“ ”;

cout<

for(i=0;i<8;i++)

cout<<“ ”;

cout<

void Rafile()//随机生成数据，并将数据保存在new.txt { int i,j;out_file.open(“new.txt”);if(out_file.fail()){

cout<<“n”<<“文件打开失败！!n”<

exit(1);} for(j=0;j<30;j++){

string name=“";

for(i=0;i<20;i++)

name+=rand()%26+'a';out_file<

《数据结构》课程设计

string phone=”“;

for(i=0;i<11;i++)

phone+=rand()%10+'0';

out_file<

string address=”“;

for(i=0;i<29;i++)

address+=rand()%26+'a';

address+=',';

out_file<

void Init_HashTable(char*fname,int n)//建立哈希表{ string name=”“;string phone=”“;string address=”“;int i,j;in_file.open(fname);if(in_file.fail()){

cout<<”n“<<”文件打开失败！!n“<

exit(1);} while(!in_file.eof()){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 23

《数据结构》课程设计

字

键字

} char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行读入数据 if(str[0]=='*')//判断数据结束

i=0;while(str[i]<=97||str[i]>=122)i++;break;for(;str[i]!=' ';i++)name+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=' ';j++,i++)phone+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=',';j++,i++)address+=str[i];if(n==1)Init_HashTable_by_name(name,phone,address);//以姓名为关键else Init_HashTable_by_phone(name,phone,address);//以电话号码为关delete str;in_file.close();}

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

int Search_by_name(string name)//根据姓名查找哈希表中的记录 { int i=0;int j=1;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'&&(intermediate_data[key].name!=name)){

key=Collision_Random(key,i+1);

j++;

if(j=count)

return-1;} return key;}

int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 25

《数据结构》课程设计

while(sign[key]=='1'&&(intermediate_data[key].phone!=phone)){

key=Collision_Rehash(key,phone);

j++;

if(j=count)

return-1;} return key;}

void main(){ count=0;sizeindex=50;int i,k;int ch;char *Fname;

sign=new char[sizeindex];

intermediate_data=new Data[sizeindex];

for(i=0;i

for(i=0;i

《数据结构》课程设计

{

}

cout<<”§**********************************************************§“<

*§”<

*§“<

*§”<

*§“<

*§”<

*§“<

cout<<”§**********************************************************§“<

do {

switch(k)cout<<”n“<< ” 请输入选择 : n“;cin>>k;cout<<”§* 0.退 出 程 序 cout<<“§* 2.随 机 生 成 cout<<”§* 1.old.TXT cout<<“§* cout<<”§* 请选择用于查找的数据来源 cout<<“§* intermediate_data[i].name=”“;intermediate_data[i].phone=”“;intermediate_data[i].address=”“;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 27

《数据结构》课程设计

{

case 0:

return;case 1:

Fname=”old.txt“;break;case 2:

Rafile();Fname=”new.txt“;break;default:

} while((k!=1)&&(k!=2)&&(k!=0));

//system(”cls“);

cout<<”§**********************************************************§“<

*§”<

*§“<

*§”<

*§“<

*§”<

cout<<”输入序号有误，请重新输入！!n“<

《数据结构》课程设计

*§”<

cout<<”§**********************************************************§“<

//system(”cls“);

endl;

*§”<

}

while((ch!=1)&&(ch!=2));cout<<”n“<< ” 请输入选择 : n“;cin>>ch;if(ch!=1&&ch!=2){ }

cout<<” 输入序号有误，请重新输入！!n“<

《数据结构》课程设计

*§”<

cout<<”§* *§“<

*§”<

*§“<

*§”<

*§“<

cout<<”§**********************************************************§“<

do {

cout<<”n“<< ” 请输入选择 : n“;

cin>>choice;cout<<”§* cout<<“§* 0.退 出 程 序！!cout<<”§* 2.显 示 哈 希 表 cout<<“§* 1.输 入 姓 名 查 找 数 据

switch(choice){

case 1: {

int key1;string name;

cout<<”n“<<” 请输入姓名: n“;

cin>>name;

key1=Search_by_name(name);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 30

《数据结构》课程设计

Outfile(name,key1);cout<<”n“<<”查找结果:n“<

Outhash(key1);

}

break;

case 2:

{ cout<<”n“<<” 哈希表: n“<

for(i=0;i

{

if(sign[i]!='0')

{

cout<<”* “;

Outhash(i);

}

}

cout<<”* *“<

}

break;

case 0:

return;default: xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 31

《数据结构》课程设计

cout<<” 输入序号有误，请重新输入！!n“<

endl;

*§”<

*§“<

*§”<

*§“<

*§”<

*§“<

cout<<”§**********************************************************§“<

cout<<”n“<< ” 请输入选择 : n“;

} } } while((choice!=1)&&(choice!=2)&&(choice!=0));

while(ch==2){ int choice;

cout<<”§**********************************************************§“<

cout<<”§* 1.输 入 电 话 查 找 数 据

cout<<“§* 2.显 示 哈 希 表

cout<<”§* 0.退 出

cout<<Ҥ*

do { xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

cin>>choice;

switch(choice)

{

case 1:

{

int key2;

string phone;do

{

cout<<”* 请输入11位的电话号码: “;

cin>>phone;

if(strlen(&phone[0])!=11)

{

cout<<”n“<<”电话号码输入不正确!请重新输入！!n“<

key2=Search_by_phone(phone);Outfile(phone,key2);

}

while(strlen(&phone[0])!=11);cout<<”n“<<”查找结果:n“<

cout<<”* “;

xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6

《数据结构》课程设计

Outhash(key2);

}

break;

case 2:

{ cout<<”n“<<”哈希表:n“<

for(i=0;i

{

if(sign[i]!='0')

{

cout<<”* “;

Outhash(i);

}

}

cout<<”* *“<

}

break;

case 0:

return;

default:

cout<<” 输入序号有误，请重新输入！!n"<

《数据结构》课程设计

}

while((choice!=1)&&(choice!=2)&&(choice!=0));

}

} xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 35

第四篇：数据结构课程设计报告

《数据结构》 课程设计报告

目录

《数据结构》...................................................................................................................................1 课程设计报告...................................................................................................................................1 目录..................................................................................................................................................2 课题一：表达式求值.......................................................................................................................3 一：算数表达式后缀版...........................................................................................................3

1、问题描述：.................................................................................................................3

2、设计思路：.................................................................................................................3

3、程序代码：.................................................................................................................3

4、运行与测试.................................................................................................................6

5、设计心得：.................................................................................................................6 二：算术表达式中缀版...........................................................................................................7

1、问题描述：.................................................................................................................7

2、设计思路：.................................................................................................................7

3、代码：.........................................................................................................................7

4、调试及测试...............................................................................................................13

5、设计心得：...............................................................................................................13 课题四：迷宫求解.........................................................................................................................14 一：问题描述：.............................................................................................................14 二：设计思路：.............................................................................................................14 三：功能函数设计.........................................................................................................14 四：代码.........................................................................................................................14 五：测试及调试.............................................................................................................21 六：设计心得.................................................................................................................23

课题一：表达式求值

一：算数表达式后缀版

1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

2、设计思路：在C++环境下，用字符数组A，保存算数式，一“#”表示结束。用栈对数字和运算符号进行操作。当扫描A不是‘#’时，判断数组成员是数字还是字符，若数字，则将数字的ASCII码入栈，若不是，则弹出两个数字，并根据字符进行相应的运算，并将结果入栈保存，以便下一次的运算操作。

3、程序代码：

#include using namespace std;class stack { private: int *base;int *top;public: int size;int empty_stack();int push_stack(int e);int pop_stack(int &e);int get_stack(int &e);stack(int Size=100){

base=new int[Size];

top=base;

size=Size;};~stack(){

delete[] base;

base=NULL;

top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(int e){ if(top-base

*top=e;

top++;

return 1;} else

return 0;} int stack::pop_stack(int &e){ if(top>base){

top--;

e=*top;

return 1;} else

return 0;} int stack::get_stack(int &e){ if(top>base){

e=*(top-1);

return 1;} else

return 0;} int match(char A[]){ stack s;int i=0,x,y,z;while(A[i]!='#'){

while(A[i]>'0'&&A[i]<='9')//char型 A[],其中0~9存储的是48~57！！!

{

s.push_stack(A[i]-'0');//存储 数字0~9 char-char

i++;

}

if(A[i]<'0'||A[i]>'9')

{

s.pop_stack(x);

s.pop_stack(y);

switch(A[i])

{

case '+':s.push_stack(x+y);break;//switch,case 'ch'的用法

case '-':s.push_stack(x-y);break;

case '*':s.push_stack(x*y);break;

case '/':s.push_stack(x/y);break;

}

}

i++;} s.pop_stack(z);printf(“%dn”,z);return z;} int main(){ char A[100];int m;scanf(“%s”,A);m=match(A);printf(“%dn”,m);return 0;}

4、运行与测试

5、设计心得：考察栈的应用，在c++环境下栈的构建与操作，在输入数组A时（用于存放数组），注意当数组元素是数字时，将A[i]-’0’，（ASCII码）作为栈相应函数的参数。后缀表达式还是相应比较简单的。

二：算术表达式中缀版

1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

2、设计思路：在C++环境下，在后缀表达式的基础上，增加将中缀转换为后缀存储的算法。自左向右扫描表达式，当扫描到的是操作数时直接输出，扫描到运算符时不能马上输出，因为后面可能还有更高的运算；若运算符栈栈顶字符比这个字符低，则入栈，继续向后处理；若高，则从运算符栈出栈一个运算符输出，继续处理当前字符；若相等，则为括号，从栈中出栈，继续向后处理，直到遇到字符’#‘，求值结束。例如：“1+2*（8-5）-4/2#”。

3、代码：

#include using namespace std;#include class stack { private: int *base;int *top;public: int size;int empty_stack();int push_stack(char e);int pop_stack(char &e);int get_stack(char &e);stack(int Size=100){

base=new int[Size];

top=base;

size=Size;};~stack(){

delete[] base;

base=NULL;

top=NULL;};};int stack::empty_stack(){ return((top==base));} int stack::push_stack(char e){ if(top-base

*top=e;

top++;

return 1;} else

return 0;} int stack::pop_stack(char &e){ if(top>base){

top--;

e=*top;

return 1;} else

return 0;} int stack::get_stack(char &e){ if(top>base){

e=*(top-1);

return 1;} else

return 0;} class temp { private: int *base;int *top;public: int size;int empty_temp();int push_temp(int e);int pop_temp(int &e);int get_temp(int &e);temp(int Size=100){

base=new int[Size];

top=base;

size=Size;};~temp(){

delete[] base;

base=NULL;

top=NULL;

};};int temp::empty_temp(){ return((top==base));} int temp::push_temp(int e){ if(top-base

*top=e;

top++;

return 1;} else

return 0;} int temp::pop_temp(int &e){ if(top>base){

top--;

e=*top;

return 1;} else

return 0;} int temp::get_temp(int &e){ if(top>base){

e=*(top-1);

return 1;} else

return 0;} char fhcg(char a,char b)//#不能传进a { int i,j;char h;char CH[7]={'+','-','*','/','(',')','#'};char R[7][7]={{'>','>','<','<','<','>','>'}，{'>','>','<','<','<','>','>'}，{'>','>','>','>','<','>','>'}，{'>','>','>','>','<','>','>'}，{'<','<','<','<','<','=','/'}，{'>','>','>','>','/','>','>'}，{'<','<','<','<','<','/','='}};for(i=0;i<7;i++){

if(CH[i]==a)

break;} for(j=0;j<7;j++){

if(CH[j]==b)

break;} h=R[i][j];return(h);} int matchcg(char A[],char B[])// { stack s;char h,x,y;int i,j;i=0;j=0;s.push_stack('#');//#没传入 // s.get_stack(y);//cout<<“栈顶”<

while(!s.empty_stack())//最后的-4/2有问题，/没进入B[j] {

if(A[i]>'0'&&A[i]<='9')

{

B[j]=A[i];

j++;

i++;

}

else//(A[i]<'0'||A[i]>'9')

{

s.get_stack(y);

// s.pop_stack(x);//

h=fhcg(y,A[i]);//

switch(h)

{

case '>':

{

s.pop_stack(x);

B[j++]=x;//x没有下移，还是‘-’只有这一步把数据压入B，j++

break;///////////

}

case '<':s.push_stack(A[i]);i++;break;

case '=':s.pop_stack(x);i++;break;

default:

return 0;

}

} } B[j]='#';//B[]由j控制进程

B[++j]='';// printf(“%sn”,B);return 1;} int matchfn(char A[]){ temp s;int i=0;int n,x,y,z;n=strlen(A);//printf(“n=%dn”,n);// printf(“%sn”,A);while(A[i]!='#')//！！！！!{

if(A[i]>'0'&&A[i]<='9')//char型 A[],其中0~9存储的是48~57！！!

{

s.push_temp(A[i]-'0');//存储 数字0~9 char-char

i++;

}

else//(A[i]<'0'||A[i]>'9')

{

s.pop_temp(x);

s.pop_temp(y);

switch(A[i])

{

case '+':s.push_temp(y+x);break;//switch,case 'ch'的用法

case '-':s.push_temp(y-x);break;

case '*':s.push_temp(x*y);break;

case '/':s.push_temp(y/x);break;

}

i++;

}

} s.pop_temp(z);return z;} int main(){ //char A[100]={“1+2*(8-5)-4/2#”};char A[100];printf(“A[]=以#结束:”);scanf(“%s”,A);

} char B[100];int m,n,i=0;m=matchcg(A,B);m=matchfn(B);printf(“%s”,A);printf(“=%dn”,m);return 0;

4、调试及测试

5、设计心得：

中缀算法是在后缀的基础上，增加了处理，是的中缀在栈的存储中为后缀，然后只用后缀的算法运算。最容易忽略的是字符数组处理是的’‘问题，所以加上了B[j]='#';B[++j]='';在int matchcg(char A[],char B[])函数后。课题四：迷宫求解

一：问题描述：设二维数组maze[m][n]为’0‘，表示此路可通,为’1‘表示此路不通.入口是maze[1][1]出口为maze[m][n]且maze[1][1]=0, maze[m][n]=0.编写寻找从入口到出口的一条路径的程序。必须沿4个方向搜索.二：设计思路：回溯法，从入口出发，按某一方向探索，若能走通并未走过（maze[i][j]==0），即该处可以到达，并标记为已走过（maze[i][j]=-1），并入栈保存前一步到达的位置，否则探索下一个方向（d++）；若所有的方向均没有通路，则按原路返回前一步到达的位置，换下一个方向继续探索，直到找到一条同路。

三：功能函数设计

typedef struct _Befor//前一点的坐标方向 typedef struct//链栈

void play(Befor temp)//temp void play(Befor temp)//temp用于实现在DOS下的界面显示

typedef struct MOVE和typedef struct _Path//用于计算四个方向的位移量

int Export(int(*maze)[10],int x0,int y0,int m,int n,PStack s)//用于探索迷宫寻找出路

四：代码

//用c表示栈

//改进，加入动态演示（子弹打飞机）

//最重大的错误，ij的位置反了，i是行，对应的是y坐标；j是列，对应的是x坐标。#include #include #include #include #include #include #include #include #include const int True = 1;const int False = 0;#define MAX 15//限定了栈的容量 //system(“cls”);#define Up

0x48 #define Down 0x50 #define Left 0x4b #define Right 0x4d #define Esc

0x1b void gotoxy(int x, int y)//光标移到（x,y）friend函数（COORD,HANDLE）屏幕宽80、高25 {

COORD point;// 创建光标位置坐标。COORD类（x,y）

HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);// 控制台屏幕缓冲区的把手。HANDLE类

point.X = x;point.Y = y;

SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),point);//设置控制台光标位置 }

void clear(int left,int top,int width,int higth)//！！!{

//函数消除轨迹

gotoxy(left,top);for(int i=0;i<=width;i++)

for(int j=0;j<=higth;j++)

{

gotoxy(left+i,top+j);

cout<<“ ”<

} } void sound(DWORD freq)//按freq HZ频率发声（50ms）{ Beep(freq,50);} void delay(DWORD dur)//延时dur毫秒 {

Sleep(dur);} //////正文

typedef struct _Befor { int x,y,d;}Befor;//前一点的坐标方向 typedef struct//链栈 { int top;Befor Node[100];//结构体每一个都是Befor型 }Stack,*PStack;//初始化栈 PStack Inite_Stack(){ PStack s;s=(PStack)malloc(sizeof(Stack));if(s){

s->top=-1;} return s;} int empty_Stack(PStack s){ return(s->top==-1);//s.top==0即为空 } int push_Stack(PStack s,Befor temp){ if(s->top==MAX-1)//限定了栈的容量

return 0;else {

s->top++;

s->Node[s->top]=temp;

return 1;} } int pop_Stack(PStack s,Befor &temp){ if(empty_Stack(s))

return 0;else {

temp=s->Node[s->top];

s->top--;

return 1;} } int get_Stack(PStack s,Befor &temp){ if(empty_Stack(s))return 0;else {

temp=s->Node[s->top];

return 1;} } void play(Befor temp)//temp { delay(500);clear(20+temp.y+temp.y*3,5+temp.x+temp.x*3,1,1);gotoxy(20+temp.y+temp.y*3,5+temp.x+temp.x*3);printf(“$”);} ////////////////////////////////////////栈完成

//迷宫点的设计，保存的坐标，保存前一点的坐标（方向），此点的四个方向坐标 //加入难度，也就是迷宫复杂化，1出现在中间区域。/*typedef struct _Befor { int x,y,d;}Befor;//前一点的坐标方向*/ typedef struct MOVE { int dx,dy;}move;typedef struct _Path {

move x,y;}Path;int Export(int(*maze)[10],int x0,int y0,int m,int n,PStack s)//二维数组做实参形参 {//(x0,y0)起始点,(m,n)将要到达的点

Befor temp;int i,j,x,y,d;struct MOVE move[4];move[0].dx=-1;//位置错误。向上i-1;向左j+1;向下i+1;向左j-1;！！！！！！！move[0].dy=0;move[1].dx=0;move[1].dy=1;move[2].dx=1;move[2].dy=0;move[3].dx=0;move[3].dy=-1;//栈初始化temp(x,y,d),入栈

temp.x=x0;temp.y=y0;temp.d=-1;push_Stack(s,temp);while(!empty_Stack(s)){

pop_Stack(s,temp);//出栈，存储为之前的点 x=temp.x;y=temp.y;d=temp.d+1;while(d<4)//四个方向转换 {

i=x+move[d].dx;//一直是1 j=y+move[d].dy;//当前点坐标y值不对，一直增长

if(maze[i][j]==0)//当前的可走 改变了，maze[i][j]没变

{

temp.x=x;

temp.y=y;

temp.d=d;

push_Stack(s,temp);//入栈保存

//加入动态（temp）

play(temp);//

x=i;

y=j;

maze[x][y]=-1;//记录当前点已走过

if(x==m&&j==n)//已走出则输出路径

{

temp.x=x;

temp.y=y;

temp.d=d;

push_Stack(s,temp);//入栈保存最后一个点，出口点/////////////////////

//加入动态（temp）

play(temp);/////////////

gotoxy(0,2);

while(!empty_Stack(s))

{

pop_Stack(s,temp);/////////////////////////

printf(“(%d,%d,%d)t”,temp.x,temp.y,temp.d);//没有改变！！!正确

}

for(i=x0;i<=m;i++)//复位迷宫

for(j=y0;j<=n;j++)

{

if(maze[i][j]==-1)

maze[i][j]=0;

}

return 1;//已成功

}

else

d=0;

}

else

d++;

} } //空栈后，恢复迷宫

for(i=x0;i<=m;i++)//复位迷宫

for(j=y0;j<=n;j++)

{

if(maze[i][j]==-1)

maze[i][j]=0;

}

retu