數據結構-2.單向鏈表的實現

節點結構體設計

struct LinkNode
{
	// 數據域
	void* data;
	// 指針域
	struct LinkNode * next;
};

• data：一個 void* 類型的指針，指向節點存儲的數據。使用 void* 是為了鏈表能夠存儲不同類型的數據。
• next：一個指向下一個 LinkNode 結構體的指針，形成鏈表的鏈接。

鏈表結構體設計

struct LList
{
	//頭節點
	struct LinkNode pHeader;
	//鏈表長度
	int m_size;
};

• pHeader：鏈表的頭節點。雖然 pHeader 本身也是 LinkNode 類型，但它可以作為鏈表的起始節點，其 next 指針指向第一個實際的數據節點。
• m_size：一個整數，表示鏈表中節點的數量。

初始化鏈表

LinkList init_LinkList()
{
	struct LList* myList = malloc(sizeof(struct LList));
	
	if (myList == NULL)
	{
		return NULL;
	}

	myList->pHeader.data = NULL;
	myList->pHeader.next = NULL;
	myList->m_size = 0;

	return myList;
}

• 使用 malloc 分配 struct LList 的記憶體。
• 初始化頭節點的 data 指針為 NULL，next 指針也為 NULL。
• 設置鏈表長度 m_size 為 0。

插入鏈表

void insert_LinkList(LinkList list, int pos, void* data)
{
	if (list == NULL) 
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	// 將list還原成struct LList數據類型
	struct LList * myList = list;

	if (pos <0 || pos > myList->m_size)
	{
		//位置無效 強制尾插
		pos = myList->m_size;
	}
	//找到插入節點的前驅
	struct LinkNode * pCurrent = &myList->pHeader;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//創建新節點
	struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//建立節點關係

	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	//更新鏈表長度
	myList->m_size++;
}

• 檢查 list 和 data 是否為空，若為空則返回。
• 如果位置 pos 無效（負數或超出鏈表當前大小），將位置設置為鏈表末尾。
• 通過遍歷找到插入位置的前驅節點 pCurrent。
• 創建新節點並插入鏈表中。
• 更新鏈表長度 m_size。

遍歷鏈表

void foreach_linkList(LinkList list,void(*myForeach)(void *))
{
	if (list == NULL)
	{
		return;
	}

	struct LList* mylist = list;

	struct LinkNode* pCurrent = mylist->pHeader.next;
	for (int i = 0; i < mylist->m_size; i++)
	{
		myForeach(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}

• 檢查 list 是否為空，若為空則返回。
• 使用 pCurrent 遍歷鏈表，從頭節點的下一個節點開始。
• 對每個節點的數據調用 myForeach，然後移動到下一個節點。

本文來自博客園，作者：ffff5，轉載請註明原文鏈接：https://www.cnblogs.com/ffff5/p/18343309