数据结构课程设计报告—迷宫求解问题

1、课题设计1：迷宫求解一. 需求分析：本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、 概要设计：1.抽象数据类型定义：adt find数据对象：d=ai?ai elemset,i=1,2,n,n0数据关系：r1=?ai-1, aid 基本操作： find (&s)初始条件：已初始化栈s，且栈为空操作结果：从栈中找出相对应的数据关系，并输出结果adt find2. 主程序的流程以及各程序模块之间的调用

2、关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find ()(4).结束程序三、相应的源程序如下：#include#includetypedef enum error, ok status;typedef struct int row, line; postype; typedef struct int di, ord; postype seat; selemtype; typedef structselemtype * base;selemtype * top;int stacksize;sqstack;status ini

3、tstack(sqstack &s); status push(sqstack &s,selemtype &a); status pop(sqstack &s,selemtype &a); status stackempty(sqstack s); status mazepath(int maze1212,sqstack &s, postype start, postype end); void initmaze(int maze1212,int size); void printmaze(int maze1212,int size); status pass(int maze1212,pos

4、type curpos); void markfoot(int maze1212, postype curpos); postype nextpos(postype curpos, int dir); void printpath(int maze1212,sqstack s,int size);void main (void) sqstack s;int size,maze1212; for(int n=0;n10;n+) printf(创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):n); scanf(%d,&size);if(size10)printf(输入错误!);return

5、; initmaze(maze,size); printmaze(maze,size); postype start,end; printf(输入入口行坐标和列坐标:);scanf(%d,&start.row);scanf(%d,&start.line); printf(输入出口行坐标和列坐标:);scanf(%d,&end.row);scanf(%d,&end.line); if(mazepath(maze,s,start,end) printpath(maze,s,size); else printf(找不到通路!nn);status mazepath(int maze1212,sqsta

6、ck &s, postype start, postype end) postype curpos;int curstep;selemtype e;initstack(s);curpos = start; curstep = 1; do if (pass(maze,curpos) markfoot(maze,curpos); e.di =1; e.ord = curstep; e.seat= curpos; push(s,e); if (curpos.row=end.row & curpos.line=end.line) return ok; curpos = nextpos(curpos,

7、1); curstep+; else if (!stackempty(s) pop(s,e); while (e.di=4 & !stackempty(s) markfoot(maze,e.seat); pop(s,e); if (e.di4) e.di+; push(s, e); curpos = nextpos(e.seat, e.di); while (!stackempty(s);return error; void initmaze(int maze1212,int size) char select; printf(选择创建方式 a:自动生成 b:手动创建n); label:sca

8、nf(%c,&select); if(select=a|select=a) for(int i=0;isize+2;i+)maze0i=1; for( i=1;isize+1;i+) mazei0=1; for(int j=1;jsize+1;j+) mazeij=rand()%2; mazeisize+1=1; for(i=0;isize+2;i+)mazesize+1i=1; else if(select=b|select=b) printf(按行输入%d*%d数据,0代表可通,1代表不可通(每行以enter结束):n,size,size); for(int i=0;isize+2;i+)

9、maze0i=1; for( i=1;isize+1;i+) mazei0=1; for(int j=1;jsize+1;j+) scanf(%d,&mazeij); mazeisize+1=1; for(i=0;isize+2;i+)mazesize+1i=1; else if(select=n)goto label; else printf(输入错误!);void printmaze(int maze1212,int size)printf(nn);printf(显示所建的迷宫(#表示外面的墙):n); for(int i=0;isize+2;i+)printf(%c ,#);printf

10、(n);for(i=1;isize+1;i+) printf(%c ,#); for(int j=1;jsize+1;j+) printf(%d ,mazeij); printf(%c,#); printf(n); for(i=0;iseat.rowp-seat.line=2; p+; for(int i=0;isize+2;i+)printf(%c ,#);printf(n);for(i=1;isize+1;i+) printf(%c ,#); for(int j=1;jsize+1;j+) if(mazeij=2) printf(%c ,0); else printf( ); printf

11、(%c,#); printf(n); for(i=0;isize+2;i+)printf(%c ,#);printf(nn);status pass(int maze1212,postype curpos)if (mazecurpos.rowcurpos.line=0) return ok; else return error; void markfoot(int maze1212,postype curpos)mazecurpos.rowcurpos.line=1;postype nextpos(postype curpos, int dir) postype returnpos; swit

12、ch (dir) case 1: returnpos.row=curpos.row; returnpos.line=curpos.line+1; break; case 2: returnpos.row=curpos.row+1; returnpos.line=curpos.line; break; case 3: returnpos.row=curpos.row; returnpos.line=curpos.line-1; break; case 4: returnpos.row=curpos.row-1; returnpos.line=curpos.line; break;return r

13、eturnpos;status initstack(sqstack &s)s.base=(selemtype *)malloc(100*sizeof(selemtype);if(!s.base)return error;s.top=s.base;s.stacksize=100;return ok;status push(sqstack &s,selemtype &a) *s.top+=a;return ok;status pop(sqstack &s,selemtype &a)if(s.top=s.base)return error;a=*-s.top;return ok;status sta

14、ckempty(sqstack s)if(s.top=s.base)return ok;return error;以下为测试数据：输入一个矩阵，例如：1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 输入入口行坐标和列坐标：1 2输入出口行坐标和列坐标：5 5通路路径为：课题设计3：joseph环一. 需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1. 输入的形式和输入值的范围 本程序中，输入报数上限值m和人数上限l，密码，均限定为

15、正整数，输入的形式为一个以“回车符”为结束标志的正整数。2. 输出的形式 从屏幕显示出列顺序。3. 程序功能 提供用户从键盘输入，joseph约瑟夫环的必要数据，并显示出列顺序。二、 概要设计以单向循环链表实现该结构。1. 抽象数据类型的定义为：adt lnode 数据对象：d=ai | aicharset，i= 1，2，n，n0 数据关系：r1=< ai-1 ，ai > | ai d， i=2，n三源程序：#include #include typedef struct node int key;/每个人持有的密码 int num;/这个人的编号 struct node *nex

16、t;/指向下一个节点 node,*link; void initlist(link &l) /创建一个空的链表 l=(node *)malloc(sizeof(node); if(!l) exit(1); l-key=0; l-num=0; l-next=l; void creater(int n,link &l) /初始化链表 link p,q; q=l; for(int i=1;ikey); p-num=i; l-next=p; l=p; l-next=q-next; free(q); void main() link l,p,q; int n,x; l=null; initlist(l)

17、;/构造出一个只有头结点的空链表 printf(please input the totle number of people:); scanf(%d,&n);/总共的人数n printf(the start key is:); scanf(%d,&x);/初始密码为x creater(n,l);/建立好一个约瑟夫环 p=l; for(int i=1;i=n;i+) for(int j=1;jnext; q=p-next; x=q-key; printf(%d ,q-num); p-next=q-next; free(q); 四、测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7

18、，2，4，7，4输出：6 7 4 1 5 3 2课题设计4：商品货架管理1、需求分析：设计一个算法，每一次上货后始终保持生产日期越近的商品越靠近栈底。求货架上剩余货物m、每天销售件数n、员工每天上货工作时间t，三者之间有何关系及t的最小值。2、源程序：#include#includestring.h#includestdio.hconst int maxsize=100; const int k=10; #define elemtype chartypedef structint month;int day;int year;date;typedef struct int num; date

19、date; node;class seqstackpublic:node stackmaxsize;int top;void inistack()top=0;void push(int x,int day,int month,int year)if(top=maxsize)cout货架已满endl;else top+;stacktop.num=x;stacktop.date.day=day;stacktop.date.month=month;stacktop.date.year=year;void pop()if(top=0)cout货架已空endl;elsetop-;elemtype get

20、top()if(top=0)cout货架已空endl;elsereturn top;bool empty()return top=0;void main()seqstack ck+1; /存放k种商品的数组,用c0来做中介货架int txqk+1; /第i种取货用的时间int txsk+1; /第i种上货用的时间int nxk+1; /第i种每天的销售数量int n=0; /每天销售总量int txk+1; /第i种每天上货的总时间int t=0; /每天上货用的总时间char yn=y;for(int i=1;i=k;i+)cout *endl;cout 商品货架管理系统endl;cout

21、*endl;node store20;char year,month;int count; /货架上第i种商品的数目 int x,d,m,y; /x为第i种商品的序号cout请输入货架上第i种货物的详细信息:endl;cout(序号,生产日期(年、月、日如2006.2.13)，现在货架上的存货数目,上货用时和取货用时)xyyearmmonthdcounttxsitxqi;nxi=maxsize-count;cout货架上还需上i货物nxi件endl;txk=txsi*(maxsize+count)+2*txqi*count;cout该货架满货需要用时txkendl;cout是否要上货?(y/n

22、)yn;if(yn=y|yn=y)int numbers,nian,yue,ri;cout请输入要上货物的数目及生产日期(年、月、日)numbersnianyueri;if(numbersmaxsize-count)cout要上的货物数目超出了货架的最大容量，请重新输入numbersnianyueri;for(int j=1;j=numbers;j+)n+=nxi;t+=txi;cout每天销售总量为:nendl;cout每天上货用的总时间为:tendl;3、测试结果：五、课程设计5：航空客运订票系统1、需求分析：对于本设计，可采用基数排序法对于一组具有结构特点的飞机航班号进行排序，利用二分查

23、找法对排好序的航班记录按航班号实现快递查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用的较少。2、源程序：#include #include #define maxspace 100#define keylen 7#define radix_n 10#define radix_c 26typedef char keytype;typedef struct char start6;char end6;char sche10;char time15;char time25;char model4;int price;infotype;typedef structkeytype

24、keyskeylen;infotype others;int next;slnode;typedef structslnode slmaxspace;int keynum;int length;sllist;typedef int arrtype_nradix_n;typedef int arrtype_cradix_c;void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,p;for(j=0;jradix_n;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;if

25、(!fj)fj=p;elseslej.next=p;ej=p;void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jradix_n-1)for(j=j+1;jradix_n-1&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)int j,p;for(j=0;jradix_c;j+)fj=ej=

26、0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jradix_c-1)for(j=j+1;jradix_c-1&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void radixsort(sllist &l)/链式int i;arrtype_n

27、fn,en;arrtype_c fc,ec;for(i=0;i=2;i-)distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i=0;i-)distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void arrange(sllist &l)/重新整理int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i+)while(pi)p=l.slp.next;q=l.slp.next;if(p!=i)temp=l.slp;l.slp=l.sli;

28、l.sli=temp;l.sli.next=p;p=q;int binsearch(sllist l,keytype key)int low,high,mid;low=1;high=l.length;while(low=high)mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0)return mid;else if(strcmp(key,l.slmid.keys)0)high=mid-1;elselow=mid+1;return 0;void seqsearch(sllist l,keytype key,int i)int j,k,m=0;print

29、f(*n);printf(* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n);for(j=1;j=1&i=5)printf(n *n);printf( * 航班信息查询系统 *n);printf( *n);printf( * 1.航 班 号 *n);printf( * 2.起 点 站 *n);printf( * 3.终 点 站 *n);printf( * 4.起飞时间 *n);printf( * 5.到达时间 *n);printf( * 0.退出系统 *n);printf( *n);printf( 请选择(0-5):);scanf(%d,&i);printf(n);switch(i)case 1:printf(输入要查询的航班号(字母要大写):);scanf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 无此航班信息，可能是输入错误！ *n);elseprintf(* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n);printf(* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n,l.slk.keys,l.slk.others.start,l.slk.others.end,l.slk.others.sche,l.slk.others.ti