資料結構（4）連結清單的介紹與代碼實作（c語言)

上篇部落格已經複習了順序表，由于順序表在底層是連續的，是以讀取元素非常簡單，但是插入和删除需要移動大量的資料非常麻煩（時間複雜度O(n) ）；為了解決這個問題，連結清單出現了。

連結清單，就是底層是鍊式存儲結構的線性表。鍊式存儲結構在存儲資料的時候不僅會儲存資料，還會額外提供一個指針，指向下一個元素，如下圖。由于連結清單在底層是不連續的空間，是以需要指針來指向下一個元素，但是如果在連結清單中插入或删除元素，隻需要改變這個元素前後指向它的指針，而不需要改變整個連結清單，是以在連結清單中進行插入和删除都非常友善。

連結清單的細分：

1. 按照指針數量分
   1. 單連結清單：隻有一個指向下一個節點的指針。
   2. 雙連結清單：有一個指向下一個節點的指針，還有一個指向上一個節點的指針。
2. 按照連結清單是否循環分
   1. 循環連結清單：即連結清單的尾指針指向頭結點
   2. 不循環連結清單：即連結清單的尾指針指向NULL
3. 按照是否帶頭結點分
   1. 帶頭結點的連結清單：連結清單中的第一個結點中不存放有效的資料（相當于哨兵）
   2. 不帶頭結點的連結清單：連結清單中的第一個節點為有效結點

在所有連結清單中以不帶頭節點，不循環的單連結清單和帶頭節點，循環的雙連結清單最為常見，下面的代碼隻實作這兩種常見結構。

在實作代碼前，有一個重要的問題需要讨論，就是傳參問題，

即什麼情況下我們需要傳二級指針？

假設形參是普通變量，在傳遞的時候，如果我們打算對普通變量進行修改，那麼我們就需要傳遞變量的位址；如果我們不打算修改普通變量（比如隻是檢視一下内容），那麼我們的形參傳遞數值就可以（此時形參是實參的一份臨時copy）。

同樣的，如果我們的形參是指針變量，如果我們打算修改這個指針變量，那麼我們傳遞的時候就需要二級指針；否則傳遞一級指針就OK。

這個理論放到連結清單實作裡就是說：我們在設計連結清單的時候會設計一個頭指針pNode，這個頭指針pNode會指向頭結點（第一個有效結點），是以頭指針裡面存的就是頭結點的位址。如果我們要修改頭指針裡面所儲存的位址（比如初始化連結清單時，讓頭指針指向NULL；再比如頭插的時候，頭指針儲存的位址會發生變化，變成新插入節點的位址）時，在設計函數的時候就需要傳遞二級指針；如果我們隻是檢視頭指針指向的内容，這樣并不會改變頭指針本身儲存的位址，此時傳遞一級指針就可以。

是以，一般銷毀，初始化，頭插等需要用到二級指針；查找，周遊等傳遞一級指針就OK。

了解了傳參的問題，開始實作代碼。

單連結清單的實作代碼

-------------------------------- SList.h-------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS 1

// #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int DataType;

typedef struct SListNode
{
	struct SListNode* next;  //指針域
	DataType data;  //資料域

}SListNode, *pSListNode, **ppSListNode;



pSListNode CreateSListNode(DataType x);//建立一個節點
void SListInit(ppSListNode pphead);//初始化
void SListPrint(pSListNode phead);//列印連結清單
void SListPushFront(ppSListNode pphead, DataType x);//頭插
void SListPushBack(ppSListNode pphead, DataType x);//尾插
void SListInsert(ppSListNode pphead, pSListNode pos, DataType x);//插入
void SListInsert(ppSListNode pphead, size_t pos, DataType x);//将x插入第pos個節點之後
void SListPopFront(ppSListNode pphead);//頭删
void SListPopBack(ppSListNode pphead);//尾删
void SListErase(ppSListNode pphead, pSListNode pos);//給定節點删除
void SListRemove(ppSListNode pphead, DataType x);//按值删除，删除遇到的第一個點
void SListRemoveALL(ppSListNode pphead, DataType x);//按值删除，删除所有的
void SListDestory(ppSListNode pphead);//銷毀
pSListNode SListFind(pSListNode phead, DataType data);//按值查找，傳回第一個找到的結點指針，如果沒有找到，傳回NULL
int SListEmpty(pSListNode phead);//判斷是否為空
int SListSize(pSListNode phead);//算節點數

           

----------------------------------------------------------SList.c--------------------------------------------------------

//建立一個節點
pSListNode CreateSListNode(DataType x)
{
	pSListNode node = (pSListNode)malloc(sizeof(SListNode));
	assert(node);
	node->data = x;
	node->next = NULL;
	return node;
}

//初始化：這裡使用了二級指針，也可以使用一級指針的引用型參數。
void SListInit(ppSListNode pphead)
{
	assert(pphead);
	*pphead = NULL;
}

//列印連結清單
void SListPrint(pSListNode phead)
{
	pSListNode cur = phead;
	for(cur = phead; cur != NULL; cur = cur->next)
	{
		printf("%2d->", cur->data);
	}
	printf("NULL\n");
	
}

//頭插
void SListPushFront(ppSListNode pphead, DataType x)
{
	assert(pphead);
	//先檢查是否為空
	if (NULL == *pphead)
	{
		//連結清單為空時，建立一個頭結點，該節點的next為NULL，指針*pphead指向它。
		*pphead = CreateSListNode(x);		
	}
	else 
	{
		pSListNode pNode = CreateSListNode(x);
		pNode->next = *pphead;
		*pphead = pNode;
	}
	
}

//尾插
void SListPushBack(ppSListNode pphead, DataType x)
{
	assert(pphead);
	if (NULL == *pphead)//先檢查是否為空
	{
		pSListNode pNode = CreateSListNode(x);
		return;
	}
	else
	{
		pSListNode cur = *pphead;
		while (NULL != cur->next)
		{
			cur = cur->next;
		}
		cur->next = CreateSListNode(x);
				
	}
}

//給定節點插入：1.先檢查pos的合法性 2.建立一個以x為值的新節點newNode（一級指針） 
void SListInsert(ppSListNode pphead, pSListNode pos, DataType x)
{

	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
		return;
	}
	pSListNode newNode = CreateSListNode(x);

#if 0  //如果常量為真，執行程式段1，否則執行程式段2

	//3.在單連結清單上找到這個位置的前一個節點tmp 4.newNOde的next指向tmp的next 5. tmp的next指向newNode。   此功能主要運算時間耗費在查找上，時間複雜度為O(n)
	pSListNode tmp = *pphead;
	while (tmp->next != pos)
	{
		tmp = tmp->next;
	}
	newNode->next = tmp->next;
	tmp->next = newNode;
#else
	newNode->data = pos->data;
	pos->data = x;
	newNode->next = pos->next;
	pos->next = newNode;

#endif
}

//将x插入第pos個節點之後
void SListInsert(ppSListNode pphead, size_t pos, DataType x)
{
	assert(pphead);
	int size = SListSize(*pphead);
	assert(pos >= 0 && pos <= size);
	pSListNode node = CreateSListNode(x);//建立一個節點
	pSListNode tmp = *pphead;
	if (0 == pos) {//頭插
		SListPushFront(pphead, x);
	}
	else 
	{
		while (pos-1)//有疑問
		{
			tmp = tmp->next;
			pos--;
		}
		node->next = tmp->next;
		tmp->next = node;
	}
}

//頭删
void SListPopFront(ppSListNode pphead)
{
	assert(pphead);
	assert(*pphead);
	pSListNode tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
}

//尾删
void SListPopBack(ppSListNode pphead)
{
	assert(pphead);
	assert(*pphead);
	//如果隻有一個頭節點
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	pSListNode first = *pphead;
	while (NULL != first->next->next)
	{
		first = first->next;

	}
	free(first->next);
	first->next = NULL;

}

//給定節點删除：1.先檢查pos的合法性  
void SListErase(ppSListNode pphead, pSListNode pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(pphead);
		return;
	}
#if 0

	//2.在單連結清單上找到删除位置的前一個節點cur 3.cur的next指向删除pos的next    此功能主要運算時間耗費在查找上，時間複雜度為O(n)
	pSListNode cur = *pphead;
	while (pos != cur->next)
	{
		cur = cur->next;
	}
	cur->next = pos->next;
	free(pos);
	pos = NULL;
#else
	if (pos != NULL && NULL != pos->next)
	{
		pSListNode node = pos->next;
		pos->data = pos->next->data;
		pos->next = node->next;
		free(node);
		node = NULL;
	}
	else if (NULL == pos->next)
	{
		//即要删除的是最後一個元素
		SListPopBack(pphead);
	}
#endif
}

//按值删除，删除遇到的第一個點
void SListRemove(ppSListNode pphead, DataType x)
{
	assert(pphead);
	assert(*pphead);
	pSListNode pos = SListFind(*pphead, x);
	if (NULL == pos)
	{
		printf("沒有這個數值\n");
	}
	else
	{
		SListErase(pphead, pos);
	}
	
}

//按值删除，删除所有的
void SListRemoveALL(ppSListNode pphead, DataType x)
{
	assert(pphead);
	assert(*pphead);

	pSListNode pos = NULL;
	while (NULL != (pos = SListFind(*pphead, x)))
	{
		SListErase(pphead, pos);
	}

}

//銷毀
void SListDestory(ppSListNode pphead)
{
	assert(pphead);
	pSListNode node = *pphead;
	while (node)
	{
		pSListNode newNode = node;
		node = node->next;
		free(newNode);
		newNode = NULL;
	}
	*pphead = NULL;
}

//按值查找，傳回第一個找到的結點指針，如果沒有找到，傳回NULL
pSListNode SListFind(pSListNode phead, DataType data)
{
	assert(phead);
	pSListNode node = phead;
	while (node)
	{
		if (data == node->data)
		{
			return node;
		}
		node = node->next;
	}
	return NULL;

}

//判斷是否為空,為空傳回0
int SListEmpty(pSListNode phead)
{
	return phead == NULL ? 0 : 1;
}

//算節點數
int SListSize(pSListNode phead)
{
	assert(phead);	
	size_t size = 0;
	pSListNode node = phead;
	while (node)
	{
		node = node->next;
		size++;
	}
	return size;
}

//逆序列印(遞歸)
void SListReverse(pSListNode phead)
{
	if (NULL == phead)
	{
		return;
	}
	SListReverse(phead->next);
	printf("%2d->", phead->data);
}

           

--------------------------------------------------------測試代碼 test.c------------------------------------------------------------

void Test()
{
	pSListNode list = NULL;
	SListInit(&list);
	
	SListPushFront(&list, 1);//頭插
	SListPushFront(&list, 2);//頭插
	SListPushFront(&list, 3);//頭插
	SListPushFront(&list, 4);//頭插
	SListPrint(list);
	
	SListPushBack(&list, 101);//尾插
	SListPushBack(&list, 102);//尾插
	SListPushBack(&list, 103);//尾插
	SListPushBack(&list, 104);//尾插
	SListPrint(list);

	SListInsert(&list, list->next, 100);//任意位置插
	SListPrint(list);

	SListErase(&list, list->next);//任意位置删
	SListPrint(list);

	int ret = SListSize(list);//算節點數
	printf("節點數%d\n", ret);
	int cur = SListEmpty(list);//判斷是否為空
	if (cur == 0)
		printf("連結清單為空\n");
	else
		printf("連結清單不為空\n");
	SListInsert(&list, list->next->next, 1);//任意位置插
	SListInsert(&list, list->next->next->next->next, 1);//任意位置插
	SListPushBack(&list, 1);//尾插
	SListPushFront(&list, 1);//頭插
	SListPrint(list);
	SListRemove(&list, 1);//删除第一個x
	SListPrint(list);

	SListRemoveALL(&list, 1);//删除所有x
	SListPrint(list);

	SListDestory(&list);//銷毀
	SListPrint(list);

	SListPushFront(&list, 1);//頭插
	SListPushFront(&list, 2);//頭插
	SListPushFront(&list, 3);//頭插
	SListPushFront(&list, 4);//頭插
	SListPrint(list);

	SListInsert(&list, 1, 100);
	SListPrint(list);

	SListReverse(list);//逆序列印
	printf("NULL\n");
}

int main()
{
	Test();
	system("pause");
	return 0;
}


           

------------------------------------------------------結果---------------------------------------

雙連結清單的實作代碼

-------------------------------------------------------------DoubleList.h-------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS 1

//  #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int DataType;
typedef struct DListNode
{
	struct DListNode *next;
	struct DListNode *prev;
	DataType data;
}DListNode, *pDListNode, **ppDListNode;

void DListInit(ppDListNode pphead);//初始化
pDListNode CreatDListNode(DataType x);//創造一個節點
void DListPushFront(ppDListNode pphead, DataType data);//頭插
void DListPushBack(ppDListNode pphead, DataType data);//尾插
void DListInsert(ppDListNode pphead, pDListNode pos, DataType data);//任意位置插入
void DListPopFront(ppDListNode pphead);//頭删
void DListPopBack(ppDListNode pphead);//尾删
void DListErase(ppDListNode pphead, pDListNode pos);//任意位置删除
void DListRemove(ppDListNode pphead, DataType x);//删除遇到的第一個數
void DListRemoveAll(ppDListNode pphead, DataType x);//删除遇到的所有的數字
pDListNode DListFind(pDListNode phead, DataType x);//查x所在的節點位置
int DListSize(pDListNode phead);//算節點數
int DListEmpty(pDListNode phead);//判斷是否為空
void DListClear(ppDListNode pphead);//清空
void DListDestory(ppDListNode pphead);//銷毀
void DListPrint(const pDListNode phead);//列印

           

-----------------------------------------------------DoubleList.c---------------------------------------------------------------

//創造一個節點
pDListNode CreatDListNode(DataType x)
{
	pDListNode newNode = (pDListNode)malloc(sizeof(DListNode));
	assert(newNode);
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

//初始化
void DListInit(ppDListNode pphead)
{
	assert(pphead);
	int num = 0;
	*pphead = CreatDListNode(num);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
	return;
}

//頭插
void DListPushFront(ppDListNode pphead, DataType data)
{
	assert(pphead);
	pDListNode newNode = CreatDListNode(data);
	pDListNode first = (*pphead)->next;

	(*pphead)->next = newNode;
	newNode->prev = *pphead;
	newNode->next = first;
	first->prev = newNode;
	return;
}

//尾插
void DListPushBack(ppDListNode pphead, DataType data)
{
	assert(pphead);
	pDListNode newNode = CreatDListNode(data);
	pDListNode end = (*pphead)->prev;

	end->next = newNode;
	newNode->prev = end;
	newNode->next = (*pphead);
	(*pphead)->prev = newNode;
}

//任意位置插入：1.建立一個以data為值的新節點newNode 2.在雙連結清單上找到插入位置的前一個節點cur 3.newNode的next指向pos 4.newNode的prev指向cur 5.将pos的prev指向newNode 6.cur的next指向newNode
void DListInsert(ppDListNode pphead, pDListNode pos, DataType data)
{
	assert(pphead);
	assert(pos);

	pDListNode newNode = CreatDListNode(data);
	pDListNode cur = pos->prev;

	newNode->next = pos;
	newNode->prev = cur;
	pos->prev = newNode;
	cur->next = newNode;
}

//頭删
void DListPopFront(ppDListNode pphead)
{
	assert(pphead);
	if (NULL == (*pphead)->next)
	{
		printf("連結清單為空，不可以删除\n");
		return;
	}

	pDListNode first = (*pphead)->next;
	pDListNode second = first->next;
	(*pphead)->next = second;
	second->prev = (*pphead);
	free(first);
	first = NULL;
}

//尾删
void DListPopBack(ppDListNode pphead)
{
	assert(pphead);
	if (NULL == (*pphead)->next)
	{
		printf("連結清單為空，不可以删除\n");
		return;
	}

	pDListNode end = (*pphead)->prev;
	pDListNode penultimate = end->prev;

	penultimate->next = (*pphead);
	(*pphead)->prev = penultimate;
	free(end);
	end = NULL;
}

//任意位置删除
void DListErase(ppDListNode pphead, pDListNode pos)
{
	assert(pphead);
	assert(pos);
	assert(pos != (*pphead));
	if (NULL == (*pphead)->next)
	{
		printf("連結清單為空，不可以删除\n");
		return;
	}

	pDListNode tmp1 = (pos)->prev;
	pDListNode tmp2 = pos->next;

	tmp1->next = tmp2;
	tmp2->prev = tmp1;

	free(pos);
	pos = NULL;

}

//查x所在的節點位置
pDListNode DListFind(pDListNode phead, DataType x)
{
	assert(phead);
	pDListNode cur = phead->next;

	while (phead != cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//删除遇到的第一個數
void DListRemove(ppDListNode pphead, DataType x)
{
	assert(pphead);
	pDListNode node = DListFind(*pphead, x);
	if ((NULL != node) && (node != *pphead))
	{
		DListErase(pphead, node);
	}
	else {
		printf("沒有這個數字，無法删除\n");
	}
}

//删除遇到的所有的數字
void DListRemoveAll(ppDListNode pphead, DataType x)
{
	assert(pphead);
	pDListNode pos;
	
	while ((NULL != (pos = DListFind(*pphead, x))) && (pos != *pphead))
	{
	
		DListErase(pphead, pos);
		
	}
}

//算節點數
int DListSize(pDListNode phead)
{
	assert(phead);
	pDListNode node = phead->next;
	size_t num = 0;
	while (node != phead)
	{
		num++;
		node = node->next;
	}
	return num;//不算頭結點
}

//判斷是否為空
int DListEmpty(pDListNode phead)
{
	return phead->next == phead ? 0 : 1;
}

//清空
void DListClear(ppDListNode pphead)
{
	assert(pphead);
	pDListNode first = (*pphead)->next;
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);

	pDListNode cur = first;
	while (first != (*pphead))
	{		
		first = first->next;
		free(cur);
		cur = NULL;
	}
}

//銷毀
void DListDestory(ppDListNode pphead)
{
	assert(pphead);
	DListClear(pphead);
	free(*pphead);
	*pphead = NULL;
}
//列印
void DListPrint(const pDListNode phead)
{
	assert(phead);
	pDListNode cur = phead->next;
	printf("連結清單内容為：%2d->", phead->data);
	while (cur != phead)
	{
		printf("%2d->", cur->data);
		cur = cur->next;
	}
	printf("%2d\n", phead->data);
}
           

-----------------------------------------------test.c---------------------------------------------------------------------------

void Test()
{
	DListNode *list = NULL;
	DListInit(&list);
	DListPushFront(&list, 1);//頭插
	DListPushFront(&list, 2);//頭插
	DListPushFront(&list, 3);//頭插
	DListPushFront(&list, 4);//頭插
	DListPrint(list);
	DListPushBack(&list, 101);//尾插
	DListPushBack(&list, 102);//尾插
	DListPushBack(&list, 103);//尾插
	DListPushBack(&list, 104);//尾插
	DListPrint(list);
	DListInsert(&list, list->next, 100);//任意位置插
	DListPrint(list);
	DListErase(&list, list->next);//任意位置删

	DListPrint(list);
	int ret = DListSize(list);//算節點數
	printf("節點數%d\n", ret);
	int cur = DListEmpty(list);//判斷是否為空
	if (cur == 0)
		printf("連結清單為空\n");
	else
		printf("連結清單不為空\n");
	DListInsert(&list, list->next->next, 1);//任意位置插
	DListPrint(list);
	DListInsert(&list, list->next->next->next->next, 1);//任意位置插
	DListPrint(list);
	DListPushBack(&list, 1);//尾插
	DListPushFront(&list, 1);//頭插
	DListPrint(list);

	DListRemove(&list, 1);//删除x
	DListPrint(list);
	printf("hehe1\n");
	DListRemoveAll(&list, 1);//删除x
	printf("hehe2\n");
	DListPrint(list);

	DListClear(&list);//清空
	DListPrint(list);
	DListDestory(&list);//銷毀
}


int main()
{
	Test();
	system("pause");
	return 0;
}

           

-----------------------------------------------------------------結果-------------------------------------------------------------