用双向循环链表求解约瑟夫环.doc

用双向循环链表求解约瑟夫环 学校：东北大学 专业：计算机科学与技术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）推荐采用静态链表实现josephus排列问题。2.需求分析 本程序要求根据输入的人数n和给定的正整数m，求得约瑟夫排列，且奇数次顺时针轮转，偶数次逆时针轮转。故可利用双向循环链表建立存储结构，利用双向循环链表的遍历与删除操作实现功能要求。3.概要设计1.抽象数据类型定义：typedef struct dulnodeint data;struct dulnode *prior;struct dulnode *next; dulnode,*dulinklist; /定义双向循环链表 2. 基本操作 int initlist_dul(dulinklist &l) /建立一个只含头结点的空双向循环链表int createlist_dul(dulinklist &l,int n) /建立一个带头结点的含n个元素的双向循环链表l int listdelete_dul(dulinklist &l,dulinklist x) /删除指针x指向的结点 3.设计思路 首先建立一个双向循环链表作为存储结构，每个结点的数据域存储每个人的编号，然后根据给定的m值对整个链表进行遍历，找到所要找的结点后，输出该结点的数据域的值，并在双向循环链表中删除该结点，重复这样的操作，一直到所有的人都出列，依次输出的数列即为所求的josephus排列。4.详细设计typedef struct dulnodeint data;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;int 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;dulinklist 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) /当剩下最后一个人时（此时还有头结点）时退出循环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），因此在对双向循环链表进行遍历和删除操作时，必须判断该结点是否是头结点，如果是，必须跳过该结点；2.收获：（1）通过对双向循环链表的建立、遍历、删除等操作的实现，对指针和链表了解得更加透彻，掌握得更加牢固；（2）对头结点问题的特殊处理，使自己解决问题的能力有了提升。6.测试结果 说明：若m是奇数，顺时针遍历双向循环链表；若m是偶数，逆时针遍历双向循环链表。附录：程序源代码/* 约瑟夫环问题求解 东北大学 计算机科学与技术*/#include#include#includeusing namespace std;# define ok 1# define error 0typedef struct dulnodeint data;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;int 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()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;coutdatadata=0)a=a-next;/跳过头结点a=a-next;i+;coutnext-datanext); free(s);/释放除头结点和最后一个结点else /偶数次逆时针转while(!(s-next=s-prior)/当剩下最后一个人时（此时还有头结