🔥個人主頁:胡蘿卜3.0
🎬作者簡介:C++研發方向學習者
📖個人專欄:??《C語言》《數據結構》?《C++干貨分享》
??人生格言:不試試怎么知道自己行不行
目錄
順序表問題與思考
正文
一、單鏈表
1.1 概念與結構
1.1.1 結點
1.1.2 鏈表的性質
1.1.3 鏈表的打印
二、實現單鏈表
2.1 單鏈表的結構
2.2? 尾插
2.2?頭插
2.3 尾刪
2.4 頭刪
2.5 查找
2.6 在指定位置之前插入數據
2.7 在指定位置之后插入數據
2.8 刪除指定位置上的結點
2.9 刪除指定位置之后的結點
2.10 銷毀單鏈表
三、完整代碼
順序表問題與思考
中間/頭部的插入刪除,時間復雜度為O(N)
增容需要申請新空間,拷貝數據,釋放舊空間,會有不小的消耗。
增容一般是呈2倍的增長,勢必會有一定的空間浪費。例如當前容量為100,滿了以后增容到200,我們再繼續插入5個數據,后面沒有數據插入了,那么就浪費了95個數據空間
那我們該如何解決以上問題呢?
ok,這時候單鏈表就閃亮登場了!!!接下來我們一起來學習單鏈表相關的知識。
正文
一、單鏈表
1.1 概念與結構
概念:鏈表是?種物理存儲結構上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
也就是說單鏈表在邏輯結構上是線性的,在物理結構上不一定是線性的
在淡季時車次的車廂會相應減少,旺季時車次的車廂會額外增加幾節。只需要將火車里的某節車箱去掉/加上,是不會影響其他車廂,每節車廂都是獨立存在的。
那么在鏈表里,每節“車廂”是什么樣的呢?
1.1.1 結點
與順序表不同的是,鏈表里的每節“車廂”都是獨立申請下來的空間,我們稱之為“節點/結點”
圖中指針變量plist保存的是第一個結點的地址,我們稱plist此時“指向”第一個結點,如果我們希望plist“指向”第二個結點時,只需要修改plist保存的內容為0x0012FFA0。
鏈表中每個結點都是獨立申請的(即需要插入數據時才去申請?塊結點的空間),我們需要通過指針變量來保存下?個結點位置才能從當前結點找到下?個結點。
1.1.2 鏈表的性質
- 鏈式機構在邏輯上是連續的,在物理結構上不?定連續
- 結點?般是從堆上申請的
- 從堆上申請來的空間,是按照?定策略分配出來的,每次申請的空間可能連續,可能不連續
結合前面學到的結構體知識,我們可以給出每個結點對應的結構體代碼:
假設當前保存的結點為整型:
struct SListNode
{int data; //結點數據struct SListNode* next; //指針變量?保存下?個結點的地址
}
當我們想要保存一個整型數據時,實際是向操作系統申請了一塊內存,這個內存不僅要保存整型數據,也需要保存下一個結點的地址(當下一個結點為空時保存的地址為空)。
當我們想要從第一個結點走到最后一個結點時,只需要在當前結點拿上下?個結點的地址就可以了。
1.1.3 鏈表的打印
給定的鏈表結構中,如何實現結點從頭到尾的打印?
思考:當我們想保存的數據類型為字符型、浮點型或者其他自定義的類型時,該如何修改?
二、實現單鏈表
在前面的學習中,我們知道單鏈表需要一個頭結點,當我們不給鏈表中插入任何數據,頭結點為一個空結點,那我們該如何定義一個空結點呢?
2.1 單鏈表的結構
typedef int SLTDataType;
typedef struct SListNode
{int data;//存儲數據struct SListNode* next;//保存的是下一個節點的地址
}SLTNode;
有了單鏈表的結構,我們是不是應該給里面插入一些值呢?必須插入一些值,那我們是在尾部插入還是應該在頭部插入呢?其實在單鏈表中,我們既可以在尾部插入,也可以在頭部插入。
2.2? 尾插
尾插尾插,不就是要找到鏈表的尾部,然后插入數據嘛,首先第一步為數據創建結點空間,然后找到鏈表的尾部,最后插入數據。
這里有個問題,剛開始,沒有向鏈表中插入任何數據,鏈表是一個空結點,那我們該怎么辦?
如果鏈表為空,我們直接將結點的地址給頭結點!!!
我們要申請新的節點(需要malloc),我們單獨封裝一個函數。
?
現在新節點就申請好了,我們要讓5和4節點連起來:
?
這就是為什么我們明明已經有phead這個指針,還要額外再定義一個指針pcur——
?
這樣一來pcur在不斷變化,phead保持不變,phead始終保存的是第一個節點的地址。在這里我不想改變phead,phead始終指向第一個節點,方便我們后面遍歷完了如果還要再從頭開始遍歷的時候我們能夠找到第一個節點的地址。
我們定義pcur,只要pcur不為空,我們就進入循環,pcur為空我們就跳出循環。
ok,看代碼
為新節點創建空間
//為節點創建空間
SLTNode* SlBuyNode(SLTDataType num)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = num;newnode->next = NULL;return newnode;
}
尾插代碼:
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType num)
{assert(pphead);//為節點申請空間SLTNode* newnode = SlBuyNode(num);//頭結點為空if (*pphead == NULL){*pphead = newnode;}else{//找到尾節點//頭結點不為空SLTNode* ptail = *pphead;while (ptail->next != NULL){ptail = ptail->next;}ptail->next = newnode;}
}
尾插的時間復雜度為:O(N)
我相信會有很多小伙伴看到上面的代碼會很疑惑?為什么是個二級指針?
ok,我們來看一下如果不傳二級指針會發生什么?
當我們在編譯器中進行調試的時候,發現程序執行完之后,鏈表中還是沒有值,這是什么原因?
我們看到在調用尾插的代碼時,實參部分傳的是plist,這是傳值調用,我們知道傳值調用,形參改變不會影響實參,所以在這里我們要使用傳址調用,當使用傳址調用時,由于plist是一個一級指針,一級指針的地址需要用二級指針來接受
2.2?頭插
我們需要將結點插入到頭結點的前面,使新節點成為新的頭結點
代碼:
//頭插
void SLPushFront(SLTNode** pphead, SLTDataType num)
{assert(pphead);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
頭插時間復雜度為:O(1)
2.3 尾刪
尾刪操作需要找到尾節點以及尾節點的前一個結點,需要先將尾節點的前一個結點的next域置為NULL,然后釋放尾節點,如果鏈表中只要一個頭結點,直接將頭結點的空間釋放。
代碼:
//尾刪
void SLPopBack(SLTNode** pphead)
{//結點為空,不能刪除assert(pphead && *pphead);//如果只有一個頭結點if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;SLTNode* ptail = *pphead;//找到尾節點以及尾節點的前一個節點while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = NULL;}
}
尾插的時間復雜度為:O(N)
2.4 頭刪
頭刪刪除的是頭結點,首先要將頭結點的下一個結點保存起來,然后釋放頭結點的空間,讓頭結點的下一個結點成為新的頭結點。
代碼:
//頭刪
void SLPopFront(SLTNode** pphead)
{//保留頭結點的下一個節點SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
頭刪的時間復雜度為:O(1)
2.5 查找
遍歷鏈表,如果找到,則返回該結點的地址;如果沒找到,返回NULL
//查找
SLTNode* SLFind(SLTNode** pphead, SLTDataType num)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur != NULL){if (pcur->data == num){return pcur;}pcur = pcur->next;}return NULL;
}
ok,既然已經學了查找的代碼,那我們就可以實現在指定位置之前/之后插入/刪除數據了。
2.6 在指定位置之前插入數據
當指定位置為頭結點時,那不是頭插嘛;如果指定位置不是頭結點,我們需要找指定位置的前一個結點,并修改其中保存的指針指向。
代碼
//在指定位置之前插入數據
void SLInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType num)
{//鏈表為空,不能插入assert(*pphead && pphead);//pos為空,不能插入assert(pos);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);//如果pos為頭結點,直接頭插if (pos == *pphead){//頭插SLPushFront(pphead, num);}else{//找到指定位置的前一個節點SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}//pcur newnode posnewnode->next = pos;pcur->next = newnode;}
}
時間復雜度為:O(N)
2.7 在指定位置之后插入數據
我們通過改變pos位置上的結點中的next指針,指針指向新結點,然后新結點中的next指針指向pos位置的后一個結點。
代碼
//在指定位置之后插入數據
void SLInsertBack(SLTNode* pos, SLTDataType num)
{assert(pos);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);newnode->next = pos->next;pos->next = newnode;
}
時間復雜度為:O(1)
2.8 刪除指定位置上的結點
思路:如果pos位置為頭結點,直接進行頭刪;如果pos位置不是頭結點,需要找到pos位置的前一個結點,然后改變前一個結點中的next指針,使其指向pos位置的后一個結點,然后釋放pos位置上的結點空間。
代碼
//刪除pos位置上的節點
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);if (pos == *pphead){//頭刪SLPopFront(pphead);}else{SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}//pcur pos pos->nextpcur->next = pos->next;free(pos);pos = NULL;}
}
2.9 刪除指定位置之后的結點
改變pos位置中的指針指向,使其指向del結點的下一個結點,然后釋放del結點的空間。
代碼
//刪除pos位置之后的節點
void SLEraseBack(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
2.10 銷毀單鏈表
遍歷鏈表,從頭結點開始釋放,先保存頭結點的下一個結點的地址,然后釋放頭結點的空間,下一個結點成為新的頭結點,重復此操作,直至遇到NULL。
代碼
//銷毀鏈表
void SLDestory(SLTNode** pphead)
{assert(*pphead);SLTNode* pcur = *pphead;while (pcur != NULL){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
三、完整代碼
SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{int data;//存儲數據struct SListNode* next;//保存的是下一個節點的地址
}SLTNode;
//打印鏈表
void SLPrint(SLTNode** pphead);
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType num);
//頭插
void SLPushFront(SLTNode** pphead, SLTDataType num);
//尾刪
void SLPopBack(SLTNode** pphead);
//頭刪
void SLPopFront(SLTNode** pphead);
//查找
SLTNode* SLFind(SLTNode** pphead, SLTDataType num);
//在指定位置之前插入數據
void SLInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType num);
//在指定位置之后插入數據
void SLInsertBack(SLTNode* pos, SLTDataType num);
//刪除pos位置上的節點
void SLErase(SLTNode** pphead,SLTNode* pos);
//刪除pos位置之后的節點
void SLEraseBack(SLTNode* pos);
//銷毀鏈表
void SLDestory(SLTNode** pphead);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//打印節點中的數據
void SLPrint(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur != NULL){printf("%d ->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
//為節點創建空間
SLTNode* SlBuyNode(SLTDataType num)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = num;newnode->next = NULL;return newnode;
}
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType num)
{assert(pphead);//為節點申請空間SLTNode* newnode = SlBuyNode(num);//頭結點為空if (*pphead == NULL){*pphead = newnode;}else{//找到尾節點//頭結點不為空SLTNode* ptail = *pphead;while (ptail->next != NULL){ptail = ptail->next;}ptail->next = newnode;}
}
//頭插
void SLPushFront(SLTNode** pphead, SLTDataType num)
{assert(pphead);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
//尾刪
void SLPopBack(SLTNode** pphead)
{assert(pphead);//如果只有一個頭結點if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;SLTNode* ptail = *pphead;//找到尾節點以及尾節點的前一個節點while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = NULL;}
}
//頭刪
void SLPopFront(SLTNode** pphead)
{//保留頭結點的下一個節點SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//查找
SLTNode* SLFind(SLTNode** pphead, SLTDataType num)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur != NULL){if (pcur->data == num){return pcur;}pcur = pcur->next;}return NULL;
}
//在指定位置之前插入數據
void SLInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType num)
{//鏈表為空,不能插入assert(*pphead && pphead);//pos為空,不能插入assert(pos);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);//如果pos為頭結點,直接頭插if (pos == *pphead){//頭插SLPushFront(pphead, num);}else{//找到指定位置的前一個節點SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}//pcur newnode pos//newnode->next = pos;pcur->next = newnode;newnode->next = pos;}
}
//在指定位置之后插入數據
void SLInsertBack(SLTNode* pos, SLTDataType num)
{assert(pos);//為新節點創建空間SLTNode* newnode = SlBuyNode(num);newnode->next = pos->next;pos->next = newnode;
}
//刪除pos位置上的節點
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);if (pos == *pphead){//頭刪SLPopFront(pphead);}else{SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}//pcur pos pos->nextpcur->next = pos->next;free(pos);pos = NULL;}
}
//刪除pos位置之后的節點
void SLEraseBack(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
//銷毀鏈表
void SLDestory(SLTNode** pphead)
{assert(*pphead);SLTNode* pcur = *pphead;while (pcur != NULL){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
void test01()
{SLTNode* plist = NULL;//尾插SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPushBack(&plist, 5);SLPushBack(&plist, 6);SLPrint(&plist);//頭插SLPushFront(&plist, 0);SLPrint(&plist);//尾刪SLPopBack(&plist);SLPrint(&plist);//頭刪SLPopFront(&plist);SLPrint(&plist);//查找SLTNode* pos=SLFind(&plist, 1);//指定位置之前插入SLInsertFront(&plist, pos, 8);SLPrint(&plist);//指定位置之后插入SLInsertBack(pos, 7);SLPrint(&plist);//刪除指定位置數據SLErase(&plist, pos);SLPrint(&plist);//刪除指定位置之后的數據pos = SLFind(&plist, 8);SLEraseBack(pos);SLPrint(&plist);//銷毀SLDestory(&plist);}
int main()
{test01();return 0;
}
運行截圖: