Josephus环算法的设计

《Josephus环算法的设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告一Josephus环算法的设计一、实验目的本实验的目的是进一步理解线性表的逻辑结构和两种存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、实验题目Josephus环算法的设计约瑟夫（Josephus）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。三、实验类型设

2、计性。方案一采用顺序存储结构实现线性表。方案二采用循环链表结构实现线性表。四、实验报告1．程序关键代码#include#includetypedefstructLnode{intdata;structLnode*next;}Lnode;Lnode*create(intn){inti;Lnode*h,*p;Lnode*r=(Lnode*)malloc(sizeof(Lnode));r->data=n;h=r;for(i=n-1;i>0;i--){p=(Lnode*)malloc(sizeof(Lnode));p->data=i;p->next=h;h=p

3、;}r->next=h;returnh;}voidjeseph(Lnode*p,intm){Lnode*q;intj=0;printf("出对序列为:");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("%d",p->data);free(p);}voidmain(){Lnode*h;intm,n;printf("请输入n和m的值:");scanf("%d,%d",&n,&m);

4、h=create(n);jeseph(h,m);}2．测试结果截图截图一：截图二：实验报告二二叉树遍历算法的设计一、实验目的本实验的目的是理解二叉树的逻辑结构和二叉链表存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、实验题目二叉树遍历算法的设计。三、实验类型设计性。方案一采用递归算法实现二叉树遍历算法。方案二采用非递归算法实现二叉树遍历算法。四、实验报告1．程序关键代码#include#includetypedefstructnode1{chardata;structnode1*lchild,*rchild;}BTCH

5、INALR;BTCHINALR*createbt(){BTCHINALR*q;structnode1*s[30];intj,i,x;printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开");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;s[i]=q;/*q新结点地址存入s指针数组中*/if(i!=1)/*i=1，对

6、应的结点是根结点*/{j=i/2;/*求双亲结点的编号j*/if(i%2==0)s[j]->lchild=q;/*q结点编号为偶数则挂在双亲结点j的左边*/elses[j]->rchild=q;}/*q结点编号为奇数则挂在双亲结点j的右边*/printf("i,x=");scanf("%d,%c",&i,&x);}returns[1];/*返回根结点地址*/}voidinorder(BTCHINALR*bt)/*中序遍历二叉树(递归算法)*/{if(bt!=NULL){inorder(bt->lchild);printf("%c",bt->data);inorder(bt->rchild)

7、;}}voidinorder_notrecursive(BTCHINALR*bt)/*中序遍历二叉树(非递归算法)*/{BTCHINALR*q,*s[20];inttop=0;intbool=1;q=bt;do{while(q!=NULL){top++;s[top]=q;q=q->lchild;}if(top==0)bool=0;else{q=s[top];top--;printf("%c",q->data);q=q->