工学数据结构课程设计

1、数据结构课程设计报告专 业：班 级：姓 名：学 号：指导教师：2011年 4 月 27日一、 设计题目（一）编程实现二叉排序树的创建于操作（二）Josephu问题的实现（三）迷宫问题求解（四）编程实现无向图的基本操作二、设计内容（一）以二叉链表作二叉排序树中序遍历得有序的存储结构，结点的数据域为int类型，实现以下几个操作：(1)以0为输入结束标志，输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作非递归中序遍历，输出遍历结果；(3)计算二叉排序树T查找成功的平均查找长度，输出结果；(4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信

2、息“x不存在”；(5) 输入元素x，查找二叉排序树T，若整棵树不存在含值为x的结点，则插入该结点，并作中序遍历(执行操作2)；否则输出信息“x已经存在”。（二）Josephu问题的实现。Josephu问题为：设编号为1，2， n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。输入数据：n,k,m 输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。  （即每输出10个元素，要求输出一个回车符）Jo

3、sephu函数要进行非法参数的判断，非法输入的情况有多种，例如：a) 输入的n、k、m的任一个小于1输出：n,m,k must bigger than 0. b) 输入：k>n输出：k should not bigger than n.（三）迷宫问题求解 迷宫有一个入口，一个出口。一个人从入口走进迷宫，目标是找到出口。阴影部分和迷宫的外框为墙，每一步走一格，每格有四个可走的方向，探索顺序为：南、东、北、西。 输入：输入迷宫数组的行数、列数和迷宫的形状（0为可通，1为墙）。输出：若有解，输出从入口到出口的一条路径，否则输出 there is no solution!（四）编程实现无向图的基

4、本操作。(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

5、问题的实现本程序所使用的模块及个模块间的调用关系：（三）迷宫问题求解本程序所使用的模块及个模块间的调用关系：（四）编程实现无向图的基本操作。本程序所使用的模块及个模块间的调用关系：四、详细设计（一）编程实现二叉排序树的创建与操作1，二叉排序树类型typedef struct bitnodeint data;struct bitnode *lson,*rson;int count;/*计数器，用于计算平均查找长度*/bitnode,*bitree;2,栈类型typedef struct seqstackbitree b100;int top;stack;3，栈的操作算法int isempty(s

6、tack* 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!&qu

7、ot;);/*若栈不空，则进行出栈操作*/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)/*若为空树，则将输入的数据赋给树根*/

8、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)/*如果不是空树

9、或者栈不为空*/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;/*栈的初始化*

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为已遍历的结点个数*/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;/*查找成功，跳出循环*/else if(x<=p->data) /*若x小于等于当前结点的数据，去当前结点的左孩子查找*/q=p;p=p->lson;else /*x大于当前结点的数据，则去当前结点的右孩子继续查找*/q=p;p=p->rson; if(p=NULL) printf("nx is not exist.&qu

12、ot;);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=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;/*将要删除结点左子树最下方的右孩子的数据赋给要删除结点，删除左子树最下方的右孩子，使之仍为一个二叉排序树*/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);/*循环结束查找成功，调用插入算将

17、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;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指针指向头结点，实现循环链表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");/每输出十个数，另起一行s->next=q;/删除结点pfree(p);p=q;/p指向删除结点的下一个结点i=1;printf("%d ",p->data);/只剩下一个结点的时候，直接输出该节点，结束此函数（三）迷宫问题求解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)/判栈空操作，栈空返回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;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;/创建元素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); /获得下一节点:当前位置的南邻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;（四）编程实现无向图的基本操作。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) /判循环队列是否满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)/用户输入顶点创建无向图，创建成功返回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

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)/递归深度优先遍历无向图int u;visitedv=1;/判断是否被访问过的数组，被访问过数组值为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)/广度优先遍历无向图queue q;int u,v,w;initqueue(&q);/队列初始化for(u=0;u<g->vexnum;u+)visitedu=0;/访问数组初始值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-;/无向图顶点数减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+)/此循环用以找到与其他顶点不连通的顶点，如果此循环循环超过一次，则为非连通图，否则为连通图if(!visitedv) dfs(g,v);count+;if(count=1) printf("nYES!");else printf("nNO!");五、测试结果及分析（一）编程实现二叉排序树的创建与操作测试所用二叉排序树：测试结果截图：由以上测试结果可以看出，程序能完成设定