單鏈表的基本操作迷宮問(wèn)題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：17 大?。?.46MB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩16頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè) 計(jì) 成果報(bào) 告　　題目： 1.單鏈表的基本操作　　2. 迷宮問(wèn)題　　課程：數(shù)據(jù)結(jié)構(gòu)A課程設(shè)計(jì)　　院（部）：管理工程學(xué)

2、院　　專(zhuān) 業(yè)：信息管理與信息系統(tǒng)　　班級(jí)： 　　學(xué)生姓名： 　　學(xué) 號(hào)： 　　指導(dǎo)教師： </

3、p>　　完成日期： 2014年1月6日　　目錄　　一、課程設(shè)計(jì)概述1　　二、課程設(shè)計(jì)題目一1　　[問(wèn)題描述]1<p

4、>　　[調(diào)試分析]5　　[運(yùn)行結(jié)果及分析]5　　三、課程設(shè)計(jì)題目二8　　[問(wèn)題描述]8　　[需求分析]8<p&g

5、t;　　[概要設(shè)計(jì)]8　　[詳細(xì)設(shè)計(jì)]8　　[調(diào)試分析]13　　[運(yùn)行結(jié)果及分析]14　　四、參考文獻(xiàn)15&l

6、t;/p>　　課程設(shè)計(jì)報(bào)告　　一、課程設(shè)計(jì)概述　　本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)共完成兩個(gè)題：1、單鏈表的基本操作；2、迷宮問(wèn)題。　　使用語(yǔ)言：C<p&

7、gt;　　編譯環(huán)境：vc6.0　　二、課程設(shè)計(jì)題目一　　[問(wèn)題描述]　　程序清單：　　#include<stdio.h>&

8、lt;p>　　#include<malloc.h>　　typedef struct lnode　　{　　char value;　　struct lnode *link;　　}

9、llistnode;　　//創(chuàng)建單鏈表　　llistnode *creat()　　{　　llistnode *head,*p;　　cha

10、r ch;　　head=(llistnode *)malloc(sizeof(llistnode));　　head->link=NULL;　　printf("input:");　　while((ch=getchar())!=&

11、#39;\n')　　{　　p=(llistnode *)malloc(sizeof(llistnode));　　p->value=ch;　　p->link=head->link;<

12、;p>　　head->link=p;　　}　　return head;　　}　　//輸出單鏈表　　v

13、oid print(llistnode *head)　　{　　llistnode *p;　　printf("\n");　　p=head->link;

14、　　while(p)　　{　　printf("%c",p->value);　　p=p->link;　　}

15、;　　}　　//查找待查結(jié)點(diǎn)地址　　llistnode *visitll(llistnode *h,char x)　　{　　llistnode *p;

16、p=h->link;;　　while((p!=NULL)&&(p->value!=x))　　p=p->link;　　return(p);　　}　　//查找待查

17、某結(jié)點(diǎn)的前驅(qū)地址　　llistnode *predall(llistnode *h,llistnode *q)　　{　　llistnode *p;　　if(q==h->link)<

18、b>　　p=NULL;　　else　　{　　p=h;　　while((p!=NULL)&&(p->link!=

19、q))　　p=p->link;　　}　　return (p);　　}　　//插入某結(jié)點(diǎn)

20、　　void insertll(llistnode *h,llistnode *q,char x)　　{　　llistnode *p,*r;　　r=(llistnode *)malloc(sizeof(llistnode));<

21、p>　　r->value=x;　　if(h->link==q)　　h->link=r;　　else　　{　　p=predall(h

22、,q);　　p->link=r;　　}　　r->link=q;　　}　　//刪除某結(jié)點(diǎn)

23、;　　void deletell(llistnode *h,llistnode *q)　　{　　llistnode *p;　　if(h->link==q)　　h->link=q->link;&l

24、t;/p>　　else　　{　　p=predall(h,q);　　p->link=q->link;　　}</p&

25、gt;　　free(q);　　}　　main()　　{　　llistnode *a;//聲明一個(gè)單

26、鏈表指針　　llistnode *result=NULL;　　int choice;　　char data,data_cz;　　a=creat();//創(chuàng)建單鏈表　　while(1)</

27、p>　　{　　printf("\n以下是單鏈表的應(yīng)用，請(qǐng)選擇：");　　printf("\n1、遍歷鏈表并依次輸出其的結(jié)點(diǎn)值");　　printf("\n2、在鏈表中查找是否存在某結(jié)點(diǎn)")

28、;　　printf("\n3、在鏈表中查找某結(jié)點(diǎn)的前驅(qū)");　　printf("\n4、在鏈表中查找某結(jié)點(diǎn)的后繼");　　printf("\n5、在鏈表中插入結(jié)點(diǎn)");　　printf("\n6、在鏈表

29、中刪除結(jié)點(diǎn)");　　printf("\n7、退出");　　scanf("%d",&choice);　　switch(choice)　　{

30、;　　case 1: print(a);break;　　case 2: getchar();　　printf("請(qǐng)輸入待查結(jié)點(diǎn)的值：");　　data=getchar();　　result=visitll(a,data);&l

31、t;p>　　if(result!=NULL)　　printf("%c在鏈表中",data);　　else　　printf("%c不在鏈表中",data);　　result=NULL;<

32、;/p>　　break;　　case 3: getchar();　　printf("請(qǐng)輸入待查結(jié)點(diǎn)的值：");　　data=getchar();　　result=visitll(a,da

33、ta);　　if(result==NULL)　　{　　printf("%c不在鏈表中",data);　　break;

34、　　}　　result=predall(a,result);　　if(result!=NULL)　　printf("%c的前驅(qū)是%c",data,result->value);　　else</b

35、>　　printf("%c沒(méi)有前驅(qū)",data);　　result=NULL;　　break;　　case 4: getchar();　　printf("請(qǐng)

36、輸入待查結(jié)點(diǎn)的值：");　　data=getchar();　　result=visitll(a,data);　　if(result==NULL)　　{　　printf("%

37、c不在鏈表中",data);　　break;　　}　　if(result->link!=NULL)　　printf("%c的后繼是%c",data,result

38、->link->value);　　else　　printf("%c沒(méi)有后繼",data);　　result=NULL;　　break;<

39、;p>　　case 5: getchar();　　printf("請(qǐng)輸入待插結(jié)點(diǎn)的值：");　　data=getchar();　　getchar();　　printf("請(qǐng)輸入插入在哪個(gè)結(jié)點(diǎn)前面：");

40、　　data_cz=getchar();　　result=visitll(a,data_cz);　　if(result==NULL)　　{　　printf("%c不在鏈表中",data);<

41、/p>　　break;　　}　　insertll(a,result,data);　　break;　　case 6: getchar

42、();　　printf("請(qǐng)輸入待刪除結(jié)點(diǎn)的值：");　　data=getchar();　　result=visitll(a,data);　　if(result==NULL)　　{</b

43、>　　printf("%c不在鏈表中",data);　　break;　　}　　deletell(a,result);<b&

44、gt;　　break;　　case 7: break;　　defalut:break;　　}　　if(choice==7)　　break;}}&l

45、t;/b>　　要求及提示：　　要求寫(xiě)出每一個(gè)函數(shù)的功能。　　llistnode *creat()：創(chuàng)建單鏈表，并返回頭指針　　void print(llistnode *head)：輸出單鏈表<p&

46、gt;　　llistnode *visitll(llistnode *h,char x)：查找待查結(jié)點(diǎn)x的地址　　llistnode *predall(llistnode *h,llistnode *q)：查找待查某結(jié)點(diǎn)（*q）的前驅(qū)地址　　void insertll(llistnode *h,llistnode *q,char x)：插入某結(jié)點(diǎn)x<

47、;/p>　　void deletell(llistnode *h,llistnode *q)：刪除某結(jié)點(diǎn)（*q）　　[調(diào)試分析]　　通過(guò)單鏈表來(lái)存儲(chǔ)數(shù)據(jù)，利用鏈表指針域?qū)φ麄€(gè)單鏈表進(jìn)行操作。　　[運(yùn)行結(jié)果及分析]

48、;　　1.創(chuàng)建：　　2.查找是否存在結(jié)點(diǎn)3，9　　3.查找8，2的前驅(qū)　　4.查找8，2的后繼　　5.插入9到8前面；插入0到2前面

49、　　6.刪除9，2，5　　三、課程設(shè)計(jì)題目二　　迷宮問(wèn)題　　[問(wèn)題描述]　　[問(wèn)題描述]</p

50、>　　以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。　　[基本要求]　　實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：

51、（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。　　編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路；　　以方陣形式輸出迷宮及其通路。（選做）　　[需求分析]　　1.編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路；以方陣形式輸出迷

52、宮及其通路　　2.輸入入口坐標(biāo)，出口坐標(biāo)，求解具體行走過(guò)程，看是否有通路　　[概要設(shè)計(jì)]　　1、void initStack(Stack *p)：入棧初始化　　2、void Push(Stack *p,int x,int y,int

53、d) ：入棧具體操作　　3、void Pop(Stack *p,int last[2],int d) ：出棧并讀出前一步的坐標(biāo)　　4、void initMaze(int Maze[11][10])：建立迷宮　　5、void Print(int Maze[11][10])：打印出迷宮<

54、p>　　6、int Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) ：尋找路徑　　7、void menu()：菜單　　8、int main()：主函數(shù)　　9.typedef stru

55、ct{ 　　int pos_x[length];　　int pos_y[length];　　int top; 　　int base; 　　}Stack;&

56、lt;/p>　　存儲(chǔ)結(jié)構(gòu)體　　[詳細(xì)設(shè)計(jì)]　　#include <stdio.h> 　　#include <malloc.h> 　　#inclu

57、de<stdlib.h>　　#define length 50　　#define d direction //用d代表所走路徑的方向　　int n=-1;　　int step=0; //記錄步數(shù)

58、　　typedef struct{ 　　int pos_x[length];//進(jìn)棧坐標(biāo)　　int pos_y[length];　　int top; 　　int base;

59、;　　}Stack; 　　//初始化棧　　void initStack(Stack *p) 　　{ 　　p->top=p->base=0; <

60、;/p>　　}　　//入棧具體操作　　void Push(Stack *p,int x,int y,int d) 　　{ <

61、b>　　step++;　　d=0;　　n=n+1; 　　p->top=p->top+1; 　　p->pos_x[n]=x; &l

62、t;p>　　p->pos_y[n]=y;　　}　　//出棧并讀出前一步的坐標(biāo)　　void Pop(Stack *p,int read[2],int d) 　　{

63、　　step++;　　d=0;　　n=n-1; 　　p->top=p->top-1; 　　read[0]=p->pos_

64、x[n]; 　　read[1]=p->pos_y[n];　　}　　//迷宮初始化　　void initMaze(int Maze[11][10])&

65、lt;b>　　{ 　　int i; 　　//周?chē)系K用8表示　　for(i=0;i<10;i++)　　{　　Maze[0]

66、[i]=8;　　Maze[10][i]=8;　　}　　for(i=1;i<10;i++)　　{　　Maze[i][0]=8;

67、　　Maze[i][9]=8;　　}　　//迷宮　　Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;　　Maze[1][5

68、]=0;Maze[1][6]=0;Maze[1][7]=1;Maze[1][8]=0; 　　Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;　　Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=1;Maze[2][8]=0; 　　Ma

69、ze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;　　Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=0;Maze[3][8]=1; 　　Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;<p&g

70、t;　　Maze[4][5]=0;Maze[4][6]=0;Maze[4][7]=1;Maze[4][8]=0; 　　Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;　　Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;Maze[5][8]=0;&

71、lt;p>　　Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=0;　　Maze[6][5]=0;Maze[6][6]=1;Maze[6][7]=0;Maze[6][8]=1;　　Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;</p&g

72、t;　　Maze[7][5]=1;Maze[7][6]=0;Maze[7][7]=0;Maze[7][8]=1;　　Maze[8][1]=1;Maze[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;　　Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0;Maze[8][8]=1;<

73、;/p>　　Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;　　Maze[9][5]=0;Maze[9][6]=0;Maze[9][7]=0;Maze[9][8]=0;　　}

74、;　　//輸出迷宮　　void Print(int Maze[11][10])　　{　　int m,n;　　printf("迷宮(8代表墻即不通,0代表可通過(guò),1代表不能通過(guò))\n"); &

75、lt;/p>　　printf("* 1 2 3 4 5 6 7 8 *\n");　　for(m=0;m<11;m++)　　{for(n=0;n<10;n++)　　{　　pr

76、intf("%d",Maze[m][n]);　　printf(" ");　　}　　printf("\n");　　}

77、　　}　　//尋找路徑　　int Ways(Stack *p,int Maze[11][10],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d)<b

78、>　　{ 　　int x,y; 　　int read[2]; 　　x=rukou_x; 　　y=rukou_y; 　　printf("第%d步:"

79、,step);　　printf("(%d,%d,%d)\n",x,y,d);　　if(x==chukou_x&&y==chukou_y)　　{　　printf("到達(dá)出口坐標(biāo)共走了%d步\

80、n",step);return 0;　　}　　else if(Maze[x][y+1]==0) 　　{　　y=y+1;d=1;　　Push(p,

81、x,y,d);　　Maze[x][y-1]=1;　　Maze[x][y]=1;　　} 　　else if(Maze[x+1][y]==0) 　　{<

82、/p>　　x=x+1;　　d=2;　　Push(p,x,y,d);　　Maze[x-1][y]=1;　　Maze[x][y]=1;<p&g

83、t;　　} 　　else if(Maze[x][y-1]==0) 　　{　　y=y-1;　　d=3;

84、　　Push(p,x,y,d);　　Maze[x][y+1]=1;　　Maze[x][y]=1;　　} 　　else if(Maze[x-1][y]==0) <b&

85、gt;　　{　　x=x-1;　　d=4;　　Push(p,x,y,d);　　Maze[x+1][y]=1;　　Maze[x][y]=1

86、;　　} 　　else 　　{ 　　Pop(p,read,d); 　　x=read[0];

87、　　y=read[1];　　if(p->top==p->base) 　　{　　printf("找不到出口\n");　　return 0;<

88、/p>　　} 　　} 　　Ways(p,Maze,x,y,chukou_x,chukou_y,d);　　return 1;<

89、b>　　} 　　void menu()　　{　　printf("************************************\n"); 　　pri

90、ntf("* 2011021674 *\n");　　printf("* 迷宮求解 *\n");　　printf("* 選擇: *\n");</p

91、>　　printf("* 進(jìn)入迷宮***請(qǐng)輸入1 *\n");　　printf("* 退出迷宮***請(qǐng)輸入0 *\n");　　printf("************************************\n&q

92、uot;);　　printf("請(qǐng)輸入您的選擇\n");　　}　　int main() 　　{ 　　Stack *p; </p&

93、gt;　　Stack S;　　p=&S; 　　int Maze[11][10];　　int elem_1[1],elem_2[1],a,j; 　　int rukou_

94、x,rukou_y,d=0;　　int chukou_x,chukou_y; 　　int sum=0; 　　initMaze(Maze); 　　menu();　　scanf("%d

95、",&a);　　if(a==1){　　Print(Maze);　　printf("請(qǐng)輸入入口坐標(biāo):"); 　　scanf("%d",&elem_1[0]); </

96、p>　　scanf("%d",&elem_1[1]);　　rukou_x=elem_1[0];rukou_y=elem_1[1]; 　　printf("請(qǐng)輸入出口坐標(biāo):"); 　　scanf("%d",&ele

97、m_2[0]); 　　scanf("%d",&elem_2[1]);　　chukou_x=elem_2[0];chukou_y=elem_2[1];　　if(elem_1[0]>10||elem_1[1]>9||elem_2[0]>10||elem_2[1]>9

98、|| 　　elem_1[0]<0||elem_1[1]<0||elem_2[0]<0||elem_2[1]<0) 　　{　　printf("輸入的入口或出口坐標(biāo)錯(cuò)誤\n");

99、;　　}　　else 　　{ printf("\n");　　printf("說(shuō)明(x,y,z)x,y代表坐標(biāo)點(diǎn);\n");　　printf("z代表上個(gè)坐標(biāo)到達(dá)

100、這個(gè)坐標(biāo)所走的方向,0為初始值,1234分別代表向右、下、左、上方向\n");　　printf("查找路徑的具體步驟:\n"); 　　initStack(p); 　　Push(p,rukou_x,rukou_y,d); 　　Ways(p,Ma

101、ze,rukou_x,rukou_y,chukou_x,chukou_y,d); 　　} 　　return main();　　}　　else{</p&g

102、t;　　printf("退出!\n");　　}　　}　　[調(diào)試分析]　　本程序主要的操作對(duì)象是記錄數(shù)組，使用的存儲(chǔ)結(jié)

103、構(gòu)是結(jié)構(gòu)體數(shù)組。另外還有對(duì)C語(yǔ)言中 “窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。這是本程序中的一個(gè)重點(diǎn)也是難點(diǎn)，是此程序出現(xiàn)問(wèn)題的主要原因之一：　　問(wèn)題一：<p&

104、gt;　　現(xiàn)象：在輸出迷宮矩陣的時(shí)候出現(xiàn)亂碼，無(wú)法顯示正確的迷宮矩陣。　　原因：程序中print函數(shù)在輸出的時(shí)候，for循環(huán)執(zhí)行的時(shí)候出錯(cuò)。　　問(wèn)題二：　　現(xiàn)象：當(dāng)順著一個(gè)方向進(jìn)行探索的時(shí)候，遇到邊界的時(shí)候就無(wú)法執(zhí)行下去了。　　原因：

105、邊界如果是1，說(shuō)明遇到的是無(wú)法通過(guò)，按原路返回，可是如果遇到的是0，說(shuō)明是可以繼續(xù)前進(jìn)，問(wèn)題是現(xiàn)在沒(méi)有路徑可以繼續(xù)，所以必須外圍要增加一圈1，這樣，到了最外圍的時(shí)候就會(huì)按原路返回。　　[運(yùn)行結(jié)果及分析]　　四、參考文獻(xiàn)：　　[1].《C程

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

單鏈表的基本操作迷宮問(wèn)題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

單鏈表的基本操作迷宮問(wèn)題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載