迷宫问题和过河问题实验报告

天津外国语大学国际商学院本科生课程论文课程名称：数据结构论文题目：实验报告姓名：杨丽文学号：1407114036专业：信息管理与信息系统年级：14级班级：14707任课教师：王斌老师2015年6月目录一、研究问题…………4二、研究思路…………4三、研究过程…………5四、结语…………………15五、参考文献……………15迷宫问题和农夫过河问题实验报告研究问题迷宫问题：从入口进入迷宫，如何才能找到它的出口？农夫过河问题：一个农夫带着一只狼，一只羊和一棵白菜身处河的南岸，他要把所有东西云运到河的对岸。只有一条能容下他和另一物品的小船，且狼吃羊，羊吃白菜。怎样才能安全过河？二、研究思路迷宫问题是栈的典型运用，运用回溯法来解决这一问题：沿某一方向进行探索，若能走通，就继续像前走；否则沿原路返回，换一个方向再进行探索，直到找到了一个出口，或者所有可能的探索都以失败告终。农夫过河问题是队列的典型运用，这里采用广度优先的方法。研究过程迷宫问题：#include<stdio.h>#include<stdlib.h>typedefstruct{intx,y,d;}DataType;typedefstructSeqStack*PSeqStack;structSeqStack{intmaxnum;intt;DataType*s;};PSeqStackcreateEmptyStack_seq(intm){PseqStackpastack=(PSeqStack)malloc(sizeof(structSeqStack)); if(pastack!=NULL){pastack->s=(DataType*)malloc(sizeof(DataType)*m); if(pastack->s){pastack->maxnum=m; pastack->t=-1; returnpastack;}elsefree(pastack);} printf("Outofspace!\n");returnNULL;}intisEmptyStack_seq(PSeqStackpastack){return(pastack->t==-1);}DataTypetop_seq(PSeqStackpastack){if(pastack->t==-1)printf("Itisempty!\n");elsereturn(pastack->s[pastack->t]);}voidpush_seq(PSeqStackpastack,DataTypex){if(pastack->t>=pastack->maxnum-1)printf("Overflow!\n");else{pastack->t++;pastack->s[pastack->t]=x;}}voidpop_seq(PSeqStackpastack){if(pastack->t==-1)printf("Underflow!\n");elsepastack->t=pastack->t-1;}voidmazePath(int*maze[],int*direction[],intx1,inty1,intx2,inty2,intM,intN){inti,j,k;intg,h;PSeqStackst;DataTypeelement;st=createEmptyStack_seq(M*N);maze[x1][y1]=2;element.x=x1;element.y=y1;element.d=-1;push_seq(st,element);while(!isEmptyStack_seq(st)){element=top_seq(st);pop_seq(st);i=element.x;j=element.y;k=element.d+1;while(k<=3){g=i+direction[k][0];h=j+direction[k][1];if(g==x2&&h==y2&&maze[g][h]==0){element.x=i;element.y=j;push_seq(st,element);element.x=g;element.y=h;push_seq(st,element);printf("thereverspathis:\n");while(!isEmptyStack_seq(st)){element=top_seq(st);pop_seq(st);printf("thenodeis:%d%d\n",element.x,element.y);}return;}if(maze[g][h]==0){maze[g][h]=2;element.x=i;element.y=j;element.d=k;push_seq(st,element);i=g;j=h;k=-1;}k=k+1;}}printf("Thepathhasnotbeenfound.\n");}intmain(){mazePath;inta,b,c,d,e,f,i,k;int*p1[8],*p2[4];intdirection[4][2]={0,1,1,0,0,-1,-1,0};intmaze[8][11]={1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1};for(i=0;i<8;i++)p1[i]=maze[i];for(k=0;k<4;k++)p2[k]=direction[k];printf("pleaseinputthelocationofenterance:\n");scanf("%d%d",&a,&b);printf("pleaseinputthelocationofexit\n");scanf("%d%d",&c,&d);printf("pleaseinputthemaxnumofthelocation\n");scanf("%d%d",&e,&f);mazePath(p1,p2,a,b,c,d,e,f);}运行结果如下：此时输出的是反向路径，后面做了改进，使其输出正向路径。具体做法是添加了一个栈。此次运行结果为农夫过河问题：#include<stdio.h>#include<stdlib.h>#defineM16typedefintDataType;structSeqQueue{intmaxnum;intf,r;DataType*q;};typedefstructSeqQueue*PSeqQueue;PSeqQueuepaqu;PSeqQueuecreateEmptyQueue_seq(intm){PSeqQueuepaqueue=(PSeqQueue)malloc(sizeof(structSeqQueue)); if(paqueue!=NULL){paqueue->q=(DataType*)malloc(sizeof(DataType)*m); if(paqueue->q){ paqueue->maxnum=m; paqueue->f=0; paqueue->r=0; returnpaqueue;} elsefree(paqueue);} printf("Outofspace!\n");returnNULL;}intisEmptyQueue_seq(PSeqQueuepaqu){return(paqu->f==paqu->r);}voidenQueue_seq(PSeqQueuepaqu,DataTypex){if((paqu->r+1)%paqu->maxnum==paqu->f)printf("Fullqueue.\n");else{paqu->q[paqu->r]=x;paqu->r=(paqu->r+1)%paqu->maxnum;}}voiddeQueue_seq(PSeqQueuepaqu){if(paqu->r==paqu->f)printf("Emptyqueue.\n");elsepaqu->f=(paqu->f+1)%paqu->maxnum;}DataTypefrontQueue_seq(PSeqQueuepaqu){if(paqu->r==paqu->f)printf("Itisempty!\n");elsereturn(paqu->q[paqu->f]);}intfarmer(intlocation){ return(0!=(location&0x08));}intwolf(intlocation){return(0!=(location&0x04));}intcabbage(intlocation){ return(0!=(location&0x02));}intgoat(intlocation){ return(0!=(location&0x01));}intsafe(intlocation){ if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location))) return0; if((goat(location)==wolf(location))&&(goat(location)!=farmer(location))) return0; return1;}intmain(){inti,movers,location,newlocation;introute[16];PSeqQueuemoveTo;moveTo=createEmptyQueue_seq(M);enQueue_seq(moveTo,0x00);for(i=0;i<16;i++) route[i]=-1;route[0]=0;while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)){ location=frontQueue_seq(moveTo); deQueue_seq(moveTo); for(movers=1;movers<=8;movers<<=1) if((0!=(location&0x08))==(0!=(location&movers))) {newlocation=location^(0x08|movers); if(safe(newlocation)&&(route[newlocation]==-1)) { route[newlocation]=location; enQueue_seq(moveTo,newlocation); } }}if(route[15]!=-1){ printf("Thereversepathis:\n"); for(location=15;location>=0;location=route[location]) { printf("Thelocationis:%d\n",location); if(location==0)exit(0); }}elseprintf("Nosolution.\n");}一开始的反向路径：做出了改进：intmain(){inti,movers,location,newlocation;introute[16];PSeqQueuemoveTo;moveTo=createEmptyQueue_seq(N);enQueue_seq(moveTo,0x00);for(i=0;i<16;i++) route[i]=-1;while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)){ location=frontQueue_seq(moveTo); deQueue_seq(moveTo); for(movers=1;movers<=8;movers<<=1) if((0!=(location&0x08))=