【資料結構】 單鏈表的簡單理解和基本操作

前言：本章主要內容是資料結構中的單鏈表，

1.為什么需要鏈表？

1.1順序表的缺陷

1.動態增容有性能消耗

2.需要頭部插入資料，需要挪動資料

鑒于以上兩點缺陷，我們引入鏈表，

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

1.2鏈表邏輯結構如下：

注釋：鏈表結點進行了分層，上層用于存盤資料 ; 下層用指標指向下一個結點,以達到連接目的

1.3物理結構如下：

（下圖僅為了舉個例子，在堆中物理結構未必線性連續）

1.4順序表和單鏈表物理結構的對比：

1.順序表是利用realloc一次性動態調整出一大塊空間,所以這一大塊空間中的每個單元,地址都是連續的，

2.單鏈表每一次都是用的malloc開辟的一個空間,那么每個空間的地址一定是不一樣且不連續的，

2.單鏈表的代碼實作

2.1 定義單鏈表

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

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

思考下為何使用typedef？

如果一開始我們就確定了結構體中的變數型別，后續在專案程序中如果需要對這個變數型別進行調整，那么所需的操作是很繁瑣的，故使用typedef，后續若是需要修改，改動typedef就足夠了，

2.2 單鏈表的空間開辟

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

2.3 單鏈表的尾插

完成尾插前先回憶下單鏈表的結構：phead（頭指標）指向頭結點(第一個結點),之后的每個結點的下層指標next指向下一個結點,其中尾結點的next為空.

實作思路：

1.遍歷找到最后一個結點(即其next為空)

2.malloc動態開辟一個空間存盤資料,然后把新開辟的空間的next置為空.

3.使用尾結點的next連接新開辟的空間

錯誤程式：

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;
}

上述尾插代碼有錯誤，思考下哪里出現bug？

1.phead未進行判空，當鏈表為空時，phead就為空，會引發例外，

2.函式傳參錯誤，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;
	}
}

2.4單鏈表的頭插

函式需要改變phead的值,所以我們的形參需要二級指標，

1.創建新節點

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

3.讓phead指標指向新節點

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

2.5單鏈表的資料列印

直接用for遍歷

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

2.6 單鏈表的尾刪

1.考慮正常情況，如下圖，

2.考慮結點數量只有0或1時，

1.從頭開始遍歷，找到倒數第二個結點，

2.free掉最后一個結點

3.將原本的倒數第二個結點的next釋放掉

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);  //結點數0
    assert(*pphead);  //結點數1
    
    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.7 單鏈表的頭刪

1.先把第二個結點的地址記下來，

2.釋放第一個結點，

3.phead鏈接到原來的第二個結點

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;
}

2.8 單鏈表的長度查找

這個函式沒有修改phead,所以選擇值傳遞，

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

2.9 單鏈表的判空操作

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

2.10 單鏈表的值查找操作

如果可以找到,就回傳那個結點,如果找不到,回傳空指標，

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

2.11 單鏈表的洗掉操作

1.找到目標結點之前位置

2.提前保存目標結點后位置

3.銷毀目標結點

4.鏈接原目標結點之前的位置與原目標結點之后的位置

void SListErase(SLTNode** pphead,SLTNode* pos)
{
    assert(pphead);
    //0結點情況
    assert(*pphead);
    //1結點時.相當于頭刪,直接呼叫頭刪.
    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;
    }
}

2.12 單鏈表的插入操作

1.找到目標結點之前結點

2.創建新結點

3.新結點鏈接目標結點

4.原目標結點之前的結點鏈接新結點

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;
	}
}

2.13 單鏈表的銷毀操作

遍歷free銷毀

void SListDestory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);

		cur = next;
	}

	*pphead = NULL;
}

3.原始碼鏈接

https://gitee.com/linkylo/c_code_2021/tree/master/c_code_2021_8_12

資料結構的單鏈表內容到此設計結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我三連（點贊、收藏、關注）——做個手有余香的人，