[工学]数据结构课程设计.docVIP

数据结构课程设计报告专 业： 班 级： 姓 名： 学 号： 指导教师： 2011年 4 月 27日一、 设计题目（一）编程实现二叉排序树的创建于操作（二）Josephu问题的实现（三）迷宫问题求解（四）编程实现无向图的基本操作二、设计内容（一）以二叉链表作二叉排序树中序遍历得有序的存储结构，结点的数据域为int类型，实现以下几个操作：(1)以0为输入结束标志，输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作非递归中序遍历，输出遍历结果；(3)计算二叉排序树T查找成功的平均查找长度，输出结果；(4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“x不存在”；(5) 输入元素x，查找二叉排序树T，若整棵树不存在含值为x的结点，则插入该结点，并作中序遍历(执行操作2)；否则输出信息“x已经存在”。 （二）Josephu问题的实现。Josephu问题为：设编号为1，2， n的n个人围坐一圈，约定编号为k（1=kn 输出：k should not bigger than n.（三）迷宫问题求解 迷宫有一个入口，一个出口。一个人从入口走进迷宫，目标是找到出口。阴影部分和迷宫的外框为墙，每一步走一格，每格有四个可走的方向，探索顺序为：南、东、北、西。 输入：输入迷宫数组的行数、列数和迷宫的形状（0为可通，1为墙）。输出：若有解，输出从入口到出口的一条路径，否则输出 there is no solution!（四）编程实现无向图的基本操作。(1)自选存储结构，输入含n个顶点和e条边的图G；(2)求每个顶点的度，输出结果；(3)指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列； (4)指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列；(5)输入顶点x，查找图G:若存在含x的顶点（深度优先or广度优先），则删除该结点及与之相关连的边，并作DFS遍历(执行操作3)；否则输出信息“不存在x”；(6)判断图G是否是连通图（遍历的顶点与创建时的顶点个数是否一样），输出信息“YES”/“NO”； 三、概要设计（一）编程实现二叉排序树的创建于操作。本程序所使用的模块及个模块间的调用关系（二）Josephu问题的实现本程序所使用的模块及个模块间的调用关系：（三）迷宫问题求解本程序所使用的模块及个模块间的调用关系：（四）编程实现无向图的基本操作。本程序所使用的模块及个模块间的调用关系：四、详细设计（一）编程实现二叉排序树的创建与操作1，二叉排序树类型typedef struct bitnodeint data;struct bitnode *lson,*rson;int count;/*计数器，用于计算平均查找长度*/bitnode,*bitree;2,栈类型typedef struct seqstackbitree b100;int top;stack;3，栈的操作算法int isempty(stack* s)/*判空操作*/if(s-top!=-1) return 1;/*若栈空返回0，否则返回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!);/*若栈不空，则进行出栈操作*/elses-top-;return(s-bs-top+1);4，对二叉排序树的操作算法：bitree creatbitree()/*创建二叉排序树*/bitree t=NULL,p;int data;printf(Please input the data to creat the tree or input 0 to quit:n);scanf(%d,&data);/*输入一个数据*/while(data!=0)if(t=NULL)/*若为空树，则将输入的数据赋给树根*/p=(bitnode*)malloc(sizeof(bitnode);p-data=data;p-lson=p-rson=NULL;t=p;elseinsert(t,data);/*如果不是空树，则调用插入函数将输入的数插入合适的位置*/scanf(%d,&data); return(t);/*返回指向树根的指针*/void traverse(bitree t)/*非递归中序遍历二叉排序树*/stack s;bitree p=t;s.top=-1;/*栈的初始化*/while(p!=NULL|isempty(&s)/*如果不是空树或者栈不为空*/if(p!=NULL)/*若当前指针不为空*/push(&s,p);/*将数据压入栈中*/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;/*栈的初始化*/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为已遍历的结点个数*/l=p;p=p-rson; a=key/num;/*平均查找长度的计算方法*/return a;bitree delete(bitree t,int x)/*删除结点*/bitree p=t,q=p,s;/*q始终指向p的父结点*/while(p!=NULL)/*如果不是空树，则进行查找*/if(x=p-data) break;/*查找成功，跳出循环*/else if(xdata) /*若x小于等于当前结点的数据，去当前结点的左孩子查找*/q=p;p=p-lson;else /*x大于当前结点的数据，则去当前结点的右孩子继续查找*/q=p;p=p-rson; if(p=NULL) printf(nx is not exist.);return t;/*循环结束，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=NULL&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-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);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;/*将要删除结点左子树最下方的右孩子的数据赋给要删除结点，删除左子树最下方的右孩子，使之仍为一个二叉排序树*/else q-lson=s-lson;free(s);traverse(t);return(t);bitree insertbst(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(xdata)q=p; p=p-lson;else q=p;p=p-rson;if(p=NULL) insert(t,x);/*循环结束查找成功，调用插入算将x插入合适的位置*/traverse(t);（二）Josephu问题的实现1，循环链表类型typedef struct nodeint data;struct node *next;lnode,*linklist;2，创建循环链表算法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;inext=(lnode*)malloc(sizeof(lnode);if(p-next=NULL) return(0);p-next-data=i;p=p-next;p-next=head;/令最后一个结点的next指针指向头结点，实现循环链表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-datanext;while(p!=p-next)/若不是只剩下一个结点while(inext;s=s-next;i+;q=p-next; printf(%d ,p-data);j+;if(j%10=0) printf(n);/每输出十个数，另起一行s-next=q;/删除结点pfree(p);p=q;/p指向删除结点的下一个结点i=1;printf(%d ,p-data);/只剩下一个结点的时候，直接输出该节点，结束此函数（三）迷宫问题求解1，坐标位置类型typedef 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=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)/判栈空操作，栈空返回1，否则返回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;iarri0=1;maze-arricol+1=1;for(i=0;iarr0i=1;maze-arrrow+1i=1;/将迷宫四周值设为1，作为围墙，不可通for(i=1;i=row;i+)for(j=1;jarrij=a;/用户输入迷宫形状void printmaze(mazetype *m,int row,int col)/打印迷宫形状 int i,j,count=0;for(i=0;i=row+1;i+)for(j=0;jarrij);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(maze-arrc.rowc.col=0) /如果当前位置可以通过,即是未曾走到的通道块 maze-arrc.rowc.col=3; /留下足迹 e.seat = c; e.di = 1; /创建元素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(,e3.seat.row,e3.seat.col);/探索成功，打印路径return 1;c=nextpos(c,1); /获得下一节点:当前位置的南邻 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.difront=q-rear=0;void enqueue(queue *q,int x)/入队操作if(q-rear+1)%100=q-front) /判循环队列是否满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=(q-front+1)%100;return(q-dataq-front);4.无向图相关操作算法int create(mgraph *g)/用户输入顶点创建无向图，创建成功返回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);/输入顶点数和边数printf(nPlease input the vertexs:);for(i=0;ivexnum;i+)/输入各顶点的值scanf(%d,&g-vexsi);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij.adj=0;/.边的初始化printf(nPlease input the vertexs of each side:);for(k=0;karcnum;k+)/输入各边得两个顶点scanf(%d%d,&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;ivexnum;i+)for(j=0;jvexnum;j+)td+=g-arcsij.adj;printf(%d：The degree is %d.n,g-vexsi,td);td=0;void dfs(mgraph *g,int v)/递归深度优先遍历无向图int u;visitedv=1;/判断是否被访问过的数组，被访问过数组值为1，否则为0visit(g,v);/打印顶点值for(u=0;uvexnum;u+)if(g-arcsvu.adj&!visitedu)dfs(g,u);/递归调用void dfsearch(mgraph *g) int v;for(v=0;vvexnum;v+)visitedv=0;printf(nDFS:);for(v=0;vvexnum;v+)if(!visitedv) dfs(g,v);void bfsearch(mgraph *g) /广度优先遍历无向图queue q;int u,v,w;initqueue(&q);/队列初始化for(u=0;uvexnum;u+)visitedu=0;/访问数组初始值printf(nBFS:);for(u=0;uvexnum;u+)if(!visitedu)/如果没有被访问过enqueue(&q,u);/入队操作while(!(q.rear=q.front)/判队列是否为空v=dequeue(&q);/出队操作visitedv=1;/标记访问过visit(g,v);/打印顶点值for(w=0;wvexnum;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;uvexnum;u+)g-vexsu=g-vexsu+1;/将要删除的顶点后的顶点都向前挪一位for(u=v;uvexnum;u+)/将邻接矩阵要删除结点下面的值都向上移一行for(w=0;wvexnum;w+)g-arcsuw.adj=g-arcsu+1w.adj;for(u=v;uvexnum;u+)/将邻接矩阵要删除结点右面的值都向作移一列for(w=0;wvexnum;w+)g-arcswu.adj=g-arcswu+1.adj;g-vexnum-;/无向图顶点数减1return 1;return 0;void isconnected(mgraph *g)/判连通操作，利用深度遍历的思想int v,count=0;for(v=0;vvexnum;v+)visitedv=0;printf(nDFS:);for(v=0;vvexnum;v+)/此循环用以找到与其他顶点不连通的顶点，如果此循环循环超过一次，则为非连通图，否则为连通图if(!visitedv) dfs(g,v);count+;if(count=1) printf(nYES!);else printf(nNO!);五、测试结果及分析（一）编程实现二叉排序树的创建与操作测试所用二叉排序树：测试结果截图：由以上测试结果可以看出，程序能完成设定的各种操作，没有错误。所以程序达到了原先的设计要求。（二）Josephu问题的实现测试数据1 n=9，k=3，m=2测试结果截图1：测试数据2:n=100，k=3，m=10测试结果截图2：测试数据3（非法输入）：n=10，k=2，m=0。测试数据4（非法输入）：n=10，k=12，m=3。 根据以上测试结果分析可知，程序能完成设定的各种操作，并且当用户非法输入时能提示错误原因，在使用多组数据进行多次运行的过程的