数据结构实验二 求解约瑟夫问题

第一篇：数据结构实验二 求解约瑟夫问题

数据结构实验二

求解约瑟夫问题

问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。

问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法：

void Josephus(int n, int m,int s)

{ //生成表头节点，空单循环链表

LNode * HL = new LNode;

HL-> next = HL;

int i;//生成含有 n 个节点的、节点值依次为1，2……，n的带表头节点的循环单链表

For(i = n;i>=1;i--)

{ LNode * newptr = new LNode;

Newptr-> data = i;

newptr-> next = HL-> next;

HL-> next = newptr;}

//从表头开始顺序查找出第s个节点，对应第一个开始报数的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i

ap = cp;

cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1个人出列 for(i=1;i

//顺序查找出待出列的人，即为循环结束后cp所指向的节点

for(int j=1;jnext;if(cp ==HL){ ap = HL;cp = HL->next;} } //输出cp节点的值，即出列的人

cout << cp->data <<”

“;//从单链表中删除cp节点

ap-> next = cp-> next;delete cp;//使cp指向被删除节点的后续节点

cp = ap-> next;//若cp指向了表头节点，则后移ap和cp指针 if(cp = = HL){ ap = HL;cp = HL-> next;} }

//使最后一人出列

count << HL->next-> data << end1;

//删除表头节点和表头附加节点

delete HL->next;

delete HL;}

补充操作系统练习：

1、有一个虚拟存储系统, 每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1

试给出下列情形下的缺页次数:

(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢?

2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：

最大需求量

已分配资源量

剩余资源量

A

B

C

A

B

C

A

B

C

P1 8

P2 4

P3 10 1

P4 3

P5 5(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？

3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号

进入时刻

估计运行时间

优先级

JOB1

8：00

90分钟

JOB2

8：10

30分钟

JOB3

8：30

20分钟

JOB4

8：50

15分钟

JOB5

9：20

10分钟

JOB6

9：40

5分钟系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）

（2）试计算出作业的平均周转时间.

第二篇：数据结构报告--约瑟夫环范文

实习报告

题目:约瑟夫环

班级：08052712学号: 08052211姓名: 葛俊峰

一、需求分析

1.本演示程序中，编号为1，2，„，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，如此下去，直到所有人全部出列为止。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即总人数，m的值，每个人所持的密码），运算结果显示在其后。

3.程序执行的命令包括：

（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。

4.测试数据：

m的初始值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。

二、概要设计

为了实现上述操作，应以单向循环链表为存储结构。为此，需要1个抽象数据类型：线性表。

1.线性表的抽象数据类型为：

ADT List{

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

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

基本操作：

InitList(&L)

操作结果：构造一个空的线性表L。

}ADT List

2.本程序包括三个模块:

1）主程序模块：

void main（）{

初始化；

输入数据；

函数调用；

}

2）构造链表并输入每个人信息的模块-----实现线性表的抽象数据类型；

3）运行模块-----模拟约瑟夫环依次出列；

各模块之间调用关系如下：

主程序模块

↓

构造链表并输入每个人信息的模块

↓

运行模块

三、详细设计

1.结点类型和指针类型

typedef struct Node{

int num;

int password;

struct Node *next;

}LNode,*LinkList;//结点类型,指针类型

Status MakeNode（LinkList &p，Elem Type e）

{

//分配由p指向的数据元素为e、后继为“空”的特点，并返回TRUE，//若分配失败，则返回FALSE

P=(LinkType)malloc（sizeof（NodeType））；

If（！p）return FALSE；

p->data=e；p->next=null；return TRUE；

}

viod Free Node（Link Type &p）

{

//释放p所指结点

}

2.主函数和其他函数

int main()

{

//主函数

LinkList L = NULL;

LinkList s ,r;

int n,i,j,m;//初始化

printf(“请输入人数nn”);

scanf(“%d”,&n);

printf(“请输入mn”);

scanf(“%d”,&m);

printf(“请依次输入每个人的密码n”);//输入数据

CreatList(L,s,r,n);//创建链表run(L,n,m);//模拟约瑟夫环并输出

return 0;

}//main

void CreatList(LinkList &L,LinkList &s,LinkList &r,int n)

{

//创建链表

int i=1;

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(“%d”,&s->password);//输入密码

s->num = i;//序号为i

if(L==NULL)

L=s;

else

r->next=s;

r=s;//为下次连接做准备

for(i=2;i<=n;i++)

{

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(“%d”,&s->password);

s->num = i;

r->next=s;//连接到下个结点

r=s;//为下次连接做准备

}

r->next = L;//闭合L = r;

} // void CreatList

void run(LinkList &L,int n,int m)

{

//模拟约瑟夫环并输出

LinkList s,r;

int i,j;

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

{

for(j = 1;j < m;j ++)

L = L->next;//报数

s = L->next;

r = s->next;

printf(“%dn”,s->num);//输出序号

m = s->password;

L->next = r;

free(s);//删除结点

}

}//run

3.函数的调用关系图反映了演示程序的层次结构:

main

↓↓

CreatListrun

↓↓

Make NodeFree Node

四、调试分析

1.刚开始由于使用头结点,使得程序不符合要求。

2.在写程序时忽略了一些变量参数的标识“&”,使调试程序费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。

3.本程序模块划分比较简单且容易看懂，但头指针赋空不太合理。

4.本实习作业采用数据抽象的设计方法，将程序划分为3个层次，使得设计时思路清晰，实现调试顺利

五、用户手册

1.本程序运行环境为DOS操作系统，执行文件为约瑟夫环.exe。

2． 进入演示程序后出现提示信息：

“请输入人数n”

输入后，出现提示信息：

“请输入m”

输入后，出现提示信息：

“请依次输入每个人的密码”

输入后，显示相应的结果。

第三篇：数据结构课程设计 背包问题的求解

2009届 电子信息科学与技术专业 数据结构课程设计

背包问题的求解

摘要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词 背包问题；

递归算法；

1问题描述

1.1问题描述

背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

1.2基本思想

（1）分别输入n件物品的重量和价值。（2）采用递归寻找物品的方案。

（3）输出最佳的装填方案，包括选中的是哪几种物品，总价值为多少。

2问题分析

背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中递归方法是比较简化程序，也比较难理解的一个。

设n件物品的重量分别为w0,w1,„,wn-1,物品的价值分别为v0,v1,„,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组option[],设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop[]，嘉定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，急需考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。2009届 电子信息科学与技术专业 数据结构课程设计 对于第i件物品的选择有两种可能：

（1）物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择；

（2）物品i不被选择，这种可能性仅当不包物品i也有可能会找大价值更大的方案的情况。

就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。

采用option[]和cop[]两个数组，来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。

3数据结构描述

背包问题结构体：

struct{

int weight;

int value;

}a[N];4算法设计

4.1程序流程图

2009届 电子信息科学与技术专业 数据结构课程设计

图4-1 程序流程图

4.2算法设计

根据问题分析中的思想写出递归算法如下：

find（物品当前选择已达到的重量和tw,本方案可能达到的总价值为tv）｛

/*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）｛

将物品i包含在当前方案中；

if(i

以当前方案作为临时最佳方案保存；

恢复物品i不包含状态；

｝ 2009届 电子信息科学与技术专业 数据结构课程设计

/*考虑物品i不包含在当前方案中的可能性*/ if（不包含物品i仅是可考虑的）

if(i

以当前方案作为临时最佳方案保存；

｝

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

/*物品i包含在当前方案的可能性*/ { cop[i]=1;if(imaxv)

/*物品i不包含在当前方案的可能性*/ if(i

opion[k]=cop[k];maxv=tv-a[i].value;} } 5详细程序清单

详细程序清单见附录。

6程序运行结果

背包问题求解界面如图6-1所示。

图6-1 背包问题求解界面

程序调试成功。

在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。

7心得体会

通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。

2009届 电子信息科学与技术专业 数据结构课程设计

在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个思想。

参考文献

[1] 徐孝凯.数据结构课程实验.北京：清华大学出版社，2002:100-132 [2] 张乃笑.数据结构与算法.北京：电子工业出版，2000:3-5 [3] 严蔚敏.数据结构（C语言版）.北京： 清华大学出版社，2002:100-132 [4] 李春葆.数据结构（C语言篇）习题与解析（修订版）.北京：清华大学出版，2000:45-66

Knapsack problem solving

Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009届 电子信息科学与技术专业 数据结构课程设计

附录：详细程序清单

#include #define N 100 int limitw，/*限制的总重量*/ totv，/*全部物品的总价*/ maxv;

/*可实现最大总价值*/ int opion[N]，cop[N];

struct{

int weight;

int value;

}a[N];int n;

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

{ cop[i]=1;if(i

/*方案的选择*/ /*当前方案的选择*/ /*背包问题结构体*/

/*物品种数*/ /*物品i包含在当前方案的可能性*/ 7

2009届 电子信息科学与技术专业 数据结构课程设计

if(tv-a[i].value>maxv)

/*物品i不包含在当前方案的可能性*/ if(i

第%d种物品（重量，价值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的总重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k

printf(“最佳装填方案是：n”);for(k=0;k

第四篇：数据结构实验二报告

数据结构实验二报告

——简单计算器

姓名：王稀宾 班 级：06111106 学号：1120111699 一实验目的

按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

二实验内容

要求：

从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。

三程序设计

程序模块：

1输入模块，输入多项式；

2计算模块，根据输入内容，判断分析，计算出结果； 3输出模块，输出计算结果。

定义结构创建结点： typedef struct { double data[50];int top;}OPND_Stack;//运算符结构体 typedef struct { char data[50];int top;}OPTR_Stack;主函数部分： void main(){ char a[80];int m;char b[80];printf(“============简易计算器============n”);printf(“[四则运算.如:-1+(2+3)*9/(-2)-6].n请输入一个表达式:n”);while(1){

gets(a);

strcpy(b,a);

while(1)

{

int p;

m=strlen(a);

p=Can(a,m);

if(p==0)break;

printf(“输入错误.请从新输入表达式:n”);

gets(a);

strcpy(b,a);

}

printf(“=*=*=*=*=*=*表达式结果=*=*=*=*=*=*n”);

printf(“该表达式的结果为:n%s=%-10.3lfn”,b,EvaluateExpression(a));

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

printf(“继续使用[四则运算.如:-1+(2+3)*9/(-2)-6].<关闭退出>.n请再输入 一个表达式:n”);} }

四程序调试分析

1在四则混合运算中，运算符号的优先级比较难判断。2心得体会: 我对编程是有很浓厚兴趣的。在编程的过程中，我深深地体会到力不从心—有些知识没能深入地理解和掌握以及VC++的许多功能没能探索和了解使我编程时有好多的思想运用不上(如设计一个美观的操作界面)。另外，我也感受到了数据结构的重要性，有了结构才能将好的思想付诸实践。同时经过查询资料了解到栈由多种运用方法，其中包括栈的顺序存储结构和链式存储结构，栈是计算表达式的经典应用。数据结构中的许多结构都是很经典思想，只有把编程语言和数据结构都熟练掌握的情况下，才能做出一些很好的作品。在编程过程中，虽然有时候是很发闷的，尤其是程序无错但结果不对，但是在完成一个完整的程序时所带来的喜悦是其它事情所不能替代的。我很喜欢编程，即使我的知识和能力有限，但我相信经过努力，一切皆有可能。

五用户使用说明

按要求正确输入表达式即可得到结果。

六程序运行结果 附程序清单

#include #include #include //算符优先级表 char First[7][7]= { //'+','-','*','/','(',')','^' /*'+'*/ '>','>','<','<','<','>','<', /*'-'*/ '>','>','<','<','<','>','<', /*'*'*/ '>','>','>','>','<','>','<', /*'/'*/ '>','>','>','>','<','>','<', /*'('*/ '>','>','>','>','>','>',' >', /*')'*/ '<','<','<','<','< ','>','<', /*'^'*/ '>','>','>','>','<','> ','<' };//运算符数组

char OP[7]={'+','-','*','/','(',')','#'};//数据结构体 typedef struct { double data[50];int top;}OPND_Stack;//运算符结构体 typedef struct

{ char data[50];int top;}OPTR_Stack;//初始化运算符栈函数

void InitStack_R(OPTR_Stack *a){ a->top=-1;} //初始化数据站函数

void InitStack_D(OPND_Stack *a){ a->top=-1;} //运算符进栈函数

void Push_R(OPTR_Stack *a,char b){ a->top++;a->data[a->top]=b;} //数据进栈函数

void Push_D(OPND_Stack *a,double b){ a->top++;a->data[a->top]=b;} //取运算符栈顶符函数

void GetTop_R(OPTR_Stack *a,char *b){ *b=a->data[a->top];} //取数据栈顶数函数

void GetTop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];} //判断数据是否为运算符函数 int In(char a,char *s){ for(int i=0;i<7;i++)

if(a==s[i])

return 1;return 0;} //算符优先级判断函数

char Precede(char a,char b){ int m,n;for(int i=0;i<7;i++){

if(a==OP[i])

m=i;

if(b==OP[i])

n=i;} return First[m][n];} //删除运算符栈顶元素，并取新栈的栈顶元素 void Pop_R(OPTR_Stack *a,char *b){ a->top--;*b=a->data[a->top];} //取数据站的栈顶元素，并从栈中删除此元素 void Pop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];a->top--;} //算符优先算法求值核心函数

double EvaluateExpression(char *s){ OPND_Stack OPND;OPTR_Stack OPTR;char ch,theta;double x,a,b;int k=0;strcat(s,“#”);InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);GetTop_R(&OPTR,&ch);while(s[k]!='#'||ch!='#'){

if(In(s[k],OP)==0)

{

x=Getdouble(s,&k);

Push_D(&OPND,x);

}

else

{

switch(Precede(ch,s[k]))

{

case'<':Push_R(&OPTR,s[k]);

k++;

break;

case'=':Pop_R(&OPTR,&ch);

k++;

break;

case'>':GetTop_R(&OPTR,&theta);Pop_R(&OPTR,&ch);

Pop_D(&OPND,&b);Pop_D(&OPND,&a);

Push_D(&OPND,Operate(a,theta,b));

break;

}

}

GetTop_R(&OPTR,&ch);} GetTop_D(&OPND,&x);return x;InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);} //判断表达式是否输入正确.int Can(char a[],int n){ int p=0,s=0,t=0;for(int i=0;i

if(a[i]=='('||a[i]==')')

p++;

if((a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')&&((a[i+1]<'0'&&a[i+1]!='(')||a[i+1]>'9'))

s++;

if(a[i]=='/'&&a[i+1]=='0')

s++;

if((a[i]=='('&&(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'))||(a[i]==')'&&a[i+1]=='('))

s++;

if(a[i]==')'&&a[i+1]!=''&&(a[i+1]!='+'&&a[i+1]!='-'&&a[i+1]!='*'&&a[i+1]!='/'))

s++;

if(a[i]=='.'&&a[i+1]=='.')

s++;} if(p%2==0&&s==0)

return 0;return 1;} //主函数 void main(){ char a[80];int m;char b[80];printf(“============简易计算器============n”);printf(“[四则运算.如:-1+(2+3)*9/(-2)-6].n请输入一个表达式:n”);while(1){

gets(a);

strcpy(b,a);

while(1)

{

int p;

m=strlen(a);

p=Can(a,m);

if(p==0)break;

printf(“输入错误.请从新输入表达式:n”);

gets(a);

strcpy(b,a);

}

printf(“=*=*=*=*=*=*表达式结果=*=*=*=*=*=*n”);

printf(“该表达式的结果为:n%s=%-10.3lfn”,b,EvaluateExpression(a));

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

printf(“继续使用[四则运算.如:-1+(2+3)*9/(-2)-6].<关闭退出>.n请再输入一个表达式:n”);} }

第五篇：数据结构课程设计-迷宫求解范文

数据结构课程设计

迷宫求解

学院：湖北工业大学计算机学院

教师：沈华老师

班级：12网络工程1班

学号：1210322118

姓名：饶进阳

时间：2013年12月22日

目

录

问题描述

.........................................................思路解析

.........................................................程序流程

.........................................................核心代码

.........................................................源程序代码........................................................程序运行实例.....................................................课设总结

.........................................................3 4 5 6 12 14 迷宫求解

问题描述：

可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

要求：

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

比如这是一个迷宫

电脑找出的出路

思

路

设定当前位置的初值为入口位置： do｛

若当前位置可通，则｛

将当前位置插入栈顶；} 若该位置是出口位置，则结束；

否则切换当前位置的东邻块为新的当前位置； 否则｛

若栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；} 若{ 栈不空但栈顶位置的四周均不可通，则删去栈顶位置；} 若{ 栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝ ｝while(栈不空)｛栈空说明没有路径存在｝

PS：类似动态求解方法

程序流程

第一次用visio做程序框图，所以只把程序的大概流程画出来了。

核心代码

//栈相关操作 int initlStack(Stack *S)int pushStack(Stack S, coordinate e)int popStack(Stack S, coordinate *e)int getTop(Stack S, coordinate *e)void show(Stack S)

//创建一个迷宫 int creatMaze(Maze *m)

//打印出一个迷宫 void showMaze(Maze *m)

//求当前结点的下一个通路

coordinate passNext(Maze *m, int i, int j)//求迷宫路径

int solveMaze(Maze *m, Stack S)//模拟出路径

void showRoad(Maze m, Stack S)

程序源码：

#include #include

#define MAX 100

#define SIZE sizeof(Node)//**************************** //栈

typedef struct { int x;//行

int y;//列 }coordinate;//坐标

typedef struct node{ coordinate data;struct node *next;}Node, *Stack;

//栈的相关操作

//栈初始化

//带头结点的链栈

int initlStack(Stack *S){(*S)=(Node *)malloc(SIZE);if((*S)== NULL){

return 1;}(*S)->next = NULL;return 0;}

//入栈

int pushStack(Stack S, coordinate e){ Node *p;

p =(Node *)malloc(SIZE);p->data.x = e.x;p->data.y = e.y;p->next = S->next;S->next = p;return 0;}

//出栈

int popStack(Stack S, coordinate *e){ Node *p;if(S->next == NULL){

printf(“nStack is empty!n”);

return 2;} e->x = S->next->data.x;e->y = S->next->data.y;p = S->next;S->next = p->next;free(p);return 0;}

//读取栈顶

int getTop(Stack S, coordinate *e){ e->x = S->next->data.x;e->y = S->next->data.y;return 0;}

//显示

void show(Stack S){ Node *p;p = S->next;while(p!= NULL){

printf(“%d %d <-”, p->data.x, p->data.y);

p = p->next;} printf(“startn”);} //***************************

//*************************** //迷宫

typedef struct { int row;int col;int arr[MAX][MAX];}Maze;

//创建一个迷宫

int creatMaze(Maze *m){ int i, j;printf(“nplease input Maze's row and col:n”);scanf(“%d%d”, &(m->row), &(m->col));printf(“nplease input the Maze's message:(0 is ok),(1 is no)n”);for(i = 0;i <= MAX1;j++){

m->arr[i][j] = 1;

} } for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

scanf(“%d”, &(m->arr[i][j]));

} } return 0;}

//显示迷宫信息

void showMaze(Maze *m){ int i, j;printf(“nthe Maze you hava input:n”);for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

printf(“%d ”, m->arr[i][j]);

}

printf(“n”);}

printf(“nlike this:n”);for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

if(m->arr[i][j]!= 0){

printf(“■ ”);

}

else {

printf(“□ ”);

}

}

printf(“n”);} } //求当前结点的下个通路 //顺时针找

coordinate passNext(Maze *m, int i, int j){ coordinate k;if(m->arr[i][j+1] == 0){//东

k.x = i;

k.y = j+1;

return k;}

if(m->arr[i+1][j] == 0){//南

k.x = i+1;

k.y = j;

return k;} if(m->arr[i][j-1] == 0){//西

k.x = i;

k.y = j-1;

return k;} if(m->arr[i-1][j] == 0){//北

k.x = i-1;

k.y = j;

return k;} else {//不存在 k.x =-1;

k.y =-1;

return k;} }

//求解迷宫

int solveMaze(Maze *m, Stack S){ int i, j;int boolean;coordinate a;i = 1;j = 1;do {

if(m->arr[i][j] == 0){

a.x = i;

a.y = j;

m->arr[i][j] = 2;

pushStack(S, a);

if(i == m->row && j == m->col){

return 0;

}

}

a = passNext(m, i, j);

if(a.x!=-1){

i = a.x;

j = a.y;

continue;

}

else if(a.x ==-1){

boolean = popStack(S, &a);

if(2 == boolean){

return 0;

}

getTop(S, &a);

i = a.x;

j = a.y;

} }while(S->next!= NULL);return 0;}

//模拟出路径

void showRoad(Maze m, Stack S){ coordinate e;int i, j;if(S->next == NULL){

printf(“nSorry!you can't go out the Maze!n”);} while(S->next!= NULL){

popStack(S, &e);

m.arr[e.x][e.y] =-1;} for(i = 1;i <= m.row;i++){

for(j = 1;j <= m.col;j++){

if(m.arr[i][j] >= 0){

printf(“■ ”);

}

else {

printf(“□ ”);

}

}

printf(“n”);} } //*************************** //主函数 int main(){ Maze m;Stack S;printf(“※ 欢迎玩耍迷宫求解游戏 ※n”);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m, S);printf(“nthe root is here:n”);show(S);showRoad(m, S);return 0;}

程序运行结果：

第一步：输入迷宫行列大小

第二步：输入迷宫信息

第四步：程序会自动求出路径

课 设 总 结

敬爱的沈华老师您好，感谢您这半年对我们的教诲，说实话，很喜欢上您的课，您上课的风采深深的吸引了我，每次上您的课，我都听得特别认真。好吧，言归正传，谈谈这次课程设计的感想。

首先看到这道题的时候，真心没多少思路，我抱着试一试的态度，去网上搜索相关的算法。网上资源蛮多的，刚开始就搜索到了，严蔚敏老师的相关算法讲解视频，虽然她讲的是思想（就是他并没有源程序的实现），但是足够让我理解了基本算法流程。

其实先开始都不知道怎么下笔，但是我还是想着从基本栈开始写吧，慢慢写着，程序大概思想框架就成型了，最后在实现求解迷宫路径的时候，着手用笔在草稿纸上面模拟，然后才敲到编译器中，最好几经调试，终于得到了想要的结果。

做完这次课设后，深刻的体会到一些道理，在信息时代，解决问题的最好方法是运用现代的信息资源。并且在实际中，开始没思路的事，慢慢完成小部分，那么你的总体思维会渐渐地成型。

做事做人，平心气和的干，总会得到成功！