前言
引入鏈表：順序表的問題及思考與討論
優(yōu)勢：
- 可通過 下標(biāo)i （數(shù)據(jù)連續(xù)（物理空間連續(xù)）） 便捷查詢查找順序表中的信息，也會在后面的 排序算法 和 堆算法 中盡顯身手
問題：
在頭部/中間的插入與刪除需要挪動數(shù)據(jù)，時間復(fù)雜度為O(N)，效率低；
增容需要申請新空間，可能會拷貝數(shù)據(jù)，釋放舊空間，會有不小的消耗；
增容一般是呈 1.5倍 或 2倍的增長，勢必會有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到 200，如果我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么會浪費(fèi)95個數(shù)據(jù)空間；
正因順序表的這些不足，我們設(shè)計(jì)出了鏈表。
一、鏈表
1、鏈表的概念及結(jié)構(gòu)
1.1 概念
- 鏈表 是一種 物理存儲結(jié)構(gòu) 上 非連續(xù)、非順序 的存儲結(jié)構(gòu)，
- 數(shù)據(jù)元素的邏輯順序是通過 鏈表中的 指針鏈接 次序 實(shí)現(xiàn)的 。
[注： 所謂的邏輯結(jié)構(gòu)指的是數(shù)據(jù)在邏輯上是如何存儲的，這是由人們主觀想象出來的；而物理結(jié)構(gòu)則是數(shù)據(jù)在物理內(nèi)存中實(shí)際存儲的方式，不隨人們的主觀意志而改變。]
帶大家感受一下鏈表；
鏈表就如同圖中的火車：
plist = 火車頭，指向第一個節(jié)點(diǎn)
每個節(jié)點(diǎn) = 每一節(jié)的火車車廂
每一節(jié)點(diǎn)中存儲的下一節(jié)點(diǎn)的指針 =火車車廂之間的鏈接
實(shí)際上鏈表的每一個節(jié)點(diǎn)都是在堆區(qū)上隨機(jī)申請的，前一個節(jié)點(diǎn)的地址可能比后一個節(jié)點(diǎn)大，也可能比后一個節(jié)點(diǎn)小，二者之前其實(shí)并沒有物理結(jié)構(gòu)上的關(guān)系。
鏈表的結(jié)構(gòu)也可以這樣
★☆★ 總結(jié)
注意：
- 從上圖可看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)
- 現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請出來的 （malloc）
- 從堆上申請的空間，是按照一定的策路來分配的，兩次申清的空同可能連續(xù)，也可能不連續(xù)
鏈表和順序表的 不同之處 在于：
順序表不僅要求邏輯結(jié)構(gòu)上連續(xù)，還要求物理結(jié)構(gòu)上也連續(xù)；而鏈表 只要求邏輯結(jié)構(gòu)上連續(xù)，物理結(jié)構(gòu)上可以不連續(xù)；正因?yàn)殒湵硎怯?指針 相連的特性。
2、鏈表的分類
-
單向/雙向
雙向鏈表對比單向鏈表來說，其結(jié)構(gòu)體中會多一個結(jié)構(gòu)體指針變量，用來指向前一個節(jié)點(diǎn)的地址。
-
帶頭/不帶頭
帶頭（哨兵位）最開始的時候會有一個節(jié)點(diǎn)，這個節(jié)點(diǎn)不用來存儲數(shù)據(jù)，僅僅作為鏈表的頭部使用，還是一個節(jié)點(diǎn)都沒有。
-
循環(huán)/不循環(huán)
非循環(huán)鏈表的最后一個節(jié)點(diǎn)的next指向NULL，而循環(huán)鏈表的最后一個節(jié)點(diǎn)的next指向鏈表的第一個節(jié)點(diǎn)。
3. 最常用的兩種鏈表
雖然鏈表有這么多中結(jié)構(gòu)，但是我們實(shí)際中最常用還是以下兩種結(jié)構(gòu)：無頭單向非循環(huán)鏈表 和 雙向帶頭循環(huán)鏈表。
（1）無頭單向非循環(huán)鏈表
結(jié)構(gòu)簡單，一般不會單獨(dú)用來存數(shù)據(jù)，實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等；另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多；其實(shí)如果不做特殊聲明，一般情況下無頭單向非循環(huán)鏈表指的就是我們的單鏈表；
（2）帶頭雙向循環(huán)鏈表
結(jié)構(gòu)最復(fù)雜，一般用于單獨(dú)存儲數(shù)據(jù)；實(shí)際中我們使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表；另外它雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)后會有發(fā)現(xiàn)結(jié)構(gòu)會帶來多優(yōu)勢，所以反而是鏈表中使用起來最簡單的。
二、單鏈表的實(shí)現(xiàn)
由于單鏈表是其他結(jié)構(gòu)鏈表學(xué)習(xí)的基礎(chǔ)，且經(jīng)常被用做其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，在筆試題中也最常被考到，所以下面我們用C語言來手動實(shí)現(xiàn)一個單鏈表，以此來加深我們對單鏈表的理解。
（一）創(chuàng)建文件
- slist.h （單鏈表的類型定義、接口函數(shù)聲明、引用的頭文件)
- slist.c （單鏈表接口函數(shù)的實(shí)現(xiàn)）
- test.c （主函數(shù)、測試順序表各個接口功能）
（二）slist.h
1、結(jié)構(gòu)體類型聲明
//類型聲明
typedef int SLTDateType; //數(shù)據(jù)類型重命名
typedef struct SListNode { //結(jié)構(gòu)體類型聲明
SLTDateType data;
struct SListNode* next; //結(jié)構(gòu)體指針-存放下一節(jié)點(diǎn)（結(jié)構(gòu)體）的地址
}SListNode;
（三）slist.c
注解都標(biāo)注在代碼旁邊，方便大家邊看代碼邊理解
2、動態(tài)創(chuàng)建新節(jié)點(diǎn)
//動態(tài)創(chuàng)建新節(jié)點(diǎn)
SListNode* BuySListNode(SLTDateType x) {
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
assert(malloc); //避免malloc失敗返回的空指針NULL，并及時報(bào)錯
newNode->data = x;
newNode->next = NULL;
return newNode;
}
3、在頭部插入數(shù)據(jù)
//單鏈表的頭插
void SListPushFront(SListNode** pphead, SLTDateType x) {
assert(pphead); //確保傳過來的不是空指針
SListNode* newNode = BuySListNode(x); //指針變量中存放的是指針（地址）
//鏈表為空 直接存放newNode的地址 在 解引用頭指針處得到的內(nèi)容處 //圖解
if (*pphead == NULL) {
*pphead = newNode;
return;
}
//鏈表不為空 //圖解
SListNode* temp = *pphead; //先將頭指針中 所指向的節(jié)點(diǎn)地址，先暫時保存
*pphead = newNode; //把新節(jié)點(diǎn)地址存入頭指針中，形成新連接
newNode->next = temp; //在把暫存的原后鏈接的地址，放入到新節(jié)點(diǎn)newNode中的 結(jié)構(gòu)體指針中，
//再形成新的后鏈接
}
4、在尾部插入數(shù)據(jù)
//單鏈表的尾插
void SListPushBack(SListNode** pphead, SLTDateType x) {
assert(pphead); //確保傳過來的不是空指針
SListNode* newNode = BuySListNode(x); //指針變量中存放的是指針（地址）
//鏈表為空 直接存放newNode的地址 在 解引用頭指針處得到的內(nèi)容處 //圖解
if (*pphead == NULL) {
*pphead = newNode;
return;
}
//鏈表不為空 我們需要找到鏈尾
SListNode* tail = *pphead; //創(chuàng)建個結(jié)構(gòu)體指針遍歷鏈表，
while (tail->next != NULL) {
tail = tail->next;
} //找到最后為空的結(jié)構(gòu)體，將其newNode地址插入該末尾結(jié)構(gòu)體
tail->next = newNode;
}
5、查找數(shù)據(jù)
// 查找數(shù)據(jù)——單鏈表查找
SListNode* SListFind(SListNode* pphead, SListDateType x) {
assert(pphead);
SListNode* cur = pphead;
while (cur != NULL) {
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
6、在pos位置前插入數(shù)據(jù)
//在pos位置前插入數(shù)據(jù)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead) //如果pos等于*pphead，相當(dāng)于頭插
{
SListPushFront(pphead, x);
return;
}
SListNode* newNode = BuySLTNode(x);
//找到pos位置的前一個節(jié)點(diǎn)
SListNode* prev = *pphead;
while (prev->next != pos)
{
assert(prev); //如果prev為空循環(huán)還沒停止，說明在鏈表中找不到pos，直接報(bào)錯
prev = prev->next;
}
prev->next = newNode;
newNode->next = pos;
}
7、在pos位置后插入數(shù)據(jù)
思考：為什么不在pos位置之前插入？
由于單鏈表在某一節(jié)點(diǎn)的前面插入數(shù)據(jù)時需要從頭遍歷尋找該節(jié)點(diǎn)的前一個節(jié)點(diǎn)， 導(dǎo)致時間復(fù)雜度為O(N)，
所以人們?yōu)榱颂岣邌捂湵淼男剩瑸閱捂湵韱为?dú)設(shè)計(jì)了在pos位置后插入數(shù)據(jù)的函數(shù)；除了單鏈表，其他數(shù)據(jù)結(jié)構(gòu)插入數(shù)據(jù)都是在前面插入。
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x) {
assert(pos);
SListNode* next = pos->next;
SListNode* newNode = BuySListNode(x);
newNode->next = next;
pos->next = newNode;
}
8、在頭部刪除數(shù)據(jù)
// 單鏈表頭刪
void SListPopFront(SListNode** pphead) {
SListNode* temp = *pphead;
if (temp == NULL) { //先判斷鏈表中是否還有數(shù)據(jù)可被刪除
printf("鏈表中無數(shù)據(jù)可刪除\n");
return;
}
*pphead = temp->next; //圖解
free(temp); //用個臨時變量 記住要free掉的節(jié)點(diǎn)的地址
temp = NULL; //記住后就可以放心大膽的將其后一個節(jié)點(diǎn)的地址傳給頭指針中，
//這樣就不怕要free掉的節(jié)點(diǎn)的地址被覆蓋而找不到該地址
}
9、在尾部刪除數(shù)據(jù)
// 單鏈表的尾刪
void SListPopBack(SListNode** pphead) {
SListNode* temp = *pphead; //由于后面還會用到頭指針中所存儲的下一節(jié)點(diǎn)的地址，
//所以干脆直接解引用拿出得到頭指針中所存儲的下一節(jié)點(diǎn)的地址，并用SListNode*保存
//（而不是SListNode** temp存儲pphead的地址，
//后面還要解引用*temp才能得到pphead中存儲的（頭指針中所存儲的下一節(jié)點(diǎn)的地址，
//*temp雖說也是指針，但 `*temp->` 這樣的格式編譯器是不允許的不成立的））
// =>所以還是直接解引用的好
if (temp == NULL) { //先判斷鏈表中是否還有數(shù)據(jù)可被刪除
printf("鏈表中無數(shù)據(jù)可刪除\n");
return;
}
while (temp->next->next != NULL) { //要刪除最后一個節(jié)點(diǎn)，當(dāng)然要找到的是它前一個節(jié)點(diǎn)的地址
// [ 因?yàn)榍耙粋€節(jié)點(diǎn)的結(jié)構(gòu)體中存有最后一個節(jié)點(diǎn)結(jié)構(gòu)體的地址 ]（沒有前一個節(jié)點(diǎn)的地址根本無法找到）
temp = temp->next; //當(dāng)然沒有前一個節(jié)點(diǎn)，最后那個節(jié)點(diǎn)遍歷到temp->next=NULL，
//temp也能遍歷到最后那個節(jié)點(diǎn)的地址，并將其free掉，但前一個地址的next也要重新設(shè)為空指針NULL，
//（就算再遍歷一遍鏈表，結(jié)尾不為NULL，也再也找不到現(xiàn)在的最后一個節(jié)點(diǎn)了
//（因?yàn)闊o法讓遍歷碰到現(xiàn)在的新最后一個節(jié)點(diǎn)停下），
//那么也將無法刪除最后一個節(jié)點(diǎn)后 的新的最后一個節(jié)點(diǎn)中的next置為NULL）
}
SListNode* temp1 = temp->next; //free掉最后一個節(jié)點(diǎn)
free(temp1);
temp1 = NULL; //記得要置回NULL空指針，避免變成野指針，很危險(xiǎn)
temp->next = NULL; //將前一個節(jié)點(diǎn)的指針置為NULL
}
10、刪除pos位置前的數(shù)據(jù)
//刪除pos位置前的數(shù)據(jù)
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead && pos);
assert(*pphead); //當(dāng)鏈表為空時，刪除元素報(bào)錯
if (pos == *pphead) //pos等于*pphead時相當(dāng)于頭刪
{
SListPopFront(pphead);
return;
}
//找到pos的前一個節(jié)點(diǎn)
SListNode* prev = *pphead;
while (prev->next != pos)
{
assert(prev); //如果prev為空循環(huán)還沒停止，說明在鏈表中找不到pos，直接報(bào)錯
prev = prev->next;
}
SListNode* tmp = pos->next;
prev->next = tmp;
free(pos);
pos = NULL;
}
11、刪除pos位置后的數(shù)據(jù)
思考：為什么不刪除pos位置？文章來源：http://www.zghlxwxcb.cn/news/detail-742852.html
和在pos位置后插入數(shù)據(jù)一樣，為了提高效率，人們也設(shè)計(jì)了一個在pos位置后刪除數(shù)據(jù)的函數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-742852.html
// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos) {
assert(pos); //確保指針不為空
if (pos->next != NULL) {
SListNode* next = pos->next->next;
SListNode* temp = pos->next;
free(temp);
temp = NULL;
pos->next = next;
}
}
12、修改pos位置處的數(shù)據(jù)
//修改pos位置處的數(shù)據(jù)
void SListModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
assert(phead && pos);
SListNode* cur = phead;
while (cur != pos)
{
assert(cur); //如果cur為空循環(huán)還沒停止，說明在鏈表中找不到pos，直接報(bào)錯
cur = cur->next;
}
cur->data = x;
}
13、打印鏈表中的數(shù)據(jù)
//打印鏈表 遞歸實(shí)現(xiàn)
void SListPrint(SListNode* pList) {
printf("%d ", pList->data);
SListPrint(pList->next);
}
14、銷毀鏈表
// 單鏈表的銷毀
void SListDestroy(SListNode* pphead) { //pphead的內(nèi)存空間也要銷毀
assert(pphead);
SListNode* cur = pphead;
while (cur != NULL) {
SListNode* temp = cur->next; //用個臨時變量先存著后一個節(jié)點(diǎn)的地址,
//以免free掉現(xiàn)在的地址后，找不到后面的地址了
free(cur);
cur = temp; //再重新找回來
}
}
三、完整代碼
1、SList.h
#pragma once //防止頭文件重復(fù)包含
//頭文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//類型聲明
typedef int SLTDateType; //數(shù)據(jù)類型重命名
typedef struct SListNode { //結(jié)構(gòu)體類型聲明
SLTDateType data;
struct SListNode* next; //結(jié)構(gòu)體指針-存放下一節(jié)點(diǎn)（結(jié)構(gòu)體）的地址
}SListNode;
//函數(shù)聲明
//創(chuàng)建新建節(jié)點(diǎn)
SListNode* BuySLTNode(SLTDateType x);
//在頭部插入數(shù)據(jù)
void SListPushFront(SListNode** pphead, SLTDateType x);
//銷毀鏈表
void SListDestory(SListNode** pphead);
//在尾部插入數(shù)據(jù)
void SListPushBack(SListNode** pphead, SLTDateType x);
//查找數(shù)據(jù)
SListNode* SListFind(SListNode* phead, SLTDateType x);
//在pos之前插入數(shù)據(jù)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
//在pos之后插入數(shù)據(jù)
void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDateType x);
//打印鏈表
void SListPrint(SListNode* phead);
//在頭部刪除數(shù)據(jù)
void SListPopFront(SListNode** pphead);
//在尾部刪除數(shù)據(jù)
void SListPopBack(SListNode** pphead);
//刪除pos位置處的數(shù)據(jù)
void SListErase(SListNode** pphead, SListNode* pos);
//刪除pos位置后的數(shù)據(jù)
void SListEraseAfter(SListNode** pphead, SListNode* pos);
//修改pos位置處的函數(shù)
void SListModify(SListNode* phead, SListNode* pos, SLTDateType x);
2、SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"slist.h"
//動態(tài)創(chuàng)建新節(jié)點(diǎn)
SListNode* BuySListNode(SLTDateType x) {
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
assert(malloc); //避免malloc失敗返回的空指針NULL，并及時報(bào)錯
newNode->data = x;
newNode->next = NULL;
return newNode;
}
// 單鏈表的頭插
void SListPushFront(SListNode** pphead, SLTDateType x) {
assert(pphead); //確保傳過來的不是空指針
SListNode* newNode = BuySListNode(x); //指針變量中存放的是指針（地址）
//鏈表為空 直接存放newNode的地址 在 解引用頭指針處得到的內(nèi)容處 //圖解
if (*pphead == NULL) {
*pphead = newNode;
return;
}
//鏈表不為空 //圖解
SListNode* temp = *pphead; //先將頭指針中 所指向的節(jié)點(diǎn)地址，先暫時保存
*pphead = newNode; //把新節(jié)點(diǎn)地址存入頭指針中，形成新連接
newNode->next = temp; //在把暫存的原后鏈接的地址，放入到新節(jié)點(diǎn)newNode中的 結(jié)構(gòu)體指針中，
//再形成新的后鏈接
}
//單鏈表的尾插
void SListPushBack(SListNode** pphead, SLTDateType x) {
assert(pphead); //確保傳過來的不是空指針
SListNode* newNode = BuySListNode(x); //指針變量中存放的是指針（地址）
//鏈表為空 直接存放newNode的地址 在 解引用頭指針處得到的內(nèi)容處 //圖解
if (*pphead == NULL) {
*pphead = newNode;
return;
}
//鏈表不為空 我們需要找到鏈尾
SListNode* tail = *pphead; //創(chuàng)建個結(jié)構(gòu)體指針遍歷鏈表，
while (tail->next != NULL) {
tail = tail->next; //找到最后為空的結(jié)構(gòu)體，將其newNode地址插入該末尾結(jié)構(gòu)體
}
tail->next = newNode;
}
// 查找數(shù)據(jù)——單鏈表查找
SListNode* SListFind(SListNode* pphead, SLTDateType x) {
assert(pphead);
SListNode* cur = pphead;
while (cur != NULL) {
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入？
//
// 由于單鏈表在某一節(jié)點(diǎn)的前面插入數(shù)據(jù)時需要從頭遍歷尋找該節(jié)點(diǎn)的前一個節(jié)點(diǎn)，
// 導(dǎo)致時間復(fù)雜度為O(N)，所以人們?yōu)榱颂岣邌捂湵淼男剩?/span>
// 為單鏈表單獨(dú)設(shè)計(jì)了在pos位置后插入數(shù)據(jù)的函數(shù)；
// 除了單鏈表，其他數(shù)據(jù)結(jié)構(gòu)插入數(shù)據(jù)都是在前面插入。
void SListInsertAfter(SListNode* pos, SLTDateType x) {
assert(pos);
SListNode* next = pos->next;
SListNode* newNode = BuySListNode(x);
newNode->next = next;
pos->next = newNode;
}
//在pos位置前插入數(shù)據(jù)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead) //如果pos等于*pphead，相當(dāng)于頭插
{
SListPushFront(pphead, x);
return;
}
SListNode* newNode = BuySLTNode(x);
//找到pos位置的前一個節(jié)點(diǎn)
SListNode* prev = *pphead;
while (prev->next != pos)
{
assert(prev); //如果prev為空循環(huán)還沒停止，說明在鏈表中找不到pos，直接報(bào)錯
prev = prev->next;
}
prev->next = newNode;
newNode->next = pos;
}
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？ //和在pos位置后插入數(shù)據(jù)一樣，為了提高效率，人們也設(shè)計(jì)了一個在pos位置后刪除數(shù)據(jù)的函數(shù)。
void SListEraseAfter(SListNode* pos) {
assert(pos); //確保指針不為空
if (pos->next != NULL) {
SListNode* next = pos->next->next;
SListNode* temp = pos->next;
free(temp);
temp = NULL;
pos->next = next;
}
}
//修改pos位置處的數(shù)據(jù)
void SListModify(SListNode* phead, SListNode* pos, SLTDateType x)
{
assert(phead && pos);
SListNode* cur = phead;
while (cur != pos)
{
assert(cur); //如果cur為空循環(huán)還沒停止，說明在鏈表中找不到pos，直接報(bào)錯
cur = cur->next;
}
cur->data = x;
}
// 單鏈表頭刪
void SListPopFront(SListNode** pphead) {
SListNode* temp = *pphead;
if (temp == NULL) { //先判斷鏈表中是否還有數(shù)據(jù)可被刪除
printf("鏈表中無數(shù)據(jù)可刪除\n");
return;
}
*pphead = temp->next; //圖解
free(temp); //用個臨時變量 記住要free掉的節(jié)點(diǎn)的地址
temp = NULL; //記住后就可以放心大膽的將其后一個節(jié)點(diǎn)的地址傳給頭指針中，
//這樣就不怕要free掉的節(jié)點(diǎn)的地址被覆蓋而找不到該地址
}
// 單鏈表的尾刪
void SListPopBack(SListNode** pphead) {
SListNode* temp = *pphead; //由于后面還會用到頭指針中所存儲的下一節(jié)點(diǎn)的地址，
//所以干脆直接解引用拿出得到頭指針中所存儲的下一節(jié)點(diǎn)的地址，并用SListNode*保存
//（而不是SListNode** temp存儲pphead的地址，
//后面還要解引用*temp才能得到pphead中存儲的（頭指針中所存儲的下一節(jié)點(diǎn)的地址，
//*temp雖說也是指針，但 `*temp->` 這樣的格式編譯器是不允許的不成立的））
// =>所以還是直接解引用的好
if (temp == NULL) { //先判斷鏈表中是否還有數(shù)據(jù)可被刪除
printf("鏈表中無數(shù)據(jù)可刪除\n");
return;
}
while (temp->next->next != NULL) { //要刪除最后一個節(jié)點(diǎn)，當(dāng)然要找到的是它前一個節(jié)點(diǎn)的地址
// [ 因?yàn)榍耙粋€節(jié)點(diǎn)的結(jié)構(gòu)體中存有最后一個節(jié)點(diǎn)結(jié)構(gòu)體的地址 ]（沒有前一個節(jié)點(diǎn)的地址根本無法找到）
temp = temp->next; //當(dāng)然沒有前一個節(jié)點(diǎn)，最后那個節(jié)點(diǎn)遍歷到temp->next=NULL，
//temp也能遍歷到最后那個節(jié)點(diǎn)的地址，并將其free掉，但前一個地址的next也要重新設(shè)為空指針NULL，
//（就算再遍歷一遍鏈表，結(jié)尾不為NULL，也再也找不到現(xiàn)在的最后一個節(jié)點(diǎn)了
//（因?yàn)闊o法讓遍歷碰到現(xiàn)在的新最后一個節(jié)點(diǎn)停下），
//那么也將無法刪除最后一個節(jié)點(diǎn)后 的新的最后一個節(jié)點(diǎn)中的next置為NULL）
}
SListNode* temp1 = temp->next; //free掉最后一個節(jié)點(diǎn)
free(temp1);
temp1 = NULL; //記得要置回NULL空指針，避免變成野指針，很危險(xiǎn)
temp->next = NULL; //將前一個節(jié)點(diǎn)的指針置為NULL
}
//打印鏈表 遞歸實(shí)現(xiàn)
void SListPrint(SListNode* pList) {
printf("%d ", pList->data);
SListPrint(pList->next);
}
// 單鏈表的銷毀
void SListDestroy(SListNode* pphead) { //pphead的內(nèi)存空間也要銷毀
assert(pphead);
SListNode* cur = pphead;
while (cur != NULL) {
SListNode* temp = cur->next; //用個臨時變量先存著后一個節(jié)點(diǎn)的地址,
//以免free掉現(xiàn)在的地址后，找不到后面的地址了
free(cur);
cur = temp; //再重新找回來
}
}
int main() {
test1();
//test2（）
//test3（）
return 0;
}
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void test1() //測試插入
{
SListNode* plist = NULL; //指向鏈表第一個節(jié)點(diǎn)的指針，因?yàn)殒湵頉]有節(jié)點(diǎn)，所以初始化為NULL；
//頭插
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPrint(plist);
//尾插
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);
SListPushBack(&plist, 6);
SListPrint(plist);
//在pos位置前插入
SListNode* pos = SListFind(plist, 5);
if (pos != NULL)
{
SListInsert(&plist, pos, 50);
}
pos = SListFind(plist, 3);
if (pos != NULL)
{
SListInsert(&plist, pos, 30);
}
SListPrint(plist);
pos = SListFind(plist, 6);
if (pos != NULL)
{
SListInsert(&plist, pos, 60);
}
SListPrint(plist);
//在pos位置后插入
pos = SListFind(plist, 1);
if (pos != NULL)
{
SListInsertAfter(&plist, pos, 10);
}
pos = SListFind(plist, 3);
if (pos != NULL)
{
SListInsertAfter(&plist, pos, 30);
}
SListPrint(plist);
//銷毀
SListDestory(&plist);
}
void test2() //測試刪除
{
SListNode* plist = NULL; //指向鏈表第一個節(jié)點(diǎn)的指針，因?yàn)殒湵頉]有節(jié)點(diǎn)，所以初始化為NULL；
//頭插
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPrint(plist);
//在頭部刪除數(shù)據(jù)
//SListPopFront(&plist);
//SListPopFront(&plist);
//SListPopFront(&plist);
//SListPrint(plist);
//在尾部刪除數(shù)據(jù)
//SListPopBack(&plist);
//SListPopBack(&plist);
//SListPopBack(&plist);
//SListPrint(plist);
//刪除pos位置處的數(shù)據(jù)
//SLTNode* pos = SListFind(plist, 1);
//if (pos != NULL)
//{
// SListErase(&plist, pos);
//}
//pos = SListFind(plist, 3);
//if (pos != NULL)
//{
// SListErase(&plist, pos);
//}
//SListPrint(plist);
//pos = SListFind(plist, 2);
//if (pos != NULL)
//{
// SListErase(&plist, pos);
//}
//SListPrint(plist);
//刪除pos位置后的數(shù)據(jù)
SListNode* pos = SListFind(plist, 2);
if (pos != NULL)
{
SListEraseAfter(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 3);
if (pos != NULL)
{
SListEraseAfter(&plist, pos);
}
SListPrint(plist);
//銷毀
SListDestory(&plist);
}
void test3() //測試查和改
{
SListNode* plist = NULL; //指向鏈表第一個節(jié)點(diǎn)的指針，因?yàn)殒湵頉]有節(jié)點(diǎn)，所以初始化為NULL；
//頭插
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPrint(plist);
//查找并修改pos位置處的數(shù)據(jù)
SListNode* pos = SListFind(plist, 3);
if (pos != NULL)
{
SListModify(plist, pos, 30);
}
SListPrint(plist);
pos = SListFind(plist, 1);
if (pos != NULL)
{
SListModify(plist, pos, 10);
}
SListPrint(plist);
//銷毀
SListDestory(&plist);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】單鏈表的增刪查改（C實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
