目錄
1.什么是鏈表。
2.鏈表的優(yōu)點(diǎn)
3.單鏈表的實(shí)現(xiàn)
1.單鏈表的結(jié)構(gòu)體
2.節(jié)點(diǎn)的創(chuàng)建
3.參數(shù)的調(diào)用
4.頭插
?5.尾插
7.頭刪
8.尾刪
8.在pos節(jié)點(diǎn)前插入x
9.在pos節(jié)點(diǎn)前插入x
10.刪除pos位置節(jié)點(diǎn)?
對(duì)于順序表我們發(fā)現(xiàn)，在此基礎(chǔ)上仍存在了些許不足：
1.中間或頭部的插入時(shí)間復(fù)雜度為O(n)，有點(diǎn)浪費(fèi)時(shí)間。
2.增容需要申請(qǐng)空間，拷貝數(shù)據(jù)，釋放空間，會(huì)有不小的消耗。
3.增容一般是呈2倍增容的，勢(shì)必會(huì)造成空間浪費(fèi)。
如何解決以上問題，我們又了解到了一種新的數(shù)據(jù)結(jié)構(gòu)-“鏈表”
1.什么是鏈表。
鏈表顧名思義，由一條鏈子連接表中各成員。實(shí)則鏈表是由每一塊獨(dú)立的空間組成，每一個(gè)空間里存放著數(shù)據(jù)和一個(gè)指針，每一個(gè)指針指向下一塊空間的地址，依次指向，我們可以想象成為用鏈條串聯(lián)起類，故叫鏈表，鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)，非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈次序?qū)崿F(xiàn)的。
就像火車一樣
我們一般將這一塊空間稱為一個(gè)節(jié)點(diǎn)，鏈表的末尾節(jié)點(diǎn)的指針是空指針。
2.鏈表的優(yōu)點(diǎn)
相較于順序表：
1.因?yàn)殒湵硎怯梢粔K塊空間構(gòu)成，所以鏈表不存在容量不夠要擴(kuò)容的問題
2.根據(jù)需求申請(qǐng)釋放空間
3.較好地解決了在頭部或中間插入刪除挪動(dòng)數(shù)據(jù)的問題
3.單鏈表的實(shí)現(xiàn)
這里還是以存放整形數(shù)據(jù)為例：
1.單鏈表的結(jié)構(gòu)體
如何來實(shí)現(xiàn)這樣的結(jié)構(gòu)呢？
typedef int SLdatatype;
typedef struct seqlist
{
SLdatatype data;
struct seqlist* next;
}SLnode;可以看到這里的結(jié)構(gòu)體里存放了本結(jié)構(gòu)體的指針，每一個(gè)結(jié)構(gòu)體里都有一個(gè)自身的指針，而這個(gè)自身的指針就代表下一個(gè)結(jié)構(gòu)體的首地址，依次下去，直至到末尾next尾空。
用單鏈表的話來說，就是每一個(gè)節(jié)點(diǎn)存放著指向下一個(gè)節(jié)點(diǎn)地址的指針，故此我們可以創(chuàng)建所需的節(jié)點(diǎn)個(gè)數(shù)存放數(shù)據(jù)，用指針連接起來。
2.節(jié)點(diǎn)的創(chuàng)建
SLnode* SLcreatnode(SLdatatype x)
{
SLnode* newnode = (SLnode*)malloc(sizeof(SLnode));
if (newnode == NULL)
{
perror("開辟錯(cuò)誤\n");
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}每創(chuàng)建一個(gè)節(jié)點(diǎn)，就是在堆區(qū)申請(qǐng)一塊空間用來存放數(shù)據(jù)，利用malloc開辟該結(jié)構(gòu)體大小的空間，之后返回該節(jié)點(diǎn)，也就是這片空間。
3.參數(shù)的調(diào)用
這里強(qiáng)調(diào)下參數(shù)，因?yàn)槲覀冃枰淖冩湵?，定義鏈表變量的時(shí)候是指針，函數(shù)的參數(shù)應(yīng)設(shè)計(jì)為二級(jí)指針。
對(duì)于一個(gè)函數(shù)我們?cè)谄渲卸x的變量生命周期只在該作用域中，出了作用域就會(huì)被銷毀，而有的函數(shù)需要去改變實(shí)參，只是簡(jiǎn)單的改變形參，是不會(huì)影響實(shí)參的，但若為實(shí)參的地址，我們可通過解引用形參來改變實(shí)參，比如：
int swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int main()
{
int x = 10;
int y = 20;
swap(&x, &y);
printf("%d %d", x, y);
return 0;
}因此，這里要想通過形參改變實(shí)參，參數(shù)設(shè)計(jì)為二級(jí)指針：這里以頭插為例
4.頭插
void SLpushfront(SLnode** p, SLdatatype x)//傳參用二級(jí)指針
{
SLnode* newnode = SLcreatnode(x);
newnode->next = *p;
*p = newnode;
}
?可以看到頭插是先malloc一個(gè)節(jié)點(diǎn)賦值給newnode,之后在將該newnode 存放到目前的頭節(jié)點(diǎn)的next中，然后賦值給頭節(jié)點(diǎn)，即實(shí)現(xiàn)頭部插入。
?5.尾插
void SLpushback(SLnode** p, SLdatatype x)//尾插
{
SLnode* newnode = SLcreatnode(x);
//鏈表為空的話
if (*p == NULL)
{
*p = newnode;
(*p)->data = x;
}
else
{
//找尾巴(前提：鏈表不為空)
SLnode* tail = *p;
while (tail ->next!= NULL)
{
tail = tail -> next;
}
tail->next = newnode;
(*p)->data = x;
}
}尾插需要我們找到最后一個(gè)節(jié)點(diǎn)，之后先改變末尾的next，（因?yàn)楸ＷC是連接的）然后再插入。
7.頭刪
void SLpopfront(SLnode** p)//頭刪
{
assert(*p);
if ((*p) ->next== NULL)
{
free(p);
*p = NULL;
}
else
{
SLnode* top = *p;
*p = (*p) -> next;//指向下一個(gè)
free(top);
top = NULL;
}
}頭刪需要分情況
8.尾刪
void SLpopback1(SLnode** p)//尾刪
{
SLnode* pre = NULL;
SLnode* tail = *p;
while (tail->next != NULL)
{
pre = tail;//找到尾節(jié)點(diǎn)前一個(gè)
tail = tail->next;
}
free(tail);//釋放最后的空間
pre->next = NULL;//同時(shí)前一個(gè)的next為空
}或者
void SLpopback2(SLnode** p)
{
SLnode* tail = *p;
while(tail->next->next)//找倒數(shù)第二個(gè)節(jié)點(diǎn)
{
tail = tail->next;
}
free(tail->next);//釋放
tail->next = NULL;//倒數(shù)第二個(gè)next置空
}主要找到最后一個(gè)節(jié)點(diǎn)或者最后一個(gè)的前一個(gè)節(jié)點(diǎn)（這里的兩種方法），在釋放掉最后一個(gè)同時(shí)，前一個(gè)節(jié)點(diǎn)next為NULL?？梢钥吹降诙N直接釋放掉前一個(gè)的next空間，即指向最后一個(gè)結(jié)點(diǎn)的空間，在置空。
8.在pos節(jié)點(diǎn)前插入x
void SLinsert(SLnode** p, SLnode* pos, SLdatatype x)//插在pos位置前
{
SLnode* newnode = SLcreatnode(x);
if (pos == *p)
{
SLpushfront(p, x);
}
SLnode* prev=*p;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
在這里需要注意在遍歷找到pos位置前的一個(gè)節(jié)點(diǎn)時(shí)，我們都是prev->next==pos這樣去尋找，但忽略了當(dāng)頭節(jié)點(diǎn)就是pos位置時(shí)的節(jié)點(diǎn)，故在開始我們還需要判斷是否頭節(jié)點(diǎn)等于pos節(jié)點(diǎn)，如何果實(shí)就直接調(diào)用頭插文章來源：http://www.zghlxwxcb.cn/news/detail-454597.html
9.在pos節(jié)點(diǎn)前插入x
//pos節(jié)點(diǎn)后插
void SLinsertafter(SLnode** p, SLnode* pos, SLdatatype x)
{
SLnode* newnode = SLcreatnode(x);
SLnode* prev = pos->next;
pos->next = newnode;
newnode->next = prev;
}10.刪除pos位置節(jié)點(diǎn)?
void SLerase(SLnode** p, SLnode* pos)//刪除pos位置的節(jié)點(diǎn)
{
SLnode* prev = *p;
if (*p == pos)
{
SLpopfront(p);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-454597.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語(yǔ)言][數(shù)據(jù)結(jié)構(gòu)][鏈表] 單鏈表的從零實(shí)現(xiàn)!](https://imgs.yssmx.com/Uploads/2024/04/847183-1.png)
