文章目錄

前言
1. 為何需要鏈表?
2. 清楚單鏈表結構
3. 定義單鏈表結構
- 代碼實作
4.單鏈表的增刪改查
- 4.1 單鏈表之尾插
- - 4.1.1 單鏈表之開辟空間
  - 4.1.2 單鏈表之列印值
- 4.2單鏈表之頭插
- 4.3單鏈表之尾刪
- 4.4 單鏈表之頭刪
- 4.5單鏈表之查鏈表長度
- 4.6單鏈表之判斷鏈表是否為空
- 4.7單鏈表之查找某一個值
- 4.8單鏈表之任意位置洗掉
- 4.9單鏈表之任意位置插入
綜合:

前言

上一章節,博主講解完畢順序表,并詳細講解了順序表的各種增刪查改方法.而這次我們需要講解的是鏈表,而又主要講解的是單鏈表

1. 為何需要鏈表?

問題: 為何需要鏈表?

在回答之前,我們回顧一下上一節我們怎樣定義順序表的結構的. 上一節的順序表

邏輯結構: 線性 ; 物理結構 : 線性(即地址連續);
空間開辟是按照2的倍數開辟,順序表中實際存盤數量size小于等于線性表容量capacity

圖示:

回顧完畢,大家有沒有發現順序表有一個致命的缺陷?? 對,那就是size數量常常小于等于capacity,導致空間浪費嚴重.

為了解決這個問題,我們的鏈表就誕生了,鏈表就是有一個內容就開辟一個空間.

這個時候有人會問,既然浪費嚴重,為何順序表不一次只開辟一個空間? 嗯,問的好,但是反問,如果只開辟一個空間,物理結構連續嗎?不連續.邏輯結構連續嗎?不連續,因為連接不起來了. 后面會解釋,請繼續往下看

每次單獨開辟的空間需要用某種方法把它們連接起來,而把它們連接起來也就是鏈表的功能

2. 清楚單鏈表結構

單鏈表類似于順序表,也具有自己獨立的 邏輯結構與物理結構,但是實際確有差別,請看下圖解釋:

順序表:

單鏈表:

解釋順序表與單鏈表中的物理結構:

在順序表中，我們回憶一下,空間是怎樣開辟的?沒錯,直接一次性開辟一大塊,當不夠用時,再翻倍開辟.
- 請看之前寫的順序表空間開辟代碼:
- 由于是利用realloc一次性動態調整出一大塊空間,所以這一大塊空間中的每個單元,地址都是連續的.

在單鏈表中,每一次都是用的malloc開辟的一個空間,那么每個空間的地址一定是不一樣且不連續的,比如:

3. 定義單鏈表結構

在第2小節中大家看到,博主畫鏈表時候是用的兩個格子疊在一起表示鏈表的一個結點,那么為什么要這樣呢? 博主現在就進行解釋:

我們已經清楚的知道,鏈表結點與結點之間是必須要連接的,這樣才符合鏈表的 邏輯結構,但是怎么進行連接呢? 答曰:指標

同時,鏈表是一種什么? 沒錯,是資料結構,那就是用來存盤資料的,所以鏈表結點便進行了分層.

上層用于存盤資料 ; 下層用于指向下一個結點,以達到連接目的,下面開始代碼實作

代碼實作

因為我們是自己在實作單鏈表,也就是相當于做一個小專案,那必然缺不了 頭檔案,源檔案,測驗檔案,我們仍然按照順序表文章風格敘述.

首先分別建立SList.h , SList.c , test.c檔案,s的意思是single,單個,SList就是單鏈表(博主使用的編譯器是VS2019)
如圖:

還記得頭檔案是寫什么的嗎? 沒錯,寫函式宣告,結構定義,頭檔案參考和定義弘等

在SList.h中實作鏈表結點,需要存盤的資料型別以int為例:

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

大家想一想,這樣寫會不會有什么麻煩? 沒錯,那就是如果我們以后不想存盤int型后,就需要在后面的成千上萬代碼中一一修改,怎么解決呢? 按照上一節順序表的思路,我們想到了typedef

修改后如下:

typedef int SLTDataType; //方便以后修改資料型別

struct SListNode
{
    SLTDatType data;
    struct SListNode* next;     
}SLTNode; //把結構體名改短一點

4.單鏈表的增刪改查

4.1 單鏈表之尾插

我們學資料結構一定要養成一個好習慣,那就善于畫圖,這樣才能理清邏輯,單鏈表也是這樣,我們看看它的結構是什么樣子 ?

即phead指向頭結點(第一個結點),之后的每個結點的next指向下一個結點,其中尾結點的next為空.

所以我們想要實作尾插,步驟是什么??

第一步: 找到最后一個結點(即其next為空)
第二步: 開辟一個空間出來(使用malloc),存盤資料,然后把新開辟的空間的next置為空.
第三步: 使用尾結點的next連接新開辟的空間

代碼實作:

在SList.h中寫尾插宣告

//既然我們知道phead是指標,所以引數設定一定需要接收指標,同時還需要接收需要插入的元素
//而phead是一個結構體(鏈表結點)指標,所以設計如下.
void SListPushBack(SLTNode* phead,SLTDataType elem);

在SList.c中寫函式定義

void SListPushBack(SLTNode* phead,SLTDataType elem)
{
    //第一步:找尾結點,  即cur->next 等于 NULL
    SLTNode* cur = phead;
    while(cur->next != NULL)
    {
        cur = cur->next;
    }
    
    //第二步:開辟新空間
    SLTNode* newnode = (SLTNode* )malloc(sizeof(SLTNode));//記得引頭檔案
    if(newnode == NULL)
    {
    	perror("錯誤原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;
    //第三步:連接
    cur->next = newnode;
}

大家看看,這樣寫完后看著是不是很憋屈? 憋屈的啥? 沒錯,那個開辟空間部分的代碼,我們在以后的任何插入操作部分,都需要用到他.

所以,既然他這么頻繁,我們為何不干脆把它搞成一個函式呢?

4.1.1 單鏈表之開辟空間

在SList.h檔案中宣告

SLTNode* ButSLTNode(SLTDatType elem);

在SList.c中寫定義

SLTNode* ButSLTNode(SLTDatType elem)
{
	SLTNode* newnode = (SLTNode* )malloc(sizeof(SLTNode));//記得引頭檔案
    if(newnode == NULL)
    {
    	perror("錯誤原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;    
    return newnode;
}

修改后的尾插

void SListPushBack(SLTNode* phead,SLTDataType elem)
{

    //第一步:找尾結點,  即cur->next 等于 NULL
    SLTNode* cur = phead;
    while(cur->next != NULL) //cur用于迭代
    {
        cur = cur->next;
    }
    //第二步:開辟新空間
    SLTNode* newnode = BuySLTNode(elem);
    //第三步:連接
    cur->next = newnode;
}

寫完以后,我們需要將進行測驗了.就是尾插幾個值進去,然后列印出來

既然需要列印,我們干脆把列印操作也進行實作吧,現在再看看這個圖:

要列印所有的值,肯定需要一個回圈,并且結束條件是該結點的next等于NULL

4.1.2 單鏈表之列印值

在SList.h檔案中宣告

void SListPrint(SLTNode* phead);

在SList.c檔案中定義

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while(cur->next != NULL)
    {
        printf("%d--->",cur->data);
    }
    printf("NULL\n");
}

測驗單鏈表尾插

結果:

發現報錯,怎么回事呢? 提示我們phead此時是一個空指標.

我們想想,什么時候,phead會是空指標?沒錯,鏈表為空的時候.

所以這段代碼還需要修改一下下.就是特判一下鏈表為空

修改如下:

void SListPushBack(SLTNode* phead, SLTDataType elem)
{
	if (phead == NULL)
	{
		phead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾結點,  即cur->next 等于 NULL
		SLTNode* cur = phead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:開辟新空間
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:連接
		cur->next = newnode;
	}
}

再次測驗:

…艸,又出問題了. 怎么回事呢 ?, 竟然沒有成功尾插進去值嗎?

在仔細分析一波我們的代碼,好像明白了為什么沒有成功輸入值.原來是我們的引數設定有問題.

還記得函式傳參的值傳遞 與 址傳遞嗎? plist的型別為SLTNode*,而我們形參型別也是SLTNode*,這屬于值傳遞

值傳遞相當于形參是實參的一份臨時拷貝,形參的改變并不會影響實參的值

怎么修改這個問題呢?沒錯,那就是用址傳遞,我們傳plist的地址.形參用二級指標,修改如下:

void SListPushBack(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead); //pphead不可以為空指標.
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾結點,  即cur->next 等于 NULL
		SLTNode* cur = *pphead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:開辟新空間
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:連接
		cur->next = newnode;
	}
}

測驗:

成功!!!

總結: 涉及到需要修改的操作,我們最好用址傳遞

4.2單鏈表之頭插

還是老規矩,寫資料結構之前我們需要畫圖.既然是頭插,那我們的步驟應該是什么?如圖:

第一步: 創建新節點并存盤資料
第二步: 讓新節點連接原來的第一個結點
第三步: 讓phead連接新節點

開始實作代碼:

在SList.h檔案中宣告

//還記得上面的總結嗎?這函式需要改變phead的值,所以我們的形參需要二級指標
void SListPushFront(SLTNode** pphead,SLTDataType elem);

在SList.c檔案中定義

void SListPushFront(SLTNode** pphead,SLTDataType elem)
{
    assert(pphead);
    //第一步,創建
    SLTNode* newnode = BuySLTNode(elem);
    //第二步,新結點連接原來第一個結點
    newnode->next = *pphead;
    //第三步,phead指標指向新節點
    *pphead = newnode;
}

測驗:

成功!!!

4.3單鏈表之尾刪

還是老規矩,先畫圖,請看下面:

第一步: 找到倒數第二個結點
第二步: 釋放最后一個結點
第三步: 將找的結點的next進行釋放

代碼實作:

在SList.h中宣告

//由于涉及到修改,所以我們需要址傳遞,也就是形參需要變成二級指標
void SListPopBack(SLTNode** pphead);

在SList.c中定義

void SListPopBack(SLTNode** pphead)
{
	//第一步,找倒數第二個結點
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一個結點(cur->next)的next等于NULL時候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,釋放尾巴
	free(cur->next);
	//第三步,將現結點變NULL
	cur->next = NULL;
}

測驗:

成功!!! 成功才怪讓博主皮一下.

大家再執行想想,這樣真的就執行完了嗎? 其實沒有, 比如鏈表只有一個資料時候和沒有資料時候,如圖:

執行!

會發現出問題了,所以我們需要改進,給它加個特判:

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);  //如果沒有結點,提示無法洗掉
    
    if((*pphead)->next == NULL)//如果只有一個結點
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    
	//第一步,找倒數第二個結點
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一個結點(cur->next)的next等于NULL時候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,釋放尾巴
	free(cur->next);
	//第三步,將現結點變NULL
	cur->next = NULL;
}

測驗:

成功!!!,這才是真的成功

4.4 單鏈表之頭刪

老規矩,先畫圖,再講解:

第一步,我們先把第二個結點的地址記下來
第二步, 釋放第一個結點
第三步,將phead鏈接到原來的第二個結點

寫代碼:

在SList.h中寫是宣告

//還是同理,因為涉及修改,所以需要址傳遞
void SListPopFront(SLTNode** pphead);

在SList.c中寫定義

還記得上面的尾刪嗎?我們考慮了3種情況:空鏈表,只有一個空間鏈表,多個結點鏈表

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	//0結點
	assert(*pphead);
	//1結點
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多結點
	//第一步,保留第二個結點地址
	SLTNode* next = (*pphead)->next;
	//第二步,釋放第一個結點
	free(*pphead);
	//第三步,連接第二個
	*pphead = next;
}

成功!!!

其實上面的代碼還可以優化些~~~,就是只有一個結點的代碼可以洗掉,大家下來畫圖想想

4.5單鏈表之查鏈表長度

這個實在過于簡單,博主就不畫圖了,直接碼代碼

在SList.h中寫宣告

//這個函式的功能只是求長度,并沒有修改,所以 值傳遞
int SListSize(SLTNode* phead);

在SList.c中寫定義

int SListSize(SLTNode* phead)
{
    SLTNode* cur = phead;
    int size = 0;
    while(cur->next != NULL)
    {
        size++;
        cur = cur->next;
    };
    return size;
}

測驗

成功!!

4.6單鏈表之判斷鏈表是否為空

過于簡單,直接上代碼

在SList.h中寫宣告

bool SListEmpty(SLTNode* phead);  //注意哦~,C語言里面沒有布林值,寫bool需要引入<stdbool.h>

在SList.c中寫定義

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;
}

測驗:

成功!!

4.7單鏈表之查找某一個值

這里博主要解釋下,很多書籍上寫這個函式時,回傳值是一個索引,代表在哪個位置,博主不建議這樣寫.為什么呢? 大家繼續往后閱讀就會明白,博主是要搭配任意位置插入和任意位置洗掉函式一起使用

在SList.h中寫宣告

// 博主對于這個函式的要求是,如果可以找到,就回傳那個結點,如果找不到,回傳空指標
SLTNode* SListFind(SLTNode* phead, SLTDataType elem);

在SList.c中寫定義

SLTNode* SListFind(SLTNode* phead, SLTDataType elem)
{
    SLTNode* cur = phead;
    while(cur->data != elem)
    {
        cur = cur->next;
    }
    if(cur->data==elem)
    {
        return cur;
    }
    return NULL;
}

測驗

4.8單鏈表之任意位置洗掉

還記得博主開始設計查找值函式時候嗎,它的回傳值是什么?沒錯就是如果找到就回傳結點,否則回傳NULL

而現在我們就需要用它的回傳值,也就是說,我們這個函式設定的形參之一就是目標結點.

老規矩,先畫圖:

第一步: 就是找到目標結點之前位置
第二步: 就是保存目標結點后位置
第三步:就是銷毀目標空間
第四步,連接

在SList.h中宣告:

//由于需要修改,所以 址傳遞,pos是目標結點地址.
void SListErase(SLTNode** pphead,SLTNode* pos);

在SList.c中定義

void SListErase(SLTNode** pphead,SLTNode* pos)
{
    assert(pphead);
    //0結點情況
    assert(*pphead);
    //一個結點情況.也就是只洗掉一個,其實就相當于頭刪,所以直接呼叫頭刪.
    if((*pphead)->next == NULL)
    {
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* cur = *pphead;
        while(cur->next != pos)
        {
            cur = cur->next;
        }
        SLTNode* two_next = pos->next;
        free(pos);
        cur->next = two_next;
    }
}

測驗

成功!!

4.9單鏈表之任意位置插入

老規矩,先畫圖

第一步,先找目標結點之前結點
第二步,新建結點保存資料
第三步,新結點連接目標結點
第四步,當前結點連接新結點

在SList.h中宣告

void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType* elem);

在SList.h中定義

void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType elem)
{
	assert(pphead);
	assert(pos);
	if (*pphead== pos)
	{
		SListPushFront(pphead,elem);
	}
	else
	{
		SLTNode* pre = *pphead;
		while (pre->next  != pos)
		{
			pre = pre->next;
		}
		SLTNode* next = BuySLTNode(elem);
		next->next = pos;
		pre->next = next;
	}
}

測驗

成功

綜合:

SList.h檔案

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//只是讀則只需要一級指標
void SListPrint(SLTNode* Phead);
int SListSize(SLTNode* phead);
SLTNode* SListFind(SLTNode* phead, SLTDataType elem);
bool SListEmpty(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType elem);


//設計讀寫和修改就要二級指標
void SListPushBack(SLTNode** phead,SLTDataType elem);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
void SListInsert(SLTNode** pphead, SLTNode* pos,SLTDataType elem);
void SListErease(SLTNode** pphead, SLTNode* pos);

SList.c檔案

#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* CUR = phead;
	while (CUR != NULL)
	{
		printf("%d-->", CUR->data);
		CUR = CUR->next;
	}
	printf("NULL\n");
}

SLTNode* BuySLTNode(SLTDataType elem)
{
	SLTNode* ptail =  (SLTNode*)malloc(sizeof(SLTNode));
	if (ptail == NULL)
	{
		perror("錯誤原因:");
		exit(-1);
	}
	ptail->data = elem;
	ptail->next = NULL;
	return ptail;
}


void SListPushBack(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead); //pphead不可以為空指標.
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾結點,  即cur->next 等于 NULL
		SLTNode* cur = *pphead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:開辟新空間
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:連接
		cur->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead);
	//第一步,創建
	SLTNode* newnode = BuySLTNode(elem);
	//第二步,新結點連接原來第一個結點
	newnode->next = *pphead;
	//第三步,phead指標指向新節點
	*pphead = newnode;
}

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);  //如果沒有結點,提示無法洗掉

	if ((*pphead)->next == NULL)//如果只有一個結點
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//第一步,找倒數第二個結點
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一個結點(cur->next)的next等于NULL時候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,釋放尾巴
	free(cur->next);
	//第三步,將現結點變NULL
	cur->next = NULL;
}

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	//0結點
	assert(*pphead);
	//1結點
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	//多結點
	//第一步,保留第二個結點地址
	SLTNode* next = (*pphead)->next;
	//第二步,釋放第一個結點
	free(*pphead);
	//第三步,連接第二個
	*pphead = next;
}

a
int SListSize(SLTNode* phead)
{
	SLTNode* CUR = phead;
	int size = 0;
	while (CUR)
	{
		size++;
		CUR = CUR->next;
	}
	return size;
}

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;
}

SLTNode* SListFind(SLTNode* phead, SLTDataType elem)
{
	SLTNode* cur = phead;
	while (cur->data != elem)
	{
		cur = cur->next;
	}
	if (cur->data == elem)
	{
		return cur;
	}
	return NULL;
}



void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType elem)
{
	assert(pphead);
	assert(pos);
	if (*pphead== pos)
	{
		SListPushFront(pphead,elem);
	}
	else
	{
		SLTNode* pre = *pphead;
		while (pre->next  != pos)
		{
			pre = pre->next;
		}
		SLTNode* next = BuySLTNode(elem);
		next->next = pos;
		pre->next = next;
	}
}



void SListErease(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	//0結點情況
	assert(*pphead);
	//一個結點情況.也就是只洗掉一個,其實就相當于頭刪,所以直接呼叫頭刪.
	if ((*pphead)->next == NULL)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* two_next = pos->next;
		free(pos);
		cur->next = two_next;
	}
}

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

標籤：其他

上一篇：哈哈！TCP泄露了作業系統資訊···

下一篇：單片機畢設教學：PCF8591 應用程式

資料結構之單鏈表

文章目錄

前言

1. 為何需要鏈表?

2. 清楚單鏈表結構

3. 定義單鏈表結構

代碼實作

4.單鏈表的增刪改查

4.1 單鏈表之尾插

4.1.1 單鏈表之開辟空間

4.1.2 單鏈表之列印值

4.2單鏈表之頭插

4.3單鏈表之尾刪

4.4 單鏈表之頭刪

4.5單鏈表之查鏈表長度

4.6單鏈表之判斷鏈表是否為空

4.7單鏈表之查找某一個值

4.8單鏈表之 任意位置洗掉

4.9單鏈表之 任意位置插入

綜合:

4.8單鏈表之任意位置洗掉

4.9單鏈表之任意位置插入