Leo

C語言 Linked List 鏈結串列:實現 C# List 的功能

發布於

C語言 Linked List 鏈結串列

如何實現 C# 中 List 這個好用的功能!?

  C# 有很多好用的功能,其中 List 絕對是榜上有名。有時候需要放大量資料到記憶體當中,然而若不知道該放多少資料,而是隨著使用者來動態決定大小的話。

  既不可能一開始就決定陣列大小,若宣告太大則浪費空間;若宣告太小則放不下!若使用 malloc 動態宣告,也是需要先在一開始就先知道要用多大的大小才能宣告。

  如果今天我希望有用到才增加,沒用到就刪除,能最有效率的使用記憶體空間,則 List 絕對是箇中翹楚!

  然而 C/C++ 中沒有像 C# 這麼方便的語法糖,直接 var list = new List(); 就能使用,尤其在 MCU 領域中更是以 C 語言為主,且對記憶體的使用斤斤計較,因此今天就來探討該如何自己實現基礎的 List 功能,又名 “鏈結串列 (Linked List)”

  首先需要了解一個簡單的 List 要有什麼功能?需要能動態增加 (Add);能動態刪除 (Clear);能動態取出 (Display)

  那要怎麼實現上述提到的功能呢?首先要先建立一個 struct 這個 struct 看你需要放什麼資料就建什麼樣的 struct,只是最後一定要有一個自己這個 struct 的指標來指向下一個 item。

例如我要建一個 “名字對應年齡的資料結構”:

#define NAME_LENGTH 255

struct MyStruct
{
	char Name[NAME_LENGTH];
	int Age;
	struct MyStruct* Next; // 一定要有這行!
};

資料結構知道了以後,我們會需要知道這個鏈結串列的 頭 跟 尾,故在全域變數中宣告兩個 struct 變數並指向 NULL:

struct MyStruct* _head = NULL;
struct MyStruct* _end = NULL;

動態增加 (Add)

接著可以開始來實現 Add function 了!整個概念就是:

  1. 先用 malloc 動態跟記憶體要了一塊 struct 大小的空間
  2. 接著把資料填入 struct 內
  3. 然後確保 struct 指向下一個 item 的位址為 NULL
  4. 確認現在要加入的資料是不是第一筆資料?
    如果是則將剛剛全域的 head 指向現在 malloc 的位址
    如果不是則將現在的位址放到全域 end 的下一筆資料 (next)
  5. 最後告訴大家尾巴的位址就是現在這個位址
    (所以如果是第一筆資料則頭 (head) 跟尾 (end) 的位址會指向同一個地方)
bool LinkedList_Add(char* name, int age)
{
	struct MyStruct* current = NULL;
	// 動態跟記憶體要一個空間,如果沒有空間了則 malloc 會返回 NULL
	current = (struct MyStruct*)malloc(sizeof(struct MyStruct));
	if (current == NULL)
		return false;

	// 將資料填入
	strncpy(current->Name, name, NAME_LENGTH - 1);
	current->Name[NAME_LENGTH - 1] = '\0';
	current->Age = age;
	// 確保最後資料為 NULL
	current->Next = NULL;

	// 如果是第一筆資料則 head 為 NULL,故資料添加到 head
	// 反之則將資料添加到最後面 (end) 的資料的下一筆 (next)
	if (_head == NULL)
		_head = current;
	else
	{
		_end->Next = current;
	}

	// 最後面的資料就是現在添加的資料
	_end = current;

	return true;
}

動態清除 (Clear) & 動態顯示 (Display)

接著因為 malloc 的資料是放在 heap,而不是 stack,所以不會自己釋放。必須要自己 free 來釋放記憶體,否則會造成 memory leak。而 清除 (clear) 與顯示 (display) 的概念是相似的,只是取出與 free 的差別而已,故放在一起展示:

void LinkedList_Display(void)
{
	// 從 head 取出現在的資料,如果是 NULL 則代表沒有添加任何資料
	// 由於每一筆資料都會確保 next 為 NULL,除非有下一筆資料添加,故若 next 為NULL 則代表沒有下一筆資料!
	struct MyStruct* current = NULL;
	current = _head;
	while (current != NULL)
	{
		printf("%s's Age is %d\n", current->Name, current->Age);
		current = current->Next;
	}
}

void LinkedList_Clear(void)
{
	// 概念與 display 相似,
	// 只是由於 malloc 是將記憶體放在 heap,而不是 stack,所以並不會自己釋放,必須要自己 free 來釋放記憶體,否則會造成 memory leak
	struct MyStruct* current = NULL;
	current = _head;
	while (current != NULL)
	{
		_end = current;
		current = current->Next;
		free(_end);
	}
}

  至此,一個簡單的 Linked List 就完成了!雖然還沒達到 List 這麼樣的靈活變化,但對我目前的專案來說已經足夠。其實整個 Linked List 的可玩性還是滿多的,未來專案有用到再來跟大家補充說明。

原文連結Leo Studio

喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

CC BY-NC-ND 2.0 版權聲明

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區