约瑟夫问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。源代码如下:
//思路:可以将约瑟夫环看成是一个循环队列 #include "iostream" using namespace std; typedef unsigned short int TYPE; typedef unsigned int INT32U; //约瑟夫循环队列节点 typedef struct _JQNode { TYPE val; struct _JQNode *next; //指向下一个节点的指针 }JQNode; //约瑟夫循环队列 typedef struct _JQueue { JQNode* first; //指向约瑟夫循环队列首节点 INT32U size; }JQueue; void joseph(TYPE *arr,int n, int m); int main(void) { TYPE array[6] = {1,2,3,4,5,6}; //数组中存放的是约瑟夫环中的元素 joseph(array,6,5); //6个人围城一圈,开始时将第5个人杀死 return 0; } //初始化队列 void JQueueInit(JQueue **pJQueue) { *pJQueue = new JQueue; (*pJQueue)->first = NULL; (*pJQueue)->size = 0; } //向队列中追加元素 void append_node(JQueue* pJQueue,TYPE val) { JQNode* new_node = new JQNode; if(NULL ==new_node) exit(-1); new_node->val = val; new_node->next = NULL; if(0 == pJQueue->size) { pJQueue->first = new_node; new_node->next = new_node; pJQueue->size++; } else { INT32U k = 0; JQNode* temp = pJQueue->first; while (k < pJQueue->size-1) { temp = temp->next; k++; } temp->next = new_node; new_node->next = pJQueue->first; pJQueue->size++; } } //删除循环队列中第number个节点,返回被删除节点所指向的下一个元素的指针 JQNode* delete_node(JQueue* pJQueue,INT32U number) { if(1 == number) { //获得指向对尾元素的指针 INT32U k = 1; JQNode* temp = pJQueue->first; while (k < pJQueue->size) { temp = temp->next; k++; } JQNode* cur = pJQueue->first; //获得将要被删除节点的指针 cout<<cur->val<<" "; pJQueue->first = cur->next; JQNode* first_node= cur->next; delete cur; //释放内存空间 temp->next = pJQueue->first; //队尾元素指向首元素 pJQueue->size--; return first_node; } else { //获得要删除元素的前一个元素的指针 INT32U k = 1; JQNode* temp = pJQueue->first; while (k < number-1) { temp = temp->next; k++; } JQNode* cur = temp->next; temp->next = cur->next; cout<<cur->val<<" "; JQNode* first_node= cur->next; delete cur; pJQueue->size--; return first_node; } } //构造新的约瑟夫队列,将pJQnode所指向的节点作为约瑟夫循环队列的第一个节点 void RebuildJQueue(JQueue** pJQueue,JQNode* pJQnode) { (*pJQueue)->first = pJQnode; } //获得队列中元素的数目 INT32U get_node_num(JQueue* pJQueue) { return pJQueue->size; } //n表示数组元素个数 m(0<m<=n)表示约瑟夫问题的起始位置 void joseph(TYPE *arr,int n, int m) { INT32U k = 0; JQueue *queue; JQueueInit(&queue); for(INT32U i=0;i<n;i++) { append_node(queue,arr[i]); //构造约瑟夫循环队列 } JQNode* temp = queue->first; JQNode* first_node = NULL; while(0 < get_node_num(queue)) //约瑟夫循环队列中的元素不为空,一直执行循环体 { first_node = delete_node(queue,m); //删除约瑟夫循环队列中第m个元素 RebuildJQueue(&queue,first_node); //构建新的约瑟夫循环队列 } }
运行结果: