约瑟夫环问题-数据结构实现代码.doc

《约瑟夫环问题-数据结构实现代码.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、以下是约瑟夫环问题的实现代码：由两部分组成jeseph.h文件和jesephMain.c文件jeseph.h文件如下：/*自定义DataType数据类型*/typedefstruct{intnumber;//每个人所对应的序号intcipher;//每个人手中的密码}DataType;/*构造循环单链表结点数据类型,包括个人信息及结点间的相互关系*/typedefstructnode{DataTypedata;structnode*next;}SCLNode;voidSCLLInitiate(SCL

2、Node**head)//初始化链表{if((*head=(SCLNode*)malloc(sizeof(SCLNode)))==NULL)exit(1);(*head)->next=*head;}intSCLLInsert(SCLNode*head,inti,DataTypex)//插入节点{SCLNode*p,*q;intj;p=head->next;j=1;/*表示结点(头结点)下标从1开始，即要插入结点的序号i就表示第几个结点若j=-1,则表示下标从0开始，要插入结点序号i表示第i-1个结点

3、*/while(p!=head&&jnext;j++;}if(j!=i-1&&i!=1)/*此时头结点的序号为1，为了保证不在头结点处或头结点前进行任何操作*/{printf("插入位置参数错！");return0;}if((q=(SCLNode*)malloc(sizeof(SCLNode)))==NULL)exit(1);q->data=x;q->next=p->next;p->next=q;return1;}intSCLLDelete(SCLNode*head,inti,

4、DataType*x)//删除一个指定位置的结点{SCLNode*p,*q;intj;p=head;j=0;while(p->next!=head&&jnext;j++;}if(j!=i-1){printf("删除位置参数出错");return0;}q=p->next;p->next=p->next->next;*x=q->data;free(q);return1;}intSCLLGet(SCLNode*head,inti,DataType*x)//获取链表中指定位置的结点{S

5、CLNode*p;intj;p=head;j=0;while(p->next!=head&&jnext;j++;}if(j!=i){printf("取元素位置参数错！");return0;}*x=p->data;return1;}intSCLLNotEmpty(SCLNode*head)//判断链表非空否{if(head->next==head)return0;//为空返回0elsereturn1;//非空返回1}jesephMain.c文件如下：#include

6、#include#include"jeseph.h"/*包含jeseph抽象数据类型*/voidSCLLDeleteAfter(SCLNode*p)//删除p指针所指结点的下一个结点{SCLNode*q=p->next;p->next=p->next->next;free(q);//将链表中断开后的节点，即要删除的节点从内存中释放}voidJesephRing(SCLNode*head,intm,intn)/*带头结点循环单链表head，初始报数值为m的约瑟夫环问题函数*/{SC

7、LNode*pre,*curr;inti,j=0;inta[n],b[n];//n表示约瑟夫环数的个数pre=head;curr=head->next;while(SCLLNotEmpty(head)==1){for(i=1;inext;if(curr==head){pre=curr;curr=curr->next;}}/*将出列约瑟夫环数的序号及其所对应的密码放在b[],a[]中*/b[j]=curr->data.number;a[j]=cu

8、rr->data.cipher;j++;m=curr->data.cipher;curr=curr->next;if(curr==head)curr=curr->next;SCLLDeleteAfter(pre);}/*分别输出a[i]和b[i]*/printf("约瑟夫环的先后出列顺序为：");for(i=0;i