單鏈表

gitee自取：
源代碼+工程檔案
單鏈表筆記

文章目錄

單鏈表
- 導言
- 一、鏈表的概念及其結構
- - 1. 概念
  - 2. 結構特點
- 二、單鏈表的增刪查改
- - 1. 單鏈表主體
  - 2. 單鏈表申請節點
  - 3. 單鏈表列印
  - 4. 單鏈表尾插
  - 5. 單鏈表頭插
  - 6. 單鏈表尾刪
  - 7. 單鏈表頭刪
  - 8. 單鏈表查找
  - 9. 單鏈表在pos之后插入
  - 10. 單鏈表在pos之前插入
  - 11. 單鏈表在pos之后洗掉
  - 12. 單鏈表在pos位子值洗掉
  - 13. 銷毀單鏈表

導言

雖然順序表一定程度上解決了定長陣列帶來的空間浪費
但是在我們約定順序表以2倍的形式擴容的時候，還是會有些空間上的浪費
每次頭部插入和尾部插入都需要移動資料，效率低下

那么資料結構中還有一種存盤結構，叫做鏈表，可以讓我們充分利用空間

本文重點介紹常見鏈表的一種——單鏈表

一、鏈表的概念及其結構

1. 概念

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

2. 結構特點

上一個結構體有下一個結構體的地址，最后指向null

在這里插入圖片描述

這樣一個結構，資料不用連續存盤，只要有頭部位置的地址就可以找到所有的資料

二、單鏈表的增刪查改

1. 單鏈表主體

每個主體都是一個結構體，上面放資料，下面放下一個指向下一個結構體的地址

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

2. 單鏈表申請節點

無論實作增刪的時候都需要有需要一個鏈表結構，首先我們得擁有一個節點

// 動態申請一個節點，此節點為新節點
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("單鏈表開辟空間失敗\n");
		exit(-1);

	}
	newnode->data = x;//存的資料
	newnode->next = NULL;//最后一個節點的標志

	return newnode;

3. 單鏈表列印

直到該節點指標指向下一節點的地址為NULL停止

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

4. 單鏈表尾插

新建一個節點，分為兩種情況考慮：

鏈表不存在，將新建的節點地址為鏈表地址
鏈表存在，找到最后一個節點，將節點指向的NULL，改為指向新節點地址

// 單鏈表尾插
void SListPushBack(SLTNode** pplist, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);//先新定義一個尾節點，將數字也插進去
	//此資料待鏈接
	//尾部節點
	SLTNode* tail = *pplist;

	if (tail == NULL)//需要鏈接的節點為空
	{
		*pplist = newnode;//新的空間就是第一個節點地址就是newnode無需鏈接
		//這里不能寫tail因為是區域變數，改變其資料不能改變本身
	}
	else
	{
		while (tail->next != NULL)//找到最后一個尾節點
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

測驗一下我們的列印和申請節點和尾插

void test1()//測驗尾插+列印
{
	SLTNode* s = NULL;
	
	//不申請直接插入
	SListPushBack(&s, 1);

	//尾插
	SListPushBack(&s, 2);
	SListPushBack(&s, 3);
	SListPushBack(&s, 4);


	//列印
	SListPrint(s);
}

int main()
{
	test1();//尾插測驗

	return 0;
}

測驗結果：符合預期

在這里插入圖片描述

5. 單鏈表頭插

頭插也是先考慮兩種情況

鏈表不存在，將新建的節點地址為鏈表地址
鏈表存在，新節點指向的NULL，改為頭節點地址，再將頭節點地址改為新節點地址

// 單鏈表的頭插
void SListPushFront(SLTNode** pplist, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);//新的節點

	//當鏈表為空的時候
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		newnode->next = *pplist;
		*pplist = newnode;
	}

}

代碼改進：

其實后來發現，兩個代碼其實可以合并為一個，就算是空也沒有關系

在這里插入圖片描述

簡化代碼：

// 單鏈表的頭插
void SListPushFront(SLTNode** pplist, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);//新的節點
	newnode->next = *pplist;
	*pplist = newnode;

}

測驗代碼：

void test2()//測驗頭插+列印
{
	SLTNode* s = NULL;
	
	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);
	SListPushFront(&s, 3);
	SListPushFront(&s, 4);

	//列印
	SListPrint(s);

}

int main()
{
	test2();//頭插測驗

	return 0;
}

除錯效果：

在這里插入圖片描述

6. 單鏈表尾刪

洗掉單鏈表最后一個元素需要考慮3種情況：

大概分為可以刪和不能刪2種情況，可以刪還分2種

單鏈表為空
單鏈表還剩最后一個數
常規單鏈表

圖解

在這里插入圖片描述

代碼實作：

// 單鏈表的尾刪
void SListPopBack(SLTNode** pplist)
{
	assert(*pplist);
	SLTNode* tail = *pplist; 

	if (tail->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

測驗代碼：

void test3()//測驗尾刪+列印
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//尾刪
	SListPopBack(&s);
	SListPopBack(&s);

	//列印
	SListPrint(s);
}

int main()
{
	test3();//尾刪測驗

	return 0;
}

測驗結果

在這里插入圖片描述

7. 單鏈表頭刪

頭刪其實和頭插類似，也是需要分3種情況，但其中兩種情況可以合并，所以最終是2種情況：

刪不了的情況
刪的了的情況

圖解：

在這里插入圖片描述

合并出代碼：

// 單鏈表頭刪
void SListPopFront(SLTNode** pplist)
{
	assert(*pplist);
	SLTNode* head = *pplist;
	head = head->next;
	free(*pplist);
	*pplist = head;
}

在尾刪測驗代碼上做一下修改

void test4()//測驗頭刪+列印
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//尾刪
	SListPopFront(&s);
	SListPopFront(&s);

	//列印
	SListPrint(s);
}
int main()
{
	test4();//頭刪測驗

	return 0;
}

測驗結果：
在這里插入圖片描述

8. 單鏈表查找

單鏈表查找和尾刪有點像，思路上是分兩種情況：

鏈表為空
常規鏈表查找

注意不是找到就可以了，要回傳該數字所在節點的地址

// 單鏈表查找
SLTNode* SListFind(SLTNode* plist, SLTDateType x)
{
	while (plist)
	{
		if (plist->data == x)
		{
			printf("找到了！\n");
			return plist;
		}
		plist = plist->next;
	}

	return NULL;//沒有找到
}

測驗代碼

void test5()//測驗查找
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2); 
	
	//查找
	s = SListFind(s, 1);
	s = SListFind(s, 3);
	//列印
	SListPrint(s);
}

int main()
{
	test5();//查找測驗

	return 0;
}

測驗結果

在這里插入圖片描述

一個找到了，一個沒找到

9. 單鏈表在pos之后插入

也是兩種情況：

鏈表為空
常規鏈表插入

//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}

測驗代碼:

void test6()//測驗查找pos后插入
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//查找
	SLTNode* pos = SListFind(s, 2);

	//插入
	SListInsertAfter(pos, 11);

	//列印
	SListPrint(s);
}

int main()
{
	test6();//pos后插入測驗

	return 0;
}

測驗結果：

在這里插入圖片描述

10. 單鏈表在pos之前插入

考慮情況：

頭插
中間插
尾插

//在pos之前插入
void SListInsert(SLTNode** pplist, SLTNode* pos, SLTDateType x)
{
	assert(pos && (*pplist));
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = *pplist;

	if (*pplist == pos)
	{
		newnode->next = tail;
		*pplist = newnode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		newnode->next = tail->next;
		tail->next = newnode;
	}

}

測驗代碼：

void test7()//pos前插入測驗
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//查找
	SLTNode* pos = SListFind(s, 1);

	//插入
	SListInsert(&s, pos, 11);

	//列印
	SListPrint(s);
}

int main()
{
	test7();//pos前插入測驗

	return 0;
}

測驗結果：

在這里插入圖片描述

11. 單鏈表在pos之后洗掉

需要考慮情況：

鏈表為空
鏈表的pos之后為空
常規

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

	SLTNode* tag = pos->next;
	pos->next = pos->next->next;
	free(tag);
	//因為tag是區域變數，函式結束后會銷毀，所以就不需要令它為NULL

}

測驗代碼：

test7()
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//查找
	SLTNode* pos = SListFind(s, 2);

	//洗掉
	SListEraseAfter(pos);

	//列印
	SListPrint(s);

}

int main()
{
	test7();//pos后刪

	return 0;
}

測驗結果

在這里插入圖片描述

12. 單鏈表在pos位子值洗掉

考慮因素：

鏈表為空
pos在首位
pos在中間

// 單鏈表洗掉pos位置的值
void SListErase(SLTNode** pplist, SLTNode* pos)
{
	assert(pos && *pplist);
	if (pos == *pplist)
	{
		SListPopFront(pplist);//頭刪
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}

測驗

test8()
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);

	//查找
	SLTNode* pos = SListFind(s, 2);

	//洗掉
	SListErase(&s, pos);

	//列印
	SListPrint(s);

}

int main()
{

	test8();//pos位置洗掉

	return 0;
}

結果

在這里插入圖片描述

13. 銷毀單鏈表

// 單鏈表的銷毀
void SListDestory(SLTNode** plist)
{
	assert(plist);
	SLTNode* tag = *plist;

	while (*plist != NULL)
	{
		*plist = tag->next;
		free(tag);
		tag = *plist;
	}
}

測驗

test9()
{
	SLTNode* s = NULL;

	//頭插
	SListPushFront(&s, 1);
	SListPushFront(&s, 2);
	//銷毀單鏈表
	SListDestory(&s);
	//列印
	SListPrint(s);

}

結果

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333790.html

標籤：其他

上一篇：(C語言)實作常見排序的介面

下一篇：【資料結構初階】鏈表詳解（一）無哨兵位單向非回圈鏈表

【資料結構】單鏈表的增刪查改，附代碼+筆記gitee自取

單鏈表

文章目錄

導言

一、鏈表的概念及其結構

1. 概念

2. 結構特點

二、單鏈表的增刪查改

1. 單鏈表主體

2. 單鏈表申請節點

3. 單鏈表列印

4. 單鏈表尾插

5. 單鏈表頭插

6. 單鏈表尾刪

7. 單鏈表頭刪

8. 單鏈表查找

9. 單鏈表在pos之后插入

10. 單鏈表在pos之前插入

11. 單鏈表在pos之后洗掉

12. 單鏈表在pos位子值洗掉

13. 銷毀單鏈表