问题概述
有 n 个人围坐成一圈，其编号为从 1 到 n 的递增数列，每个人有一个正整数密码。先选定一个任意正整数 m，并从 1 号开始报 1，2号报 2，以此类推，报到 m 时停止，该人出局，并把他的密码作为新的 m 值。重复该过程，直到所有人出局，求出局人编号顺序。
修改前代码
#include#include typedef struct node { int number; int password; struct node *next;} node;node *createCircularLinkedList(int n) { node *temp = NULL; node *head = (node *) malloc(sizeof(node)); head->next = head; // Necessary when n == 1; temp = head; for (int i = 0; i < n - 1; ++i) { temp->next = (node *) malloc(sizeof(node)); temp = temp->next; temp->next = NULL; } temp->next = head; return head;}int inputCircularLinkedList(node *head) { if (NULL == head) // If a blank linked list. return 0; node *temp = head; int count = 0; int password; count = 1; do { scanf("%d", &password); temp->password = password; temp->number = count++; temp = temp->next; } while (temp != head); return 1;}int printCircularLinkedList(node *head) { // Just for test. if (NULL == head) // If a blank linked list. return 0; node *temp = head; do { printf("%d-%d\n", temp->number, temp->password); temp = temp->next; } while (temp != head); return 1;}node *rearOfCircularLinkedList(node *head) { node *p = NULL; if (NULL == head) // If a blank linked list. return 0; p = head; while (p->next != head) p = p->next; return p;}node *deleteNodeOfCircularLinkedList(node *head, node *del) { if (NULL == head) // If a blank linked list. return 0; node *pre = head; while (pre->next != del) pre = pre->next; if (pre->next == head) { head = head->next; } pre->next = del->next; free(del); return head;}int main() { int n = 0, m = 0, password = 0; node *head = NULL; // Create a blank linked list. printf("Please input m:\n"); scanf("%d", &m); printf("Please input n:\n"); scanf("%d", &n); head = createCircularLinkedList(n); printf("Please input password:\n"); inputCircularLinkedList(head); printf("Data received:\n"); printCircularLinkedList(head); printf("Answer:\n"); node *p = head; node *pCopy = NULL; int count = 0; while (n > 0) { for (int i = 0; i < m-1; ++i) { p = p->next; } // P should out. printf("%d out\n", p->number); pCopy = p; m=p->password; p = p->next; head = deleteNodeOfCircularLinkedList(head, pCopy); n--; } return 0;}
代码问题
循环链表只需要有指针指向其即可，不需要固定头指针或尾指针。
删除函数又重复遍历了一遍链表，效率低下。
当密码为很大的数字时，可以用取余来提高效率。
修改后代码
#include#include typedef struct node { int number; int password; struct node *next;} node;node *nodePioneerOfCll(int m, node *p) { for (int i = 0; i < m - 1; ++i) { p = p->next; } // (p+1) - out. printf("%d - out\n", p->next->number); return p;}node *rearOfCll(node *p) { while (p->next->number != 1) { p = p->next; } return p;}node *createCll(int n) { node *temp = NULL; node *head = (node *) malloc(sizeof(node)); head->next = head; // n == 1 temp = head; for (int i = 0; i < n - 1; ++i) { temp->next = (node *) malloc(sizeof(node)); temp = temp->next; temp->next = NULL; } temp->next = head; // 尾元素指向头指针 return head;}int inputCll(node *p) { if (NULL == p) return 0; node *temp = p; int count = 1; do { scanf("%d", &temp->password); temp->number = count++; temp = temp->next; } while (temp != p); return 1;}int printCll(node *p) { if (NULL == p) return 0; node *temp = p; do { printf("%d-%d\n", temp->number, temp->password); temp = temp->next; } while (temp != p); return 1;}int deleteNextNodeOfCll(node *p) { if (NULL == p) return 0; node *del = p->next; p->next = p->next->next; int m = del->password; free(del); return m;}int main() { int n = 0, m = 0, password = 0; printf("Please input m:\n"); scanf("%d", &m); // 输入m值 printf("Please input n:\n"); scanf("%d", &n); // 输入n值 node *p = createCll(n); // 创建有n元循环链表 printf("Please input password:\n"); inputCll(p); // 输入密码 printf("Data received:\n"); printCll(p); // 反显密码 printf("Answer:\n"); p = rearOfCll(p); // p移到尾 for (; n > 0; n--) { p = nodePioneerOfCll(m % n ? m % n : n, p); // 移到待删节点前驱 m = deleteNextNodeOfCll(p); // 删除p后继 } return 0;}