Josephus环算法的设计.doc

实验报告一 Josephus环算法的设计一、实验目的本实验的目的是进一步理解线性表的逻辑结构和两种存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、实验题目 Josephus环算法的设计约瑟夫（Josephus）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。三、实验类型设计性。方案一采用顺序存储结构实现线性表。方案二采用循环链表结构实现线性表。四、实验报告1程序关键代码# include # include typedef struct Lnodeint data;struct Lnode *next; Lnode;Lnode *create(int n) int i; Lnode *h, *p; Lnode *r=(Lnode*) malloc(sizeof(Lnode); r-data=n; h=r; for(i=n-1; i0; i-) p=(Lnode*) malloc(sizeof(Lnode); p-data=i; p-next=h; h=p; r-next=h; return h;void jeseph (Lnode *p, int m)Lnode *q; int j=0; printf (出对序列为: n); do j+; if(j=m-1) q= p-next; p-next=q-next; printf(%d ,q-data); j=0; m=q-data; free(q); p=p-next; while(p-next!=p); printf(%dn,p-data); free(p);void main( ) Lnode *h; int m,n; printf(n请输入n和m的值: ); scanf(%d,%d,&n,&m); h=create(n); jeseph(h,m);2测试结果截图截图一：截图二：实验报告二 二叉树遍历算法的设计一、实验目的本实验的目的是理解二叉树的逻辑结构和二叉链表存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、实验题目二叉树遍历算法的设计。三、实验类型设计性。方案一采用递归算法实现二叉树遍历算法。方案二采用非递归算法实现二叉树遍历算法。四、实验报告1程序关键代码#include #include typedef struct node1char data;struct node1 *lchild,*rchild;BTCHINALR;BTCHINALR * createbt( )BTCHINALR *q;struct node1 *s30;int j,i,x;printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn);printf(i,x = );scanf(%d,%c,&i,&x);while(i != 0 & x != $) q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一个新结点q*/ q-data = x; q-lchild = NULL; q-rchild = NULL; si = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ j = i / 2; /*求双亲结点的编号j*/ if(i % 2 = 0) sj-lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj-rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(i,x = ); scanf(%d,%c,&i,&x);return s1; /*返回根结点地址*/void inorder(BTCHINALR *bt)/*中序遍历二叉树(递归算法)*/if(bt != NULL)inorder(bt-lchild);printf(%c ,bt-data);inorder(bt-rchild);void inorder_notrecursive(BTCHINALR *bt)/*中序遍历二叉树(非递归算法)*/BTCHINALR *q, *s20; int top = 0; int bool = 1; q = bt; do while(q != NULL) top +; stop = q; q = q-lchild; if(top = 0) bool = 0; else q = stop; top -; printf(%c ,q-data); q = q-rchild; while(bool); main( ) BTCHINALR *bt; char ch; int i; bt = createbt(); i = 1; while(i) printf(n中序遍历二叉树(递归按y键，非递归按n键): ); fflush(stdin); scanf(%c,&ch); if(ch = y) inorder(bt); else inorder_notrecursive(bt); printf(n); printf(n继续操作吗?(继续按1键，结束按0键):); fflush(stdin); scanf(%d,&i); 2测试截图截图一截图二实验三 BFS和DFS算法的设计一、实验目的本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、实验题目BFS和DFS算法的设计三、实验类型 设计性。方案一采用BFS深度优先搜索算法实现图的遍历。方案二采用DFS广度优先搜索算法实现图的遍历。四、实验报告1程序关键代码广度遍历/ 001.cpp : Defines the entry point for the console application./#include stdio.h#include #include #define VEXTYPE int#define DATATYPE int#define MAXLEN 40typedef struct node3 /*表结点结构*/ int adjvex; /*存放与表头结点相邻接的顶点在数组中的序号*/struct node3 *next; /*指向与表头结点相邻接的下一个顶点的表结点*/EDGENODE;typedef struct VEXTYPE vertex; /*存放图中顶点的信息*/EDGENODE *link; /*指针指向对应的单链表中的表结点*/VEXNODE;typedef struct VEXNODE adjlistMAXLEN; /*邻接链表表头向量*/int vexnum,arcnum; /*顶点数和边数*/int kind; /*图的类型*/ADJGRAPH;typedef struct qnode int data;struct qnode *next;LINKQLIST;typedef struct LINKQLIST front; LINKQLIST rear;LINKQUEUE;ADJGRAPH creat_adjgraph()EDGENODE *p;int i, s, d;ADJGRAPH adjg;adjg.kind = 2;printf(nn输入顶点数和边数(用逗号隔开) : );scanf(%d,%d, &s, &d);fflush(stdin);adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/printf(nn);for(i = 0; i adjg.vexnum; i+) printf(输入顶点 %d 的值 : , i + 1); scanf(%d, &adjg.adjlisti.vertex); /*输入顶点的值*/ fflush(stdin); adjg.adjlisti.link = NULL;printf(nn);for(i = 0; i adjg.arcnum; i+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): , i + 1); scanf(%d,%d, &s, &d); /*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s adjg.vexnum | d adjg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d, &s, &d); s -; d -; p = malloc(sizeof(EDGENODE); /*建立一个和边相关的结点*/ p-adjvex = d; p-next = adjg.adjlists.link; /*挂到对应的单链表上*/ adjg.adjlists.link = p; p = malloc(sizeof(EDGENODE); /*建立另一个和边相关的结点*/ p-adjvex = s; p-next = adjg.adjlistd.link; /*挂到对应的单链表上*/ adjg.adjlistd.link = p;return adjg;void initlinkqueue(LINKQUEUE *q)/*初始化广度遍历中用到的链队列*/(q-front).next = malloc(sizeof(LINKQLIST);(q-front).next = NULL;(q-rear).data = (q-front).data;int emptylinkqueue(LINKQUEUE *q)/*判队列是否为空？*/int v;if(q-front).data =(q-rear).data)v = 1;elsev = 0;return v;void enlinkqueue(LINKQUEUE *q, DATATYPE x)/*元素x入队列*/(q-rear).next = malloc(sizeof(LINKQLIST);(q-rear).next = (q-rear).next-next;(q-rear).data = x;(q-rear).next = NULL;DATATYPE dellinkqueue(LINKQUEUE *q)/*删除队头元素*/LINKQLIST *p;DATATYPE v;if(emptylinkqueue(q) printf(队列空.n);v = 0;else p = (q-front).next;(q-front).next = p-next;if(p-next = NULL) q-rear = q-front;v = p-data;free(p);return v;void bfs(ADJGRAPH adjg, int vi)/*连通图的广度遍历算法：从vi顶点出发*/int visitedMAXLEN;int i, v;EDGENODE *p;LINKQUEUE que, *q;q = &que;initlinkqueue(q);for(i = 0; i adjvex = 0) visitedp-adjvex = 1; printf( %d, adjg.adjlistp-adjvex.vertex); enlinkqueue(q, (p-adjvex)+1); /*遍历到的结点编号入队列*/ p = p-next; void main() ADJGRAPH ag;int j; printf(n连通图的广度遍历n); ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/ printf(nn输入深度遍历起始顶点(1 - %d) : ,ag.vexnum); scanf(%d,&j); printf(nn广度遍历结果序列 : ); bfs(ag,j); /*连通图的广度遍历算法*/ printf(nn);深度遍历#include #include #define VEXTYPE int#define MAXLEN 40typedef struct node3 /*表结点结构*/int adjvex; /*存放与表头结点相邻接的顶点在数组中的序号*/struct node3 *next; /*指向与表头结点相邻接的下一个顶点的表结点*/EDGENODE;typedef structVEXTYPE vertex; /*存放图中顶点的信息*/EDGENODE *link; /*指针指向对应的单链表中的表结点*/VEXNODE;typedef structVEXNODE adjlistMAXLEN; /*邻接链表表头向量*/int vexnum,arcnum; /*顶点数和边数*/int kind; /*图的类型*/ADJGRAPH;int visitedMAXLEN;ADJGRAPH creat_adjgraph() EDGENODE *p; int i, s, d; ADJGRAPH adjg;adjg.kind = 2;printf(nn输入顶点数和边数(用逗号隔开) : );scanf(%d,%d, &s, &d);fflush(stdin);adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/printf(nn);for(i = 0; i adjg.vexnum; i+) /*输入顶点的值*/ printf(输入顶点 %d 的值 : , i + 1); scanf(%d, &adjg.adjlisti.vertex); fflush(stdin); adjg.adjlisti.link = NULL; printf(n);for(i = 0; i adjg.arcnum; i+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): , i+1); scanf(%d,%d, &s, &d); /*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s adjg.vexnum | d adjg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d, &s, &d); s -; d -; p = (EDGENODE *)malloc(sizeof(EDGENODE); /*建立一个和边相关的结点*/ p-adjvex = d; p-next = adjg.adjlists.link; /*挂到对应的单链表上*/ adjg.adjlists.link = p; p = (EDGENODE *)malloc(sizeof(EDGENODE); /*建立另一个和边相关的结点*/ p-adjvex = s