問題概述
有 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;
}