当前位置 博文首页 > 用心编码:算法-循环链表[约瑟夫问题]
/**
* 约瑟夫问题
* 循环链表
*/
#include "stdafx.h"
#include "stdlib.h"
#define LEN 41
using namespace std;
typedef int TYPE;
typedef struct Node {
TYPE data;
Node* next;
Node* prev;
}LNode,*PNode;
PNode head;
void create_list() {
PNode node = (PNode)malloc(sizeof(LNode));
if (NULL != node) {
node->data = 1;
node->next = NULL;
node->prev = NULL;
head = node;
}
PNode newhead = head;
for (int i = 2; i <= LEN;i++) {
PNode newnode = (PNode)malloc(sizeof(LNode));
newnode->data = i;
if (i == LEN) {
newnode->next = head;
head->prev = newnode;
}
else {
newnode->next = NULL;
}
newhead->next = newnode;
newnode->prev = newhead;
newhead = newnode;
}
}
// index == 3
void joseph(int index) {
int i = 1, j = LEN;
PNode newhead = head;
printf("dead people:\0");
while (i++ <= LEN) {
newhead = newhead->next;
if (j==2) {
printf("remainder:%d \0",newhead->data);
printf("%d",newhead->prev->data);
return;
}
if (i == index) {
PNode nextTemp = newhead->next;
PNode prevTemp = newhead->prev;
prevTemp->next = nextTemp;
nextTemp->prev = prevTemp;
printf("%d \0",(newhead->data));
//newhead = NULL;
//free(newhead); // 释放内存
j--;
i = 0;
}
}
}
int main()
{
create_list();
joseph(3);
return 0;
}
cs