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

2.基本要求：

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

3.算法思想：

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

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

程序包含以下函數(shù)：LinkListInitRing(intn,LinkListR)：初始化一個(gè)約瑟夫環(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é)點(diǎn) { for(j=1;j<=k-2;j++)//沿鏈前進(jìn)k-2步，找到被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) p=p->next; q=p->next;//q為被刪除結(jié)點(diǎn) p->next=q->next; printf("%4d",q->num);//輸入一個(gè)被拋入大海者 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,報(bào)數(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.測(cè)試情況：截圖二、二叉樹的基本操作的實(shí)現(xiàn)1.問題描述：在主程序中編寫一個(gè)簡(jiǎn)單的菜單，將有關(guān)二叉樹的操作整合在一起，包括遞歸算法和非遞歸算法。

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

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

4.模塊劃分：①先序遍歷構(gòu)造二叉樹②層次遍歷輸出二叉樹③先序、中序、后序遍歷二叉樹④葉子結(jié)點(diǎn)統(tǒng)計(jì)⑤二叉樹的深度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)計(jì)二叉樹bt中葉子節(jié)點(diǎn)數(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ù)組表示隊(duì)列，front和rear分別表示隊(duì)守和隊(duì)尾指針*/ 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)計(jì)二叉樹bt中葉子節(jié)點(diǎn)數(shù)*/ intn; if(bt==NULL)n=0; elseif(bt->lchild==NULL&&bt->rchild==NULL)n=1; elsen=leafcount(bt->lchild)+leafcount(bt->rchild); /*二叉樹葉子節(jié)點(diǎn)數(shù)等于左右子樹的節(jié)點(diǎn)數(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)計(jì)葉子節(jié)點(diǎn)數(shù)的個(gè)數(shù)********\n"); printf("*******構(gòu)造一顆二叉樹并對(duì)其進(jìn)行遍歷******\n"); printf("請(qǐng)讀入構(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é)點(diǎn)數(shù)是:%d\n",m); printf("\n二叉樹的深度是:%d\n",depth(B)); printf("\n"); } else printf("二叉樹建立不成功!!!\n");}測(cè)試情況：截圖：三、圖的基本操作的實(shí)現(xiàn)1.問題描述：在主程序中建立一個(gè)菜單，實(shí)現(xiàn)圖的基本操作。2.基本要求：建立圖的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷以及利用圖的拓?fù)渑判蝌?yàn)證圖中是否存在環(huán)。

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

4.模塊劃分：①建立圖的存儲(chǔ)結(jié)構(gòu)②實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷（遞歸和非遞歸）③廣度優(yōu)先搜索遍歷④利用圖的拓?fù)渑判蝌?yàn)證圖中是否存在環(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/*最大頂點(diǎn)個(gè)數(shù)*//*以下定義鄰接矩陣類型*/typedefstruct{ intno;/*頂點(diǎn)編號(hào)*/ InfoTypeinfo;/*頂點(diǎn)其他信息*/}VertexType;/*頂點(diǎn)類型*/typedefstruct/*圖的定義*/{ intedges[MAXV][MAXV];/*鄰接矩陣*/ intvexnum,arcnum;/*頂點(diǎn)數(shù)，弧數(shù)*/ VertexTypevexs[MAXV];/*存放頂點(diǎn)信息*/}MGraph;/*圖的鄰接矩陣類型*//*以下定義鄰接表類型*/typedefstructANode/*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/{ intadjvex;/*該弧的終點(diǎn)位置*/ structANode*nextarc;/*指向下一條弧的指針*/ InfoTypeinfo;/*該弧的相關(guān)信息，這里用于存放權(quán)值*/}ArcNode;typedefintVertex;typedefstructVnode/*鄰接表頭結(jié)點(diǎn)的類型*/{ Vertexdata;/*頂點(diǎn)信息*/ ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV];/*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist;/*鄰接表*/ intn,e;/*圖中頂點(diǎn)數(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é)點(diǎn)的指針域置初值*/ G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++)/*檢查鄰接矩陣中每個(gè)元素*/ for(j=n-1;j>=0;j--) if(g.edges[i][j]!=0)/*鄰接矩陣的當(dāng)前元素不為0*/ { p=(ArcNode*)malloc(sizeof(ArcNode));/*創(chuàng)建一個(gè)接點(diǎn)*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);/*輸出被訪問頂點(diǎn)的編號(hào)*/ p=G->adjlist[v].firstarc;/*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若p->adjvex頂點(diǎn)未訪問，遞歸訪問它*/ DFS(G,p->adjvex); p=p->nextarc;/*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/ }}voidDFS1(ALGraph*G,intv){ inti,visited[MAXV],St[MAXV],top=-1; ArcNode*p; for(i=0;i<G->n;i++) visited[i]=0;/*結(jié)點(diǎn)訪問標(biāo)志均置成0*/ printf("%3d",v);/*訪問頂點(diǎn)v*/ top++;/*v入棧*/ St[top]=v;visited[v]=1; while(top>-1)/*棧不空時(shí)循環(huán)*/ { v=St[top];/*取棧頂元素*/ p=G->adjlist[v].firstarc; while(p!=NULL&&visited[p->adjvex]==1) p=p->nextarc; if(p==NULL)/*若沒有退到前一個(gè)*/ top--; else/*若有，選擇一個(gè)*/ { v=p->adjvex; printf("%3d",v);/*訪問頂點(diǎn)*/ visited[v]=1; top++;/*入棧*/ St[top]=v; } } printf("\n");}voidBFS(ALGraph*G,intv){ ArcNode*p; intqueue[MAXV],front=0,rear=0;/*定義循環(huán)隊(duì)列并初始化*/ intvisited[MAXV];/*定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組*/ intw,i; for(i=0;i<G->n;i++)visited[i]=0;/*訪問標(biāo)志數(shù)組初始化*/ printf("%3d",v);/*輸出被訪問結(jié)點(diǎn)的編號(hào)*/ visited[v]=1;/*置已訪問標(biāo)志*/ rear=(rear+1)%MAXV; queue[rear]=v;/*v進(jìn)隊(duì)*/ while(front!=rear)/*若隊(duì)列不空時(shí)循環(huán)*/ { front=(front+1)%MAXV; w=queue[front];/*出隊(duì)并賦給w*/ p=G->adjlist[w].firstarc;/*找與頂點(diǎn)w鄰接的第一個(gè)頂點(diǎn)*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若當(dāng)前鄰接頂點(diǎn)未被訪問*/ { printf("%3d",p->adjvex);/*訪問相鄰頂點(diǎn)*/ visited[p->adjvex]=1;/*置該頂點(diǎn)已被訪問的標(biāo)志*/ rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc;/*找下一個(gè)鄰接頂點(diǎn)*/ } } 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é)點(diǎn){ intadjvex;//該弧所指向的頂點(diǎn)的位置 ArcNode1*nextarc;//指向下一條弧的指針};structVNode1//頭結(jié)點(diǎn){ chardata;//該結(jié)點(diǎn)的字符 ArcNode1*firstarc;//指向下一個(gè)結(jié)點(diǎn)的指針};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<<"輸入頂點(diǎn)數(shù):"; cin>>vexnum; if(vexnum<0) { cout<<"ERROR";//頂點(diǎn)數(shù)不能為負(fù) return; } cout<<"輸入邊數(shù)："; cin>>arcnum; if(arcnum<0) { cout<<"ERROR";//邊數(shù)不能為負(fù) return; } ch=newchar[vexnum]; cout<<"輸入各頂點(diǎn)的符號(hào):"; cin>>ch; for(intm=0;m<vexnum;m++) { vertices[m].data=ch[m];//輸入各頂點(diǎn)的符號(hào) 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";//頂點(diǎn)未找到 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[])//求頂點(diǎn)的入度{ for(inti=0;i<vexnum;i++) indegree[i]=0; f