1.循環鏈表和約瑟夫
循環鏈表：將單鏈表的首尾連接，使其成為了一個環狀鏈表，通常稱為循環鏈表。
約瑟夫環：是一個經典的循環鏈表問題，題意是：已知 n 個人（分別用編號 1，2，3，…，n 表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數，數到 m 的那個人出列；他的下一個人又從 1 開始，還是順時針開始報數，數到 m 的那個人又出列；依次重復下去，直到圓桌上剩余一個人。
2.算法思路
- #include<stdio.h>
- #include<stdlib.h>
- typedef struct node{
- int number;
- struct node* next;
- }person;
- person *initLink(int n)
- {
- person *head=(person*)malloc(sizeof(person));
- head->number=1;
- head->next=NULL;
- person *cyclic=head;
- int i;
- for(i=2;i<=n;i++)
- {
- person *temp=(person*)malloc(sizeof(person));
- temp->number=i;
- temp->next=NULL;
- head->next=temp;
- head=head->next;
- }
- head->next=cyclic;
- return cyclic;
- }
- void linkPrint(person *temp)
- {
- person *head=temp;
- if(!temp)
- printf("the link is empty\n");
- else
- {
- while(temp)
- {
- printf("%d\t",temp->number);
- temp=temp->next;
- if(temp==head)
- break;
- }
- }
- }
- void findANDkill(person *head,int k,int m)
- {
- person *tail=head;
- //找到鏈表第一個結點的上一個結點，為刪除操作做準備
- while(tail->next!=head)
- tail=tail->next;
- person * p=head;
- //找到編號為k的人
- while(p->number!=k)
- {
- tail=p;
- p=p->next;
- }
- //從編號為k的人開始，只有符合p->next==p時，說明鏈表中除了p結點，所有編號都出列了，
- while(p->next!=p)
- {
- //找到從p報數1開始，報m的人，并且還要知道數m-1de人的位置tail，方便做刪除操作。
- for(int i=1;i<m;i++)
- {
- tail=p;
- p=p->next;
- }
- tail->next=p->next;//從鏈表上將p結點摘下來
- printf("出列人的編號為:%d\n",p->number);
- free(p);
- p=tail->next;//繼續使用p指針指向出列編號的下一個編號，游戲繼續
- }
- printf("出列人的編號為:%d\n",p->number);
- free(p);
- }
- int main()
- {
- int n,k,m;
- printf("請輸入圓桌上的人數：\n");
- scanf("%d",&n);
- person *head=initLink(n);
- //linkPrint(head);
- printf("從第k人開始報數(k>1且k<%d)：",n);
- scanf("%d",&k);
- printf("數到m的人出列：");
- scanf("%d",&m);
- findANDkill(head,k,m);
- return 0;
- }
3.以上源碼
約瑟夫環表.zip
(1.04 KB, 下載次數: 7)
2021-9-12 11:34 上傳
點擊文件名下載附件
|
