C語言實作單鏈表的增刪查改

一、什么是鏈表

鏈表是一種再=在物理上存盤是非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接依次實作的，
鏈表有雙鏈表和單鏈表，
單鏈表如圖所示：

上一個結點保存自己的資料和下一個資料的地址，這就是單鏈表，通過這樣的形式把所有結點鏈接起來，
雙鏈表如圖所示：
雙鏈表可以通過指標訪問后一個元素，也可以訪問前一個元素，

二、多檔案實作單鏈表

1、自己撰寫的頭檔案SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#pragma warning(disable:4996)


typedef int SLTDateType;
typedef struct SListNode//把結點保存在結構體中
{
	SLTDateType date;
	struct SListNode* next;

}SListNode;

//函式宣告
//列印鏈表函式
void PrintSListNode(SListNode* phead);

//鏈表尾插函式
void SLNodePushBack(SListNode** pphead, SLTDateType x);

//鏈表尾刪函式
void SLNodePopBack(SListNode** pphead);

//鏈表頭插函式
void SListPushFront(SListNode** pphead, SLTDateType x);

//鏈表頭刪函式
void SListNodePopFront(SListNode** pphead);

//鏈表中在x之后插入函式
void SListNodeInsertAfter(SListNode*pos, SLTDateType x);

//鏈表查找函式
SListNode* FindSListNode(SListNode* phead, SLTDateType pos);

//鏈表洗掉pos位置之后（中間洗掉）的函式
void SListNodeEraseaAfter(SListNode* pos);
```c
3、源檔案SList.c
在SList.c中主要實作單鏈表的增刪查改介面（函式），一定要包含自己寫的頭檔案，
（1）.動態申請結點函式：
在我們需要增加資料的時候才會申請結點，并將插入的值給新結點的date，
回傳新結點的地址給其他結點（他的前一個或者后一個）保存
```c
SListNode* BuySListNode(SLTDateType x)//創建一個新的結點
{
	SListNode* newNode = (SListNode*)malloc(sizeof(struct SListNode));//用malloc函式申請一個節點的大小，
	if (newNode == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->date = x;//將插入的值給新結點的date
	newNode->next = NULL; //新結點的next為NULL

	return newNode;//回傳新結點的地址
}

（2）.列印鏈表函式：
從鏈表的頭到尾依次列印，cur==NULL時為鏈表的尾，

void PrintSListNode(SListNode* phead)
{
	struct SListNode* cur = phead;
	while (cur!= NULL)//從頭開始列印，直到最后一個的next為空
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL");
}

（3）、鏈表尾插函式
有兩種情況： 1 鏈表中 沒有結點，沒有結點，
此時 pphead==NULL;將增加的值給新結點，將新結點的地址給pphead如圖：
2、有多個結點
插入時，首先要找到鏈表的尾，然后將尾（tail）,tail->next=新結點的地址，
還是畫圖比較容易理解：
代碼如下：

void SLNodePushBack(SListNode** pphead, SLTDateType x)
{
	//尾插有兩種情況 1 沒有結點
	//               2 有結點
	struct SListNode* newNode = BuySListNode(x);//插入就需要創建新的結點
	if (*pphead == NULL)
	{
		*pphead = newNode;//將新的結點地址給頭（也是尾）
	}
	else
	{
		struct SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		
		tail->next = newNode;//把新的結點地址給尾
	}

}

（3）鏈表的尾刪函式：
尾刪分三種情況：1 、沒有結點
直接退出，不用洗掉
2 、只有一個結點
釋放掉，然后讓鏈表的頭為空（*pphead=NULL）

                          3  、2個及以上
					找到最后一個和他的前一個，然后釋放掉最后一個，最后一個的前一個（perv）,讓perv->next為空
					畫圖理解一下：

代碼如下：

void SLNodePopBack(SListNode** pphead)
{
	//尾刪分三種情況：1 沒有結點
	//            2 只有一個結點
	//			  3 2個及以上
	
	if (*pphead == NULL)
	{
		return;//沒有結點直接退出函式
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);//有一個結點，釋放掉，并讓其指向空
		*pphead = NULL;
	}
	else
	{
		struct SListNode* tail = *pphead;
		struct SListNode* perv = NULL;
	//有多個結點，先找到最后一個，然后釋放掉，再讓倒數第二個結點next為空
		while (tail->next!= NULL)
		{
			perv = tail;
			tail = tail->next;
		}
		free(tail);
		perv->next = NULL;
	}
}

（4）、鏈表的頭插函式
頭插就是將要添加的資料當作鏈表新的頭，只要將原來頭的地址給新結點的next，再將newNode的地址給*pphead作為新的頭，
如圖：

代碼如下：

`void SListPushFront(struct SListNode** pphead, SLTDateType x)
{
	struct SListNode* newNode = BuySListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;//newNode是新的頭
}`

（5）頭刪函式
將鏈表的第一個結點洗掉
分三種情況1 沒有結點
如果鏈表為空，直接退出
// 2 、只有一個結點
// 3 、2個及以上
2和3可以兼容
有兩種方法，第一種直接讓第二個結點的地址作為頭
第二種：先保存下一個結點的地址，再將第一個二結點釋放，然后將第二個地址給到*pphead
畫圖理解一下：

void SListNodePopFront(SListNode** pphead)
{    
 //分三種情況1 沒有結點
		//   2 只有一個結點
		//	 3 2個及以上  2.3可以兼容
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		//兩種方法，第一種直接讓第二個結點的地址作為頭
		//*pphead = (*pphead)->next;

		//第二種如下：
		SListNode* cur = (*pphead)->next;//保存第二個地址
		free(*pphead);//釋放第一個
		*pphead = NULL;
		*pphead= cur;//讓第二個成為新的頭
	}
}					

（6）、查找函式
將你要查找的值，與鏈表中所有的結點的date對比，如果有就回傳他的地址
代碼如下：

SListNode* FindSListNode(SListNode* phead, SLTDateType pos)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur!= NULL)
	{
		if (cur->date != pos)
		{
			cur = cur->next;
		}
		else
		{
			break;
		}
	}
	if (cur!=NULL)
	{
		printf("找到了\n");
		return cur;
	}
	else
	{
		printf("不存在\n");
		return NULL;
	}
}

（7）、中間插入函式
給定一個位置(pos)，再他之后添加
   1、先將pos下下一個的地址賦值給新結點（newNde）的next,再將新結點的地址賦值給pos的next,這樣就鏈接起來了
   如圖所示：

代碼如下：

void SListNodeInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	//SListNode* newNode = BuySListNode(x);
	//SListNode* temp = pos->next;//先保存pos下一個結點的地址
	//pos->next = newNode;//將新結點地址給到pnextNode->next
	//newNode->next =pos->next->next;	
	SListNode*newNode= BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

（8）、中間洗掉函式

給定一個位置(pos)，緊跟之后的一個洗掉
將pos的下下一個節點的地址賦給pos->next
代碼如下：

void SListNodeEraseaAfter(SListNode* pos)
{
	SListNode* next = pos->next;//pos下一個地址
	SListNode* nextnext = next->next;//pos下下一個結點地址
	pos->next = nextnext;
	free(next);//釋放pos之后的第一個（next）
	next = NULL;
}

三、代碼運行結果

測驗代碼在源檔案main.c 中
代碼如下：

#include"SList.h"
void text()
{
	SListNode* ps = NULL;
	SLNodePushBack(&ps, 1);
	SLNodePushBack(&ps, 2);
	SLNodePushBack(&ps, 3);
	SLNodePushBack(&ps, 4);
	SLNodePushBack(&ps, 5);
	SLNodePushBack(&ps, 6);
	SLNodePushBack(&ps, 7);
	SLNodePushBack(&ps, 8);

	SListPushFront(&ps, 10);
	PrintSListNode(ps);
	printf("\n");
	SListNodePopFront(&ps);
	PrintSListNode(ps);
	printf("\n");
	SListNode* pos = FindSListNode(ps, 5);
	SListNodeInsertAfter(pos, 22);
	PrintSListNode(ps);
	printf("\n");
	SListNode* pos2 = FindSListNode(ps, 2);
	SListNodeEraseaAfter(pos2);
	PrintSListNode(ps);
	printf("\n");


}
int main()
{
	text();//測驗函式
	return 0;
}

下邊測驗代碼不一定與main.c中的代碼相同
1、尾插，尾刪測驗如下圖：

2、頭刪，頭插函式如下圖：
3、鏈表查找函式測驗結果如下：
在鏈表中找5：

在鏈表中找7：

4、中間插入，中間洗掉
在5之后添加了22，洗掉了2之后的3，