哈嘍，大家好，今天我們學(xué)習(xí)的是數(shù)據(jù)結(jié)構(gòu)里的鏈表，這里主要講的是不帶哨兵衛(wèi)頭節(jié)點(diǎn)的單向鏈表，下篇將會(huì)繼續(xù)帶大家學(xué)習(xí)雙向鏈表。
目錄
1.鏈表的概念
2.單向鏈表接口的實(shí)現(xiàn)
2.1動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
2.2單鏈表打印
2.3單鏈表尾插
2.4單鏈表頭插
2.5單鏈表尾刪
2.6單鏈表頭刪
2.7在pos位置插入x
2.7.1在pos位置前插入x
2.7.2在pos位置后插入x
2.8刪除pos位置值
2.9 查找x的地址
2.10銷毀鏈表
3.完整代碼
1.鏈表的概念
在上篇文章，我們已經(jīng)學(xué)習(xí)了順序表，不知大家有沒有發(fā)現(xiàn)順序表在一定程度上是存在缺陷的，比如說：
- 空間不夠了的時(shí)候需要擴(kuò)容，擴(kuò)容需要付出代價(jià)（特別是異地?cái)U(kuò)空間）
- 為了避免頻繁擴(kuò)容，我們滿了基本都是擴(kuò)2倍，可能會(huì)導(dǎo)致一定的空間浪費(fèi)
- 順序表要求數(shù)據(jù)從開始位置連續(xù)存儲(chǔ)，那么我們?cè)陬^部或者中間位置插入刪除數(shù)據(jù)就需要挪動(dòng)數(shù)據(jù)，效率不高
針對(duì)順序表的缺陷，就有了鏈表來存儲(chǔ)數(shù)據(jù)
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
?鏈表的定義：
?這里的data就是要存放的數(shù)據(jù)
2.單向鏈表接口的實(shí)現(xiàn)
下面是要介紹的常用到的鏈表接口函數(shù)以及實(shí)現(xiàn)方法：
//打印
void SListPrint(SLTNode* phead);
//創(chuàng)建新節(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//頭插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//頭刪
void SListPopBack(SLTNode** pphead);
//尾刪
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//刪除
void SListErase(SLTNode** pphead, SLTNode* pos);
//銷毀
void SListDestroy(SLTNode** pphead);
2.1動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
由于我們每次給鏈表插入數(shù)據(jù)時(shí)，都需要?jiǎng)討B(tài)開辟空間來申請(qǐng)節(jié)點(diǎn)，所以我們把這個(gè)過程封裝成一個(gè)函數(shù)，方便后續(xù)操作。
動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)的步驟是先向計(jì)算機(jī)內(nèi)存申請(qǐng)一塊空間，這里我們將申請(qǐng)的空間用指針變量newnode來存儲(chǔ)，然后將newnode中的data賦值，因?yàn)檫@是新開辟的節(jié)點(diǎn)，所以暫時(shí)將newnode中的next指向空。
注意：為了提高程序的可靠性，我們?cè)趧?dòng)態(tài)內(nèi)存申請(qǐng)后記得檢查是否申請(qǐng)失敗了，如果申請(qǐng)失敗了輸出提示信息，并退出程序。
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果動(dòng)態(tài)內(nèi)存申請(qǐng)失敗就退出程序
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}2.2單鏈表打印
打印鏈表就是一個(gè)遍歷鏈表的過程，我們首先定義一個(gè)指針(cur)指向鏈表的頭節(jié)點(diǎn)，然后輸出該節(jié)點(diǎn)的值，然后將指針指向下一個(gè)節(jié)點(diǎn)（cur=cur->next),依次進(jìn)行，直到cur為空指針時(shí)停止
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//將cur指向下一個(gè)節(jié)點(diǎn)
}
printf("NULL\n");
}2.3單鏈表尾插
尾插，就是先找到鏈表中最后一個(gè)節(jié)點(diǎn)，然后將數(shù)據(jù)插入到最后。
但是，我們要先判斷鏈表是否為空，如果鏈表為空，我們直接直接將鏈表的頭指針賦予要插入的數(shù)據(jù)。
由于尾插要改變鏈表，所以傳參要用二級(jí)指針，包括下面的尾插，尾刪，頭刪等都要用二級(jí)指針傳參
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}2.4單鏈表頭插
頭插是比較簡(jiǎn)單的一種操作，只需要申請(qǐng)新節(jié)點(diǎn)，將新節(jié)點(diǎn)的next指向鏈表的頭，再讓新節(jié)點(diǎn)成為鏈表的頭即可。
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}2.5單鏈表尾刪
尾刪：每次找到鏈表的最后一個(gè)節(jié)點(diǎn)和倒數(shù)第二個(gè)節(jié)點(diǎn)，然后釋放最后一個(gè)節(jié)點(diǎn)所占的看空間并將最后一個(gè)節(jié)點(diǎn)置空，同時(shí)將倒數(shù)第二個(gè)節(jié)點(diǎn)的next指向NULL；如果鏈表只剩下一個(gè)節(jié)點(diǎn)，直接釋放并置空該節(jié)點(diǎn)（這一步需要單獨(dú)考慮）
注意：為了避免鏈表為空但有調(diào)用尾刪的情況，我們需要斷言一下，當(dāng)傳過來的鏈表是空鏈表的時(shí)候，程序就會(huì)報(bào)錯(cuò)
void SListPopBack(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
//當(dāng)鏈表中只有一個(gè)節(jié)點(diǎn)
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}2.6單鏈表頭刪
頭刪是將第一個(gè)節(jié)點(diǎn)釋放然后指向第二個(gè)節(jié)點(diǎn)，在此之前需要定義一個(gè)指針next來保存第二個(gè)節(jié)點(diǎn)的地址。
void SListPopFront(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}2.7在pos位置插入x
在pos位置插入x分為兩種情況，一種是在pos前位置插入x ，另一種是在pos后位置插入x，下面將分別為大家介紹：
2.7.1在pos位置前插入x
在pos位置前插入x,只需要找到pos的前一個(gè)位置，我們把pos的前一個(gè)位置命名為posPrev，然后創(chuàng)建一個(gè)新節(jié)點(diǎn)newnode，將posPrev的下一個(gè)節(jié)點(diǎn)指向newnode，newnode的下一個(gè)節(jié)點(diǎn)指向pos即可，如下圖：
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一個(gè)位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}2.7.2在pos位置后插入x
在pos位置后插入x比在pos位置前插入x要簡(jiǎn)單，不需要遍歷鏈表即可完成
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
?? ?assert(pos != NULL);
?? ?SLTNode* newnode = BuyListNode(x);
?? ?newnode->next = pos->next;
?? ?pos->next = newnode;
}2.8刪除pos位置值
刪除pos位置值也需要先找到pos的前一個(gè)節(jié)點(diǎn)，因此也要考慮pos是鏈表的頭節(jié)點(diǎn)的情況
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}2.9 查找x的地址
查找x的地址，如果查找到了x，則返回該節(jié)點(diǎn)的地址，否則返回空指針。這個(gè)步驟也要遍歷鏈表。
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}2.10銷毀鏈表
銷毀鏈表需要將所有節(jié)點(diǎn)所占的內(nèi)存全部釋放，再將鏈表的頭置為空即可。
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.完整代碼
SList.h文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;//存放下一個(gè)鏈表的地址
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//創(chuàng)建新節(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//頭插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//頭刪
void SListPopBack(SLTNode** pphead);
//尾刪
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//刪除
void SListErase(SLTNode** pphead, SLTNode* pos);
//銷毀
void SListDestroy(SLTNode** pphead);SList.c文件：文章來源：http://www.zghlxwxcb.cn/news/detail-438989.html
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//將cur指向下一個(gè)節(jié)點(diǎn)
}
printf("NULL\n");
}
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果動(dòng)態(tài)內(nèi)存申請(qǐng)失敗就退出程序
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
//當(dāng)鏈表中只有一個(gè)節(jié)點(diǎn)
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一個(gè)位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}總結(jié)：這篇文章主要寫的是單向鏈表，后續(xù)將繼續(xù)帶領(lǐng)大家學(xué)習(xí)雙向鏈表。如果我寫的有什么的不好之處，請(qǐng)?jiān)谖恼孪路浇o出你寶貴的意見。如果覺得我寫的好的話請(qǐng)點(diǎn)個(gè)贊贊和關(guān)注哦~??文章來源地址http://www.zghlxwxcb.cn/news/detail-438989.html
到了這里，關(guān)于單向鏈表——C語(yǔ)言實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Collection與數(shù)據(jù)結(jié)構(gòu)] 鏈表與LinkedList (一):鏈表概述與單向無頭非循環(huán)鏈表實(shí)現(xiàn)](https://imgs.yssmx.com/Uploads/2024/04/858484-1.png)
