《用双向循环链表求解约瑟夫环》由会员分享，可在线阅读，更多相关《用双向循环链表求解约瑟夫环（9页珍藏版）》请在金锄头文库上搜索。
1、用双向循环链表求解约瑟夫环 学校：东北大学 专业：计算机科学与技术1.问题描述 Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整数mn，从第1人开始，沿环计数，第m人出列。这个过程一直进行到所有人都出列为止。最后出列者为优胜者。全部出列次序定义了1，2，n的一个排列。称为（n，m）Josephus排列。例如，（7，3）Josephus排列为3,6,2,7,5,1,4。 【实验要求】 设计求解Josephus排列问题程序。 （1）采用顺序表、单链表或双向循环链表等数据结构。 （2）采用双向循环链表实现Josephus排列问题，且奇数次顺时针轮转，偶数次逆时针轮转。 （3
2、）推荐采用静态链表实现Josephus排列问题。2.需求分析 本程序要求根据输入的人数n和给定的正整数m，求得约瑟夫排列，且奇数次顺时针轮转，偶数次逆时针轮转。故可利用双向循环链表建立存储结构，利用双向循环链表的遍历与删除操作实现功能要求。3.概要设计1.抽象数据类型定义：typedef struct DuLNodeint data;struct DuLNode *prior;struct DuLNode *next; DuLNode,*DuLinkList; /定义双向循环链表 2. 基本操作 int InitList_Dul(DuLinkList &L) /建立一个只含头结点的空双向循环链
3、表int CreateList_DuL(DuLinkList &L,int n) /建立一个带头结点的含n个元素的双向循环链表L int ListDelete_DuL(DuLinkList &L,DuLinkList x) /删除指针x指向的结点 3.设计思路 首先建立一个双向循环链表作为存储结构，每个结点的数据域存储每个人的编号，然后根据给定的m值对整个链表进行遍历，找到所要找的结点后，输出该结点的数据域的值，并在双向循环链表中删除该结点，重复这样的操作，一直到所有的人都出列，依次输出的数列即为所求的Josephus排列。4.详细设计typedef struct DuLNodeint dat
4、a;struct DuLNode *prior;struct DuLNode *next;DuLNode,*DuLinkList; /定义双向循环链表int InitList_Dul(DuLinkList &L) /建立一个只含头结点的空双向循环链表L=(DuLinkList) malloc(sizeof(DuLNode);if(!L) return ERROR;L-data=0;L-next=L;L-prior=L;return OK;int CreateList_DuL(DuLinkList &L,int n) /建立一个带头结点的含n个元素的双向循环链表LDuLinkList p,q;i
5、nt i;q=L;for(i=0;idata=i+1; /m值的自动获取p-next=q-next;q-next=p;p-prior=q;L-prior=p;q=p;return OK;int ListDelete_DuL(DuLinkList &L,DuLinkList x) /删除指针x指向的结点x-prior-next=x-next;x-next-prior=x-prior;free(x);return 0;int main()int n,m;int i=1;cinn;DuLinkList S;InitList_Dul(S);CreateList_DuL(S,n);cinm;DuLink
6、List a=S-next;/a指向第一个结点（不是头结点）if(m%2=1) /奇数次顺时针转while(!(S-next=S-prior) /当剩下最后一个人时（此时还有头结点）时退出循环if(i=m)DuLinkList p;if(a-data=0)a=a-next;/跳过头结点p=a;a=a-next;coutdatadata=0)a=a-next;/跳过头结点a=a-next;i+;coutnext-datanext); free(S); /释放除头结点和最后一个结点else /偶数次逆时针转while(!(S-next=S-prior) /当剩下最后一个人时（此时还有头结点）时退出
7、循环if(i=m) DuLinkList p;if(a-data=0)a=a-prior; /跳过头结点p=a;a=a-prior;coutdatadata=0)a=a-prior; /跳过头结点a=a-prior;i+; coutnext-datanext);free(S); /释放除头结点和最后一个结点return 0;5.调试分析1. 遇到的问题：（1）开始对双向循环链表的删除操作的指针改变顺序出现了问题，导致删除结点时出现了错误；（2）双向循环链表中带有头结点，而头结点的数据域是空的（该程序中设为0），因此在对双向循环链表进行遍历和删除操作时，必须判断该结点是否是头结点，如果是，必须跳
8、过该结点；2.收获：（1）通过对双向循环链表的建立、遍历、删除等操作的实现，对指针和链表了解得更加透彻，掌握得更加牢固；（2）对头结点问题的特殊处理，使自己解决问题的能力有了提升。6.测试结果 说明：若m是奇数，顺时针遍历双向循环链表；若m是偶数，逆时针遍历双向循环链表。附录：程序源代码/* 约瑟夫环问题求解 东北大学 计算机科学与技术*/#include#include#includeusing namespace std;# define OK 1# define ERROR 0typedef struct DuLNodeint data;struct DuLNode *prior;str
9、uct DuLNode *next;DuLNode,*DuLinkList; /定义双向循环链表int InitList_Dul(DuLinkList &L) /建立一个只含头结点的空双向循环链表L=(DuLinkList) malloc(sizeof(DuLNode);if(!L) return ERROR;L-data=0;L-next=L;L-prior=L;return OK;int CreateList_DuL(DuLinkList &L,int n) /建立一个带头结点的含n个元素的双向循环链表LDuLinkList p,q;int i;q=L;for(i=0;idata=i+1;
10、 /m值的自动获取p-next=q-next;q-next=p;p-prior=q;L-prior=p;q=p;return OK;int ListDelete_DuL(DuLinkList &L,DuLinkList x) /删除指针x指向的结点x-prior-next=x-next;x-next-prior=x-prior;free(x);return 0;int main()while(1) /主程序循环执行int n,m;int i=1;cout请输入竞赛者人数n:n;DuLinkList S;InitList_Dul(S);CreateList_DuL(S,n);cout请输入正整数m:m;cout(n,m)Josephus排列(奇数次顺时针轮转，偶数次逆时针轮转）为：next;/a指向第一个结点（不是头结点）if(m%2=1) /奇数次顺时针转while(!(S-next=S-prior) /当剩下最后一个人时（此时还有头结点）时退出循环if(i=m)DuLinkList p;if(a-data=0)a=a-next;/跳过头结点p=a;a=a-next;coutdata ;ListDelete_Du
