C++語言循環鏈表(約瑟夫環)源程序

1.循環鏈表和約瑟夫
循環鏈表：將單鏈表的首尾連接，使其成為了一個環狀鏈表，通常稱為循環鏈表。
約瑟夫環：是一個經典的循環鏈表問題，題意是：已知 n 個人（分別用編號 1，2，3，…，n 表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數，數到 m 的那個人出列；他的下一個人又從 1 開始，還是順時針開始報數，數到 m 的那個人又出列；依次重復下去，直到圓桌上剩余一個人。
2.算法思路

3.源碼

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. 
   
5. typedef struct node{
   
6.     int number;
   
7.     struct node* next;
   
8. }person;
   
9. 
   
10. person *initLink(int n)
    
11. {
    
12.     person *head=(person*)malloc(sizeof(person));
    
13.     head->number=1;
    
14.     head->next=NULL;
    
15.     person *cyclic=head;
    
16.     int i;
    
17.     for(i=2;i<=n;i++)
    
18.     {
    
19.         person *temp=(person*)malloc(sizeof(person));
    
20.         temp->number=i;
    
21.         temp->next=NULL;
    
22. 
    
23.         head->next=temp;
    
24.         head=head->next;
    
25.     }
    
26.     head->next=cyclic;
    
27.     return cyclic;
    
28. }
    
29. 
    
30. 
    
31. void linkPrint(person *temp)
    
32. {
    
33.     person *head=temp;
    
34.     if(!temp)
    
35.         printf("the link is empty\n");
    
36.     else
    
37.     {
    
38.         while(temp)
    
39.         {
    
40.             printf("%d\t",temp->number);
    
41.             temp=temp->next;
    
42.             if(temp==head)
    
43.                 break;
    
44.         }
    
45.     }
    
46. }
    
47. 
    
48. void findANDkill(person *head,int k,int m)
    
49. {
    
50.     person *tail=head;
    
51.     //找到鏈表第一個結點的上一個結點，為刪除操作做準備
    
52.     while(tail->next!=head)
    
53.         tail=tail->next;
    
54.     person * p=head;
    
55.     //找到編號為k的人
    
56.     while(p->number!=k)
    
57.     {
    
58.         tail=p;
    
59.         p=p->next;
    
60.     }
    
61.     //從編號為k的人開始，只有符合p->next==p時，說明鏈表中除了p結點，所有編號都出列了，
    
62.     while(p->next!=p)
    
63.     {
    
64.         //找到從p報數1開始，報m的人，并且還要知道數m-1de人的位置tail，方便做刪除操作。
    
65.         for(int i=1;i<m;i++)
    
66.         {
    
67.             tail=p;
    
68.             p=p->next;
    
69.         }
    
70. 
    
71.         tail->next=p->next;//從鏈表上將p結點摘下來
    
72.         printf("出列人的編號為:%d\n",p->number);
    
73.         free(p);
    
74.         p=tail->next;//繼續使用p指針指向出列編號的下一個編號，游戲繼續
    
75.     }
    
76.     printf("出列人的編號為:%d\n",p->number);
    
77.     free(p);
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.     int n,k,m;
    
83.     printf("請輸入圓桌上的人數：\n");
    
84.     scanf("%d",&n);
    
85.     person *head=initLink(n);
    
86.     //linkPrint(head);
    
87.     printf("從第k人開始報數(k>1且k<%d)：",n);
    
88.     scanf("%d",&k);
    
89.     printf("數到m的人出列：");
    
90.     scanf("%d",&m);
    
91. 
    
92.     findANDkill(head,k,m);
    
93.     return 0;
    
94. }

復制代碼

【必讀】版權免責聲明

1、本主題所有言論和內容純屬會員個人意見，與本論壇立場無關。2、本站對所發內容真實性、客觀性、可用性不做任何保證也不負任何責任，網友之間僅出于學習目的進行交流。3、對提供的數字內容不擁有任何權利，其版權歸原著者擁有。請勿將該數字內容進行商業交易、轉載等行為，該內容只為學習所提供，使用后發生的一切問題與本站無關。 4、本網站不保證本站提供的下載資源的準確性、安全性和完整性;同時本網站也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的損失或傷害。 5、本網站所有軟件和資料均為網友推薦收集整理而來，僅供學習用途使用，請務必下載后兩小時內刪除，禁止商用。6、如有侵犯你版權的，請及時聯系我們（電子郵箱1370723259@qq.com）指出，本站將立即改正。