鏈表介紹

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，

實際中，鏈表的結構多種多樣：
1、帶頭，不帶頭，

2、單向，雙向，

3、回圈，非回圈，

通過以上的這些情況組合起來，就有八種鏈表結構，即帶頭單向回圈鏈表、帶頭單向非回圈鏈表、帶頭雙向回圈鏈表、帶頭雙向非回圈鏈表、無頭單向回圈鏈表、無頭單向非回圈鏈表、無頭雙向回圈鏈表、無頭雙向非回圈鏈表，

本篇博客講解的是無頭單向非回圈鏈表，

初始化鏈表

鏈表是由一個個結點鏈接而成，創建一個鏈表之前，我們首先要創建一個結點型別，該型別由兩部分組成：資料域和指標域，

typedef int SLTDataType;//篇博客以存放整型資料為例

typedef struct SListNode
{
	SLTDataType data;//資料域：用于存盤該結點的資料
	struct SListNode* next;//指標域：用于存放下一個結點的地址
}SListNode;

列印單鏈表

列印鏈表時，我們需要從頭指標指向的位置開始，依次向后列印，直到指標指向NULL時，結束列印，

//列印鏈表
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;//接收頭指標
	while (cur != NULL)//判斷鏈表是否列印完畢
	{
		printf("%d->", cur->data);//列印資料
		cur = cur->next;//指標指向下一個結點
	}
	printf("NULL\n");//列印NULL，表明鏈表最后一個結點指向NULL
}

增加結點

仔細想想，每當我們需要增加一個結點之前，我們必定要先申請一個新結點，然后再插入到相應位置，于是我們可以將該功能封裝成一個函式，

//創建一個新結點，回傳新結點地址
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));//向新結點申請空間
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;//將資料賦值到新結點的資料域
	node->next = NULL;//將新結點的指標域置空
	return node;//回傳新結點地址
}

單鏈表的頭插

頭插時，我們只需要先讓新結點的指標域指向頭指標指向的位置（即原來的第一個結點），然后讓頭指標指向新結點即可，

//頭插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	SListNode* newnode = BuySLTNode(x);//申請一個新結點
	newnode->next = *pplist;//讓新結點的指標域指向地址為pos的結點的下一個結點
	*pplist = newnode;//讓地址為pos的結點指向新結點
}

注：這兩步操作的順序不能顛倒，若先讓頭指標指向新結點，那么就無法找到原來第一個結點的位置了，

單鏈表的尾插

尾插的時候我們需要先判斷鏈表是否為空，若為空，則直接讓頭指標指向新結點即可；若不為空，我們首先需要利用回圈找到鏈表的最后一個結點，然后讓最后一個結點的指標域指向新結點，

//尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newnode = BuySLTNode(x);//申請一個新結點
	if (*pplist == NULL)//判斷是否為空表
	{
		*pplist = newnode;//頭指標直接指向新結點
	}
	else
	{
		SListNode* tail = *pplist;//接收頭指標
		while (tail->next != NULL)//若某結點的指標域為NULL，說明它是最后一個結點
		{
			tail = tail->next;指標指向下一個結點
		}
		tail->next = newnode;//讓最后一個結點的指標域指向新結點
	}
}

注：新結點創建的時候指標域就已經置空，所以尾插時不需要再將新結點的指標域置空，

在給定位置之后插入

在給定位置后插入結點也只需要兩步：先讓新結點的指標域指向該位置的下一個結點，然后再讓該位置的結點指向新結點即可，

//在給定位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);//確保傳入地址不為空
	SListNode* newnode = BuySLTNode(x);//申請一個新結點
	newnode->next = pos->next;//讓新結點的指標域指向地址為pos的結點的下一個結點
	pos->next = newnode;//讓地址為pos的結點指向新結點
}

注：這兩步操作也不能顛倒順序，理由與頭插時相同，

在給定位置之前插入

要想在給定位置的前面插入一個新結點，我們首先還是要找到該位置之前的一個結點，然后讓新結點的指標域指向地址為pos的結點，讓前一個結點指向新結點即可，需要注意的是，當給定位置為頭指標指向的位置時，相當于頭插，

//在給定位置之前插入
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pos);//確保傳入地址不為空
	SListNode* newnode = BuySLTNode(x);//申請一個新結點
	if (pos == *pplist)//判斷給定位置是否為頭指標指向的位置
	{
		newnode->next = pos;//讓新結點的指標域指向地址為pos的結點
		*pplist = newnode;//讓頭指標指向新結點
	}
	else
	{
		SListNode* prev = *pplist;//接收頭指標
		while (prev->next != pos)//找到地址為pos的結點的前一個結點
		{
			prev = prev->next;
		}
		newnode->next = prev->next;//讓新結點的指標域指向地址為pos的結點
		prev->next = newnode;//讓前一個結點指向新結點
	}
}

洗掉結點

單鏈表的頭刪

頭刪較為簡單，若為空表，則不必做處理；若不為空表，則直接讓頭指標指向第二個結點，然后釋放第一個結點的記憶體空間即可，

//頭刪
void SListPopFront(SListNode** pplist)
{
	if (*pplist == NULL)//判斷是否為空表
	{
		return;
	}
	else
	{
		SListNode* tmp = *pplist;//記錄第一個結點的位置
		*pplist = (*pplist)->next;//讓頭指標指向第二個結點
		free(tmp);//釋放第一個結點的記憶體空間
		tmp = NULL;//及時置空
	}
}

單鏈表的尾刪

尾刪相對麻煩一些，我們需要考慮三種不同的情況：

1、當鏈表為空時，不做處理，
2、當鏈表中只有一個結點時，直接釋放該結點，然后將頭指標置空，
3、當鏈表中有多個結點時，我們需要先找到最后一個結點的前一個結點，然后將最后一個結點釋放，將前一個結點的指標域置空，使其成為新的尾結點，

//尾刪
void SListPopBack(SListNode** pplist)
{
	if (*pplist == NULL)//判斷是否為空表
	{
		return;
	}
	else if ((*pplist)->next == NULL)//判斷是否只有一個結點
	{
		free(*pplist);//釋放該結點
		*pplist = NULL;//及時置空
	}
	else
	{
		SListNode* prev = *pplist;//接收頭指標
		SListNode* tail = (*pplist)->next;//接收第一個結點的地址
		while (tail->next != NULL)//當tail指向最后一個結點時停止回圈
		{
			prev = tail;//使prev始終指向tail的前一個結點
			tail = tail->next;//tail指標后移
		}
		free(tail);//釋放最后一個結點
		tail = NULL;//及時置空
		prev->next = NULL;//將倒數第二個結點的指標域置空，使其成為新的尾節點
	}
}

洗掉給定位置之后的結點

要洗掉給定位置之后的值，我們首先判斷傳入地址是否為最后一個結點的地址，若是，則不做處理，因為最后一個結點后面沒有結點可洗掉，若不是最后一個結點，我們首先讓地址為pos的結點指向待洗掉結點的后一個結點，然后將待洗掉結點釋放即可，

//洗掉給定位置之后的值
void SListErasetAfter(SListNode* pos)
{
	assert(pos);//確保傳入地址不為空
	if (pos->next == NULL)//判斷傳入地址是否為最后一個結點的地址
	{
		return;
	}
	SListNode* after = pos->next;//待洗掉的結點
	pos->next = after->next;//讓pos結點指向待洗掉的結點的下一個結點
	free(after);//釋放結點
	after = NULL;//及時置空
}

洗掉給定位置的結點

要洗掉給定位置的結點，我們首先要判斷該結點是否為第一個結點，若是，則操作與頭刪相同；若不是，我們就需要先找到待洗掉結點的前一個結點，然后讓其指向待洗掉結點的后一個結點，最后才能釋放待洗掉的結點，

//洗掉給定位置的值
void SListErasetCur(SListNode** pplist, SListNode* pos)
{
	assert(pos);//確保傳入地址不為空
	if (pos == *pplist)//判斷待洗掉的結點是否為第一個結點
	{
		*pplist = pos->next;//讓頭指標指向第二個結點
		free(pos);//釋放第一個結點
		pos=NULL;//及時置空
	}
	else
	{
		SListNode* prev = *pplist;//接收頭指標
		while (prev->next != pos)//找到待洗掉結點的前一個結點
		{
			prev = prev->next;
		}
		prev->next = pos->next;//讓待洗掉的結點的前一個結點指向待洗掉結點的后一個結點
		free(pos);//釋放待洗掉結點
		pos = NULL;//及時置空
	}
}

查找資料

查找資料相對于前面的來說就非常簡單了，我們只需要遍歷一遍鏈表，在遍歷的程序中，若找到了目標結點，則回傳結點的地址；若遍歷結束也沒有找到目標結點，則直接回傳空指標，

//查找資料
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;//接收頭指標
	while (cur != NULL)//遍歷鏈表
	{
		if (cur->data == x)//判斷結點是否為待找結點
			return cur;//回傳目標結點的地址
		cur = cur->next;//指標后移
	}
	return NULL;//沒有找到資料為x的結點
}

修改資料

修改資料，嗯…其實我覺得根本不用寫出來，但是鏈表的一般功能就是增、刪、查、改嘛，為了完整性，還是加上吧，

//修改資料
void SListModify(SListNode* pos, SLTDataType x)
{
	pos->data = x;//將結點的資料改為目標資料
}