目錄

鏈表的概念及結構

單鏈表?

單鏈表的實作

單鏈表的定義

單鏈表的空間開辟

單鏈表的尾插

尾插思路:

單鏈表的頭插

頭插思路:

單鏈表的列印

列印思路:用for陳述句列印輸出

單鏈表的尾刪

尾刪思路:

頭刪思路:

單鏈表的值查找:

值查找思路:除錯幾遍

單鏈表的在pos位置洗掉

pos位置洗掉思路:

單鏈表在pos位置插入

pos位置插入思路:

鏈表的概念及結構

注意：
1.眾上圖可看出，鏈式結構在邏輯上是連續的，但是在物理上不一定連續
2.現實中的結點一般都是從堆上申請出來的
3.從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續，也可能不連續

假設在32位系統上，結點中值域為int型別，則一個節點的大小為8個位元組，則也可能有下述鏈表：

單鏈表

1. 無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結 構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，
2. 帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向 回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而 簡單了，后面我們代碼實作了就知道了，

單鏈表的實作

單鏈表的定義

//定義單鏈表
typedef int SLTDataType;//方便修改存盤資料型別

typedef struct SlistNode//節點
{
	SLTDataType data;//資料域
	struct SlistNode* next;//指標域
}SLTNode;//結構名改短一點

單鏈表的空間開辟

//單鏈表的空間開辟
SLTNode* BuySLTNode(SLTDataType el)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開辟新節點,判斷是否錯誤
	if (newnode == NULL)
	{
		perror("錯誤原因");
		exit(-1);
	}
	//給新節點的資料域和指標域分別賦值
	newnode->data = el;
	newnode->next = NULL;
	return newnode;
}

單鏈表的尾插

//單鏈表的尾插
void SListPushBack(SLTNode** pphead, SLTDataType el)
{
	//0節點
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(el);
	}
	else
	{
		//找到尾結點
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//到尾了,開辟空間
		SLTNode* newnode = BuySLTNode(el);
		//連接
		tail->next = newnode;

	}

}

尾插思路:

1.找到尾結點

2.到尾了,開辟空間

3.連接新開辟的空間

單鏈表的頭插

//單鏈表的頭插
void SListPushFront(SLTNode** pphead, SLTDataType el)
{
	assert(pphead);//0節點
	//創建新節點
	SLTNode* newnode = BuySLTNode(el);
	//新節點連接原來的頭結點
	newnode->next = *pphead;
	//*pphead指向新節點
	*pphead = newnode;
}

頭插思路:

1.創建新節點

2.新節點連接原來的頭結點

3.*pphead指向新節點

單鏈表的列印

//單鏈表的資料列印--for遍歷
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

列印思路:用for陳述句列印輸出

單鏈表的尾刪

//單鏈表的尾刪
void SListPopBack(SLTNode** pphead)
{
    assert(pphead);//0節點
	// 溫柔的一點
	/*if (*pphead == NULL)
	{
	return;
	}*/

	// 粗暴一點
	assert(*pphead);//1節點
	//兩種情況:
	//1個節點
	//2個節點以上
	if ((*pphead)->next == NULL)//只有一個節點時
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多節點時 找倒數第二個節點
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL)
	{
		cur = cur->next;
	}
	//free去掉最后一個節點
	free(cur->next);
    //置NULL
	cur->next = NULL;

}

尾刪思路:

2種情況

一個節點時,釋放且置空

多節點時:

1.找倒數第二個節點

2.free最后一個節點

3.置空

單鏈表頭刪

//單鏈表的頭刪
void SListPopFront(SLTNode** pphead)
{	
	assert(*pphead);//0節點
    assert(*pphead);//1節點
	SLTNode* next = (*pphead)->next;//記住第二個節點地址
	free(*pphead);//釋放第一個節點
	*pphead = next;//連接第二個節點
}

頭刪思路:

1.記住第二個節點地址

2.釋放第一個節點

3.鏈接第二個節點

單鏈表的值查找:

//單鏈表的值查找操作
SLTNode* SListFind(SLTNode* phead, SLTDataType el)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == el)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}

	return NULL;
}

值查找思路:除錯幾遍

單鏈表的在pos位置洗掉

//單鏈表在pos位置洗掉
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//0節點情況
	assert(pos);//防止向空鏈表洗掉

//1個節點直接頭刪
	if (*pphead == pos)
	{
		/*pphead=pos->next;
		free(pos);*/
		SlistPopFront(pphead);
	}
//多個節點時
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos前位置
		{
			prev = prev->next;
		}
		prev->next = pos->next;//鏈接目標節點前后
		free(pos);//銷毀目標節點
	}
}

pos位置洗掉思路:

1個節點:直接頭刪

多個節點:

1.找到pos位置

2.鏈接目標節點前后位置

3.銷毀目標節點

單鏈表pos位置洗掉圖片

單鏈表在pos位置插入

//單鏈表在pos位置前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//防止空節點情況
	assert(pos);//防止向空鏈表插入

	SLTNode* newnode = BuylistNode(x);
	//一個節點,頭插
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	
	}
    //多個節點
	else
	{
		//找到pos的前一個位置
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
        //鏈接
		posPrev->next = newnode;
		newnode->next = pos;
	}
}

pos位置插入思路:

一個節點:頭插

多個節點:找到pos前位置,進行鏈接