约瑟夫环问题-循环链表VS数组

2013-08-18 21:27:50

循环链表、数组解决约瑟夫环问题的比较

注意几点：

循环链表的建立不难，在删除循环链表中元素时，用pCur->next != pCur判断结束；
每一轮计数开始，将计数器归1，counter = 1;
并将指针指向下一个元素，pCur = pCur->next; //从下一个元素开始计数

代码（测试暂未发现错误，欢迎交流指正）：

  1 #include <iostream>
  2 #include <cassert>
  3 using namespace std;
  4 
  5 typedef int DataType; 
  6 
  7 typedef struct node
  8 {
  9     DataType data;
 10     struct node *next;
 11 }LNode,*PLNode;
 12 
 13 
 14 //头插法建立循环链表
 15 PLNode CreatCircularLink(PLNode &pHead,size_t n)
 16 {
 17     pHead = NULL;
 18     PLNode pTail = NULL;
 19     PLNode pNew = NULL;
 20     size_t counter = n;
 21 
 22     while (counter >= 1)
 23     {
 24         pNew = new LNode;
 25         pNew->data = counter;
 26         pNew->next = pHead;
 27         pHead = pNew;
 28 
 29         if (NULL == pTail)
 30         {
 31             pTail = pNew;
 32         }
 33         --counter;
 34     }
 35 
 36     pTail->next = pHead;
 37     return pHead;
 38 }
 39 
 40 //利用循环链表，显示出队序列
 41 void DisplaySequenceOfDequeue(PLNode &pHead,size_t n,size_t m)
 42 {
 43     CreatCircularLink(pHead,n);
 44 
 45     assert( n > 0 && m > 0 && n > m );
 46 
 47     PLNode pCur = pHead;
 48     PLNode pNodeToDelete = NULL;
 49     size_t counter = 0;
 50 
 51     while (pCur->next != pCur)
 52     {
 53         counter = 1;    //新一轮计数，计数值归1
 54         while (counter < m - 1)
 55         {
 56             pCur = pCur->next;
 57             ++counter;
 58         }
 59         pNodeToDelete = pCur->next;
 60         pCur->next = pCur->next->next;
 61         cout<<pNodeToDelete->data<<"	";
 62         delete pNodeToDelete;
 63 
 64         pCur = pCur->next;  //从下一个元素开始计数
 65     }
 66 
 67     cout<<pCur->data<<"	";
 68     delete pCur;
 69     cout<<endl;
 70 }
 71 
 72 //显示循环链表
 73 void DisplayCircularLink(PLNode &pHead)
 74 {
 75     PLNode pCur = pHead;
 76     PLNode pTail = pHead;
 77 
 78     while (pCur->next != pTail)
 79     {
 80         cout<<pCur->data<<"	";
 81         pCur = pCur->next;
 82     }
 83     cout<<pCur->data<<"	";
 84     cout<<endl;
 85 }
 86 
 87 typedef struct JRnode
 88 {
 89     size_t id;
 90     bool flag;
 91 }JRNode,*PJRNode;
 92 //
 93 //void JosephRing(size_t n,size_t m,size_t *(&outQueue))
 94 //{
 95 //    JRNode *inQueue = new JRNode[n];
 96 //    size_t counter = 0;
 97 //    size_t step = 0;
 98 //    int index = 0;
 99 //
100 //    for (index = 0;index < n;++index)
101 //    {
102 //        inQueue[index].id = index + 1;
103 //        inQueue[index].flag = true;
104 //    }
105 //
106 //    index = 0;
107 //    while (counter < n)
108 //    {
109 //        step = 0;
110 //        while (step < m)
111 //        {
112 //            while (!inQueue[index].flag)
113 //            {
114 //                index = (index + 1) % n;
115 //            }
116 //            index = (index + 1) % n;
117 //            ++step;
118 //        }
119 //
120 //        inQueue[index].flag = false;
121 //        outQueue[counter++] = index;   
122 //
123 //        /*if (index == n)
124 //        {
125 //        index = n - 1;
126 //        }*/
127 //        
128 //    }
129 //
130 //    delete [] inQueue;
131 //}
132 
133 //用数组解决
134 void Circle_out(size_t n, size_t s, size_t m, size_t *p)
135 {
136     int i;
137     int *circle = new int[n];
138     int pos = s-1;
139     int cnt = 0;
140     int p_cnt = 0;
141     int N = n;
142     for(i=0;i<n;++i)
143         circle[i] = 0;
144     while(n--)
145     {
146         cnt = m;
147         while(cnt)
148         {
149             if(circle[pos]==0)        //如果该位置未出圈，将该位置计入
150                 cnt--;
151             pos++;
152             if(pos==N)        //注意：不是if(pos==n)，因为n在执行的过程中是变化的，是临时变量
153                 pos = 0;
154         }
155         //cout<<"pos = "<<pos<<endl;
156         if(pos==0)            //此处必须对pos为0的情况进行特殊处理
157         {
158             circle[N-1] = 1;
159             p[p_cnt++] = N;
160         }
161         else
162         {
163             circle[pos-1] = 1;        //circle[pos-1]，not circle[pos]
164             p[p_cnt++] = pos;    //pos,not (pos-1)
165         }    
166     }
167     delete [] circle;
168 }
169 
170 void DisplayArray(size_t *array,size_t len)
171 {
172     assert(NULL != array && len > 0);
173     size_t index = 0;
174 
175     while (index < len)
176     {
177         cout<<array[index]<<"	";
178         index++;
179     }
180     cout<<endl;
181 
182 }
183 
184 //测试约瑟夫环
185 void TestCircularLink()
186 {
187     PLNode pHead = NULL;
188     size_t n = 0;
189     size_t m = 0;
190 
191     cout<<"Please enter n and m : "<<endl;
192     while (cin>>n>>m)
193     {
194         //CreatCircularLink(pHead,n);
195         //DisplayCircularLink(pHead);
196         cout<<"(DisplaySequenceOfDequeue)The Sequence Of Dequeue is :"<<endl;
197         DisplaySequenceOfDequeue(pHead,n,m);
198 
199         size_t *outQueue = new size_t[n];
200         Circle_out(n, 0, m, outQueue);
201 
202         cout<<"(Circle_out)The Sequence Of Dequeue is :"<<endl;
203         DisplayArray(outQueue,n);
204 
205         delete [] outQueue;
206 
207         cout<<"Please enter n and m : "<<endl;
208     }
209 }
210 
211 int main()
212 {
213     TestCircularLink();
214     return 0;
215 }

测试结果：

Please enter n and m :
5 2
(DisplaySequenceOfDequeue)The Sequence Of Dequeue is :
2       4       1       5       3
(Circle_out)The Sequence Of Dequeue is :
2       4       1       5       3
Please enter n and m :
5 3
(DisplaySequenceOfDequeue)The Sequence Of Dequeue is :
3       1       5       2       4
(Circle_out)The Sequence Of Dequeue is :
3       1       5       2       4
Please enter n and m :
^Z
请按任意键继续. . .