1、 用双向循环链表求解 约瑟夫环 学校： 东北大学 专业：计算机科学与技术 1.问题描述 Josephus 排列问题定义如下：假设 n 个竞赛者排成一个环形。给定一个正整数m n，从第 1 人开始，沿环计数，第 m 人出列。这个过程一直进行到所有人都出列为止。最后出列者为优胜者。全部出列次序定义了 1， 2， n 的一个排列。称为（ n， m） Josephus 排列。例如，（ 7， 3） Josephus 排列为 3,6,2,7,5,1,4。 【实验要求】 设计求解 Josephus 排列问题程序。 （ 1）采用顺序表、单链表或双向循环链表等数据结构。 （ 2）采用双向循环链表实现 Josep
2、hus 排列问题，且奇数次顺时针轮转，偶数次逆时针轮转。 （ 3）推荐采用静态链表实现 Josephus 排列问题。 2.需求分析 本程序要求根据输入的人数 n 和给定的正整数 m，求得约瑟夫排列，且奇数次顺时针轮转，偶数次逆时针轮转。故可利用双向循环链表建立存储结构，利用双向循环链表的遍历与删除操作实现功能要求。 3.概要设计 1.抽象数据类型定义： typedef struct DuLNode int data; struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList; /定义双向循环链表 2.基本操作 int In
3、itList_Dul(DuLinkList struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList; /定义双向循环链表 int InitList_Dul(DuLinkList if(!L) return ERROR; L-data=0; L-next=L; L-prior=L; return OK; int CreateList_DuL(DuLinkList int i; q=L; for(i=0;idata=i+1; /m值的自动获取 p-next=q-next; q-next=p; p-prior=q; L-pri
4、or=p; q=p; return OK; int ListDelete_DuL(DuLinkList 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) D
5、uLinkList 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-
6、prior; /跳过头结点 a=a-prior; i+; coutnext-datanext); free(S); /释放除头结点和最后一个结点 return 0; 5.调试分析 1. 遇到的问题： （ 1）开始对双向循环链表的 删除操作的指针改变顺序出现了问题，导致删除结点时出现了错误； （ 2）双向循环链表中带有头结点，而头结点的数据域是空的（该程序中设为 0），因此在对双向循环链表进行遍历和删除操作时，必须判断该结点是否是头结点，如果是，必须跳过该结点； 2.收获： （ 1）通过对双向循环链表的建立、遍历、删除等操作的实现，对指针和链表了解得更加透彻，掌握得更加牢固； （ 2）对头结点问
7、题的特殊处理，使自己解决问题的能力有了提升。 6.测试结果 说明：若 m是奇数，顺时针遍历双向循环链表；若 m是偶数，逆时针遍历双向循环链表。 附录：程序源代码 /* 约瑟夫环问题求解 东北大学 计算机科学与技术 */ #include #include #include using namespace std; # define OK 1 # define ERROR 0 typedef struct DuLNode int data; struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList; /定义双向循环链表 in
8、t InitList_Dul(DuLinkList if(!L) return ERROR; L-data=0; L-next=L; L-prior=L; return OK; int CreateList_DuL(DuLinkList 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 x-next-prior=x-prior; free(x); return 0; int mai
9、n() while(1) /主程序循环执行 int n,m; int i=1; coutn; DuLinkList S; InitList_Dul(S); CreateList_DuL(S,n); coutm; coutnext;/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);/释放除头结点和最后一个结点 /while(1) return 0;
