?c語(yǔ)言中的小小白-CSDN博客c語(yǔ)言中的小小白關(guān)注算法,c++,c語(yǔ)言,貪心算法,鏈表,mysql,動(dòng)態(tài)規(guī)劃,后端,線(xiàn)性回歸,數(shù)據(jù)結(jié)構(gòu),排序算法領(lǐng)域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343
給大家分享一句我很喜歡我話(huà):
知不足而奮進(jìn),望遠(yuǎn)山而前行!??!
鐵鐵們,成功的路上必然是孤獨(dú)且艱難的,但是我們不可以放棄,遠(yuǎn)山就在前方,但我們能力仍然不足,所有我們更要奮進(jìn)前行?。?!
今天我們更新了單鏈表內(nèi)容,
?? 歡迎大家關(guān)注??點(diǎn)贊??收藏??留言??
鏈表的概念:
概念:鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),但鏈表在邏輯上是連續(xù)的,順序的,而數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針連接次序?qū)崿F(xiàn)的。
鏈表的結(jié)構(gòu):
鏈表是由一個(gè)個(gè)結(jié)點(diǎn)組成的,結(jié)點(diǎn)如下圖所示:
注意:鏈表中的最后一個(gè)結(jié)點(diǎn)的next指向空,next=NULL。
一個(gè)個(gè)結(jié)點(diǎn)串成了鏈表,如下圖所示:
?有人可能會(huì)有疑問(wèn),不是說(shuō)鏈表只是在邏輯結(jié)構(gòu)上是連續(xù)的,在物理存儲(chǔ)結(jié)構(gòu)上是不連續(xù)的,那為什么上圖中一個(gè)個(gè)結(jié)點(diǎn)明明是挨在一起的,那么它在物理存儲(chǔ)結(jié)構(gòu)上肯定是連續(xù)的呀,其實(shí)不然,上圖是為了方便大家理解,才用線(xiàn)條連接了結(jié)點(diǎn),實(shí)際上在內(nèi)存中,每個(gè)結(jié)點(diǎn)可能會(huì)隔得很遠(yuǎn),仔細(xì)觀(guān)察每個(gè)結(jié)點(diǎn)上面的紅色文字,那就是這個(gè)結(jié)點(diǎn)的地址,而藍(lán)色文字是下一個(gè)結(jié)點(diǎn)的地址,很明顯能看到這兩個(gè)結(jié)點(diǎn)并不是相鄰的,因此也驗(yàn)證了順序表在邏輯結(jié)構(gòu)上確實(shí)是連續(xù)的,但在物理存儲(chǔ)結(jié)構(gòu)上確實(shí)是不連續(xù)的。
鏈表的實(shí)現(xiàn):
1.1定義節(jié)點(diǎn)
介紹一下單鏈表的英文名——single linked list,我們簡(jiǎn)寫(xiě)成SL(區(qū)別于順序表的SeqList或者SQL)。
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType Date;
SListNode* next;
}SListNode;
1.2鏈表的功能
鏈表要實(shí)現(xiàn)那些功能呢?其實(shí)這些功能我們都很熟悉,數(shù)據(jù)結(jié)構(gòu)無(wú)非是對(duì)數(shù)據(jù)進(jìn)行管理,要實(shí)現(xiàn)數(shù)據(jù)的增刪查改,因此鏈表的基本功能也都是圍繞著數(shù)據(jù)的增刪查改展開(kāi)。
這里我們要注意一點(diǎn),鏈表是不需要進(jìn)行初始化的
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead);
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead);
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead);
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印單鏈表
void PrintSLT(SLTNode * phead);
鏈表功能的實(shí)現(xiàn)
2.1打印單鏈表
注意:鏈表和順序不同的是,順序表傳過(guò)來(lái)的指針是肯定不會(huì)為空的,而鏈表傳過(guò)來(lái)的指針是可能為空的,比如說(shuō)當(dāng)鏈表中沒(méi)有元素時(shí),頭指針?biāo)赶虻木褪荖ULL,如果在第一行寫(xiě)上斷言就會(huì)有問(wèn)題。
當(dāng)cur指向空的時(shí)候就可以停止打印了。
void PrintSLT(SListNode*phead)
{
//注意:不需要斷言assert(psl);
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL");
printf("\n");
//最后打印出來(lái)的效果就是 1->2->3->4->NULL
}
2.2 創(chuàng)建一個(gè)新結(jié)點(diǎn)
后面我們要在單鏈表中進(jìn)行頭插和尾插,此時(shí)插入的不再是像順序表一樣簡(jiǎn)單的SLDateType數(shù)據(jù)了,而是一個(gè)結(jié)點(diǎn),這個(gè)結(jié)點(diǎn)是包括SLTDateType數(shù)據(jù)以及SLTDateType*的指針,因此,為了方便和減少代碼的重復(fù)度,我們另寫(xiě)一個(gè)函數(shù)用來(lái)專(zhuān)門(mén)創(chuàng)建新結(jié)點(diǎn)。
//創(chuàng)建一個(gè)新結(jié)點(diǎn)
SListNode* BuySLTNode(SLDateType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
perror("malloc:");
return;
}
newNode->date = x;
newNode->next = NULL;
return newNode;
}
2.3?單鏈表尾插
注意:在創(chuàng)建結(jié)點(diǎn)時(shí),已經(jīng)讓 結(jié)點(diǎn).next=NULL,所以不需要在插入完結(jié)點(diǎn)后,再讓新結(jié)點(diǎn)的next指針為NULL。
有人可能會(huì)有疑問(wèn),為什么之前打印鏈表的時(shí)候不用斷言指針,而在尾插時(shí)就要斷言指針,以及為什么函數(shù)的形參是二級(jí)指針,而不使用一級(jí)指針。
因?yàn)?,尾插分為兩種情況(下面有寫(xiě)),當(dāng)鏈表為空時(shí),頭指針phead指向NULL,尾插相當(dāng)于頭插,此時(shí)要改變phead的指向,讓phead指向這個(gè)新結(jié)點(diǎn),此時(shí)就需要二級(jí)指針來(lái)改變一級(jí)指針的值(如果我們用一級(jí)指針做形參,形參的改變不會(huì)影響實(shí)參,那么一級(jí)指針phead就不會(huì)被改變)。
至于這個(gè)什么時(shí)候要斷言指針,什么時(shí)候不用斷言指針:一級(jí)指針也就是phead,當(dāng)鏈表為空的時(shí)候,phead就是為NULL,而二級(jí)指針永遠(yuǎn)指向phead,phead的地址是永遠(yuǎn)存在的,那么pphead就一定不可能為空,所以需要斷言pphead。
//單鏈表尾插
void SLTPushBack(SListNode**pphead, SLDateType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
//1.鏈表為空
//2.鏈表不為空
if (*pphead == NULL)
{
*pphead = newnode;
//不需要讓newnode->next=NULL,在BuySLTNode中我們就已經(jīng)進(jìn)行過(guò)這個(gè)操作了
}
else
{
//找到鏈表的尾巴tail
SListNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
2.4順序表頭刪
頭刪沒(méi)什么好說(shuō)的,記住要斷言*pphead,保證鏈表內(nèi)容不為空。
//頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);
cur = NULL;
}
2.5順序表頭插
現(xiàn)在是不是覺(jué)得頭插很簡(jiǎn)單了??!
//頭插
void SListPushFront(SListNode** pphead,SLDateType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
2.6查找某個(gè)結(jié)點(diǎn)
這個(gè)函數(shù)返回值不再是void,而是SListNode*,把找到的結(jié)點(diǎn)的地址返回去,這個(gè)函數(shù)一般會(huì)跟結(jié)點(diǎn)修改之類(lèi)的函數(shù)一起使用。
//單鏈表結(jié)點(diǎn)的查找
SListNode* SListNodeFind(SListNode* phead,SLDateType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->date == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.7刪除某個(gè)結(jié)點(diǎn)
//刪除某個(gè)結(jié)點(diǎn)
void SListNodeErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
//頭刪
//非頭刪
if (*pphead == pos)
{
SListNode* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);
cur = NULL;
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev->next);
//這里為什么要加個(gè)斷言?
}
prev->next = pos->next;
free(pos);
}
}
注意:
- pos也要斷言,pos可不能為空呀!
- cur->next也要斷言,因?yàn)楫?dāng)cur->next為NULL時(shí),說(shuō)明整個(gè)鏈表的結(jié)點(diǎn)都排查完了,最后還是沒(méi)有找到地址為pos的結(jié)點(diǎn),證明pos傳值有誤。
?2.8單鏈表結(jié)點(diǎn)修改
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
SLTNode* cur = phead;
while (cur != pos)
{
cur = cur->next;
assert(cur);
}
pos->data = x;
}
2.9單鏈表前插入結(jié)點(diǎn)
//單鏈表前插入結(jié)點(diǎn)
void SLTInsertFront(SListNode** pphead, SListNode* pos,SLDateType x)
{
assert(pphead);
assert(pos);
//頭插
//非頭插
SListNode* newnode = BuySLTNode(x);
if ((*pphead)->next == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev->next);
}
newnode->next = pos;
prev->next = newnode;
}
}
2.10單鏈表后插入結(jié)點(diǎn)
這里我要提醒一下,千萬(wàn)不要忘記判斷pos是否正確,不要只單單斷言pos是否為NULL,還要判斷能不能在鏈表中找到pos這個(gè)地址(我第一次寫(xiě)鏈表就忘記檢查了,第二次寫(xiě)還是忘記了,非常容易忘記文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-847737.html
//單鏈表后插入結(jié)點(diǎn)
void SLTInsertBack(SListNode* phead, SListNode* pos, SLDateType x)
{
assert(pos);
SListNode* cur = phead;
//防止pos傳錯(cuò)了
while (cur != pos)
{
cur = cur->next;
assert(pos);
}
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.11銷(xiāo)毀鏈表
銷(xiāo)毀鏈表這一塊,咱可不敢直接free(phead),因?yàn)殒湵碓谖锢斫Y(jié)構(gòu)上是不連續(xù)存儲(chǔ)的,銷(xiāo)毀鏈表必須要一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)去銷(xiāo)毀!?。?!最后不要忘記把phead置為NULL。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-847737.html
//銷(xiāo)毀鏈表
void SLTDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
總代碼:
3.1 SLT.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SLTNode
{
SLTDateType data;
struct SLTNode* next;
}SLTNode;
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead);
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead);
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead);
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印單鏈表
void PrintSLT(SLTNode * phead);
3.2 SLT.c
#include"SLT.h"
//建立一個(gè)新的結(jié)點(diǎn)
//這是鏈表的缺點(diǎn):經(jīng)常需要使用malloc為newnode開(kāi)辟空間
SLTNode* BuyListNode(SLTDateType x)
{
//為什么要用malloc,是因?yàn)椋绻贐uyListNode函數(shù)中SLTNode newnode,出了這個(gè)函數(shù),newnode就被銷(xiāo)毀了,
//用malloc開(kāi)辟空間,只要我們不主動(dòng)釋放這個(gè)空間,這個(gè)空間的數(shù)據(jù)一直存在,
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//static SLTNode newnode;
if (newnode == NULL)
{
perror("malloc:");
exit(0);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);//phead可能為NULL,但是pphead指向phead,不可能為空
SLTNode* newnode = BuyListNode(x);
//這里可不是newnode->next = (*pphead)->next;
newnode->next = *pphead;
*pphead = newnode;
}
//尾插
//尾插特別容易出錯(cuò),當(dāng)鏈表中沒(méi)有數(shù)據(jù),即phead=NULL時(shí),尾插就相當(dāng)于頭插了,此時(shí)需要改變phead的值
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
//1、空
//2、非空
if (*pphead == NULL)
{
*pphead = newnode;
//newnode->next = NULL;這一步是不需要的,newnode在建立的時(shí)候就默認(rèn)newnode->next=NULL;
}
else
{
SLTNode* cur = *pphead;
//這是單向鏈表的缺點(diǎn),需要去找尾
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
//頭刪
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//溫柔的檢查
if (*pphead == NULL)
return;
//暴力的檢查
assert(*pphead);
SLTNode* head = *pphead;
*pphead = (*pphead)->next;
free(head);
head = NULL;
}
//尾刪
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
//1、一個(gè)結(jié)點(diǎn)
//2、兩個(gè)結(jié)點(diǎn)
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* cur = *pphead;
while (cur->next->next)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
//打印單向鏈表
void PrintSLT(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
//單鏈表查找某個(gè)結(jié)點(diǎn)
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{
SLTNode* find = phead;
//別忘記分析找不到結(jié)點(diǎn)的情況
while (find)
{
if (find->data == x)
{
return find;
}
find = find->next;
}
return NULL;
}
//刪除pos位置的結(jié)點(diǎn)
void SLTErase(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已經(jīng)為空了,說(shuō)明鏈表已經(jīng)查完了,還沒(méi)有查到pos
//證明pos傳入有誤
assert(prev->next);
}
prev->next = pos->next;
free(pos);
//pos = NULL;這個(gè)沒(méi)必要,改變不了pos
}
}
//單鏈表結(jié)點(diǎn)前插
//一般插入結(jié)點(diǎn)都是在pos之前插入,但單鏈表在實(shí)現(xiàn)前插是比較困難的
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
//頭插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
//非頭插
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev->next);
}
SLTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//單鏈表結(jié)點(diǎn)后插
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
SLTNode* cur = *pphead;
while (cur != pos)
{
cur = cur->next;
//防止pos傳錯(cuò)了
assert(cur);
}
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
SLTNode* cur = phead;
while (cur != pos)
{
cur = cur->next;
assert(cur);
}
pos->data = x;
}
//銷(xiāo)毀鏈表
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
//比cur->next!=NULL更好一些
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
3.3 test.c
#include"SLT.h"
void test1()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 0);
SLTPushFront(&plist, -1);
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
PrintSLT(plist);
SLTPopFront(&plist);
SLTPopBack(&plist);
PrintSLT(plist);
SLTNode* pos = SLTNodeFind(plist, 0);
SLTInsert(&plist, pos, -2);
PrintSLT(plist);
SLTInsert(&plist, pos, -1);
PrintSLT(plist);
SLTInsertBack(&plist, pos, 3);
PrintSLT(plist);
SLTModify(plist, pos, 4);
PrintSLT(plist);
}
int main()
{
test1();
}
到了這里,關(guān)于【數(shù)據(jù)結(jié)構(gòu)】——單鏈表超詳細(xì)介紹(小白必看!?。。┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!