鏈表的概念及結(jié)構(gòu)
鏈表的概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
一、鏈表的邏輯結(jié)構(gòu)是什么樣的？
所謂的邏輯結(jié)構(gòu)其實就是能讓我們自己能夠更好的理解這個東西是什么？那么我們就用畫圖來理解理解吧??！在單鏈表中，存放著兩個量，一個是地址量，一個是數(shù)據(jù)量，如圖所示，這是一個帶頭的單鏈表。
二、鏈表的初始化
2.1鏈表初始化的示意
正如上圖所說，單鏈表中存在一個數(shù)據(jù)量和一個地址量，所以我們定義結(jié)構(gòu)體的時候，應(yīng)該定一個data數(shù)據(jù)量，和一個指針用來存放自己所以定義的地址量。
2.2鏈表初始化代碼實現(xiàn)
代碼如下：
typedef int SLTDataType;
typedef struct SListnode
{
SLTDataType data;
struct SListnode* next;
}SLTNode;
并且還需要定義幾個頭文件如下所示
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
這里介紹一個查詢頭文件的網(wǎng)站CPlusplus
三、鏈表的各類接口函數(shù)定義
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos之前插入
void SLInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode* phead);
四、鏈表的各類接口函數(shù)的代碼實現(xiàn)
4.1鏈表的打印代碼實現(xiàn)
因為我們寫的是帶頭的單鏈表，所以我們就可以從頭開始遍歷。我們定義一個結(jié)構(gòu)體指針用來存放頭結(jié)點，因為頭結(jié)點此時存放的是下一個位置的地址，所以我們只需要拿一個指針去接收它就行啦。
那我們此時該思考一下，我們雖然是通過遍歷來打印數(shù)據(jù)，但是我們是不是得想一下結(jié)束條件呢？如果我們用cur->next == NULL 作為結(jié)束條件，那么我們是不是想錯了呢？我們畫圖解釋一下吧！從圖中看，如果我們以cur->next為結(jié)束條件那么，最后一個數(shù)我們是不是就打印不了，所以我們就想錯啦
我們在來看看下圖，我們發(fā)現(xiàn)用cur本身去遍歷就可以把全部都遍歷完，好啦這里我們算是解釋通啦！
4.1.1打印代碼的實現(xiàn)
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
4.2鏈表的尾插代碼實現(xiàn)
尾插顧名思義就是在尾部進(jìn)行插入，那么我們應(yīng)該怎么樣去實現(xiàn)單鏈表的尾部插入呢？我們還是畫圖進(jìn)行理解,如下圖所示。
我們想要在尾部進(jìn)行插入，我們是不是應(yīng)該先遍歷到尾結(jié)點呢？是的沒錯！但是這里我們就得注意我們遍歷結(jié)束的條件了，為什么這么說呢？假設(shè)如果按照我們上面打印那樣遍歷的話，我們就會遍歷成野指針，所以我們遍歷的條件為cur->next ，這樣是不是就解決啦！
這里我們得考慮兩種情況。
1、當(dāng)這個鏈表是空的時候我們應(yīng)該怎么去處理他呢？我們直接讓新建立的節(jié)點賦值給我們的頭就行啦
2、也就是正常的插入啦！讓最后一個節(jié)點的指針指向新節(jié)點，然后再把最后一個節(jié)點的位置改變就完成啦！
4.2.1尾插代碼實現(xiàn)
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyLTNode(x);
if ((*pphead) == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
4.3鏈表的頭插代碼實現(xiàn)
關(guān)于頭插我們應(yīng)該這樣處理：
1、因為我們是帶有頭結(jié)點的單鏈表，又因為我們頭結(jié)點存儲的是第一個節(jié)點的地址，所以只需要把頭結(jié)點所存儲的地址賦給新開的節(jié)點的next位置，此時的新節(jié)點所指向的就是原來第一個節(jié)點的位置
2、因為頭結(jié)點存儲第一個節(jié)點的地址，所以我們要把新開的節(jié)點的地址賦給頭結(jié)點，這樣就完成了頭插！
1圖文解釋：插入前：
2、插入中：
3、結(jié)束插入：
4.3.1頭插代碼的實現(xiàn)
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
4.4BuyLTNode函數(shù)的實現(xiàn)
本函數(shù)的意思是動態(tài)的開辟一個節(jié)點在堆上！
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
4.5鏈表的尾刪代碼實現(xiàn)
在單鏈表中，尾刪的效率其實是非常的差的，因為單鏈表需要一直遍歷查找，所以效率耗費的十分的嚴(yán)重。
在尾刪的過程中，我們也需要考慮兩種情況！
第一種情況：當(dāng)鏈表中只有一個節(jié)點的時候我們應(yīng)該怎么樣的刪除
第二種情況：當(dāng)鏈表中有多個節(jié)點的時候我們應(yīng)該怎么刪除呢？
當(dāng)只有一個節(jié)點的時候，我們應(yīng)該直接把節(jié)點free掉，因為我們的節(jié)點都是動態(tài)開辟的，所以我們應(yīng)用free這個函數(shù)，把節(jié)點摧毀掉
當(dāng)有多個節(jié)點的時候，我們應(yīng)該用兩個指針，一個在前面一個在后面，當(dāng)前面的節(jié)點為空時，說明我們找到了尾，我們free掉尾結(jié)點就行啦！
4.5.1尾刪代碼的實現(xiàn)
void SLTPopBack(SLTNode** pphead)
{
//當(dāng)只有一個節(jié)點的時候
//多個節(jié)點
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
4.6鏈表的頭刪代碼實現(xiàn)
如下圖所示，先讓pphead往前先走一步，提前找好一個前節(jié)點，然后free掉他，然后把pphead賦值給prev，再讓*pphead往前走！
4.6.1頭插代碼的實現(xiàn)
void SLTPopFront(SLTNode** pphead)
{
//空鏈表
assert(*pphead);
assert(pphead);
SLTNode* prev = *pphead;
*pphead = prev->next;
free(prev);
}
五、完整代碼的實現(xiàn)
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"listnode.h"
void test1()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 0);
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPrint(plist);
SLTPushBack(&plist, -1);
SLTPrint(plist);
}
void test2()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, -1);
SLTPushBack(&plist, 0);
SLTPushBack(&plist, 1);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
void test3()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, -1);
SLTPushBack(&plist, 0);
SLTPushBack(&plist, 1);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPopFront(&plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
void test4()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
pos->data = 30;
SLInsert(&plist, pos, 20);
SLTPrint(plist);
SLInsertAfter(pos, 40);
SLTPrint(plist);
SLEraseAfter(pos);
SLTPrint(plist);
SLTDestroy(plist);
}
int main()
{
test4();
return 0;
}
listnode.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "listnode.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyLTNode(x);
if ((*pphead) == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾刪的第一種方式
void SLTPopBack(SLTNode** pphead)
{
//當(dāng)只有一個節(jié)點的時候
//多個節(jié)點
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
//尾刪的第二種方式
/*
void SLTPopBack(SLTNode** pphead)
{
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
*/
void SLTPopFront(SLTNode** pphead)
{
//空鏈表
assert(*pphead);
assert(pphead);
SLTNode* prev = *pphead;
*pphead = prev->next;
free(prev);
//一個節(jié)點
//if ((*pphead)->next == NULL)
//{
// free(*pphead);
// *pphead = NULL;
//}
多個節(jié)點
//else
//{
// SLTNode* prev = *pphead;
// *pphead = prev->next;
// free(prev);
//}
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
//在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//刪除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SLEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
void SLTDestroy(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
phead = phead->next;
free(cur);
cur = phead;
}
}
listnode.h文章來源：http://www.zghlxwxcb.cn/news/detail-456863.html
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListnode
{
SLTDataType data;
struct SListnode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos之前插入
void SLInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode* phead);
總結(jié)
好啦，今天的單鏈表的大部分解決思路我都給大家詳細(xì)的寫出來啦！我們下期再見！嘿我們天天見?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-456863.html
到了這里，關(guān)于初階數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)（四）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語言][數(shù)據(jù)結(jié)構(gòu)][鏈表] 單鏈表的從零實現(xiàn)!](https://imgs.yssmx.com/Uploads/2024/04/847183-1.png)
