工學數(shù)據(jù)結構課程設計

1、數(shù)據(jù)結構課程設計報告專 業(yè)：班 級：姓 名：學 號：指導教師：2011年 4 月 27日一、 設計題目（一）編程實現(xiàn)二叉排序樹的創(chuàng)建于操作（二）Josephu問題的實現(xiàn)（三）迷宮問題求解（四）編程實現(xiàn)無向圖的基本操作二、設計內容（一）以二叉鏈表作二叉排序樹中序遍歷得有序的存儲結構，結點的數(shù)據(jù)域為int類型，實現(xiàn)以下幾個操作：(1)以0為輸入結束標志，輸入數(shù)列L，生成一棵二叉排序樹T；(2)對二叉排序樹T作非遞歸中序遍歷，輸出遍歷結果；(3)計算二叉排序樹T查找成功的平均查找長度，輸出結果；(4)輸入元素x，查找二叉排序樹T，若存在含x的結點，則刪除該結點，并作中序遍歷(執(zhí)行操作2)；否則輸出信

2、息“x不存在”；(5) 輸入元素x，查找二叉排序樹T，若整棵樹不存在含值為x的結點，則插入該結點，并作中序遍歷(執(zhí)行操作2)；否則輸出信息“x已經存在”。（二）Josephu問題的實現(xiàn)。Josephu問題為：設編號為1，2， n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數(shù)，數(shù)到m 的那個人出列，它的下一位又從1開始報數(shù)，數(shù)到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。輸入數(shù)據(jù)：n,k,m 輸出：按照出列的順序依次輸出出列人的編號，編號中間相隔一個空格,每10個編號為一行。  （即每輸出10個元素，要求輸出一個回車符）Jo

3、sephu函數(shù)要進行非法參數(shù)的判斷，非法輸入的情況有多種，例如：a) 輸入的n、k、m的任一個小于1輸出：n,m,k must bigger than 0. b) 輸入：k>n輸出：k should not bigger than n.（三）迷宮問題求解 迷宮有一個入口，一個出口。一個人從入口走進迷宮，目標是找到出口。陰影部分和迷宮的外框為墻，每一步走一格，每格有四個可走的方向，探索順序為：南、東、北、西。 輸入：輸入迷宮數(shù)組的行數(shù)、列數(shù)和迷宮的形狀（0為可通，1為墻）。輸出：若有解，輸出從入口到出口的一條路徑，否則輸出 there is no solution!（四）編程實現(xiàn)無向圖的基

4、本操作。(1)自選存儲結構，輸入含n個頂點和e條邊的圖G；(2)求每個頂點的度，輸出結果；(3)指定任意頂點x為初始頂點，對圖G作DFS遍歷，輸出DFS頂點序列； (4)指定任意頂點x為初始頂點，對圖G作BFS遍歷，輸出BFS頂點序列；(5)輸入頂點x，查找圖G:若存在含x的頂點（深度優(yōu)先or廣度優(yōu)先），則刪除該結點及與之相關連的邊，并作DFS遍歷(執(zhí)行操作3)；否則輸出信息“不存在x”；(6)判斷圖G是否是連通圖（遍歷的頂點與創(chuàng)建時的頂點個數(shù)是否一樣），輸出信息“YES”/“NO”； 三、概要設計（一）編程實現(xiàn)二叉排序樹的創(chuàng)建于操作。本程序所使用的模塊及個模塊間的調用關系（二）Josephu

5、問題的實現(xiàn)本程序所使用的模塊及個模塊間的調用關系：（三）迷宮問題求解本程序所使用的模塊及個模塊間的調用關系：（四）編程實現(xiàn)無向圖的基本操作。本程序所使用的模塊及個模塊間的調用關系：四、詳細設計（一）編程實現(xiàn)二叉排序樹的創(chuàng)建與操作1，二叉排序樹類型typedef struct bitnodeint data;struct bitnode *lson,*rson;int count;/*計數(shù)器，用于計算平均查找長度*/bitnode,*bitree;2,棧類型typedef struct seqstackbitree b100;int top;stack;3，棧的操作算法int isempty(s

6、tack* s)/*判空操作*/if(s->top!=-1) return 1;/*若?？辗祷?，否則返回1*/else return 0;void push(stack* s,bitree p)/*壓棧操作*/if(s->top=100) printf("The stack is overflow!");/*若棧不滿，則進行壓棧操作*/elses->top+;s->bs->top=p;bitree pop(stack* s)/*出棧操作*/if(s->top=-1) printf("The stack is empty!&qu

7、ot;);/*若棧不空，則進行出棧操作*/elses->top-;return(s->bs->top+1);4，對二叉排序樹的操作算法：bitree creatbitree()/*創(chuàng)建二叉排序樹*/bitree t=NULL,p;int data;printf("Please input the data to creat the tree or input 0 to quit:n");scanf("%d",&data);/*輸入一個數(shù)據(jù)*/while(data!=0)if(t=NULL)/*若為空樹，則將輸入的數(shù)據(jù)賦給樹根*/

8、p=(bitnode*)malloc(sizeof(bitnode);p->data=data;p->lson=p->rson=NULL;t=p;elseinsert(t,data);/*如果不是空樹，則調用插入函數(shù)將輸入的數(shù)插入合適的位置*/scanf("%d",&data); return(t);/*返回指向樹根的指針*/void traverse(bitree t)/*非遞歸中序遍歷二叉排序樹*/stack s;bitree p=t;s.top=-1;/*棧的初始化*/while(p!=NULL|isempty(&s)/*如果不是空樹

9、或者棧不為空*/if(p!=NULL)/*若當前指針不為空*/push(&s,p);/*將數(shù)據(jù)壓入棧中*/p=p->lson;/*當前指針指向其左孩子*/elsep=pop(&s);/*若當前指針為空，彈出棧頂元素，當前指針指向該元素*/printf("%d ",p->data);p=p->rson;/*當前指針指向其右孩子*/ float asl(bitree t)/*計算二叉排序樹的平均查找長度，利用中序遍歷的思想*/stack x;bitree p=t,l=p;float a,num=0,key=0;x.top=-1;/*棧的初始化*

10、/p->count=0;while(p!=NULL|isempty(&x)if(p!=NULL)push(&x,p);p->count=l->count+1;/*p的查找長度為其父結點的查找長度加1*/key=key+p->count;/*key為已遍歷過的所有結點的查找長度之和*/l=p;p=p->lson; /*l始終指向p的父結點*/elsep=pop(&x);num+;/*彈出一個元素，num就加1，num為已遍歷的結點個數(shù)*/l=p;p=p->rson; a=key/num;/*平均查找長度的計算方法*/return a;b

11、itree delete(bitree t,int x)/*刪除結點*/bitree p=t,q=p,s;/*q始終指向p的父結點*/while(p!=NULL)/*如果不是空樹，則進行查找*/if(x=p->data) break;/*查找成功，跳出循環(huán)*/else if(x<=p->data) /*若x小于等于當前結點的數(shù)據(jù)，去當前結點的左孩子查找*/q=p;p=p->lson;else /*x大于當前結點的數(shù)據(jù)，則去當前結點的右孩子繼續(xù)查找*/q=p;p=p->rson; if(p=NULL) printf("nx is not exist.&qu

12、ot;);return t;/*循環(huán)結束，p為空，查找失敗*/if(p->rson=NULL&&p->lson=NULL) /*若要刪除的結點沒有左右孩子*/if(q->rson=p) /*若p是其父結點的右孩子，令父結點的右孩子為空，釋放p*/q->rson=NULL;free(p); else if(q->lson=p) /*若p是其父結點的左孩子，令父結點的左孩子為空，釋放p*/q->lson=NULL;free(p);else if(q=p) t=NULL;/*要刪除的元素為根結點，令根為空*/else if(p->lson=N

13、ULL&&p->rson!=NULL)/*要刪除結點沒有左孩子，有右孩子*/if(q->rson=p) /*若p是其父結點的右孩子，令父結點的右孩子指向刪除結點的右孩子，釋放p*/q->rson=p->rson;free(p); else if(q->lson=p) /*若p是其父結點的左孩子，令父結點的右孩子指向刪除結點的右孩子，釋放p*/q->lson=p->rson;free(p);else if(q=p) /*要刪除的元素為根結點，令根指向刪除結點的右孩子，釋放p*/ t=p->rson;free(p);else if(p

14、->rson=NULL&&p->lson!=NULL) /*要刪除結點有左孩子沒有右孩子*/if(q->rson=p) /*若p是其父結點的右孩子，令父結點的右孩子指向刪除結點的左孩子，釋放p*/q->rson=p->lson;free(p); else if(q->lson=p) /*若p是其父結點的左孩子，令父結點的右孩子指向刪除結點的左孩子，釋放p*/q->lson=p->lson;free(p);else if(q=p) /*要刪除的元素為根結點，令根指向刪除結點的左孩子，釋放p*/t=p->lson;free(p)

15、;else if(p->rson!=NULL&&p->lson!=NULL)/*要刪除結點有左孩子也有右孩子*/q=p;s=p->lson;while(s->rson)q=s;s=s->rson;p->data=s->data;if(q!=p) q->rson=s->lson;/*將要刪除結點左子樹最下方的右孩子的數(shù)據(jù)賦給要刪除結點，刪除左子樹最下方的右孩子，使之仍為一個二叉排序樹*/else q->lson=s->lson;free(s);traverse(t);return(t);bitree insertb

16、st(bitree t,int x)/*插入結點算法*/bitree p=t,q;if(t=NULL) t->data=x;traverse(t);return t;/*若為空樹，則將x賦給跟結點的值*/while(p!=NULL)if(x=p->data) printf("nThere is a x in the tree.");return t;/*查找算法*/if(x<=p->data)q=p; p=p->lson;else q=p;p=p->rson;if(p=NULL) insert(t,x);/*循環(huán)結束查找成功，調用插入算將

17、x插入合適的位置*/traverse(t);（二）Josephu問題的實現(xiàn)1，循環(huán)鏈表類型typedef struct nodeint data;struct node *next;lnode,*linklist;2，創(chuàng)建循環(huán)鏈表算法linklist creatlist(int n)p=(lnode*)malloc(sizeof(lnode);if(p=NULL) return(0);/若空間分配失敗，返回0head=p;p->data=1;p->next=NULL;for(i=2;i<=n;i+)/為n個結點賦值編號p->next=(lnode*)malloc(siz

18、eof(lnode);if(p->next=NULL) return(0);p->next->data=i;p=p->next;p->next=head;/令最后一個結點的next指針指向頭結點，實現(xiàn)循環(huán)鏈表return(head);3，約瑟夫問題的求解算法void delete(linklist head,int k,int m)linklist p=head,s=head,q;/s為指向p的前一個結點的指針int j=0,i=1;while(p->data<k)/找到編號為k的結點，p指向這個結點s=p;p=p->next;while(p!=

19、p->next)/若不是只剩下一個結點while(i<m)/找到從k開始第m個結點p=p->next;s=s->next;i+;q=p->next;printf("%d ",p->data);j+;if(j%10=0) printf("n");/每輸出十個數(shù)，另起一行s->next=q;/刪除結點pfree(p);p=q;/p指向刪除結點的下一個結點i=1;printf("%d ",p->data);/只剩下一個結點的時候，直接輸出該節(jié)點，結束此函數(shù)（三）迷宮問題求解1，坐標位置類型ty

20、pedef structint row;int col;postype;2.迷宮類型typedef structint arr100100;mazetype;3，棧類型typedef structpostype seat;int di;stype;typedef structstype s100;int top;sqstack;4，棧的相關操作void push(sqstack *p, stype e)/壓棧操作if(p->top=100) printf("The stack is overflow!")；elsep->top+;p->sp->top

21、=e;stype pop(sqstack *s)/出棧操作，返回刪除的元素if(s->top=-1) printf("The stack is empty!");elses->top-;return s->ss->top+1;int stackempty(sqstack *s)/判?？詹僮?，?？辗祷?，否則返回0if(s->top=-1) return 1;else return 0;5，迷宮相關算法void initmaze(mazetype *maze, int row, int col)/迷宮的初始化int i,j,a;for(i=0;i

22、<=row+1;i+)maze->arri0=1;maze->arricol+1=1;for(i=0;i<=col+1;i+)maze->arr0i=1;maze->arrrow+1i=1;/將迷宮四周值設為1，作為圍墻，不可通for(i=1;i<=row;i+)for(j=1;j<=col;j+)scanf("%d",&a);maze->arrij=a;/用戶輸入迷宮形狀void printmaze(mazetype *m,int row,int col)/打印迷宮形狀 int i,j,count=0;for(

23、i=0;i<=row+1;i+)for(j=0;j<=col+1;j+)printf("%d",m->arrij);count+;if(count=row+2) /count=0;printf("n"); int mazepath(mazetype *maze,postype start, postype end)/求解迷宮maze中,從入口start到出口end的一條路徑/若存在,返回1,否則返回0sqstack s,s1;stype e,e2,e3;postype c=start; s.top=-1;s1.top=-1;do if(

24、maze->arrc.rowc.col=0)/如果當前位置可以通過,即是未曾走到的通道塊 maze->arrc.rowc.col=3; /留下足跡e.seat = c; e.di = 1;/創(chuàng)建元素push(&s,e);if(c.row=end.row && c.col=end.col) while(!stackempty(&s)e2=pop(&s);push(&s1,e2);while(!stackempty(&s1)e3=pop(&s1);printf("<%d,%d>",e3.se

25、at.row,e3.seat.col);/探索成功，打印路徑return 1;c=nextpos(c,1); /獲得下一節(jié)點:當前位置的南鄰else /當前位置不能通過 if(!stackempty(&s)pop(&s);if(e.di=4 && !stackempty(&s)maze->arre.seat.rowe.seat.col=4; /留下不能通過的標記e=pop(&s);c=e.seat;if(e.di<4)e.di+; /換一個方向探索push(&s,e); c=nextpos(e.seat,e.di); /求下一

26、個結點while(!stackempty(&s);return 0;（四）編程實現(xiàn)無向圖的基本操作。1，無向圖類型ypedef structint adj;arccell,adjmatrix100100;typedef structint vexs100;adjmatrix arcs;int vexnum,arcnum;mgraph;2，隊類型typedef structint data100;int front,rear;queue;3，隊相關操作void initqueue(queue *q)/隊列初始化q->front=q->rear=0;void enqueue(q

27、ueue *q,int x)/入隊操作if(q->rear+1)%100=q->front) /判循環(huán)隊列是否滿printf("The queue is full!");exit(0); else q->rear=(q->rear+1)%100;q->dataq->rear=x;int dequeue(queue *q)/出隊操作if(q->rear=q->front)/判隊列是否為空，是空返回0printf("The queue is empty!");return(0);else q->front

28、=(q->front+1)%100;return(q->dataq->front);4.無向圖相關操作算法int create(mgraph *g)/用戶輸入頂點創(chuàng)建無向圖，創(chuàng)建成功返回1int i,j,k;int v1,v2;printf("Please input the number of vertexs and the number of sides: ");scanf("%d%d",&g->vexnum,&g->arcnum);/輸入頂點數(shù)和邊數(shù)printf("nPlease input

29、the vertexs:");for(i=0;i<g->vexnum;i+)/輸入各頂點的值scanf("%d",&g->vexsi);for(i=0;i<g->vexnum;i+)for(j=0;j<g->vexnum;j+)g->arcsij.adj=0;/.邊的初始化printf("nPlease input the vertexs of each side:");for(k=0;k<g->arcnum;k+)/輸入各邊得兩個頂點scanf("%d%d"

30、;,&v1,&v2);i=locate(*g,v1);/定位對應頂點，返回頂點值j=locate(*g,v2);g->arcsij.adj=1;g->arcsji=g->arcsij;return 1;void getdegree(mgraph *g)/計算無向圖的度int i,j,td=0;for(i=0;i<g->vexnum;i+)for(j=0;j<g->vexnum;j+)td+=g->arcsij.adj;printf("%d：The degree is %d.n",g->vexsi,td);

31、td=0;void dfs(mgraph *g,int v)/遞歸深度優(yōu)先遍歷無向圖int u;visitedv=1;/判斷是否被訪問過的數(shù)組，被訪問過數(shù)組值為1，否則為0visit(g,v);/打印頂點值for(u=0;u<g->vexnum;u+)if(g->arcsvu.adj&&!visitedu)dfs(g,u);/遞歸調用void dfsearch(mgraph *g) int v;for(v=0;v<g->vexnum;v+)visitedv=0;printf("nDFS:");for(v=0;v<g->

32、;vexnum;v+)if(!visitedv) dfs(g,v);void bfsearch(mgraph *g)/廣度優(yōu)先遍歷無向圖queue q;int u,v,w;initqueue(&q);/隊列初始化for(u=0;u<g->vexnum;u+)visitedu=0;/訪問數(shù)組初始值printf("nBFS:");for(u=0;u<g->vexnum;u+)if(!visitedu)/如果沒有被訪問過enqueue(&q,u);/入隊操作while(!(q.rear=q.front)/判隊列是否為空v=dequeue(&

33、amp;q);/出隊操作visitedv=1;/標記訪問過visit(g,v);/打印頂點值for(w=0;w<g->vexnum;w+)/訪問當前頂點的鄰接點if(g->arcsvw.adj&&!visitedw)visitedw=1;enqueue(&q,w);int deletevex(mgraph *g,int x)/刪除頂點操作，刪除成功返回1，刪除失敗返回0int v,u,w;v=locate(*g,x);/定位操作，返回頂點值if(v!=-1)/存在該頂點for(u=v;u<g->vexnum;u+)g->vexsu=g

34、->vexsu+1;/將要刪除的頂點后的頂點都向前挪一位for(u=v;u<g->vexnum;u+)/將鄰接矩陣要刪除結點下面的值都向上移一行for(w=0;w<g->vexnum;w+)g->arcsuw.adj=g->arcsu+1w.adj;for(u=v;u<g->vexnum;u+)/將鄰接矩陣要刪除結點右面的值都向作移一列for(w=0;w<g->vexnum;w+)g->arcswu.adj=g->arcswu+1.adj;g->vexnum-;/無向圖頂點數(shù)減1return 1;return

35、0;void isconnected(mgraph *g)/判連通操作，利用深度遍歷的思想int v,count=0;for(v=0;v<g->vexnum;v+)visitedv=0;printf("nDFS:");for(v=0;v<g->vexnum;v+)/此循環(huán)用以找到與其他頂點不連通的頂點，如果此循環(huán)循環(huán)超過一次，則為非連通圖，否則為連通圖if(!visitedv) dfs(g,v);count+;if(count=1) printf("nYES!");else printf("nNO!");五、測試結果及分析（一）編程實現(xiàn)二叉排序樹的創(chuàng)建與操作測試所用二叉排序樹：測試結果截圖：由以上測試結果可以看出，程序能完成設定