2013-08-18 21:27:50
循环链表、数组解决约瑟夫环问题的比较
注意几点：
- 循环链表的建立不难，在删除循环链表中元素时，用pCur->next != pCur判断结束；
- 每一轮计数开始，将计数器归1，counter = 1;
- 并将指针指向下一个元素，pCur = pCur->next; //从下一个元素开始计数
代码（测试暂未发现错误，欢迎交流指正）：
#include <iostream>
#include <cassert>
using namespace std; typedef int DataType; typedef struct node
{
DataType data;
struct node *next;
}LNode,*PLNode; //头插法建立循环链表
PLNode CreatCircularLink(PLNode &pHead,size_t n)
{
pHead = NULL;
PLNode pTail = NULL;
PLNode pNew = NULL;
size_t counter = n; while (counter >= )
{
pNew = new LNode;
pNew->data = counter;
pNew->next = pHead;
pHead = pNew; if (NULL == pTail)
{
pTail = pNew;
}
--counter;
} pTail->next = pHead;
return pHead;
} //利用循环链表，显示出队序列
void DisplaySequenceOfDequeue(PLNode &pHead,size_t n,size_t m)
{
CreatCircularLink(pHead,n); assert( n > && m > && n > m ); PLNode pCur = pHead;
PLNode pNodeToDelete = NULL;
size_t counter = ; while (pCur->next != pCur)
{
counter = ; //新一轮计数，计数值归1
while (counter < m - )
{
pCur = pCur->next;
++counter;
}
pNodeToDelete = pCur->next;
pCur->next = pCur->next->next;
cout<<pNodeToDelete->data<<"\t";
delete pNodeToDelete; pCur = pCur->next; //从下一个元素开始计数
} cout<<pCur->data<<"\t";
delete pCur;
cout<<endl;
} //显示循环链表
void DisplayCircularLink(PLNode &pHead)
{
PLNode pCur = pHead;
PLNode pTail = pHead; while (pCur->next != pTail)
{
cout<<pCur->data<<"\t";
pCur = pCur->next;
}
cout<<pCur->data<<"\t";
cout<<endl;
} typedef struct JRnode
{
size_t id;
bool flag;
}JRNode,*PJRNode;
//
//void JosephRing(size_t n,size_t m,size_t *(&outQueue))
//{
// JRNode *inQueue = new JRNode[n];
// size_t counter = 0;
// size_t step = 0;
// int index = 0;
//
// for (index = 0;index < n;++index)
// {
// inQueue[index].id = index + 1;
// inQueue[index].flag = true;
// }
//
// index = 0;
// while (counter < n)
// {
// step = 0;
// while (step < m)
// {
// while (!inQueue[index].flag)
// {
// index = (index + 1) % n;
// }
// index = (index + 1) % n;
// ++step;
// }
//
// inQueue[index].flag = false;
// outQueue[counter++] = index;
//
// /*if (index == n)
// {
// index = n - 1;
// }*/
//
// }
//
// delete [] inQueue;
//} //用数组解决
void Circle_out(size_t n, size_t s, size_t m, size_t *p)
{
int i;
int *circle = new int[n];
int pos = s-;
int cnt = ;
int p_cnt = ;
int N = n;
for(i=;i<n;++i)
circle[i] = ;
while(n--)
{
cnt = m;
while(cnt)
{
if(circle[pos]==) //如果该位置未出圈，将该位置计入
cnt--;
pos++;
if(pos==N) //注意：不是if(pos==n)，因为n在执行的过程中是变化的，是临时变量
pos = ;
}
//cout<<"pos = "<<pos<<endl;
if(pos==) //此处必须对pos为0的情况进行特殊处理
{
circle[N-] = ;
p[p_cnt++] = N;
}
else
{
circle[pos-] = ; //circle[pos-1]，not circle[pos]
p[p_cnt++] = pos; //pos,not (pos-1)
}
}
delete [] circle;
} void DisplayArray(size_t *array,size_t len)
{
assert(NULL != array && len > );
size_t index = ; while (index < len)
{
cout<<array[index]<<"\t";
index++;
}
cout<<endl; } //测试约瑟夫环
void TestCircularLink()
{
PLNode pHead = NULL;
size_t n = ;
size_t m = ; cout<<"Please enter n and m : "<<endl;
while (cin>>n>>m)
{
//CreatCircularLink(pHead,n);
//DisplayCircularLink(pHead);
cout<<"(DisplaySequenceOfDequeue)The Sequence Of Dequeue is :"<<endl;
DisplaySequenceOfDequeue(pHead,n,m); size_t *outQueue = new size_t[n];
Circle_out(n, , m, outQueue); cout<<"(Circle_out)The Sequence Of Dequeue is :"<<endl;
DisplayArray(outQueue,n); delete [] outQueue; cout<<"Please enter n and m : "<<endl;
}
} int main()
{
TestCircularLink();
return ;
}
测试结果：
Please enter n and m : (DisplaySequenceOfDequeue)The Sequence Of Dequeue is : (Circle_out)The Sequence Of Dequeue is : Please enter n and m : (DisplaySequenceOfDequeue)The Sequence Of Dequeue is : (Circle_out)The Sequence Of Dequeue is : Please enter n and m :
^Z
请按任意键继续. . .