数据结构课程设计报告

数据结构课程设计报告书课程设计的名称：一、生死者游戏1.问题描述：有n个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入大海，其余人才能幸免遇难．无奈，大家只得同意这种办法，并议定n个人围坐一圈，从1,2,3…到n进行编号。由第一个人数起，依次报数，数到第m人，将它扔进大海中，然后再从他的下一个人数起，数到第m人，再将他扔进大海，如此循环进行，直到剩下一半人为止，问哪几个人是将被扔进大海的人。

2.基本要求：

利用单向循环链表存储结构模拟此过程，输出生者的编号。

3.算法思想：

该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的不带头结点的单循环链表，再给出报数上限值m(假设m>1).在链表的首结点开始从1计数，计到m-1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到m-1，再将其下一个结点从单循环链表删除，直到剩下一半结点为止。4.模块划分：

①建立一个由头指针head指示的有n个结点的约瑟夫单循环链表InitRing。②生者与死者的选择：p指向链表第一个结点，初始化i为1；while(i<=n/2)//删除一半的结点{从p指向的结点沿链前进k-1步，删除第k个结点（q所指向的结点；p指向q的下一个结点；输出其位置q->data;}③输出所有生者的编号。5.数据结构：

程序包含以下函数：LinkListInitRing(intn,LinkListR)：初始化一个约瑟夫环。LinkListDeleteDeath(intn,intk,LinkListR)：寻找被扔入大海的人voidoutput(LinkListR)：输出所有生存者函数

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++)//删除一半结点 { for(j=1;j<=k-2;j++)//沿链前进k-2步，找到被删除结点的前驱结点 p=p->next; q=p->next;//q为被删除结点 p->next=q->next; printf("%4d",q->num);//输入一个被抛入大海者 free(q); p=p->next; }//for returnp;}/*输入所有生存者函数*/voidoutput(LinkListR){ Node*p; p=R; do {printf("%4d",p->num); p=p->next; } while(p!=R);}voidmain(){ LinkListR; intn,m; printf("总人数n,报数上限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.测试情况：截图二、二叉树的基本操作的实现1.问题描述：在主程序中编写一个简单的菜单，将有关二叉树的操作整合在一起，包括递归算法和非递归算法。

2.基本要求：建立一棵二叉树的存储结构、遍历一棵二叉树、统计二叉树叶子结点的个数、求二叉树的深度

3.算法思想：建立一棵二叉树的存储结构;二叉树常用的存储结构为二叉链表形式，二叉链表由一个数据项Data和两个指针项Lchild、rchild组成。Data用于存放结点的值，lchild/rchild分别指向该结点的左右子树。遍历一棵二叉树:先序遍历：若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中序遍历：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后序遍历：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。统计二叉树叶子结点的个数:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。求二叉树的深度:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

4.模块划分：①先序遍历构造二叉树②层次遍历输出二叉树③先序、中序、后序遍历二叉树④叶子结点统计⑤二叉树的深度5.数据结构：

程序包含以下函数：BiTreeCreateBiTree(BiTreeT)/*先序遍历二叉树*/voidLevelOrder(BiTreeT)/*层次遍历输出*/StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType))先序遍历二叉树StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType))中序遍历二叉树StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType))后序遍历二叉树intleafcount(BiTreebt){/*统计二叉树bt中叶子节点数*/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; /*用一维数组表示队列，front和rear分别表示队守和队尾指针*/ intfront,rear; front=rear=0; if(T)/*若数非空*/ { 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){/*统计二叉树bt中叶子节点数*/ intn; if(bt==NULL)n=0; elseif(bt->lchild==NULL&&bt->rchild==NULL)n=1; elsen=leafcount(bt->lchild)+leafcount(bt->rchild); /*二叉树叶子节点数等于左右子树的节点数之和*/ 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("*****构造一棵二叉树并统计叶子节点数的个数********\n"); printf("*******构造一颗二叉树并对其进行遍历******\n"); printf("请读入构造二叉树的字符序列:"); B=CreateBiTree(T); if(B) { m=leafcount(B); printf("二叉树建立成功!"); printf("\n该二叉树的先序遍历是:"); PreOrderTraverse(B,PrintElement); printf("\n该二叉树的中序遍历是:"); InOrderTraverse(B,PrintElement); printf("\n该二叉树的后续遍历是:"); PostOrderTraverse(B,PrintElement); printf("\n该二叉树的层次遍历是:"); LevelOrder(B);printf("\n该二叉树的叶子节点数是:%d\n",m); printf("\n二叉树的深度是:%d\n",depth(B)); printf("\n"); } else printf("二叉树建立不成功!!!\n");}测试情况：截图：三、图的基本操作的实现1.问题描述：在主程序中建立一个菜单，实现图的基本操作。2.基本要求：建立图的存储结构，实现图的深度优先搜索遍历，广度优先搜索遍历以及利用图的拓扑排序验证图中是否存在环。

3.算法思想：编写函数实现图的邻接矩阵结构，然后编写函数实现邻接表结构转换连通图的深度优先搜索遍历：从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。非连通图的深度优先搜索遍历：首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。广度优先搜索遍历：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

4.模块划分：①建立图的存储结构②实现图的深度优先搜索遍历（递归和非递归）③广度优先搜索遍历④利用图的拓扑排序验证图中是否存在环。

数据结构：

程序包含以下函数：ALGraph*MatToList(MGraphg)/*将邻接矩阵g转换成邻接表G*/voidDispAdj(ALGraph*G)/*输出邻接表G*/voidDFS(ALGraph*G,intv)深度优先遍历图的的递归算法voidDFS1(ALGraph*G,intv)深度优先遍历图的非递归算法voidBFS(ALGraph*G,intv)广度优先遍历图的算法voidCALGraph::If_Circle()//用拓扑排序判断有向图是否存在环

6.源程序：

typedefintInfoType;#defineMAXV100/*最大顶点个数*//*以下定义邻接矩阵类型*/typedefstruct{ intno;/*顶点编号*/ InfoTypeinfo;/*顶点其他信息*/}VertexType;/*顶点类型*/typedefstruct/*图的定义*/{ intedges[MAXV][MAXV];/*邻接矩阵*/ intvexnum,arcnum;/*顶点数，弧数*/ VertexTypevexs[MAXV];/*存放顶点信息*/}MGraph;/*图的邻接矩阵类型*//*以下定义邻接表类型*/typedefstructANode/*弧的结点结构类型*/{ intadjvex;/*该弧的终点位置*/ structANode*nextarc;/*指向下一条弧的指针*/ InfoTypeinfo;/*该弧的相关信息，这里用于存放权值*/}ArcNode;typedefintVertex;typedefstructVnode/*邻接表头结点的类型*/{ Vertexdata;/*顶点信息*/ ArcNode*firstarc;/*指向第一条弧*/}VNode;typedefVNodeAdjList[MAXV];/*AdjList是邻接表类型*/typedefstruct{ AdjListadjlist;/*邻接表*/ intn,e;/*图中顶点数n和边数e*/}ALGraph;/*图的邻接表类型*/#include<stdio.h>#include<iostream>usingnamespacestd;constintMAX_VERTEX_NUM=20;#include<malloc.h>intvisited[MAXV];/*全局数组*/ALGraph*MatToList(MGraphg)/*将邻接矩阵g转换成邻接表G*/{ inti,j,n=g.vexnum; ArcNode*p; ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i<n;i++)/*给邻接表中所有头结点的指针域置初值*/ G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++)/*检查邻接矩阵中每个元素*/ for(j=n-1;j>=0;j--) if(g.edges[i][j]!=0)/*邻接矩阵的当前元素不为0*/ { p=(ArcNode*)malloc(sizeof(ArcNode));/*创建一个接点*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;/*置已访问标记*/ printf("%3d",v);/*输出被访问顶点的编号*/ p=G->adjlist[v].firstarc;/*p指向顶点v的第一条弧的弧头结点*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若p->adjvex顶点未访问，递归访问它*/ DFS(G,p->adjvex); p=p->nextarc;/*p指向顶点v的下一条弧的弧头结点*/ }}voidDFS1(ALGraph*G,intv){ inti,visited[MAXV],St[MAXV],top=-1; ArcNode*p; for(i=0;i<G->n;i++) visited[i]=0;/*结点访问标志均置成0*/ printf("%3d",v);/*访问顶点v*/ top++;/*v入栈*/ St[top]=v;visited[v]=1; while(top>-1)/*栈不空时循环*/ { 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;/*定义循环队列并初始化*/ intvisited[MAXV];/*定义存放结点的访问标志的数组*/ intw,i; for(i=0;i<G->n;i++)visited[i]=0;/*访问标志数组初始化*/ printf("%3d",v);/*输出被访问结点的编号*/ visited[v]=1;/*置已访问标志*/ rear=(rear+1)%MAXV; queue[rear]=v;/*v进队*/ while(front!=rear)/*若队列不空时循环*/ { front=(front+1)%MAXV; w=queue[front];/*出队并赋给w*/ p=G->adjlist[w].firstarc;/*找与顶点w邻接的第一个顶点*/ while(p!=NULL) { if(visited[p->adjvex]==0)/*若当前邻接顶点未被访问*/ { printf("%3d",p->adjvex);/*访问相邻顶点*/ visited[p->adjvex]=1;/*置该顶点已被访问的标志*/ 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()//判断栈是否为空{ if(-1==top) return1; elsereturn0;}voidCSqStack::Push(intx)//入栈{ top++; base[top]=x;}intCSqStack::Pop()//出栈{ intc; if(-1!=top) c=base[top]; top--; returnc;}structArcNode1//表结点{ intadjvex;//该弧所指向的顶点的位置 ArcNode1*nextarc;//指向下一条弧的指针};structVNode1//头结点{ chardata;//该结点的字符 ArcNode1*firstarc;//指向下一个结点的指针};classCALGraph{public: VNode1vertices[MAX_VERTEX_NUM]; intvexnum,arcnum;public: voidCreateGraph(); intLocateVex(charc); voidFindIndegree(intindegree[]); voidIf_Circle();};voidCALGraph::CreateGraph(){//创建有向图 char*ch; chart,h; inti,j; ArcNode1*p=NULL; cout<<"输入顶点数:"; cin>>vexnum; if(vexnum<0) { cout<<"ERROR";//顶点数不能为负 return; } cout<<"输入边数："; cin>>arcnum; if(arcnum<0) { cout<<"ERROR";//边数不能为负 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