学步园

#include "stdio.h"<br /> #include "malloc.h"<br /> /*编写一<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>来解决与瑟夫环问题。<br /> * 设有n个人围坐在圆桌周围，从第S个人开始报数，数到第M个人出列，<br /> * 然后从出列的下一个人重新开始报数，数到第M个人出列……<br /> * 如此重复直到所有的人全部出列为止。<br /> * 例如当N=8,m=4,s=1,得到的新序列为4,8,5,2,1,3,7,6*/</p> <p>#define M 4<br /> #define N 8<br /> #define S 1</p> <p>typedef int elemtype;</p> <p>typedef struct node //单链表结点<br /> {<br /> elemtype data;<br /> struct node *next;<br /> }lnode, *linklist;</p> <p>lnode *create()//创建循环链表 储存所有人的编号<br /> {<br /> lnode *h, *p, *rear;<br /> int i;<br /> h = (lnode *) malloc( sizeof(lnode) );//创建头结点<br /> h->data=1;<br /> h->next=NULL;<br /> rear=h;</p> <p> for(i=2; i<N+1; i++) // 尾插法，共创建了N个节点<br /> {<br /> p=(lnode *)malloc(sizeof(lnode));<br /> p->data=i;;<br /> p->next =NULL;<br /> rear->next =p;<br /> rear=p;<br /> }<br /> rear->next=h;<br /> return h;<br /> }</p> <p>void dis(lnode *h)// 显示循环链表的数据域(不删结点)<br /> {<br /> int i;<br /> printf("循环链表的数据域为：/n");<br /> for(i=1; i<N+1; i++)<br /> {<br /> printf("%d/n",h->data);<br /> h=h->next;<br /> }<br /> printf("*************************/n");//第3个循环执行不到<br /> }</p> <p>void dis_order(lnode *h) //出圈算法，删除出圈结点<br /> {<br /> int i;<br /> lnode *p, *t;<br /> printf("出圈：/n");</p> <p> while(1)<br /> {<br /> p = h;<br /> for(i=1; i<3; i++) //指针后移两个<br /> {<br /> p=p->next ;<br /> }<br /> t=p->next; //第四个结点准备出环</p> <p> printf("%d/n", t->data); </p> <p> if(p!=t) //至少两个结点<br /> {<br /> h=t->next;<br /> p->next=h;<br /> free(t);<br /> }<br /> else<br /> {<br /> free(t);<br /> break;<br /> }<br /> }</p> <p>}</p> <p>void main()<br /> {<br /> lnode *head;<br /> head=create();<br /> dis(head);<br /> dis_order(head);<br /> //free操作在出圈中完成<br /> }</p> <p>

亮点：

尾插法创建循环链表

不足：

1.未保证M，N，S值可自由设定，特别是S

2.未实现相应的C++面向对象程序