前段時間寫了一篇關(guān)于順序表的博客，http://t.csdn.cn/0gCRp
順序表在某些時候存在著一些不可避免的缺點:
問題：1. 中間 / 頭部的插入刪除，時間復(fù)雜度為 O(N)2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。3. 增容一般是呈 2 倍的增長，勢必會有一定的空間浪費。例如當(dāng)前容量為 100 ，滿了以后增容到 200，我們再繼續(xù)插入了 5 個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了 95 個數(shù)據(jù)空間。
???????????????????????一.單鏈表的概念、結(jié)構(gòu)和優(yōu)缺點
1.1概念
1.2單鏈表的結(jié)構(gòu)
單鏈表是由一系列結(jié)點組成的線性結(jié)構(gòu)，每個結(jié)點包含兩個域：數(shù)據(jù)域和指針域。
數(shù)據(jù)域用來存儲數(shù)據(jù)，指針域用來存儲下一個結(jié)點的指針。單鏈表的頭結(jié)點指向第一個結(jié)點，最后一個結(jié)點的指針域為空。
一個結(jié)點的結(jié)構(gòu)：
?物理結(jié)構(gòu):?實際內(nèi)存中，真實的樣子。
1.3單鏈表的優(yōu)缺點
單鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，它具有以下優(yōu)缺點：
優(yōu)點：
- ????????插入和刪除操作效率高：由于單鏈表的節(jié)點包含指向下一個節(jié)點的指針，因此在插入和刪除節(jié)點時，只需要修改指針的指向，不需要移動大量的數(shù)據(jù)元素，因此效率較高。
- ????????空間利用率高：單鏈表的節(jié)點只包含數(shù)據(jù)和指針兩部分，不需要預(yù)先分配內(nèi)存空間，因此空間利用率相對較高。
- ????????長度可變：單鏈表的長度可以根據(jù)需要動態(tài)增長或縮小，不需要預(yù)先定義數(shù)組大小，具有較好的靈活性。
缺點：
- ????????隨機訪問效率低：由于單鏈表的節(jié)點只包含指向下一個節(jié)點的指針，因此無法直接訪問某個節(jié)點之前的節(jié)點，需要從頭節(jié)點開始遍歷到該節(jié)點，因此隨機訪問效率較低。
- ????????存儲空間浪費：由于單鏈表的每個節(jié)點都需要存儲下一個節(jié)點的指針，因此在存儲相同數(shù)據(jù)量的情況下，單鏈表需要更多的存儲空間。
- ????????鏈接信息的丟失：單鏈表中只有指向下一個節(jié)點的指針，無法直接訪問前一個節(jié)點，因此在需要反向遍歷鏈表或者刪除節(jié)點時，需要保存前一個節(jié)點的指針，否則將無法完成操作。
二.單鏈表的實現(xiàn)
單鏈表各接口函數(shù)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;//這樣做的目的是為了增加代碼的可讀性和可維護性，以及提高代碼的可移植性，
//因為如果將來需要更改 SLTDataType 的類型，只需要在 typedef 語句中修改一處即可，
// 如果我們在程序的其他地方需要修改 SLTDataType 的類型，
//只需在 typedef 語句中修改 int 為其他類型即可，不需要修改其他代碼。
//typedef int SLTADataType;
typedef struct SListNode //--single Linked List
{
SLTDataType data;//成員變量
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//void SLPushFront(SLTNode* pphead,SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);//頭部插入
//void SLPushBack(SLTNode* phead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾部插入
void SLPopFront(SLTNode** pphead);//頭部刪除
void SLPopBack(SLTNode** pphead);//尾部刪除
//單鏈表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//單鏈表pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//單鏈表pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//單鏈表pos位置刪除
void SLErase(SLTNode** pphead, SLTNode* pos);
//單鏈表pos之后刪除
void SLEraseAfter(SLTNode* phead);2.1結(jié)點的定義
英文簡寫:
單鏈表的英文為:Single linked list --簡寫為SL
而順序表的英文是:Sequence table -- 簡寫為Seq
結(jié)點的英文為:node
typedef的主要作用有:主要用于提高代碼的可讀性和可維護性，這樣代碼的可讀性會更好,因為SLTDataType這個名字說明了變量x的類型含義，可以為這個數(shù)據(jù)類型創(chuàng)建一個更簡潔、更明了的別名，這樣可以使代碼更易讀、更易維護。
typedef int SLTDataType;
typedef struct SListNode //--single Linked List
{
SLTDataType data;//成員變量
struct SListNode* next;
}SLTNode;定義了一個單鏈表節(jié)點的結(jié)構(gòu)體?SLTNode，其中包含了兩個成員變量：一個名為?data?的int變量?SLTDataType，和一個名為?next?的指向下一個節(jié)點的指針。
2.2鏈表的打印
? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??“指針賦值的本質(zhì)是將一個指針變量的地址復(fù)制給另一個指針變量”
int *p1, *p2;?
p1 = (int*)malloc(sizeof(int)); // 為p1分配內(nèi)存
*p1 = 10; // 設(shè)置p1指向的內(nèi)存的值為10
p2 = p1; // 將p1的地址賦值給p2上面代碼中,p1和p2都是指針變量。p1被分配了內(nèi)存,并指向該內(nèi)存。p2 = p1這行代碼將p1的地址復(fù)制給了p2,使p2也指向p1所指向的內(nèi)存。
所以指針賦值后,兩個指針變量指向同一塊內(nèi)存,通過任一指針變量訪問內(nèi)存的值都會相同。
指針賦值不會復(fù)制指針指向的內(nèi)存內(nèi)容,僅僅是將指針變量中的地址值進行復(fù)制。
畫圖:
?代碼實現(xiàn):
//函數(shù)的作用是遍歷單鏈表，并將每個節(jié)點的數(shù)據(jù)元素打印到屏幕上。
void SLTPrint(SLTNode* phead)//參數(shù)是一個指向 SLTNode 類型的指針 phead，表示單鏈表的頭節(jié)點。
{
SLTNode* cur = phead;//頭結(jié)點存儲的地址給cur指針。
while (cur != NULL)//使用一個while循環(huán)對單鏈表進行遍歷，循環(huán)條件為 cur 不為 NULL。
{ //cur 可以表示當(dāng)前正在處理的節(jié)點的地址，
//通過訪問 cur->data 和 cur->next 成員變量，可以獲取當(dāng)前節(jié)點的數(shù)據(jù)元素和下一個節(jié)點的地址
printf("%d->", cur->data);
cur = cur->next;//cur是存著當(dāng)前結(jié)點的地址,cur->next是下一結(jié)點地址
}
printf("NULL\n");
}
2.3創(chuàng)建一個新結(jié)點
SLTNode* BuyLTNode(SLTDataType x)//表示要創(chuàng)建的節(jié)點的數(shù)據(jù)元素。
//函數(shù)的作用是創(chuàng)建一個新的單鏈表節(jié)點，并將其初始化為包含數(shù)據(jù)元素 x 的節(jié)點。
{
//SLTNode node;//這樣是不行,處于不同的空間，出了作用域是會銷毀的。
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//使用malloc函數(shù)動態(tài)分配了一個大小為SLTNode的內(nèi)存塊，
//并將其強制轉(zhuǎn)換為 SLTNode 指針類型，即創(chuàng)建了一個新的節(jié)點。
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
//需要注意的是，在使用 malloc 函數(shù)動態(tài)分配內(nèi)存時，需要手動釋放內(nèi)存，否則會導(dǎo)致內(nèi)存泄漏
//因此，在創(chuàng)建單鏈表節(jié)點后，我們應(yīng)該在適當(dāng)?shù)臅r候使用 free 函數(shù)釋放節(jié)點所占用的內(nèi)存
newnode->data = x;
newnode->next = NULL;
return newnode;//返回的是一個結(jié)點的地址
}該函數(shù)的作用是創(chuàng)建一個新的單鏈表節(jié)點，并將其初始化為包含數(shù)據(jù)元素 x 的節(jié)點。具體實現(xiàn)過程是通過使用 malloc 函數(shù)動態(tài)分配內(nèi)存塊，然后將其強制轉(zhuǎn)換為 SLTNode 指針類型，即創(chuàng)建了一個新的節(jié)點。然后將該節(jié)點的 data 成員設(shè)置為 x，next 成員設(shè)置為 NULL，最后返回新節(jié)點的指針地址。
需要注意的是，在使用 malloc 函數(shù)動態(tài)分配內(nèi)存時，需要手動釋放內(nèi)存，否則會導(dǎo)致內(nèi)存泄漏。因此，在創(chuàng)建單鏈表節(jié)點后，我們應(yīng)該在適當(dāng)?shù)臅r候使用 free 函數(shù)釋放節(jié)點所占用的內(nèi)存。
2.4單鏈表尾插
錯誤代碼1:
void SLPushBack(SLTNode* phead, SLTDataType x)
{
?? ?SLTNode* tail = phead;
?? ?while (tail != NULL)
?? ?{
? ? ? ? ? tail = tail->next;
?? ?}?? ?SLTNode* newnode = BuyLTNode(x);
?? ?tail = newnode;//這個地方?jīng)]有鏈接起來
}
1.鏈表沒有鏈接起來
2.出了作用域指針變量銷毀，內(nèi)存泄露
?補充一下內(nèi)存泄露的知識:
如果沒有使用free函數(shù)釋放通過malloc函數(shù)分配的內(nèi)存空間，這些內(nèi)存空間將一直占用著系統(tǒng)資源，直到程序結(jié)束或者操作系統(tǒng)重啟。
當(dāng)程序結(jié)束時，操作系統(tǒng)會回收該程序使用的所有內(nèi)存空間，包括沒有通過free函數(shù)釋放的空間。但是，在程序運行期間，這些沒有釋放的內(nèi)存空間會一直占用著系統(tǒng)資源，可能導(dǎo)致系統(tǒng)的內(nèi)存資源耗盡，從而影響系統(tǒng)的穩(wěn)定性和性能。
因此，為了避免內(nèi)存泄漏問題，開發(fā)人員需要在程序中顯式地使用free函數(shù)來釋放不再使用的內(nèi)存空間，以確保系統(tǒng)資源的有效利用。
錯誤代碼2：
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode* phead, SLTDataType x);
void TestSList1()?
{
?? ?SLTNode* plist = NULL;
?? ?SLPushFront(&plist,1);
?? ?SLPushFront(&plist,2);
?? ?SLPushFront(&plist,3);
?? ?SLPushFront(&plist,4);?? ?SLTPrint(plist);
?? ?SLPushBack(plist, 5);//這里傳了一級指針
?? ?SLTPrint(plist);}
void SLPushBack(SLTNode* phead, SLTDataType x)
{
?? ?SLTNode* tail = phead;
?? ?while (tail->next!= NULL)
?? ?{
?? ??? ?tail = tail->next;
?? ?}?? ?SLTNode* newnode = BuyLTNode(x);
?? ?tail->next = newnode;
}
這種情況是先頭插然后再尾插，頭插每次都需要二級指針，然而尾插需要第一次是傳二級指針，后面可以傳一級指針，但是參數(shù)是統(tǒng)一的，無法實現(xiàn)寫兩個相同的函數(shù),第一次傳一級指針，后面?zhèn)鞫壷羔槨?/p>
所以一致傳二級指針。
這種情況前提條件是鏈表不為空，可以直接修改結(jié)構(gòu)體的next，存下新結(jié)點的地址。
執(zhí)行：
錯誤代碼3：
畫圖:
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode* phead, SLTDataType x);void TestSList2()
{
?? ?SLTNode* plist = NULL;
?? ?SLPushBack(plist, 1);
?? ?SLPushBack(plist, 2);
?? ?SLTPrint(plist);
}void SLPushBack(SLTNode* phead, SLTDataType x)
{
?? ?SLTNode* newnode = BuyLTNode(x);
?? ?if (phead == NULL)
?? ?{
?? ??? ?phead = newnode;
?? ?}
?? ?else
?? ?{
?? ??? ?SLTNode* tail = phead;
?? ??? ?while (tail->next != NULL)
?? ??? ?{
?? ??? ??? ?tail = tail->next;
?? ??? ?}?? ??? ?tail->next = newnode;
?? ?}
}
輸出:
?列舉了這么多錯誤案例接下來到正確案例:
void SLPushBack(SLTNode** pphead, SLTDataType x)
void TestSList2()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
}
//要讓新節(jié)點和tail鏈接起來,一定要去改tail的next
void SLPushBack(SLTNode** pphead, SLTDataType x)//尾插的本質(zhì)是讓上一個結(jié)點鏈接下一個結(jié)點
{
SLTNode* newnode = BuyLTNode(x);
// 1、空鏈表
// 2、非空鏈表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}?代碼執(zhí)行:
2.5單鏈表頭插
頭插思路:
頭插第二個節(jié)點思路:
頭插的代碼可以寫成這樣
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//使用malloc函數(shù)動態(tài)分配了一個大小為SLTNode的內(nèi)存塊，
//并將其強制轉(zhuǎn)換為 SLTNode 指針類型，即創(chuàng)建了一個新的節(jié)點。
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
//需要注意的是，在使用 malloc 函數(shù)動態(tài)分配內(nèi)存時，需要手動釋放內(nèi)存，否則會導(dǎo)致內(nèi)存泄漏
//因此，在創(chuàng)建單鏈表節(jié)點后，我們應(yīng)該在適當(dāng)?shù)臅r候使用 free 函數(shù)釋放節(jié)點所占用的內(nèi)存
newnode->data = x;
newnode->next = NULL;
//return newnode;//返回的是一個結(jié)點的地址
newnode->next = *pphead;
*pphead = newnode;//將頭節(jié)點*pphead 更新為新節(jié)點的地址，以使新節(jié)點成為新的頭節(jié)點。
}但是為了避免創(chuàng)建新節(jié)點的程序重復(fù)編寫,可以利用上面的BuyLTNode(x)函數(shù)定義新節(jié)點達成簡寫的目的，也可以頭插的函數(shù)也可以寫成這樣:
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}在?
SLPushFront?函數(shù)中，我們首先調(diào)用?BuyLTNode(x)?函數(shù)創(chuàng)建一個新的節(jié)點，然后將新節(jié)點的?next?指針指向當(dāng)前鏈表頭節(jié)點，接著將鏈表頭指針指向新節(jié)點，從而完成了在鏈表頭部插入新節(jié)點的操作。
代碼執(zhí)行:
2.6單鏈表尾刪?
錯誤案例:
?方法1:
方法2:
?代碼實例:
void SLPopBack(SLTNode** pphead)
{
//沒有節(jié)點(空鏈表)
//暴力檢查
assert(*pphead);
//溫柔檢查
if (*pphead == NULL)
{
return;
}
//一個節(jié)點
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}//多個節(jié)點
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
//找尾
//方法一
/*while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;*/
//方法二
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}執(zhí)行:?
?
?2.7單鏈表頭刪
思路:
void SPopFront(SLTNode** pphead)
{
//沒有節(jié)點
//暴力檢查
assert(*pphead);
//溫柔檢查
if (*pphead == NULL)
return;// 一個節(jié)點
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//多個節(jié)點
else
{
SLTNode* del = *pphead;//相當(dāng)于一個標(biāo)記,刪掉的標(biāo)記
//寫法一
//*pphead = del->next;
//寫法二
*pphead = (*pphead)->next;
free(del);
}
}執(zhí)行:
2.8單鏈表查找/修改某個值
使用尾插將1,2,3,4按先后順序分別插入鏈表中，接著找到鏈表中值為3的元素，并把其改為30(可以通過定義結(jié)構(gòu)體類型的指針訪問data為3的結(jié)點,并直接通過pos->next=30修改)
注意:直接在main函數(shù)內(nèi)定義一個test函數(shù)修改值即可,不必另定義新函數(shù)。
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
//assert(phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}執(zhí)行:
2.9單鏈表在pos之前插入
思路:
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);//&plist
assert(pos);
//assert(*pphead);
//一個節(jié)點
if (*pphead == NULL)
{
SLPushFront(pphead, x);
}
else//多個節(jié)點
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}?執(zhí)行:
2.10單鏈表在pos之后插入
思路:
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.11單鏈表刪除pos的值
思路:?
void SLErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
2.12單鏈表刪除pos之后的值
思路:
void SLEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* next= pos->next;
pos->next = next->next;
free(next);
}?
文章來源：http://www.zghlxwxcb.cn/news/detail-600356.html
三.案例函數(shù)實現(xiàn)
3.1測試
void TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(&plist,1);
SLPushFront(&plist,2);
SLPushFront(&plist,3);
SLPushFront(&plist,4);
SLTPrint(plist);
SLPushBack(plist, 5);
SLTPrint(plist);
}3.2頭插
void TestSList2()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLTPrint(plist);
SLPushBack(&plist, 5);
SLTPrint(plist);
}3.3尾插
void TestSList3()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLTPrint(plist);
SLPushBack(&plist, 2);
SLTPrint(plist);
SLPushBack(&plist, 3);
SLTPrint(plist);
SLPushBack(&plist, 4);
SLTPrint(plist);
}3.4頭刪
void TestSList4()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
//頭刪
SLPopFront(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLTPrint(plist);
}3.5尾刪
void TestSList5()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
}3.6查找/修改某值
void TestSList6()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist,3);
if (pos)
pos->data = 30;
SLTPrint(plist);
}3.7在pos之前插入?
void TestSList7()//pos之前插入
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist,3);
if (pos)
{
SLInsert(&plist, pos, 30);
}
SLTPrint(plist);
}3.8在pos之后插入?
void TestSList8()//pos之后插入
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist, 3);
if (pos)
{
SLInsertAfter(pos, 50);
}
SLTPrint(plist);
}3.9刪除pos位置的值
void TestSList9() {
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist, 3);
if (pos)
{
SLErase(&plist,pos);
}
SLTPrint(plist);
}3.10刪除pos之后的值
void TestSList10() {
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLPushBack(&plist, 5);
SLTPrint(plist);
SLTNode* pos = STFind(plist, 2);
if (pos)
{
SLEraseAfter(pos);
}
SLTPrint(plist);
}本章完，如有錯誤歡迎各位大佬指點，感謝你的來訪。文章來源地址http://www.zghlxwxcb.cn/news/detail-600356.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】C--單鏈表(小白入門基礎(chǔ)知識)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
