yosefu - 复制.c

清华版数据结构实习题约瑟夫环的代码

#include <stdio.h> 
#include <stdlib.h> 
/* 链表结点 */ 
typedef struct _linknode { 
int nIndex; 
int nPassword; 
struct _linknode* next; 
} NODE, *PNODE; 
/* 函数声明 */ 
PNODE CreateLinkList(int* pn); 
PNODE AddNode(PNODE pHead, int index); 
PNODE DelNode(PNODE pHead, int index, int* pm); 
void SimOut(PNODE pHead, int m, int count); 
/* 主函数 */ 
int main(void) 
{ 
int m, n; 
PNODE pHead = CreateLinkList(&n); 
printf("Please input m: "); 
scanf("%d", &m); 
SimOut(pHead, m, n); 
return 0; 
} 
/* 创建链表，并返回头结点 */ 
PNODE CreateLinkList(int* pn) 
{ 
int n, i; 
PNODE p, q; 
/* 初始化头结点 */ 
p = (PNODE)malloc(sizeof(NODE)); 
p->nIndex = -1; 
p->nPassword = -1; 
p->next = NULL; 
/* 取得总人数 */ 
printf("Please input the number of the peoples: "); 
scanf("%d", &n); 
*pn = n; 
/* 创建其它结点 */ 
for (i = 0; i < n; i++) 
q = AddNode(p, i); 
/* 创建约瑟夫环 */ 
q->next = p->next; 
free(p); 
return q; 
} 
/* 添加一个结点，返回其地址 */ 
PNODE AddNode(PNODE pHead, int index) 
{ 
PNODE p, q; 
int i = 0; 
/* 定位结点 */ 
for (p = pHead; p->next != NULL; p = p->next) 
if (i++ == index) 
break; 
/* 创建结点 */ 
q = (PNODE)malloc(sizeof(NODE)); 
q->nIndex = index + 1; 
printf("Please input person #%d password: ", index + 1); 
scanf("%d", &q->nPassword); 
p->next = q; 
q->next = NULL; 
return q; 
} 
/* 删除结点，并返回前一个结点 */ 
PNODE DelNode(PNODE pHead, int index, int* pm) 
{ 
PNODE p, q; 
int i = -1; 
/* 定位结点 */ 
for (p = pHead ; p != NULL; p = p->next) 
if (++i == index) 
break; 
/* 删除结点 */ 
q = p->next; 
printf("Number %d is out.\n", q->nIndex); 
p->next = q->next; 
/* pm传回新的m值 */ 
*pm = q->nPassword; 
free(q); 
/* 返回前一个结点，以备下次删除之用 */ 
return p; 
} 
/* 模拟约瑟夫环的报数过程 */ 
void SimOut(PNODE pHead, int m, int count) 
{ 
int x = m; 
int n = count; 
PNODE p = pHead; 
while (n > 0) 
{ 
p = DelNode(p, x % n != 0 ? x % n - 1 : n - 1, &x); 
n--; 
} 
}