數(shù)據(jù)結(jié)構(gòu)課程設(shè)計2

1、數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計報告書班級 計算機(jī)121 學(xué)號 1208010128 姓名 指導(dǎo)老師 目錄一課程設(shè)計的目的和任務(wù)3二、課程設(shè)計名稱：迷宮的求解問題31、 問題的描述32、 基本要求33、 算法思想34、 需要解決的問題35、 模塊劃分36、 源程序?yàn)?7、 測試結(jié)果為4三、課程設(shè)計名稱：生死者游戲71、 問題的描述72、 問題的解決方法73、 模塊劃分84、 函數(shù)之間的調(diào)用關(guān)系85、 程序包含的函數(shù)86、 源程序?yàn)?7、 程序的運(yùn)行結(jié)果為10四、課程設(shè)計的名稱：二叉樹基本操作的實(shí)現(xiàn)101、 問題的描述102、 源程序?yàn)?03、 測試結(jié)果為14五、課程設(shè)計的名稱：圖的基本操作的實(shí)現(xiàn)151、

2、 問題的描述為152、 源程序?yàn)?53、 測試結(jié)果為19六、二叉排序樹的設(shè)計與實(shí)現(xiàn)以及快速排序算法的實(shí)現(xiàn)201、 問題的描述為202、 源程序?yàn)?03、 測試結(jié)果為25一、課程設(shè)計的目的和任務(wù)：1、 使學(xué)生進(jìn)一步理解和掌握課程上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們在程序中的使用方法2、 使學(xué)生掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計的能力3、 使學(xué)生掌握使用各種計算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計的基本技能二、課程設(shè)計名稱：迷宮的求解問題1、 問題的描述：迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子

3、的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解迷宮問題，即找出從入口到出口的路徑。2、 基本要求：（1） 建立一個大小為m*n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2） 找出一條通路的二元組（i，j)數(shù)據(jù)序列，（i,j）表示通路上某一點(diǎn)的坐標(biāo)（3） 在屏幕上輸出迷宮和通路3、 算法思想：采用回溯法，回溯法是一種不斷試探且及時糾正錯誤的搜索方法。本問題可從入口出發(fā)，按某一方向向未走過的前方探索，若能走通，則到達(dá)新點(diǎn)，否則試探下一方向; 若所有的方向均沒有通路，則沿原路返

4、回前一點(diǎn)，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。這也是一種“窮舉求解”的方法。4、 需要解決的問題：（1） 表示迷宮的數(shù)據(jù)結(jié)構(gòu)（2） 試探方向（3）棧的設(shè)計（4）防止重復(fù)到達(dá)某點(diǎn)，避免發(fā)生死循環(huán)5、模塊劃分：（1) 表示一個m行n列迷宮用mazemn表示，0=im,0=jnmazeij=0; 通路mazeij=1; 不通迷宮的定義：#define m 8 /*迷宮的實(shí)際行*/#define n 8/*迷宮的實(shí)際列*/int maze m+2n+2;（2） 試探方向表示位置的類型postype定義如下：typedef structint x

5、, y;postype;試探順序規(guī)定為：從正東衍順時針方向與點(diǎn)(x,y)相鄰的4個點(diǎn)及坐標(biāo) (x-1,y) (x,y-1) (x,y) (x,y+1) (x+1,y) （3） 棧中設(shè)計棧中每個元素的組成通道塊在路徑上的序號坐標(biāo)位置前進(jìn)方向（東為1，南為2，西為3，北為4）棧元素的類型定義：typedef struct int ord;postype seat;int di;selemtype;（4）防止重復(fù)到達(dá)某點(diǎn)走過不通之處要加以標(biāo)記（markprint操作）6、 源程序?yàn)椋?include#include#define n1 10#define n2 10typedef struct no

6、deint x;int y;int c;linkstack;linkstack top100;int mazen1n2=1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,;int i,j,k,m=0;void main()for(i=0;in1*n2

7、;i+)topi.c=1;printf(the maze is:n);for(i=0;in1;i+)for(j=0;jn2;j+)printf(mazeij?*: );printf(n);i=0;topi.x=1;topi.y=0;maze10=2;doif(topi.c5)if(topi.x=5 & topi.y=9)printf(the way &d is:n,m+);for(j=0;j,topj.x,topj.y);printf(n);for(j=0;jn1;j+)for(k=0;k1）（3） 在鏈表的首結(jié)點(diǎn)開始從1計數(shù)，計到m-1時，將下一個結(jié)點(diǎn)從鏈表中刪除，然后再從被刪除結(jié)點(diǎn)的下一個

8、結(jié)點(diǎn)又從1開始計數(shù)，數(shù)到m-1，再將其下一個結(jié)點(diǎn)從單循環(huán)鏈表刪除，直到剩下一半結(jié)點(diǎn)為止。3、模塊劃分：（1） 建立一個頭指針head指示的有n個結(jié)點(diǎn)的約瑟夫單循環(huán)鏈表initring（2） 生者與死者的選擇： p指向鏈表的第一個結(jié)點(diǎn)，初始化i為1； while (idata； （3）輸出所有生者的編號4、函數(shù)間的調(diào)用關(guān)系： main output deletedeath initring5、 程序包含的函數(shù)：（1） linklist initring(int n, linklist r)：初始化一個約瑟夫環(huán)（2） linklist deletedeath(int n,int k,linklis

9、t r)：尋找被扔入大海的人（3） void output(linklist r)：輸出所有生存者函數(shù)6、 源程序?yàn)椋?include#includetypedef struct nodeint num;struct node *next;node,*linklist;linklist initring(int n,linklist r)node *q,*p;int i;r=q=(node*)malloc(sizeof(node); for(i=1;inum =i;q-next=p;q=p; p-num =n;p-next =r;return r;linklist deletedeath(in

10、t n,int k,linklist r) int i,j;node *p,*q;p=r;for(i=1;i=n/2;i+)for(j=1;jnext; q=p-next ;p-next =q-next ;printf(%4d,q-num);free(q);p=p-next;return p;/*輸出所有生存者函數(shù)*/void output(linklist r)node *p;p=r;doprintf(%4d,p-num);p=p-next;while(p!=r);void main() linklist r; int n,m; printf(總?cè)藬?shù)n，報數(shù)上限m（用，分隔開）：); sca

11、nf(%d,%d,&n,&m); r=initring(n,r); output(r); printf(n被拋入大海的人有：); r=deletedeath(n,m,r); printf(n生存下來的人有：); output(r); printf(n);7、 程序運(yùn)行結(jié)果為：四、課程設(shè)計名稱：二叉樹的基本操作的實(shí)現(xiàn)1、 問題的描述：在主程序中編寫一個簡單的菜單，將有關(guān)二叉樹的操作（建立一棵二叉樹的存儲結(jié)構(gòu)、遍歷一棵二叉樹、統(tǒng)計二叉樹葉子結(jié)點(diǎn)的個數(shù)，求二叉樹的深度）等整合在一起，包括遞歸算法和非遞歸算法。2、 源程序?yàn)椋?*頭文件bitnode.h*/#include #include #inc

12、lude #define max 20#define ok 1#define error 0#define null 0#define overflow 0typedef char telemtype;typedef int status;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;/*先序遍歷構(gòu)造二叉樹*/bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=#) t=null;else t=(bitnode*

13、)malloc(sizeof(bitnode);if(!t) exit(overflow); t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t;void levelorder(bitree t)bitree queuemax,b;int front,rear;front=rear=0;if(t)queuerear+=t;while(front!=rear)b=queuefront+;printf(%2c,b-data);if(b-lchild!=null) queuerear+=

14、b-lchild;if(b-rchild!=null) queuerear+=b-rchild;（1）構(gòu)造二叉樹：#include bitnode.hvoid main ()bitree t=null;printf(*采用遞歸函數(shù)構(gòu)造一棵二叉樹*n);printf(請讀入構(gòu)造二叉樹的字符序列：);if(t=createbitree(t)printf(二叉樹建立成功！并以層序遍歷出構(gòu)造的二叉樹n);levelorder(t);printf(n);elseprintf(很遺憾，不能成功建立二叉樹！n);（2） 二叉樹的遍歷：#include #include bitnode.hstatus pri

15、ntelement(telemtype e)printf(%2c,e);return ok;status preordertraverse(bitree t,status(*visit)(telemtype)int i,j,k;if(t=null)return ok;elsei=visit(t-data);if(i)j=preordertraverse(t-lchild ,visit);if(j)k=preordertraverse(t-rchild ,visit);if(k) return ok;/if(j)/if(i)else return error;/elsestatus inorde

16、rtraverse(bitree t,status(*visit)(telemtype)/*中序遍歷*/if(t)if(inordertraverse(t-lchild ,visit)if(visit(t-data )if(inordertraverse(t-rchild ,visit) return ok;return error;else return ok;status postordertraverse(bitree t,status(*visit)(telemtype)/*后序遍歷*/if(t)if(postordertraverse(t-lchild,visit)if(postor

17、dertraverse(t-rchild,visit)if(visit(t-data)return ok;return error;else return ok;void main()bitree t=null,b=null;printf(*構(gòu)造一顆二叉樹并對其進(jìn)行遍歷*n);printf(請讀入構(gòu)造二叉樹的字符序列:);b = createbitree(t);if(b)printf(二叉樹建立成功!);printf(n該二叉樹的先序遍歷是:);preordertraverse(b,printelement);printf(n該二叉樹的中序遍歷是:);inordertraverse(b,pri

18、ntelement);printf(n該二叉樹的后序遍歷:);postordertraverse(b,printelement);printf(n該二叉樹的層次遍歷是:);levelorder(b);printf(n);elseprintf(二叉樹建立不成功!n);（3） 葉子結(jié)點(diǎn)的統(tǒng)計#include #include bitnode.hint leafcount(bitree bt)int n;if(bt=null) n=0;else if(bt-lchild=null&bt-rchild=null) n=1; else n=leafcount(bt-lchild)+leafcount(b

19、t-rchild); return n;void main ()bitree t=null;int m;printf(*構(gòu)造一棵二叉樹并求其結(jié)點(diǎn)數(shù)和深度*n);printf(請輸入所構(gòu)造的二叉樹的結(jié)點(diǎn)序列:);t=createbitree(t);if(t)printf(二叉樹建立成功！以層序遍歷輸出構(gòu)造的二叉樹n);levelorder(t);m=leafcount(t);printf(n該二叉樹的葉子結(jié)點(diǎn)數(shù)是:%dn,m);else printf(二叉樹建立不成功！n);（4） 二叉樹的深度統(tǒng)計：#include #include bitnode.hint depth(bitree t)/*

20、求二叉樹的深度*/int dep1,dep2;if(t=null)return error;elsedep1=depth(t-lchild);dep2=depth(t-rchild);return dep1dep2?dep1+1:dep2+1;/elsevoid main ()bitree t=null;printf(*構(gòu)造一棵二叉樹并求對其進(jìn)行深度統(tǒng)計*n);printf(請輸入所構(gòu)造的二叉樹的結(jié)點(diǎn)序列:);t=createbitree(t);if(t)printf(二叉樹建立成功！并以層序遍歷輸出構(gòu)造的二叉樹n);levelorder(t); printf(n二叉樹的深度是:%dn,dep

21、th(t);else printf(二叉樹建立不成功！n);3、 測試結(jié)果為：（1）二叉樹的建立的程序運(yùn)行結(jié)果為：（2） 二叉樹的遍歷的運(yùn)行結(jié)果：（3）葉子結(jié)點(diǎn)的統(tǒng)計的程序運(yùn)行結(jié)果為：（4） 二叉樹的深度統(tǒng)計的程序的運(yùn)行結(jié)果為：五、課程設(shè)計名稱：圖的基本操作的實(shí)現(xiàn)1、 問題的描述：在主程序中建立一個菜單，實(shí)現(xiàn)圖的基本操作，包括：建立圖的存儲結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷以及利用圖的拓?fù)渑判蝌?yàn)證圖中是否存在環(huán)2、 源程序?yàn)椋侯^文件graph的內(nèi)容為：typedef int infotype;#define maxv 100/*以下定義鄰接矩陣類型*/typedef struct

22、int no;infotype info;vertextype;typedef structint edgesmaxvmaxv;int vexnum,arcnum;vertextype vexsmaxv;mgraph;/*以下定義鄰接表類型*/typedef struct anodeint adjvex;struct anode*nextarc;infotype info;arcnode;typedef int vertex;typedef struct vnodevertex data;arcnode *firstarc;vnode;typedef vnode adjlistmaxv;typ

23、edef structadjlist adjlist;int n,e;algraph;（1）實(shí)現(xiàn)圖的遍歷算法的主程序?yàn)椋?include #include #include graph.hint visitedmaxv; algraph*mattolist(mgraph g)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表g*/int i,j,n=g.vexnum;arcnode*p;algraph*g;g=(algraph*)malloc(sizeof(algraph);for(i=0;iadjlisti.firstarc=null;for(i=0;i=0;j-)if(g.edgesij!=0)p=(arcno

24、de*)malloc(sizeof(arcnode);p-adjvex=j;p-info=g.edgesij;p-nextarc=g-adjlisti.firstarc;g-adjlisti.firstarc=p;g-n=n;g-e=g.arcnum;return g;void dispadj(algraph*g)/*輸出鄰接表g*/int i;arcnode*p;for(i=0;in;i+)p=g-adjlisti.firstarc;if(p!=null)printf(%3d:,i);while(p!=null)printf(%3d,p-adjvex);p=p-nextarc;printf(

25、n);void dfs(algraph*g,int v)arcnode*p;visitedv=1;printf(%3d,v);p=g-adjlistv.firstarc;while(p!=null)if(visitedp-adjvex=0)dfs(g,p-adjvex);p=p-nextarc;void dfs1(algraph*g,int v)int i,visitedmaxv,stmaxv,top=-1;arcnode*p;for(i=0;in;i+)visitedi=0;printf(%3d,v);top+;sttop=v;visitedv=1;while(top-1)v=sttop;p

26、=g-adjlistv.firstarc;while(p!=null & visitedp-adjvex=1)p=p-nextarc;if(p=null)top-;elsev=p-adjvex;printf(%3d,v);visitedv=1;top+;sttop=v;printf(n);void bfs(algraph*g,int v)arcnode*p;int queuemaxv,front=0,rear=0;int visitedmaxv;int w,i;for(i=0;in;i+) visitedi=0;printf(%3d,v);visitedv=1;rear=(rear+1)%ma

27、xv;queuerear=v;while(front!=rear)front=(front+1)%maxv;w=queuefront;p=g-adjlistw.firstarc;while(p!=null)if(visitedp-adjvex=0)printf(%3d,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%maxv;queuerear=p-adjvex;p=p-nextarc;printf(n);void main()int i,j;mgraph g;algraph *g;int amaxv5=0,1,1,0,0,1,0,0,1,1,1,0,0,0

28、,0,0,1,0,0,0,0,1,0,0,0,;g.vexnum=5;g.arcnum=4;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.edgesij=aij;g=mattolist(g);printf(圖g的鄰接表:n);dispadj(g);printf(從頂點(diǎn)0開始的dfs（遞歸算法）:n);dfs(g,0);printf(n);printf(從頂點(diǎn)0開始的dfs（非遞歸算法）:n);dfs1(g,0);printf(從頂點(diǎn)0開始的bfs（遞歸算法）:n);bfs(g,0); 3、 測試結(jié)果為： 六、課程設(shè)計名稱：二叉排序樹的設(shè)計與實(shí)現(xiàn)以及快速

29、排序算法的實(shí)現(xiàn)1、問題的描述：（1）編寫一個程序?qū)崿F(xiàn)二叉樹的基本運(yùn)算，并在此基礎(chǔ)上完成如下功能：a、由4,9,0,1,8,6,3,5,2,7,創(chuàng)建一棵bt并以括號表示法輸出；b、判斷bt是否為一棵二叉排序樹c、采用遞歸和非遞歸兩種方法查詢關(guān)鍵字為6的結(jié)點(diǎn)，并輸出其查找路徑；d、分別刪除bt中的關(guān)鍵字4和5的結(jié)點(diǎn)，并輸出刪除后的二叉排序樹。（2)編寫一個程序，實(shí)現(xiàn)對某一張順序表的快速排序算法2、源程序：（1）二叉樹的設(shè)計與實(shí)現(xiàn)：#include #include #define maxsize 100typedef int keytype;typedef char infotype;typede

30、f struct nodekeytype key;infotype data;struct node *lchild,*rchild;bstnode;int pathmaxsize;void dispbst(bstnode *b);int insertbst(bstnode *p,keytype k)if(p=null)p=(bstnode *)malloc(sizeof(bstnode);p-key=k;p-lchild=p-rchild=null;return 1;else if(k=p-key)return 0;else if(kkey )return insertbst(p-lchil

31、d ,k);else return insertbst(p-rchild ,k);bstnode*creatbst(keytype a,int n)bstnode *bt=null;int i=0;while(irchild!=null)delete1(p,r-rchild );elsep-key=r-key ;q=r;r=r-lchild;free(q);void delete(bstnode *p)bstnode*q;if(p-rchild=null)q=p;p=p-lchild;free(q);else if(p-lchild=null)q=p;p=p-rchild;free(q);el

32、se delete1(p,p-lchild);int deletebst(bstnode*bt,keytype k)if(bt=null)return 0;elseif(kkey )return deletebst(bt-lchild,k);else if(kbt-key )return deletebst(bt-rchild,k);elsedelete(bt);return 1;void searchbst1(bstnode *bt,keytype k,keytype path,int i)int j;if(bt=null)return;else if(k=bt-key)pathi+1=bt

33、-key;for(j=0;jkey;if(kkey)searchbst1(bt-lchild,k,path,i+1);elsesearchbst1(bt-rchild,k,path,i+1);int searchbst2(bstnode*bt,keytype k)if(bt=null)return 0;else if(k=bt-key )printf(%3d,bt-key );return 1;else if(kkey )searchbst2(bt-lchild ,k);else searchbst2(bt-rchild ,k);printf(%3d,bt-key );void dispbst(bstnode *bt)if(bt!=null)printf(%d,bt-key );if(bt-lchild!=null|bt-rchild!=null)printf();dispbst(bt-lchild);if(bt-rchild!=null)printf(,);dispbst(bt-rchild );printf();keytype predt=-32767;int judgebst(bstnode*bt)int b1,b2;if(bt=null)return 1;elseb1=judgebst(bt-lchild);if(b1=0|predt=bt