天天看點

資料結構之循環連結清單的建立(C語言)

概念

将單連結清單中終端結點的指針端由空指針改為指向頭結點,就使整個單連結清單形成一個環。這種頭尾相接的單連結清單稱為單循環連結清單,簡稱循環連結清單(circular linked list)

循環連結清單帶有頭結點的空連結清單

資料結構之循環連結清單的建立(C語言)

非空的循環連結清單

資料結構之循環連結清單的建立(C語言)

其實循環連結清單和單連結清單的主要差異就是在循環的判斷條件上,原來是判斷p->next是否為空,現在是p->next不等于頭結點,則循環結束。

不使用頭指針,使用指向終端結點的尾指針表示循環連結清單,此時查找開始結點和終端結點就比較友善。

資料結構之循環連結清單的建立(C語言)

上圖所示,終端結點使用尾指針rear訓示,則查找終端結點是O(1),而開始結點,其實就是rear->next->next,其時間複雜度也為O(1).

将兩個循環連結清單合成一個表

有了尾指針合并就非常簡單,他們的尾指針分别是rearA和rearB。

資料結構之循環連結清單的建立(C語言)

我們現在把兩個連結清單合并

資料結構之循環連結清單的建立(C語言)
p = rearA->next;  //儲存表A的頭結點
rearA->next = rearB ->next->next; //将本是指向表B的第一個結點(不是頭結點)指派給rearA->next
rearB->next = p;  //将原表A的頭結點指派給rearB->next
free(p)   //釋放p
           

繼續閱讀