目錄
一，鏈表的概念及結(jié)構(gòu)
二，接口實(shí)現(xiàn)
????????1，單鏈表的創(chuàng)建
????????2，接口函數(shù)
????????3，動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
????????4，打印
????????5，頭插
????????6，頭刪
????????7，尾插
????????8，尾刪
????????9，查找
????????10，單鏈表在pos位置之后插入x
????????11，單鏈表刪除pos位置之后的值
????????12，銷(xiāo)毀
三，源代碼
LKList.h
LKList.c
四，總結(jié)
一，鏈表的概念及結(jié)構(gòu)
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的
?
?
?而在數(shù)據(jù)結(jié)構(gòu)中：
注意：
1，從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)
?2，現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請(qǐng)出來(lái)的
?3，從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)；
?實(shí)際中鏈表的結(jié)構(gòu)非常多樣，今天我們來(lái)寫(xiě)一下單鏈表，此表一會(huì)其他的自然水到渠成！
二，接口實(shí)現(xiàn)
????????1，單鏈表的創(chuàng)建
//無(wú)頭 + 單向 + 非循環(huán)鏈表增刪查改實(shí)現(xiàn)
typedef int LKLDataType;
typedef struct LinKedListNode
{
LKLDataType data;
struct LinKedListNode* next;
}LKLNode;首先創(chuàng)建一個(gè)結(jié)構(gòu)體表示單鏈表，data是存儲(chǔ)的值，LKLDataType是儲(chǔ)存的值的數(shù)據(jù)類(lèi)型，next是結(jié)點(diǎn)----指向下一個(gè)；
這里的LKLDataType是int的重命名，也可以說(shuō)是數(shù)據(jù)類(lèi)型的重命名，這樣統(tǒng)一化方便后續(xù)更改；
????????2，接口函數(shù)
// 動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 頭插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 頭刪
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾刪
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 單鏈表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 單鏈表刪除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 銷(xiāo)毀
void LKLDestroy(LKLNode** plist);?這是以上要實(shí)現(xiàn)的接口函數(shù)；
????????3，動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
//動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
LKLNode* BuyLKLNode(LKLDataType x)
{
LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}后面創(chuàng)立新節(jié)點(diǎn)時(shí)直接調(diào)用此函數(shù)，一定要向堆區(qū)申請(qǐng)空間，這樣函數(shù)結(jié)束空間會(huì)保留不會(huì)被回收；
????????4，打印
//打印
void LKLPrint(LKLNode* phead)
{
assert(phead);
LKLNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}打印也就是打印data的值，用cur=phead然后每次打印完都讓cur走向下一個(gè)直到為空結(jié)束；
????????5，頭插
//頭插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{
assert(phead);
LKLNode* newnode = BuyLKLNode(x);
newnode->next = *phead;
*phead = newnode;
}先斷言一下，既然插入數(shù)據(jù)那就要申請(qǐng)一個(gè)新節(jié)點(diǎn)，然后令新節(jié)點(diǎn)的next指向phead然后再令phead指向新節(jié)點(diǎn)；
????????6，頭刪
//頭刪
void LKLNodeBackFront(LKLNode** phead)
{
assert(phead);
//為空
assert(*phead);
//非空
LKLNode* newnode = (*phead)->next;
free(*phead);
*phead = newnode;
}還是先斷言，有人會(huì)問(wèn)為什么要斷言?xún)纱?？其?shí)很好判斷，哪個(gè)需要解引用那個(gè)就需要斷言；
令一個(gè)變量newnode等于頭結(jié)點(diǎn)的下一個(gè)，在釋放頭結(jié)點(diǎn)，在令頭結(jié)點(diǎn)指向newnode即可；
????????7，尾插
//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{
assert(phead);
assert(*phead);
LKLNode* newnode= BuyLKLNode(x);
LKLNode* cur = *phead;
//為空
if (*phead == NULL)
{
*phead = newnode;
}
//非空
else
{
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
}還是先斷言判斷，然后要插入一個(gè)新的數(shù)據(jù)先申請(qǐng)一個(gè)新結(jié)點(diǎn)，如果頭結(jié)點(diǎn)為空則直接讓頭結(jié)點(diǎn)指向新結(jié)點(diǎn)即可，如果頭結(jié)點(diǎn)不為空，則需要找到next為空的結(jié)點(diǎn)，這里用一個(gè)循環(huán)搞定，然后再直接讓next為空的結(jié)點(diǎn)指向新節(jié)點(diǎn)即可；
????????8，尾刪
//尾刪
void LKLNodePopBack(LKLNode** phead)
{
assert(phead);
//為空
assert(*phead);
//一個(gè)
if ((*phead)->next==NULL)
{
free(*phead);
*phead = NULL;
}
//兩個(gè)及以上
else
{
LKLNode* tail = *phead;
/*LKLNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(prev->next);
prev->next = NULL;*/
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}還是先斷言一下，然后這里有兩種情況，鏈表只有一個(gè)結(jié)點(diǎn)，兩個(gè)以上結(jié)點(diǎn)的時(shí)候；
當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)也就是頭結(jié)點(diǎn)，直接頭刪即可；
兩個(gè)以上結(jié)點(diǎn)的時(shí)候，我這里有兩種解決方案；
方案一常規(guī)法：先用循環(huán)找到next為空的結(jié)點(diǎn)，并且在循環(huán)里保留上一個(gè)結(jié)點(diǎn)prev，然后釋放next為空的結(jié)點(diǎn)再讓prev的next指向空即可；
方案二：不需要標(biāo)記上一個(gè)結(jié)點(diǎn)，直接原地判斷，判斷結(jié)點(diǎn)的next的next是否為空，否則繼續(xù)向后推進(jìn)，是則釋放結(jié)點(diǎn)的next然后再令自己的next指向空也就相當(dāng)于變成了尾結(jié)點(diǎn)；
????????9，查找
// 單鏈表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{
assert(phead);
LKLNode* pos = phead;
while (pos)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}老樣子先斷言一下，然后直接用循環(huán)遍歷鏈表找到data是x的值然后返回此結(jié)點(diǎn)即可；
????????10，單鏈表在pos位置之后插入x
// 單鏈表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{
assert(pos);
LKLNode* newnode= BuyLKLNode(x);
LKLNode* cur = pos;
newnode->next = cur->next;
cur->next = newnode;
}先斷言，要插入數(shù)據(jù)先申請(qǐng)一個(gè)新結(jié)點(diǎn)，然后令新結(jié)點(diǎn)的next指向pos的next，再返回來(lái)讓pos的next指向新結(jié)點(diǎn)；
????????11，單鏈表刪除pos位置之后的值
// 單鏈表刪除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{
assert(pos);
assert(pos->next);
LKLNode* cur = pos;
LKLNode* newnode = cur->next->next;
free(cur->next);
cur->next = newnode;
}要?jiǎng)h除值首先要確保得有值，所以開(kāi)始斷言；
先定義一個(gè)變量newnode指向pos的next的next，然后再釋放pos的next，再令pos指向newnode以達(dá)到刪除之后的效果；
????????12，銷(xiāo)毀
// 單鏈表的銷(xiāo)毀
void LKLDestroy(LKLNode** phead)
{
assert(phead);
assert(*phead);
LKLNode* cur = *phead;
LKLNode* next = NULL;
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
}老樣子那個(gè)需要解引用那個(gè)就先斷言一下，然后用循環(huán)遍歷，先標(biāo)記下一個(gè)結(jié)點(diǎn)，然后釋放自己，再讓自己指向標(biāo)記的結(jié)點(diǎn)直到為空結(jié)束；
三，源代碼
LKList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//無(wú)頭 + 單向 + 非循環(huán)鏈表增刪查改實(shí)現(xiàn)
typedef int LKLDataType;
typedef struct LinKedListNode
{
LKLDataType data;
struct LinKedListNode* next;
}LKLNode;
// 動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 頭插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 頭刪
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾刪
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 單鏈表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 單鏈表刪除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 銷(xiāo)毀
void LKLDestroy(LKLNode** plist);
LKList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"LKList.h"
//動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
LKLNode* BuyLKLNode(LKLDataType x)
{
LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//頭插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{
assert(phead);
LKLNode* newnode = BuyLKLNode(x);
newnode->next = *phead;
*phead = newnode;
}
//頭刪
void LKLNodeBackFront(LKLNode** phead)
{
assert(phead);
//為空
assert(*phead);
//非空
LKLNode* newnode = (*phead)->next;
free(*phead);
*phead = newnode;
}
//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{
assert(phead);
assert(*phead);
LKLNode* newnode= BuyLKLNode(x);
LKLNode* cur = *phead;
//為空
if (*phead == NULL)
{
*phead = newnode;
}
//非空
else
{
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
}
//尾刪
void LKLNodePopBack(LKLNode** phead)
{
assert(phead);
//為空
assert(*phead);
//一個(gè)
if ((*phead)->next==NULL)
{
free(*phead);
*phead = NULL;
}
//兩個(gè)及以上
else
{
LKLNode* tail = *phead;
/*LKLNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(prev->next);
prev->next = NULL;*/
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
// 單鏈表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{
assert(phead);
LKLNode* pos = phead;
while (pos)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
// 單鏈表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{
assert(pos);
LKLNode* newnode= BuyLKLNode(x);
LKLNode* cur = pos;
newnode->next = cur->next;
cur->next = newnode;
}
// 單鏈表刪除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{
assert(pos);
assert(pos->next);
LKLNode* cur = pos;
LKLNode* newnode = cur->next->next;
free(cur->next);
cur->next = newnode;
}
// 單鏈表的銷(xiāo)毀
void LKLDestroy(LKLNode** phead)
{
assert(phead);
assert(*phead);
LKLNode* cur = *phead;
LKLNode* next = NULL;
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
}
//打印
void LKLPrint(LKLNode* phead)
{
assert(phead);
LKLNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}四，總結(jié)
做數(shù)據(jù)結(jié)構(gòu)的題目畫(huà)圖很重要，小伙伴們剛開(kāi)始喜歡用腦子去構(gòu)圖想象，但遇到復(fù)雜的情況會(huì)紊亂的，畫(huà)圖最為可觀方便，可以培養(yǎng)一個(gè)良好的畫(huà)圖習(xí)慣；
如有不足之處歡迎來(lái)補(bǔ)充交流！文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-686161.html
完結(jié)。。。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-686161.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】手撕?jiǎn)捂湵淼奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]鏈表之單鏈表（詳解）](https://imgs.yssmx.com/Uploads/2024/01/400368-1.png)
