數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告―迷宮求解問題

1、課題設(shè)計(jì)1：迷宮求解一. 需求分析：本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認(rèn)后程序自動運(yùn)行，當(dāng)迷宮有完整路徑可以通過時(shí)，以0和1所組成的迷宮形式輸出，標(biāo)記所走過的路徑結(jié)束程序；當(dāng)迷宮無路徑時(shí)，提示輸入錯(cuò)誤結(jié)束程序。二、 概要設(shè)計(jì)：1.抽象數(shù)據(jù)類型定義：ADT Find數(shù)據(jù)對象：D=ai?ai ElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=?ai-1, aiD 基本操作： find (&S)初始條件：已初始化棧S，且棧為空操作結(jié)果：從棧中找出相對應(yīng)的數(shù)據(jù)關(guān)系，并輸出結(jié)果ADT Find2. 主程序的流程以及各程序模塊之間的調(diào)用

2、關(guān)系：(1).定義變量i、j、w、z為整形變量(2).輸入迷宮二維數(shù)組maze(0:m,0:n)(3).調(diào)用子程序find ()(4).結(jié)束程序三、相應(yīng)的源程序如下：#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(創(chuàng)建一個(gè)正方形迷宮，請輸入迷宮尺寸(注意不要大于50):n); scanf(%d,&size);if(size10)printf(輸入錯(cuò)誤!);return

5、; Initmaze(maze,size); printmaze(maze,size); PosType start,end; printf(輸入入口行坐標(biāo)和列坐標(biāo):);scanf(%d,&start.row);scanf(%d,&start.line); printf(輸入出口行坐標(biāo)和列坐標(biāo):);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(選擇創(chuàng)建方式 A:自動生成 B:手動創(chuàng)建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數(shù)據(jù),0代表可通,1代表不可通(每行以Enter結(jié)束):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(輸入錯(cuò)誤!);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;以下為測試數(shù)據(jù)：輸入一個(gè)矩陣，例如：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 輸入入口行坐標(biāo)和列坐標(biāo)：1 2輸入出口行坐標(biāo)和列坐標(biāo)：5 5通路路徑為：課題設(shè)計(jì)3：joseph環(huán)一. 需求分析：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號。首先創(chuàng)建一個(gè)空鏈表，初始化鏈表，構(gòu)造出一個(gè)只有頭結(jié)點(diǎn)的空鏈表，建立好一個(gè)約瑟夫環(huán)。1. 輸入的形式和輸入值的范圍 本程序中，輸入報(bào)數(shù)上限值m和人數(shù)上限l，密碼，均限定為

15、正整數(shù)，輸入的形式為一個(gè)以“回車符”為結(jié)束標(biāo)志的正整數(shù)。2. 輸出的形式 從屏幕顯示出列順序。3. 程序功能 提供用戶從鍵盤輸入，Joseph約瑟夫環(huán)的必要數(shù)據(jù)，并顯示出列順序。二、 概要設(shè)計(jì)以單向循環(huán)鏈表實(shí)現(xiàn)該結(jié)構(gòu)。1. 抽象數(shù)據(jù)類型的定義為：ADT LNode 數(shù)據(jù)對象：D=ai | aiCharSet，i= 1，2，n，n0 數(shù)據(jù)關(guān)系：R1=< ai-1 ，ai > | ai D， I=2，n三源程序：#include #include typedef struct Node int key;/每個(gè)人持有的密碼 int num;/這個(gè)人的編號 struct Node *nex

16、t;/指向下一個(gè)節(jié)點(diǎn) Node,*Link; void InitList(Link &L) /創(chuàng)建一個(gè)空的鏈表 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、;/構(gòu)造出一個(gè)只有頭結(jié)點(diǎn)的空鏈表 printf(please input the totle number of people:); scanf(%d,&n);/總共的人數(shù)n printf(the start key is:); scanf(%d,&x);/初始密碼為x Creater(n,L);/建立好一個(gè)約瑟夫環(huán) 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); 四、測試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7

18、，2，4，7，4輸出：6 7 4 1 5 3 2課題設(shè)計(jì)4：商品貨架管理1、需求分析：設(shè)計(jì)一個(gè)算法，每一次上貨后始終保持生產(chǎn)日期越近的商品越靠近棧底。求貨架上剩余貨物M、每天銷售件數(shù)N、員工每天上貨工作時(shí)間T，三者之間有何關(guān)系及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種商品的數(shù)組,用c0來做中介貨架int Txqk+1; /第i種取貨用的時(shí)間int Txsk+1; /第i種上貨用的時(shí)間int Nxk+1; /第i種每天的銷售數(shù)量int N=0; /每天銷售總量int Txk+1; /第i種每天上貨的總時(shí)間int T=0; /每天上貨用的總時(shí)間char yn=Y;for(int i=1;i=k;i+)cout *endl;cout 商品貨架管理系統(tǒng)endl;cout

21、*endl;Node store20;char year,month;int count; /貨架上第i種商品的數(shù)目 int x,d,m,y; /x為第i種商品的序號cout請輸入貨架上第i種貨物的詳細(xì)信息:endl;cout(序號,生產(chǎn)日期(年、月、日如2006.2.13)，現(xiàn)在貨架上的存貨數(shù)目,上貨用時(shí)和取貨用時(shí))xyyearmmonthdcountTxsiTxqi;Nxi=maxsize-count;cout貨架上還需上i貨物Nxi件endl;Txk=Txsi*(maxsize+count)+2*Txqi*count;cout該貨架滿貨需要用時(shí)Txkendl;cout是否要上貨?(Y/N

22、)yn;if(yn=Y|yn=y)int numbers,nian,yue,ri;cout請輸入要上貨物的數(shù)目及生產(chǎn)日期(年、月、日)numbersnianyueri;if(numbersmaxsize-count)cout要上的貨物數(shù)目超出了貨架的最大容量，請重新輸入numbersnianyueri;for(int j=1;j=numbers;j+)N+=Nxi;T+=Txi;cout每天銷售總量為:Nendl;cout每天上貨用的總時(shí)間為:Tendl;3、測試結(jié)果：五、課程設(shè)計(jì)5：航空客運(yùn)訂票系統(tǒng)1、需求分析：對于本設(shè)計(jì)，可采用基數(shù)排序法對于一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)航班號進(jìn)行排序，利用二分查

23、找法對排好序的航班記錄按航班號實(shí)現(xiàn)快遞查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進(jìn)行，因?yàn)樗鼈冇玫妮^少。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)/鏈?zhǔn)絠nt 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(* 航班號 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)間 到達(dá)時(shí)間 機(jī)型 票價(jià) *n);for(j=1;j=1&i=5)printf(n *n);printf( * 航班信息查詢系統(tǒng) *n);printf( *n);printf( * 1.航 班 號 *n);printf( * 2.起 點(diǎn) 站 *n);printf( * 3.終 點(diǎn) 站 *n);printf( * 4.起飛時(shí)間 *n);printf( * 5.到達(dá)時(shí)間 *n);printf( * 0.退出系統(tǒng) *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(* 無此航班信息，可能是輸入錯(cuò)誤！ *n);elseprintf(* 航班號 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)間 到達(dá)時(shí)間 機(jī)型 票價(jià) *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