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

《用双向循环链表求解约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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）采

2、用双向循环链表实现Josephus排列问题，且奇数次顺时针轮转，偶数次逆时针轮转。（3）推荐采用静态链表实现Josephus排列问题。2.需求分析本程序要求根据输入的人数n和给定的正整数m，求得约瑟夫排列，且奇数次顺时针轮转，偶数次逆时针轮转。故可利用双向循环链表建立存储结构，利用双向循环链表的遍历与删除操作实现功能要求。3.概要设计1.抽象数据类型定义：typedefstructDuLNode{intdata;structDuLNode*prior;structDuLNode*next;}DuL

3、Node,*DuLinkList;//定义双向循环链表2.基本操作intInitList_Dul(DuLinkList&L)//建立一个只含头结点的空双向循环链表intCreateList_DuL(DuLinkList&L,intn)//建立一个带头结点的含n个元素的双向循环链表LintListDelete_DuL(DuLinkList&L,DuLinkListx)//删除指针x指向的结点3.设计思路首先建立一个双向循环链表作为存储结构，每个结点的数据域存储每个人的编号，然后根据给定的m值对整个链

4、表进行遍历，找到所要找的结点后，输出该结点的数据域的值，并在双向循环链表中删除该结点，重复这样的操作，一直到所有的人都出列，依次输出的数列即为所求的Josephus排列。4.详细设计typedefstructDuLNode{intdata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;//定义双向循环链表intInitList_Dul(DuLinkList&L)//建立一个只含头结点的空双向循环链表{L=(DuLinkLis

5、t)malloc(sizeof(DuLNode));if(!L)returnERROR;L->data=0;L->next=L;L->prior=L;returnOK;}intCreateList_DuL(DuLinkList&L,intn)//建立一个带头结点的含n个元素的双向循环链表L{DuLinkListp,q;inti;q=L;for(i=0;idata=i+1;//m值的自动获取p->nex

6、t=q->next;q->next=p;p->prior=q;L->prior=p;q=p;}returnOK;}intListDelete_DuL(DuLinkList&L,DuLinkListx)//删除指针x指向的结点{x->prior->next=x->next;x->next->prior=x->prior;free(x);return0;}intmain(){intn,m;inti=1;cin>>n;DuLinkListS;InitList_Dul(S);CreateList_DuL(

7、S,n);cin>>m;DuLinkLista=S->next;//a指向第一个结点（不是头结点）if(m%2==1)//奇数次顺时针转{while(!(S->next==S->prior))//当剩下最后一个人时（此时还有头结点）时退出循环{if(i==m){DuLinkListp;if(a->data==0)a=a->next;//跳过头结点p=a;a=a->next;cout<data<<"";ListDelete_DuL(S,p);//删除节点pi=1;}else{if(a->da

8、ta==0)a=a->next;//跳过头结点a=a->next;i++;}}cout<next->data<next);free(S);//释放除头结点和最后一个结点}else//偶数次逆时针转{while(!(S->next==S->prior))//当剩下最后一个人时（此时还有头结点）时退出循环{if(i==m){DuLinkListp;if(a->data==0)a=a->prior;//跳过头结点p=a;a