C語言自學攻略-認識鏈結串列

動態記憶體配置

首先，在介紹鏈結串列之前，我們必須認識動態記憶體配置與如何表示一個節點，以下為語法:

動態記憶體配置語法

資料型別 *ptr = (資料型別 *)malloc(sizeof(資料型別) X 數量);

示範分配一個整數大小的記憶體

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

int main() {
    int *ptr = (int *)malloc(sizeof(int));  // 分配一個整數大小的記憶體塊
    if (ptr == NULL) {
        printf("記憶體分配失敗\n");
        return 1;
    }

    *ptr = 10;  // 使用動態分配的記憶體
    printf("動態分配的值: %d\n", *ptr);

    free(ptr);  // 釋放記憶體
    return 0;
}

示範動態配置一連續記憶體陣列

#include <stdlib.h>
#include <stdio.h>
int main(void)
{
		int *ptr, i;
		ptr=(int *) malloc(3*sizeof(int));
		*ptr=12;
		*(ptr+1)=35;
		*(ptr+2)=140;
		
				for(i=0; i<3; i++)
				printf("*ptr+%d=%d\n",i,*(ptr+i)); //指標方式存取
				free(ptr);
				getchar();
   	return 0;
}

這邊我提一下另一個有關動態記憶體配置的函式realloc()，該函式用於調整已經動態分配的記憶體塊大小(擴展或縮小) :

有時，動態分配的記憶體不足或超出需求。

在這種情況下，我們使用realloc()函式來更改動態分配的記憶體大小。以下為語法:

ptr =realloc(ptr, newSize);

• 在這裡，我們重新分配ptr了新的大小。

範例:

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

int main() {
    int *arr;
    int n = 5;

    // 動態分配初始記憶體
    arr = (int *)malloc(n * sizeof(int));

    // 初始化陣列
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }

    // 顯示原始陣列
    printf("原始陣列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 擴展記憶體
    n = 10;
    arr = (int *)realloc(arr, n * sizeof(int));

    // 初始化新元素
    for (int i = 5; i < n; i++) {
        arr[i] = i + 1;
    }

    // 顯示擴展後的陣列
    printf("擴展後的陣列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 釋放記憶體
    free(arr);
    return 0;
}

鏈結串列

鏈結串列中的每個節點包含兩個主要部分：

1. 資料部分：存放節點的值。
2. 指標部分：指向下一個節點的位址。

語法:

struct Node {
    int data;           // 資料部分
    struct Node *next;  // 指標部分，指向下一個 Node 節點
};

接下來示範如何使用:

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

// 主函數：程式進入點
int main(void)
{
    int num, i;  // 宣告變數：num 用來存放學生數量，i 為迴圈計數器

    // 定義結構體 student，包含學生姓名與分數兩個成員
    struct student       
    {
        char name[10]; // 用來存放學生姓名的字元陣列，最多可存 9 個字元 + '\0'
        int score;     // 用來存放學生分數
    } *ptr;  // 宣告一個指向 struct student 結構的指標 ptr

    // 提示使用者輸入學生數量
    printf("Number of student: ");
    scanf("%d", &num);  // 讀取使用者輸入的學生數量，存入變數 num

    // 使用 malloc 根據學生數量動態配置記憶體，配置的空間大小為 num 個 student 結構的大小
    ptr = (struct student *) malloc(num * sizeof(struct student));

    // 使用迴圈逐一輸入每位學生的資料
    for (i = 0; i < num; i++)
    {
        // 輸入學生姓名
        printf("name for student %d: ", i + 1);
        // 將使用者輸入的字串存入第 i 個 student 結構的 name 成員
        scanf("%s", (ptr + i)->name);

        // 輸入學生分數
        printf("score for student %d: ", i + 1);
        // 將使用者輸入的整數存入第 i 個 student 結構的 score 成員
        scanf("%d", &(ptr + i)->score);
    }

    // 使用迴圈逐一印出所有學生的姓名與分數
    for (i = 0; i < num; i++)
    {
        printf("%s: score=%d\n", (ptr + i)->name, (ptr + i)->score);
    }

    // 釋放先前使用 malloc 配置的記憶體空間，以避免記憶體洩漏
    free(ptr);

    return 0; // 程式正常結束
}

• -> 是用來透過指標存取結構體成員的運算子，不要忘記喔!
• ptr 是指向結構體的指標。
• (ptr + i) 透過指標運算，指向學生陣列中的第 i 個元素。
• ->name 則存取該結構中的 name 成員。

有了基本的認識，接下來就可以示範鏈結串列，這個程式碼功能為輸入節點個數，並且針對每個節點輸入資料，並在最後顯示節點的資料以及指向關係，讀者可以搭配程式碼下方的圖來了解程式流程:

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

struct node
{
    int data;                   // 資料成員
    struct node *next;          // 鍊結成員，存放指向下一個節點的指標
};

typedef struct node NODE;       // 將 struct node 定義成 NODE 型態

int main(void)
{
    int i, val, num;
    NODE *first, *current, *previous;   // 建立 3 個指向 NODE 的指標
    printf("Number of nodes: ");
    scanf("%d", &num);                  // 輸入節點的個數

    for (i = 0; i < num; i++)
    {
        current = (NODE *) malloc(sizeof(NODE));    // 建立新的節點
        if (current == NULL)
        {
            printf("Memory allocation failed\n");
            return 1;                               // 若分配失敗，結束程式
        }
        printf("Data for node %d: ", i + 1);
        scanf("%d", &(current->data));              // 輸入節點的 data 成員
        if (i == 0)
            first = current;                        // 如果是第一個節點，把標示 first 指向目前的節點
        else
            previous->next = current;               // 把前一個節點的 next 指向目前的節點
        current->next = NULL;                       // 把目前節點的 next 指向 NULL
        previous = current;                         // 把前一個節點設成目前的節點
    }

    current = first;                                // 設定 current 為第一個節點
    while (current != NULL)                         // 如果還沒有到串列末端，則進行走訪的動作
    {
        printf("address=%p, ", (void *)current);    // 印出節點的位址
        printf("data=%d, ", current->data);         // 印出節點的 data 成員
        printf("next=%p\n", (void *)current->next); // 印出節點的 next 成員
        previous = current;                         // 使用 previous 暫存當前節點
        current = current->next;                    // 設定 current 指向下一個節點
        free(previous);                             // 釋放當前節點
    }

    // 將 沒用到的指針 指向 NULL，避免成為野指標(current最後值已經是 NULL，不用再設定)
    first = NULL;
		previous = NULL;
		
		    return 0;
}

節點創建流程圖示:

節點走訪流程圖示: