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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告書課程設(shè)計的名稱：一、生死者游戲1.問題描述：有n個旅客同乘一條船，因為嚴(yán)重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入大海，其余人才能幸免遇難．無奈，大家只得同意這種辦法，并議定n個人圍坐一圈，從1,2,3…到n進行編號。由第一個人數(shù)起，依次報數(shù)，數(shù)到第m人，將它扔進大海中，然后再從他的下一個人數(shù)起，數(shù)到第m人，再將他扔進大海，如此循環(huán)進行，直到剩下一半人為止，問哪幾個人是將被扔進大海的人。

2.基本要求：

利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，輸出生者的編號。

3.算法思想：

該問題是由古羅馬著名史學(xué)家Josephus提出的問題演變而來，所以通常稱之為Josephus問題。Josephus問題的解決需要采用循環(huán)鏈表，先構(gòu)造一個有n個結(jié)點的不帶頭結(jié)點的單循環(huán)鏈表，再給出報數(shù)上限值m(假設(shè)m>1).在鏈表的首結(jié)點開始從1計數(shù)，計到m-1時，將下一個結(jié)點從鏈表中刪除，然后再從被刪除結(jié)點的下一個結(jié)點又從1開始計數(shù)，數(shù)到m-1，再將其下一個結(jié)點從單循環(huán)鏈表刪除，直到剩下一半結(jié)點為止。4.模塊劃分：

①建立一個由頭指針head指示的有n個結(jié)點的約瑟夫單循環(huán)鏈表InitRing。②生者與死者的選擇：p指向鏈表第一個結(jié)點，初始化i為1；while(i<=n/2)//刪除一半的結(jié)點{從p指向的結(jié)點沿鏈前進k-1步，刪除第k個結(jié)點（q所指向的結(jié)點；p指向q的下一個結(jié)點；輸出其位置q->data;}③輸出所有生者的編號。5.數(shù)據(jù)結(jié)構(gòu)：

程序包含以下函數(shù)：LinkListInitRing(intn,LinkListR)：初始化一個約瑟夫環(huán)。LinkListDeleteDeath(intn,intk,LinkListR)：尋找被扔入大海的人voidoutput(LinkListR)：輸出所有生存者函數(shù)

6.源程序：

#include<stdio.h>#include<malloc.h>typedefstructNode{ intnum; structNode*next;}Node,*LinkList;LinkListInitRing(intn,LinkListR){ Node*q,*p; inti; R=q=(Node*)malloc(sizeof(Node)); for(i=1;i<n;i++) { p=(Node*)malloc(sizeof(Node)); q->num=i; q->next=p; q=p; } p->num=n; p->next=R; returnR;}LinkListDeleteDeath(intn,intk,LinkListR){ inti,j; Node*p,*q; p=R; for(i=1;i<=n/2;i++)//刪除一半結(jié)點 { for(j=1;j<=k-2;j++)//沿鏈前進k-2步，找到被刪除結(jié)點的前驅(qū)結(jié)點 p=p->next; q=p->next;//q為被刪除結(jié)點 p->next=q->next; printf("%4d",q->num);//輸入一個被拋入大海者 free(q); p=p->next; }//for returnp;}/*輸入所有生存者函數(shù)*/voidoutput(LinkListR){ Node*p; p=R; do {printf("%4d",p->num); p=p->next; } while(p!=R);}voidmain(){ LinkListR; intn,m; printf("總?cè)藬?shù)n,報數(shù)上限m(之間用,分隔):"); scanf("%d,%d",&n,&m); R=InitRing(n,R); output(R); printf("\n被拋入大海的人有:"); R=DeleteDeath(n,m,R); printf("\n生存下來的人有:"); output(R); printf("\n");}7.測試情況：截圖二、二叉樹的基本操作的實現(xiàn)1.問題描述：在主程序中編寫一個簡單的菜單，將有關(guān)二叉樹的操作整合在一起，包括遞歸算法和非遞歸算法。

2.基本要求：建立一棵二叉樹的存儲結(jié)構(gòu)、遍歷一棵二叉樹、統(tǒng)計二叉樹葉子結(jié)點的個數(shù)、求二叉樹的深度

3.算法思想：建立一棵二叉樹的存儲結(jié)構(gòu);二叉樹常用的存儲結(jié)構(gòu)為二叉鏈表形式，二叉鏈表由一個數(shù)據(jù)項Data和兩個指針項Lchild、rchild組成。Data用于存放結(jié)點的值，lchild/rchild分別指向該結(jié)點的左右子樹。遍歷一棵二叉樹:先序遍歷：若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。中序遍歷：若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。后序遍歷：若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。統(tǒng)計二叉樹葉子結(jié)點的個數(shù):先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點”的操作改為：若是葉子，則計數(shù)器增1。求二叉樹的深度:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加1。

4.模塊劃分：①先序遍歷構(gòu)造二叉樹②層次遍歷輸出二叉樹③先序、中序、后序遍歷二叉樹④葉子結(jié)點統(tǒng)計⑤二叉樹的深度5.數(shù)據(jù)結(jié)構(gòu)：

程序包含以下函數(shù)：BiTreeCreateBiTree(BiTreeT)/*先序遍歷二叉樹*/voidLevelOrder(BiTreeT)/*層次遍歷輸出*/StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType))先序遍歷二叉樹StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType))中序遍歷二叉樹StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType))后序遍歷二叉樹intleafcount(BiTreebt){/*統(tǒng)計二叉樹bt中葉子節(jié)點數(shù)*/intdepth(BiTreeT){/*求二叉樹的深度*/

6.源程序：

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAX20#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/*先序遍歷二叉樹*/BiTreeCreateBiTree(BiTreeT){ charch; scanf("%c",&ch); if(ch=='#')T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T)exit(OVERFLOW); T->data=ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); }//else returnT;}//CreateBiTree/*層次遍歷輸出*/voidLevelOrder(BiTreeT){ BiTreeQueue[MAX],b; /*用一維數(shù)組表示隊列，front和rear分別表示隊守和隊尾指針*/ intfront,rear; front=rear=0; if(T)/*若數(shù)非空*/ { Queue[rear++]=T; while(front!=rear) { b=Queue[front++]; printf("%2c",b->data); if(b->lchild!=NULL)Queue[rear++]=b->lchild; if(b->rchild!=NULL)Queue[rear++]=b->rchild; }//while }//if}/*LevelOrder*/StatusPrintElement(TElemTypee){ printf("%2c",e); returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){ inti,j,k; if(T==NULL) returnOK; else { i=Visit(T->data); if(i) { j=PreOrderTraverse(T->lchild,Visit); if(j) { k=PreOrderTraverse(T->rchild,Visit); if(k)returnOK; }//if(j) }//if(i) elsereturnERROR; }//else}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){ if(T) { if(InOrderTraverse(T->lchild,Visit)) if(Visit(T->data)) if(InOrderTraverse(T->rchild,Visit))returnOK; returnERROR; }elsereturnOK;}//InOrderTaverseStatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){ if(T) { if(PostOrderTraverse(T->lchild,Visit)) if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data))returnOK; returnERROR; } elsereturnOK;}//PostOrderTraverseintleafcount(BiTreebt){/*統(tǒng)計二叉樹bt中葉子節(jié)點數(shù)*/ intn; if(bt==NULL)n=0; elseif(bt->lchild==NULL&&bt->rchild==NULL)n=1; elsen=leafcount(bt->lchild)+leafcount(bt->rchild); /*二叉樹葉子節(jié)點數(shù)等于左右子樹的節(jié)點數(shù)之和*/ returnn;}intdepth(BiTreeT){/*求二叉樹的深度*/ intdep1,dep2; if(T==NULL) returnERROR; else { dep1=depth(T->lchild); dep2=depth(T->rchild); returndep1>dep2?dep1+1:dep2+1; }//else}/*depth*/voidmain(){ BiTreeT=NULL,B=NULL; intm; printf("*****構(gòu)造一棵二叉樹并統(tǒng)計葉子節(jié)點數(shù)的個數(shù)********\n"); printf("*******構(gòu)造一顆二叉樹并對其進行遍歷******\n"); printf("請讀入構(gòu)造二叉樹的字符序列:"); B=CreateBiTree(T); if(B) { m=leafcount(B); printf("二叉樹建立成功!"); printf("\n該二叉樹的先序遍歷是:"); PreOrderTraverse(B,PrintElement); printf("\n該二叉樹的中序遍歷是:"); InOrderTraverse(B,PrintElement); printf("\n該二叉樹的后續(xù)遍歷是:"); PostOrderTraverse(B,PrintElement); printf("\n該二叉樹的層次遍歷是:"); LevelOrder(B);printf("\n該二叉樹的葉子節(jié)點數(shù)是:%d\n",m); printf("\n二叉樹的深度是:%d\n",depth(B)); printf("\n"); } else printf("二叉樹建立不成功!!!\n");}測試情況：截圖：三、圖的基本操作的實現(xiàn)1.問題描述：在主程序中建立一個菜單，實現(xiàn)圖的基本操作。2.基本要求：建立圖的存儲結(jié)構(gòu)，實現(xiàn)圖的深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷以及利用圖的拓?fù)渑判蝌炞C圖中是否存在環(huán)。

3.算法思想：編寫函數(shù)實現(xiàn)圖的鄰接矩陣結(jié)構(gòu)，然后編寫函數(shù)實現(xiàn)鄰接表結(jié)構(gòu)轉(zhuǎn)換連通圖的深度優(yōu)先搜索遍歷：從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。非連通圖的深度優(yōu)先搜索遍歷：首先將圖中每個頂點的訪問標(biāo)志設(shè)為FALSE,之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。廣度優(yōu)先搜索遍歷：從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。

4.模塊劃分：①建立圖的存儲結(jié)構(gòu)②實現(xiàn)圖的深度優(yōu)先搜索遍歷（遞歸和非遞歸）③廣度優(yōu)先搜索遍歷④利用圖的拓?fù)渑判蝌炞C圖中是否存在環(huán)。

數(shù)據(jù)結(jié)構(gòu)：

程序包含以下函數(shù)：ALGraph*MatToList(MGraphg)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/voidDispAdj(ALGraph*G)/*輸出鄰接表G*/voidDFS(ALGraph*G,intv)深度優(yōu)先遍歷圖的的遞歸算法voidDFS1(ALGraph*G,intv)深度優(yōu)先遍歷圖的非遞歸算法voidBFS(ALGraph*G,intv)廣度優(yōu)先遍歷圖的算法voidCALGraph::If_Circle()//用拓?fù)渑判蚺袛嘤邢驁D是否存在環(huán)

6.源程序：

typedefintInfoType;#defineMAXV100/*最大頂點個數(shù)*//*以下定義鄰接矩陣類型*/typedefstruct{ intno;/*頂點編號*/ InfoTypeinfo;/*頂點其他信息*/}VertexType;/*頂點類型*/typedefstruct/*圖的定義*/{ intedges[MAXV][MAXV];/*鄰接矩陣*/ intvexnum,arcnum;/*頂點數(shù)，弧數(shù)*/ VertexTypevexs[MAXV];/*存放頂點信息*/}MGraph;/*圖的鄰接矩陣類型*//*以下定義鄰接表類型*/typedefstructANode/*弧的結(jié)點結(jié)構(gòu)類型*/{ intadjvex;/*該弧的終點位置*/ structANode*nextarc;/*指向下一條弧的指針*/ InfoTypeinfo;/*該弧的相關(guān)信息，這里用于存放權(quán)值*/}ArcNode;typedefintVertex;typedefstructVnode/*鄰接表頭結(jié)點的類型*/{ Vertexdata;/*頂點信息*/ ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV];/*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist;/*鄰接表*/ intn,e;/*圖中頂點數(shù)n和邊數(shù)e*/}ALGraph;/*圖的鄰接表類型*/#include<stdio.h>#include<iostream>usingnamespacestd;constintMAX_VERTEX_NUM=20;#include<malloc.h>intvisited[MAXV];/*全局?jǐn)?shù)組*/ALGraph*MatToList(MGraphg)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{ inti,j,n=g.vexnum; ArcNode*p; ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i<n;i++)/*給鄰接表中所有頭結(jié)點的指針域置初值*/ G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++)/*檢查鄰接矩陣中每個元素*/ for(j=n-1;j>=0;j--) if(g.edges[i][j]!=0)/*鄰接矩陣的當(dāng)前元素不為0*/ { p=(ArcNode*)malloc(sizeof(ArcNode));/*創(chuàng)建一個接點*p*/ p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc;/*將*p鏈到鏈表后*/ G->adjlist[i].firstarc=p; } G->n=n;G->e=g.arcnum; returnG;}voidDispAdj(ALGraph*G)/*輸出鄰接表G*/{ inti; ArcNode*p; for(i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; if(p!=NULL)printf("%3d:",i); while(p!=NULL) { printf("%3d",p->adjvex); p=p->nextarc; } printf("\n"); }}voidDFS(ALGraph*G,intv){ ArcNode*p; visited[v]=1;/*置已訪問標(biāo)記*/ printf("%3d",v);/*輸出被訪問頂點的編號*/ p=G->adjlist[v].firstarc;/*p指向頂點v的第一條弧的弧頭結(jié)點*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若p->adjvex頂點未訪問，遞歸訪問它*/ DFS(G,p->adjvex); p=p->nextarc;/*p指向頂點v的下一條弧的弧頭結(jié)點*/ }}voidDFS1(ALGraph*G,intv){ inti,visited[MAXV],St[MAXV],top=-1; ArcNode*p; for(i=0;i<G->n;i++) visited[i]=0;/*結(jié)點訪問標(biāo)志均置成0*/ printf("%3d",v);/*訪問頂點v*/ top++;/*v入棧*/ St[top]=v;visited[v]=1; while(top>-1)/*棧不空時循環(huán)*/ { v=St[top];/*取棧頂元素*/ p=G->adjlist[v].firstarc; while(p!=NULL&&visited[p->adjvex]==1) p=p->nextarc; if(p==NULL)/*若沒有退到前一個*/ top--; else/*若有，選擇一個*/ { v=p->adjvex; printf("%3d",v);/*訪問頂點*/ visited[v]=1; top++;/*入棧*/ St[top]=v; } } printf("\n");}voidBFS(ALGraph*G,intv){ ArcNode*p; intqueue[MAXV],front=0,rear=0;/*定義循環(huán)隊列并初始化*/ intvisited[MAXV];/*定義存放結(jié)點的訪問標(biāo)志的數(shù)組*/ intw,i; for(i=0;i<G->n;i++)visited[i]=0;/*訪問標(biāo)志數(shù)組初始化*/ printf("%3d",v);/*輸出被訪問結(jié)點的編號*/ visited[v]=1;/*置已訪問標(biāo)志*/ rear=(rear+1)%MAXV; queue[rear]=v;/*v進隊*/ while(front!=rear)/*若隊列不空時循環(huán)*/ { front=(front+1)%MAXV; w=queue[front];/*出隊并賦給w*/ p=G->adjlist[w].firstarc;/*找與頂點w鄰接的第一個頂點*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若當(dāng)前鄰接頂點未被訪問*/ { printf("%3d",p->adjvex);/*訪問相鄰頂點*/ visited[p->adjvex]=1;/*置該頂點已被訪問的標(biāo)志*/ rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc;/*找下一個鄰接頂點*/ } } printf("\n");}classCSqStack{private: intbase[MAX_VERTEX_NUM]; inttop;public: CSqStack(); intStackEmpty(); voidPush(int); intPop();};CSqStack::CSqStack(){ top=-1;}intCSqStack::StackEmpty()//判斷棧是否為空{(diào) if(-1==top) return1; elsereturn0;}voidCSqStack::Push(intx)//入棧{ top++; base[top]=x;}intCSqStack::Pop()//出棧{ intc; if(-1!=top) c=base[top]; top--; returnc;}structArcNode1//表結(jié)點{ intadjvex;//該弧所指向的頂點的位置 ArcNode1*nextarc;//指向下一條弧的指針};structVNode1//頭結(jié)點{ chardata;//該結(jié)點的字符 ArcNode1*firstarc;//指向下一個結(jié)點的指針};classCALGraph{public: VNode1vertices[MAX_VERTEX_NUM]; intvexnum,arcnum;public: voidCreateGraph(); intLocateVex(charc); voidFindIndegree(intindegree[]); voidIf_Circle();};voidCALGraph::CreateGraph(){//創(chuàng)建有向圖 char*ch; chart,h; inti,j; ArcNode1*p=NULL; cout<<"輸入頂點數(shù):"; cin>>vexnum; if(vexnum<0) { cout<<"ERROR";//頂點數(shù)不能為負(fù) return; } cout<<"輸入邊數(shù)："; cin>>arcnum; if(arcnum<0) { cout<<"ERROR";//邊數(shù)不能為負(fù) return; } ch=newchar[vexnum]; cout<<"輸入各頂點的符號:"; cin>>ch; for(intm=0;m<vexnum;m++) { vertices[m].data=ch[m];//輸入各頂點的符號 vertices[m].firstarc=NULL; } for(m=1;m<=arcnum;m++) { cout<<"輸入邊："; cin>>ch; t=ch[0];h=ch[1];//t為弧尾,h為弧頭 i=LocateVex(t); j=LocateVex(h); if(i<0||j<0) { cout<<"ERROR";//頂點未找到 return; } p=newArcNode1; p->adjvex=j; p->nextarc=NULL; ArcNode1*q=NULL; if(!vertices[i].firstarc)vertices[i].firstarc=p; else { for(q=vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } }}intCALGraph::LocateVex(charc){ inti; for(i=0;i<vexnum;i++) { if(vertices[i].data==c) returni; } return-1;}voidCALGraph::FindIndegree(intindegree[])//求頂點的入度{ for(inti=0;i<vexnum;i++) indegree[i]=0; f