動態記憶體配置
首先，在介紹鏈結串列之前，我們必須認識動態記憶體配置與如何表示一個節點，以下為語法:
動態記憶體配置是透過標準函式庫中的malloc來完成的，而在使用完記憶體後要記得釋放它以避免記憶體洩漏。那要使用這些函數，我們必須引入標頭檔stdlib.h動態記憶體配置語法
資料型別 *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;
}
鏈結串列
鏈結串列中的每個節點包含兩個主要部分：
- 資料部分：存放節點的值。
- 指標部分：指向下一個節點的位址。
語法:
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;
}
節點創建流程圖示:
節點走訪流程圖示:
