單鏈表~增刪查改（附代碼）~簡單實作

目錄

動態申請一個節點

單鏈表列印

單鏈表的尾刪

單鏈表的頭刪

單鏈表尾插

單鏈表的頭插

單鏈表的查找

單鏈表在pos位置之后插入x

單鏈表洗掉pos位置之后的值

單鏈表的銷毀

所有函式代碼

鏈表的概念及結構
概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈
接次序實作的 ，

今天我們主要了解的是鏈表中的單鏈表

我們對一個結構體簡單定義

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

對于一個單鏈表，我們一般需要實作的功能如下

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表列印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表洗掉pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestory(SListNode* plist);

下面是每一個功能的具體實作

動態申請一個節點

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	plist->data = x;
	plist->next = NULL;
	return plist;
}

這里我們利用了return把創建的節點回傳.

單鏈表列印

// 單鏈表列印
void SListPrint(SListNode* plist)
{
	while (plist)
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
	printf("NULL\n");
}

這里我們依次列印，直到最后一個節點.

單鏈表的尾刪

對于尾刪我們需要考慮以下幾種情況：

1.單鏈表已空 2.只有一個節點 3.具有多個節點

已空的話，我們就不能對單鏈表進行洗掉了

只有一個節點的話，我們直接將單鏈表空間釋放，然后再置空就好了，

具有多個節點的話，我們需要將最后一個節點釋放，然后再將前一個結點的尾節點置空，（這里我們需要保存前一個節點）

//尾刪
void SLictPopBack(SListNode **pphead)
{
	assert(pphead);
	SListNode*tail = *pphead;//
	//如果只有一個
	if (tail->next == NULL)
	{
		free(tail);
		tail = NULL;
	}
	//如果有多個
	else
	{
		//先找到前一個位置
	    while(tail->next->next )
		{
			tail = tail->next;
		}
		//釋放后一個位置
		free(tail->next);
		tail->next = NULL;
	}
}

單鏈表的頭刪

單鏈表的頭刪我們需要考慮的情況如下

1.單鏈表已空 2.只有一個節點 3.具有多個節點

單鏈表已空的話，我們不能洗掉，直接判斷一下就好了

單鏈表只有一個節點的情況跟尾刪一樣，直接釋放再置空就好了.

單鏈表有多個節點的話，我們保存第二個節點，然后釋放第一個節點，然后將鏈表指標指向第二個節點就好了.

//頭刪
void SListPopFront(SListNode** pphead)
{
	assert(pphead&&*pphead );
	SListNode* next = (*pphead)->next;//
	//如果只有一個
	if (next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果有多個
	else 
	{
		free(*pphead);
		*pphead =next ;
	}
}

單鏈表尾插

單鏈表的尾插我們需要考慮的情況如下

1.單鏈表已空 2.單鏈表非空

單鏈表已空的話我們直接創建一個節點

單鏈表非空的話，我們直接在鏈表后方接一個節點

// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	//如果鏈表為空，創建鏈表
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	//鏈表非空
	else
	{
		SListNode* cur = *pplist;
		while (cur->next)//找到最后一個節點
		{
			cur = cur->next;
		}
		cur->next = BuySListNode(x);//接上我們新建的節點
	}
}

單鏈表的頭插

單鏈表的頭插我們需要考慮的情況如下

1.單鏈表已空 2.單鏈表非空

這里我們會發現無論單鏈表是否為空，我們直接在前面加一個節點就好了，所以不在乎鏈表是否為空.

// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
		SListNode* cur = BuySListNode(x);//建立新節點
		cur->next = *pplist;
		*pplist = cur;
}

單鏈表的查找

單鏈表的查找我們需要考慮的情況如下

1.單鏈表為空 2.單鏈表中不含我們要查找的節點 3.單鏈表含有我們要查找的節點

// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	while(plist)
	{
		if (plist->data==x)
		{
			return plist;//找到了回傳
		}
		plist = plist->next;//找不到繼續往后
	}
	return NULL;
}

單鏈表在pos位置之后插入x

這里我們只需要注意將節點正確連接就好了

// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* newnode= BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

單鏈表洗掉pos位置之后的值

我們只需要分析下一個節點是否為空

然后將節點間正確連接就好了.

// 單鏈表洗掉pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next)//如果下一個節點非空
	{
		SListNode* next = pos->next;
		pos->next=pos->next->next;
		free(next);
	}
}

單鏈表的銷毀

// 單鏈表的銷毀
void SListDestory(SListNode** plist)
{
	assert(plist);//判空
	SListNode* prev, * cur;
	cur = *plist;
	prev = NULL;
	while (cur)
	{
		prev = cur;
		cur = cur->next;
		free(prev);
	}
	*plist = NULL;
}

所有函式代碼

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	plist->data = x;
	plist->next = NULL;
	return plist;
}

// 單鏈表列印
void SListPrint(SListNode* plist)
{
	while (plist)
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
	printf("\n");
}

//尾刪
void SLictPopBack(SListNode **pphead)
{
	assert(pphead);
	SListNode*tail = *pphead;//
	//如果只有一個
	if (tail->next == NULL)
	{
		free(tail);
		tail = NULL;
	}
	//如果有多個
	else
	{
		//先找到前一個位置
	    while(tail->next->next )
		{
			tail = tail->next;
		}
		//釋放后一個位置
		free(tail->next);
		tail->next = NULL;
	}
}

//頭刪
void SListPopFront(SListNode** pphead)
{
	assert(pphead&&*pphead );
	SListNode* next = (*pphead)->next;//
	//如果只有一個
	if (next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果有多個
	else 
	{
		free(*pphead);
		*pphead =next ;
	}
}

// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	//如果鏈表為空，創建鏈表
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	//鏈表非空
	else
	{
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = BuySListNode(x);
	}
}

// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
		SListNode* cur = BuySListNode(x);
		cur->next = *pplist;
		*pplist = cur;
}

// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	while(plist)
	{
		if (plist->data==x)
		{
			return plist;
		}
		plist = plist->next;
	}
	return NULL;
}

// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* newnode= BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// 單鏈表洗掉pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next)
	{
		SListNode* next = pos->next;
		pos->next=pos->next->next;
		free(next);
	}
}

// 單鏈表的銷毀
void SListDestory(SListNode** plist)
{
	assert(plist);
	SListNode* prev, * cur;
	cur = *plist;
	prev = NULL;
	while (cur)
	{
		prev = cur;
		cur = cur->next;
		free(prev);
	}
	*plist = NULL;
}