[資料結構] 雙向環狀鏈結串列教學[1]: 新增與印出
在之前的篇章中,介紹了鏈結串列、雙向鏈結串列以及環狀鏈結串列,這篇文章將介紹雙向環狀鏈結串列。所謂的雙向鏈結串列,英文名稱為doubly circular linked list,在這個資料結構中,串列的每個結點是可以前後互相連通的,並且當遍歷整個串列後,最後會回到最源頭的那個結點
完整程式碼
新增結點的函數: add_node
主函數
int main()
{
Node *head = NULL;
add_node(&head, 5);
inverse_print_list(head);
free_list(head);
return 0;
}
這裡我們先建立第一個結點,這是第一個結點,所以這個不管是往前指還是往後指,都會是自己,也就是new_node->next = new_node,new_node->prev = new_node,最後再去確認,如果是新增第一個結點,也就是*start還沒有被真正設定,就讓設定的new_node等同於*start
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = new_node;
new_node->prev = new_node;
if(*start == NULL) {
*start = new_node;
return;
}
這時候創造完第一個結點後,就可以印出來確認是否創造doubly circular linked list成功
印出串列數值的函數: print_list
這邊的print_list函數,會讓第一個node先印出數值,接著讓指向下一個node,然後進入迴圈,這個迴圈地跳出條件為當node為第一個node的時候就會跳出,要不然就會印出目前的訊息,然後再往下指,跳出後還會再印出目前結點的數值,其實就是要印出第一個結點的數值。
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
輸出結果
5 5
反向印出串列數值的函數: inverse_print_list
其實調用的方法與print_list是一樣的,都是把第一個結點當作參數帶入到函數中,但是這邊將第一個結點命名為last_node,並且往前去走。這邊與print_list的方式一樣,先印出last_node的數值,接著將結點往前移,接著進入迴圈,如果是最後一個結點,就會跳出迴圈,如果不是的話,會印出結點內容,接著就會把結點往前移。
最後跳出迴圈的時候,會再印出最後一個結點的數值。
void inverse_print_list(Node *node)
{
Node *last_node = node;
printf("%d ", node->data);
node = node->prev;
while(node != NULL) {
if(node == last_node) break;
printf("%d ", node->data);
node = node->prev;
}
printf("%d\n", node->data);
}
對於只有一個結點的情況,印出數值5之後,由於是最後一個結點,在迴圈的判斷中就會跳出,跳出迴圈後,會再印出最後一個結點的數值,其實數值就是5
5 5
現在我們新增第二個數值為128的結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
新增第二個數值為128的結點後,此時在add_node的函數裡,因為不是屬於第一個結點,所以會執行else裡面的程式碼。
在else裡面的程式碼,其實就是宣告一個current的指標,並將*start設定為current,接下來就開始迭代這個鏈結串列,最後當迴圈走回到第一個結點的時候,就跳出迴圈。
這樣的程式碼就代表,經過迴圈的迭代之後,current會留在第一個結點的前一個結點
void add_node(Node **start, int value)
{
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = new_node;
new_node->prev = new_node;
if(*start == NULL) {
*start = new_node;
return;
}
else {
Node *current;
current = *start;
while(current->next != *start) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
new_node->next = *start;
(*start)->prev = new_node;
}
}
此時就開始執行添加結點的第一個程式碼,將目前結點的下一個結點,指向new_node
current->next = new_node;
接著將這個數值為128的結點,往前指向數值為5的解點
new_node->prev = current;
新結點的下一個結點,將會指向第一個結點
new_node->next = *start;
第一個結點的前一個結點,會指向新結點
(*start)->prev = new_node;
最後執行程式碼,不管是正向印出,還是反向印出,都可以得到相同的結果
正向印出
5 128 5
反向印出
5 128 5
新增第三個數值為41的結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
新增完之後,doubly circular linked list的示意圖會如下
輸出結果為
正向印出
5 128 41 5
反向印出
5 41 128 5
釋放掉記憶體的函數: free_list
最後當所有鏈結串列都建置完成之後,就可以來釋放掉記憶體
這裡首先先設置一個total_node的變數,給予數值為1,接著開始使用迴圈迭代整個串列,以得到整個串列到底有多少結點
在確定有多少個結點之後,在這邊使用一個for迴圈,將current結點設定為第一個結點,並且讓current等同於temp,然後讓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);
}
}