久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

 找回密碼
 立即注冊

QQ登錄

只需一步，快速開始

搜索
查看: 2980|回復: 0
收起左側

C++語言判斷單鏈表是否有環鏈表 程序源碼

[復制鏈接]
ID:618366 發表于 2021-9-12 11:25 | 顯示全部樓層 |閱讀模式
1.問題：如果給定一個單鏈表，如何判斷其是否為有環鏈表
2.方法：
（1）從給定鏈表的第一個節點開始遍歷，每遍歷至一個節點，都將其和所有的前驅節點進行比對，如果為同一個節點，則表明當前鏈表中有環；反之，如果遍歷至鏈表最后一個節點，仍未找到相同的節點，則證明該鏈表中無環。
NBQ(S_`2~N$F_E2A_CB`P[2.png

如上所示，當函數的返回值為 True，表示該鏈表有環；反之若函數返回值為 False，表明鏈表中無環。顯然，此實現方案的時間復雜度為O(n2)。
（2）在一個鏈表中，如果 2 個指針（假設為 H1 和 H2）都從表頭開始遍歷鏈表，其中 H1 每次移動 2 個節點的長度（H1 = H1->next->next）,而 H2 每次移動 1 個節點的長度（H2 = H2->next），如果該鏈表為有環鏈表，則 H1、H2 最終必定會相等；反之，如果該鏈表中無環，則 H1、H2 永遠不會相遇。
2.png

本算法的時間復雜度為 O(n)。

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

  4. //自定義 bool 類型
  5. typedef enum Bool
  6. {
  7.     False=0,
  8.     True=1
  9. }Bool;

  11. typedef struct link{
  12.     int data;
  13.     struct link* next;
  14. }link;

  16. link *linkIint(int n)
  17. {
  18.     link *head=(link*)malloc(sizeof(link));
  19.     head->data=1;
  20.     head->next=NULL;
  21.     link *phead=head;
  22.     int i;
  23.     for(i=2;i<=n;i++)
  24.     {
  25.         link *temp=(link*)malloc(sizeof(link));
  26.         temp->data=i;
  27.         temp->next=NULL;

  29.         head->next=temp;
  30.         head=head->next;
  31.     }
  32.         head->next=phead;
  33.     return phead;
  34. }

  36. #if 1
  37. Bool HaveRing(link *temp)
  38. {
  39.     link *H2=temp;
  40.     link *H1=temp->next;
  41.         if(H2==NULL||H2==NULL)
  42.         {
  43.                 return False;
  44.         }
  45.     while(H1)
  46.     {
  47.         if(H1==H2)
  48.         {
  49.             printf("this links have a ring\n");
  50.             return True;
  51.         }
  52.         else
  53.         {
  54.             H1=H1->next;
  55.             if (!H1)
  56.             {
  57.                 printf("this links no ring\n");
  58.                 return False;
  59.             }
  60.             else
  61.             {
  62.                 H1=H1->next;
  63.                 H2=H2->next;
  64.             }
  65.         }
  66.     }
  67.     //鏈表中無環
  68.     printf("this links no ring\n");
  69.     return False;
  70. }
  71. #else

  73. Bool HaveRing(link *H)
  74. {
  75.     link * Htemp = H;
  76.     //存儲所遍歷節點所有前驅節點的存儲地址，64位環境下地址占 8 個字節，所以這里用 long long 類型
  77.     long long addr[20] = { 0 };
  78.     int length = 0, i = 0;
  79.         if(Htemp==NULL||Htemp->next==NULL)
  80.         {
  81.                 return False;
  82.         }
  83.     //逐個遍歷鏈表中各個節點
  84.     while (Htemp) {
  85.         //依次將 Htemp 和 addr 數組中記錄的已遍歷的地址進行比對
  86.         for (i = 0; i < length; i++) {
  87.             //如果比對成功，則證明有環
  88.             if (Htemp == (link*)addr[i]) {
  89.                 return True;
  90.             }
  91.         }
  92.         //比對不成功，則記錄 Htemp 節點的存儲地址
  93.         addr[length] = (long long)Htemp;
  94.         length++;
  95.         Htemp = Htemp->next;
  96.     }
  97.     return False;
  98. }

  100. #endif

  102. void linkPrint(link *temp)
  103. {
  104.         link *phead=temp;
  105.     if(!temp)
  106.         printf("the link is empty\n");
  107.     else
  108.     {
  109.         while(temp)
  110.         {
  111.             printf("%d\t",temp->data);
  112.             temp=temp->next;
  113.             if(temp==phead)
  114.             {
  115.                                 printf("\r\n");
  116.                 break;
  117.             }
  118.         }
  119.     }
  120. }

  122. int main()
  123. {
  124.     link *head=linkIint(6);
  125.     linkPrint(head);
  126.     if(HaveRing(head)==True)
  127.         {
  128.                 printf("the link has a ring\r\n");
  129.         }
  130.         else
  131.         {
  132.                 printf("the link no rave\r\n");
  133.         }
  134.     return 0;
  135. }
復制代碼


51hei.png

3.以上源碼： 有環鏈表判定.7z (1.09 KB, 下載次數: 5)

評分

參與人數 1黑幣 +30 收起 理由
admin + 30 共享資料的黑幣獎勵！

查看全部評分

回復

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 立即注冊

本版積分規則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術交流QQ群281945664

Powered by 單片機教程網

快速回復 返回頂部 返回列表
主站蜘蛛池模板： 欧美精品一区二区三区在线播放 | 日韩一级二级片 | 日韩电影在线一区 | 精品自拍视频 | 国外成人在线视频网站 | 91精品国产日韩91久久久久久 | 伊人久久综合 | 亚洲自拍偷拍视频 | 欧美日韩国产在线观看 | 精品在线一区 | 91在线精品一区二区 | 成年人在线观看视频 | 在线午夜 | 天天操欧美 | a级毛片免费高清视频 | 亚洲国产精品视频 | 国产欧美一区二区三区在线播放 | 精品av | 亚洲高清在线 | 欧美激情久久久 | 日韩精品在线一区 | 一区二区精品 | 91免费在线播放 | 国产美女黄色 | 久久久久久久夜 | 久草久草久草 | 天天狠狠 | 国产96色在线 | 国产成人一区在线 | 欧美成人专区 | 国产精品视频一区二区三区四区国 | 久久精品91久久久久久再现 | 91免费观看国产 | 久久一二区 | 四虎最新地址 | 国产一区二区在线播放 | 亚洲日本激情 | 国产 日韩 欧美 在线 | 又黄又爽的网站 | 久久五月婷 | 亚洲精品乱码久久久久久按摩观 |