[資料結構] 環狀鏈結串列教學[1]: 新增與印出
我們之前已經學過鏈結串列的部分，而所謂的環狀鏈結串列，英文名為 circular linked list，就是鏈結串列的最後一個結點所指向的下一個結點，會是第一個結點，而不像鏈結串列中的最後一個結點就直接指向 NULL
完整程式碼
新增結點的函數: add_node
現在我們新增第一個數值為 5 的結點
主函數
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);print_list(head);
free_list(head);
return 0;
}
首先我們先建立一個 new_node 的結點，然後由於這是第一個結點，所以我們讓第一個結點的下一個結點，仍為自己，也就是 (*start)->next = *start;
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = NULL;
if(*start == NULL) {
*start = new_node;
(*start)->next = *start;
return;
}
這個時候我們如把只有一個結點的情況印出來，以下是環狀鏈結串列中印出所有結點的函數，這裡我們跟鏈結串列不一樣的地方在於，當我們把整個串列都印出來後，還會回頭再印出串列第一個結點的數值，代表這是個循環的鏈結串列。
印出串列數值的函數: print_list
我們首先先印出第一個結點的數值，然後再指向下一個結點，接著進入一個迴圈，這個迴圈只要 node 不等同於 NULL ，就會一直循環，但是有一個跳出條件，就是當結點又循環到原本的第一個結點的時候，也就是遍歷了所有的結點又循環到第一個結點時，就會跳出迴圈。這裡當我們經過每一個結點的時候都會印出數值，最後跳出迴圈之後，還會再印出數值一次。
void print_list(Node *node)
{
Node *first_node = node;
printf("%d ", node->data);
node = node->next;
while(node != NULL) {
if(node == first_node) break;
printf("%d ", node->data);
node = node->next;
}
printf("%d\n", node->data);
}輸出結果
5 5現在我們新增第二個數值為 128 的結點
主函數
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128)print_list(head);
free_list(head);
return 0;
}
現在我們要新增第二個數值為 128 的結點，首先我們先宣告一個 current 的結點為第一個結點，然後使用一個迴圈，當目前的 current 結點的下一個結點不是第一個結點的話，我們就讓這個這個 current 結點再成為下一個結點，直到成為這一個串列的最後一個結點。
當 current 已經是這個串列的最後一個結點的時候，我們就讓這個結點的下一個結點為新結點，並讓新結點的下一個指向第一個結點，以此完成環狀 (circular) 的效果。
else {
Node *current;
current = *start;
while(current->next != *start) {
current = current->next;
}
current->next = new_node;
new_node->next = *start;
return;
}
輸出結果
5 128 5新增第三個數值為 41 的結點
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);print_list(head);
free_list(head);
return 0;
}
輸出結果
5 128 41 5釋放掉記憶體的函數: free_list
現在我們要結束程式，所以我們要釋放掉所有的結點記憶體
這裡我們首先讓 Node *first = node，讓 first 成為第一個結點，接著我們讓 node = node ->next; 先來到第二個結點，接著我們使用一個 while 迴圈，當結點不是第一個節點的時候，我們就讓結點繼續指下去。然後依此計算整個串列有多少個結點。
計算完這個串列有多少個結點後，我們讓 current 為第一個結點，讓 temp 等同於 current，並讓 current 指向下一個結點後，再釋放掉 temp 的記憶體。如此迴圈完成後，就可以釋放掉整個串列的記憶體。
void free_list(Node *node)
{
int total_node = 1;
Node *first = node;
node = node->next;
while(node != first) {
node = node->next;
total_node++;
}Node *current = first;
Node *temp;
int i;
for(i = 0; i < total_node; i++) {
temp = current;
current = current->next;
free(temp);
}
}
