嘉峪關(guān)市建設(shè)局建管科網(wǎng)站外鏈價(jià)格
?
這么可愛的貓貓不值得點(diǎn)個(gè)贊嗎😽😻
目錄
一.鏈表的概念和結(jié)構(gòu)
二.單鏈表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
1.邏輯結(jié)構(gòu)
?2.物理結(jié)構(gòu)
三.結(jié)構(gòu)體的定義
四.增加
1.尾插? ?SListpushback
2.頭插? SListpushfront
五.刪除
1.尾刪? SListpopback
2.頭刪? SListpopfront
六.查找? 插入? 釋放? ?打印
1.查找? ?SListfind
2.插入? SListinsert
3.釋放? SListerase
4.打印? SListprint
七.源碼
1.SList.h
2.SList.c
3.test.c
一.鏈表的概念和結(jié)構(gòu)
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的
鏈表其實(shí)有很多種類:
1.單向? 雙向
2.帶頭? 不帶頭
3.循環(huán)? 不循環(huán)
其中共能組合出8種形式的鏈表;
這篇文章講的是結(jié)構(gòu)最簡單的鏈表,也就是單向不帶頭不循環(huán)鏈表,即單鏈表。
單鏈表中的元素稱為節(jié)點(diǎn),節(jié)點(diǎn)有一個(gè)數(shù)據(jù)data,還有一個(gè)結(jié)構(gòu)體指針next 存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址,最后一個(gè)節(jié)點(diǎn)的next是NULL。
二.單鏈表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
1.邏輯結(jié)構(gòu)
?2.物理結(jié)構(gòu)
三.結(jié)構(gòu)體的定義
typedef int SLdatatype; //對數(shù)據(jù)類型重定義,方便后續(xù)更改typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;
四.增加
1.尾插? ?SListpushback
想要實(shí)現(xiàn)尾插,就要先找到尾節(jié)點(diǎn),但要注意,當(dāng)鏈表是空時(shí),就沒有尾節(jié)點(diǎn),這個(gè)時(shí)候直接插入就行了;
我們可以申請一個(gè)新的節(jié)點(diǎn)newnode,然后插入鏈表中,由于尾插和頭插都需要申請新的節(jié)點(diǎn),所以我們可以將這封裝成一個(gè)函數(shù);
注意,不管是尾插還是頭插,最后都會(huì)使鏈表發(fā)生改變,所以我們要傳二級(jí)指針進(jìn)去。
找尾節(jié)點(diǎn)時(shí),while里的循環(huán)條件要寫成 tail->next !=NULL??
請看邏輯結(jié)構(gòu):
申請新節(jié)點(diǎn) BuySListNode
SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode->data = x; //x是要插入的數(shù)據(jù)newnode->next = NULL;return newnode;
}
尾插 SListpushback
?
void SListpushback(SLNode** pphead,SLdatatype x) //注意傳的是二級(jí)指針
{SLNode* newnode = BuySListNode(x);if (*pphead == NULL) //判斷鏈表是否為空{(diào)*pphead = newnode;}else{SLNode* tail = *pphead; //尋找尾節(jié)點(diǎn)while (tail->next != NULL) //注意這里不能寫成 while(tail!=NULL){tail = tail->next;}tail->next = newnode;}
}
2.頭插? SListpushfront
頭插時(shí)只需讓新節(jié)點(diǎn)的 next 指向舊的頭節(jié)點(diǎn),然后再把 newnode 賦給頭節(jié)點(diǎn),使之成為新的頭節(jié)點(diǎn),即使是空表也沒關(guān)系,newnode 會(huì)直接成為頭節(jié)點(diǎn)。
?
void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}
五.刪除
1.尾刪? SListpopback
尾刪前,我們需要判斷:
1.若為空表,則直接結(jié)束函數(shù);
2.若鏈表中只有一個(gè)節(jié)點(diǎn),則直接 free 頭節(jié)點(diǎn),然后置為NULL;
3.尋找尾節(jié)點(diǎn) tail 和尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) pre ,因?yàn)槲覀冡尫诺粑补?jié)點(diǎn)后,pre就成為了新的尾節(jié)點(diǎn),而尾節(jié)點(diǎn)的 next 是 NULL ,所以我們需要找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
找尾的方法和之前的一樣。
void SListpopback(SLNode** pphead)
{if (*pphead == NULL){return;}else if ((*pphead)->next == NULL) //注意這里因?yàn)閮?yōu)先級(jí)的問題,*pphead 要打括號(hào){free(*pphead);*pphead = NULL;}else{SLNode* pre = NULL;SLNode* tail = *pphead;while (tail->next != NULL){pre = tail; //記錄 tail 的前一個(gè)節(jié)點(diǎn)tail = tail->next;}pre->next = NULL; //next 置為NULL}
}
2.頭刪? SListpopfront
在頭刪前:
1.判斷是否為空表;
2.定義一個(gè) next 用來保存頭節(jié)點(diǎn)中的 next? ,釋放完后,這個(gè) next 就成為了新的頭節(jié)點(diǎn)。
void SListpopfront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}
六.查找? 插入? 釋放? ?打印
1.查找? ?SListfind
在插入和釋放前,都需要調(diào)用 find 函數(shù),來找到希望插入或是釋放的位置。
SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}
}
2.插入? SListinsert
如果是鏈表中只有一個(gè)節(jié)點(diǎn),就變成了頭插,只需要調(diào)用頭插函數(shù)就行了,如果是空表也不用擔(dān)心,可以設(shè)置成不調(diào)用函數(shù);
在插入前,需要找到指定位置 pos 的前驅(qū) pre,
使pre->next=newnode? , newnode->next=pos
如圖所示,假設(shè)在3的前一個(gè)位置插入數(shù)據(jù):
?
void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (pos->next == NULL){SListpushfront(pphead, x);}else{SLNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = newnode;newnode->next = pos;}
}
3.釋放? SListerase
釋放前:
1.如果只有一個(gè)節(jié)點(diǎn),則直接釋放頭節(jié)點(diǎn),再置為空即可;
2.如果不止一個(gè)節(jié)點(diǎn),還需找到要釋放的位置的前一個(gè)節(jié)點(diǎn) pre ,將 pre 的 next 指向 pos 的next,然后再釋放;
如圖所示,假設(shè)要釋放掉3這個(gè)節(jié)點(diǎn):
?
void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = *pphead;while (pre->next !=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}
4.打印? SListprint
雖然可以直接用頭節(jié)點(diǎn) phead 遍歷,但博主還是推薦定義一個(gè)新的結(jié)構(gòu)體指針? cur? ,把phead 的值賦給 cur ,會(huì)顯得更優(yōu)雅;
注意這里的 while 里的式子要寫成? cur? ,如果 寫成 cur->next ,那么最終打印出來的結(jié)果會(huì)少一個(gè)節(jié)點(diǎn)的數(shù)據(jù)。
void SListprint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
七.源碼
1.SList.h
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLdatatype;typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;void SListprint(SLNode* phead); //打印void SListpushback(SLNode** pphead,SLdatatype x); //尾插void SListpushfront(SLNode** pphead, SLdatatype x); //頭插void SListpopfront(SLNode** pphead); //頭刪void SListpopback(SLNode** pphead); //尾刪SLNode* SListfind(SLNode* phead,SLdatatype x); //查找void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x); //插入void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x); //釋放
2.SList.c
#define _CRT_SECURE_NO_WARNINGS#include "SList.h"void SListprint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}void SListpushback(SLNode** pphead,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tail = *pphead; //尋找尾節(jié)點(diǎn)while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListpopfront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}void SListpopback(SLNode** pphead)
{if (*pphead == NULL){return;}else if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = NULL;SLNode* tail = *pphead;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;}
}SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}
}void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (pos->next == NULL){SListpushfront(pphead, x);}else{SLNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = newnode;newnode->next = pos;}
}void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = *pphead;while (pre->next !=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}
3.test.c
博主寫的主函數(shù)只是用來測試單鏈表的,寫起主函數(shù)來也不難,大家可以自行編寫。
#include "SList.h"void testSList1()
{SLNode* plist = NULL;SListpushback(&plist,1);SListpushback(&plist,2);SListpushback(&plist,3);SListpushback(&plist,4);SListprint(plist);SListpushfront(&plist, 0);SListprint(plist);SListpopfront(&plist);SListpopfront(&plist);SListpopfront(&plist);SListprint(plist);SListpopback(&plist);SListpopback(&plist);SListpopback(&plist);SListprint(plist);
}void testSList2()
{SLNode* plist = NULL;SListpushback(&plist, 1);SListpushback(&plist, 2);SListpushback(&plist, 3);SListpushback(&plist, 4);SLNode* pos = SListfind(plist, 3);if (pos){SListinsert(&plist,pos, 20);SListprint(plist);}pos = SListfind(plist, 2);if (pos){SListerase(&plist,pos,2);SListprint(plist);}}int main()
{//testSList1();testSList2();return 0;
}
八.單鏈表的一些問題
在單鏈表中,要想找到某一個(gè)數(shù)據(jù),就需要從頭節(jié)點(diǎn)開始,所以單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu),且要想對單鏈表進(jìn)行一些操作,總是要找到前驅(qū)節(jié)點(diǎn),有時(shí)還需判斷一些特殊情況,有什么辦法能解決這些問題呢?
博主將在下篇雙向帶頭循環(huán)鏈表中講解,敬情期待~
🤩🥰本篇文章到此就結(jié)束了,如有錯(cuò)誤或是建議,歡迎小伙伴們提出~😍😃
🐲👻希望可以多多支持博主哦~🥰😍
🤖🐯謝謝你的閱讀~👻🦁
?