欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標(biāo)題: C++語(yǔ)言循環(huán)鏈表(約瑟夫環(huán))源程序 [打印本頁(yè)]

作者: HWXBCMZ    時(shí)間: 2021-9-12 11:34
標(biāo)題: C++語(yǔ)言循環(huán)鏈表(約瑟夫環(huán))源程序
1.循環(huán)鏈表和約瑟夫
循環(huán)鏈表:將單鏈表的首尾連接,使其成為了一個(gè)環(huán)狀鏈表,通常稱為循環(huán)鏈表
約瑟夫環(huán):是一個(gè)經(jīng)典的循環(huán)鏈表問(wèn)題,題意是:已知 n 個(gè)人(分別用編號(hào) 1,2,3,…,n 表示)圍坐在一張圓桌周圍,從編號(hào)為 k 的人開(kāi)始順時(shí)針報(bào)數(shù),數(shù)到 m 的那個(gè)人出列;他的下一個(gè)人又從 1 開(kāi)始,還是順時(shí)針開(kāi)始報(bào)數(shù),數(shù)到 m 的那個(gè)人又出列;依次重復(fù)下去,直到圓桌上剩余一個(gè)人。
2.算法思路

  1. #include<stdio.h>
  2. #include<stdlib.h>


  3. typedef struct node{
  4.     int number;
  5.     struct node* next;
  6. }person;

  7. person *initLink(int n)
  8. {
  9.     person *head=(person*)malloc(sizeof(person));
  10.     head->number=1;
  11.     head->next=NULL;
  12.     person *cyclic=head;
  13.     int i;
  14.     for(i=2;i<=n;i++)
  15.     {
  16.         person *temp=(person*)malloc(sizeof(person));
  17.         temp->number=i;
  18.         temp->next=NULL;

  19.         head->next=temp;
  20.         head=head->next;
  21.     }
  22.     head->next=cyclic;
  23.     return cyclic;
  24. }


  25. void linkPrint(person *temp)
  26. {
  27.     person *head=temp;
  28.     if(!temp)
  29.         printf("the link is empty\n");
  30.     else
  31.     {
  32.         while(temp)
  33.         {
  34.             printf("%d\t",temp->number);
  35.             temp=temp->next;
  36.             if(temp==head)
  37.                 break;
  38.         }
  39.     }
  40. }

  41. void findANDkill(person *head,int k,int m)
  42. {
  43.     person *tail=head;
  44.     //找到鏈表第一個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn),為刪除操作做準(zhǔn)備
  45.     while(tail->next!=head)
  46.         tail=tail->next;
  47.     person * p=head;
  48.     //找到編號(hào)為k的人
  49.     while(p->number!=k)
  50.     {
  51.         tail=p;
  52.         p=p->next;
  53.     }
  54.     //從編號(hào)為k的人開(kāi)始,只有符合p->next==p時(shí),說(shuō)明鏈表中除了p結(jié)點(diǎn),所有編號(hào)都出列了,
  55.     while(p->next!=p)
  56.     {
  57.         //找到從p報(bào)數(shù)1開(kāi)始,報(bào)m的人,并且還要知道數(shù)m-1de人的位置tail,方便做刪除操作。
  58.         for(int i=1;i<m;i++)
  59.         {
  60.             tail=p;
  61.             p=p->next;
  62.         }

  63.         tail->next=p->next;//從鏈表上將p結(jié)點(diǎn)摘下來(lái)
  64.         printf("出列人的編號(hào)為:%d\n",p->number);
  65.         free(p);
  66.         p=tail->next;//繼續(xù)使用p指針指向出列編號(hào)的下一個(gè)編號(hào),游戲繼續(xù)
  67.     }
  68.     printf("出列人的編號(hào)為:%d\n",p->number);
  69.     free(p);
  70. }

  71. int main()
  72. {
  73.     int n,k,m;
  74.     printf("請(qǐng)輸入圓桌上的人數(shù):\n");
  75.     scanf("%d",&n);
  76.     person *head=initLink(n);
  77.     //linkPrint(head);
  78.     printf("從第k人開(kāi)始報(bào)數(shù)(k>1且k<%d):",n);
  79.     scanf("%d",&k);
  80.     printf("數(shù)到m的人出列:");
  81.     scanf("%d",&m);

  82.     findANDkill(head,k,m);
  83.     return 0;
  84. }
復(fù)制代碼

3.以上源碼 約瑟夫環(huán)表.zip (1.04 KB, 下載次數(shù): 7)





歡迎光臨 (http://m.raoushi.com/bbs/) Powered by Discuz! X3.1