在順序表中我們了解了順序表的概念與如何創建一個順序表與它的介面函式完成增刪查改的功能，本文將繼續介紹線性存盤的內容，對單鏈表的概念進行了相關闡述并且給出了它的介面函式的C語言實作
單鏈表及其介面函式
- 順序表的一些缺點：
- 什么是單鏈表？
- 鏈表的優點：
- 鏈表的缺點:
- 單鏈表的實作
- 小結
順序表的一些缺點：
在順序表階段，我們了解到順序表在記憶體中是一塊連續存盤的空間，元素與元素之間緊挨存放，不用經過太多思考，我們就可以發現順序表在實際應用中的一些缺點：
- 為了能動態的進行存盤，那么就需要創建一個動態鏈表進行資料存盤，
- 為了避免頻繁擴容，在使用realloc進行申請空間時，往往直接申請當前空間的二倍空間，這就免不了空間浪費，
- 在插入或者洗掉資料時，需要挪動整個順序表，效率極低，
- realloc函式在申請記憶體空間時，有申請失敗的風險，
于是有人就考慮用鏈表的方式來解決上述相關問題，
什么是單鏈表？
顧名思義，單鏈表是一種區別于順序表的一種不需要在記憶體中連續存盤的資料存盤型別，各個資料元素可以在記憶體中分別存盤，資料與資料之間通過next指標的方式，相互連接，在結構上如同“鉸鏈”一樣形成一個整體，如圖所示，可以方便你更加清晰的認識單鏈表的結構：
單鏈表仍然以一個結構體作為基本結構，在Data中存放資料，而結構體的next指標中存放下一個資料的地址，只要通過對當前資料的next指標進行解參考操作就可以找到下一個資料元素，單鏈表總是以一個指向第一個元素的頭指標開始，直到最后一個元素的空指標作為結束標志，在上述圖中，我們可以發現：由于指標的尋址特性，所以鏈表不需要連續存盤在記憶體中，
鏈表的優點：
按需申請空間，不用了就釋放空間（更合理的使用了空間）
頭部、中間插入資料，不需要挪動資料
鏈表的缺點:
每一個資料都要一個指標去存鏈接后面資料的結點
不支持隨機訪問（用下標訪問第i個）
與順序表不同的是，
鏈表是以頭指標開始的，而不是如順序表一樣單純的用一個結構體變數的物體化來創建的，單鏈表是用指標來進行維護的，鏈表的起始是用一個為NULL的結構體指標開始的，對于指標進行了賦值操作即完成了初始化，固不再額外使用初始化函式對其進行初始化，
注意：要理解好空指標NULL的相關概念，空指標是不能進行解參考操作的，空指標存放的就是0x00000000，它不能解參考訪問任何內容，所以一切對空指標的解參考操作都是錯誤的，但是存放NULL的指標（也就是空指標）是有地址的，尾插傳遞的就是這個空指標的地址，對空指標的地址的解參考是有效的，得到的是0x00000000這個NULL值，
單鏈表的實作
鏈表的每一個節點需要具備的功能有：
1、存放資料
2、訪問下一個節點存放的內容
所以對于一個單鏈表來說，同樣采用結構體的方式對其中內容進行定義：
為了方便更換資料型別將我們將int等型別可以型別重定義為SLTDataType
//.h檔案
#pragma once
#include<stido.h>
#include<stdlib.h>
typedef int SLTDataType
typedef struct SListNode
{
SLTDataType data;//存的資料
struct SlistNode* next;//next指標
}SLTNode;
//輔助函式用于新節點創建
SLTNode* BuyListNode(SLTDataType x);
//列印函式
void SListPrint(SLTNode* phead);
//尾插
void SListPushBack(SLTNode** pphead,SLDataType x);
//頭插
void SListPushFront(SLTNode** pphead,SLDataType x);
//尾刪
void SListPopBack (SLNode** pphead);
//頭刪
void SListPopFront(SLNode** pphead);
//查找函式
void SListFind(SLTNode* phead,SLTNodeType x);
//指定下標插入
void SListInsert(SLTNode* phead,SLTNode *pos,SLTDataType x);
//指定下標之后的一個位置插入
void SListInsertAfter(SLNode* pos,SLTDatatpye x);
//擦除某個特定位置的元素
void SListErase(SLTNode** pphead, STLNode pos,SLTDataType x);
//擦除某個特定未知的之后的元素
void SListEraseAfter(SLTNode* pos);
//銷毀鏈表
void SlistDestory(SLTNode** pphead);
介面函式的具體實作
//.h對應的.c檔案
//輔助函式 用于結點創建
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if(newnode==NULL)
{
printf("空間不夠了");
exit(-1);
}
else
{
newnode->data=x;
newnode->next=NULL;
}
return newnode;
}
//列印函式
void SListPrint(SLTNode* phead)
{
SLTNode*cur=phead;
while(cur!=NULL)
{
printf("%d->",cur->data);
cur=cur->next;
}
}
//尾插函式
void SListPushBack(SLTNode** pphead, SLTDataType x)
//切記這個地方要用二級指標來接收 維護鏈表的phead對其進行傳址操作處理
{
SListNode* newnode=BuyListNode(x);
if(*pphead==NULL)//判斷是否phead記憶體儲的是空，即需要判斷鏈表是否開始了
{
*pphead=newnode;//讓頭指標指向 這個newnode新節點所維護的struct空間
}
else//此時說明鏈表中的有元素，需要尋找尾結點
{
SLTNode* tail=*pphead;
//尾結點的標志是next為空
//找到尾結點
while(tail->next !=NULL)
{
tail=tail->next;
}
tail->next=newnode;
}
}
//頭插函式
//頭插時不需要對頭指標判空，只需要申請空間創建節點并賦予頭指標即可
void SListPushFront(SLTNode** pphead,SLTDataType x)
{
SListNode* newnode=BuyListNode(x);
newnode->next=*pphead;
*pphead=newnode;
}
//尾刪
void SListPopBack (SLNode** pphead)
{
if(*pphead==NULL)//鏈表為空的時候直接回傳0，這里也可以用assert保證鏈表不為空
{
return 0;
}
if((*phead)->next ==NULL)//只有一個節點時
{
free(*pphead);
*pphead=NULL;
}
else
{
SLNode* prev=NULL;
SLNode* tail= *pphead;
while(tail->next!=NULL)
{
prev=tail;
tail=tail->next;
}
free(tail);//將最后一個節點的內容free掉
tail=NULL;
//將指向最后節點的tail指標置空，但此時鏈表中的倒數第二個的next指標并沒有被修改為NULL，原因是tail被free掉之后為一個隨機值
//所以要對倒數第二個節點的next置NULL完成尾刪，
prev->next=NULL;
//通過倒數第三個結構體的next指標訪問倒數第二個next指標將其置空，就完成了倒數第二個的next指標置空
}
/*//也可以用這種方法
SLTNode* tail=*pphead;
while(tail->next->next)
{
tail=tail->next;
}
//當調出回圈時，tail為倒數第二個節點
//將tail的下一個位置的free掉
free(tail->next);
//tail作為倒數第二個節點需要對其next指標置空
tail->next=NULL;
*/
}
//頭刪
void SListPopFront(SLNode** pphead)
{
if(*pphead==NULL)
{
return 0;
}
SLNode* head =*pphead->next;
free(*pphead);
*pphead=head;
}
//查找函式
STLNode* SListFind(SLTNode* phead,SLTNodeType x)
{
SLTNode* pf=phead;
/* while(pf->data!=x)
{
pf=pf->next;
}
if(pf->data==x)
{
retrun 1;
}
else
{
return -1;
}*/
while(pf)
{
if(of->data==x)
{
retunn pf;
}
else
{
pf=pf->data;
}
}
return NULL;
}
//指定Pos位置插入(前插)
void SListInsert(SLTNode** pphead, STLNode * pos,SLTDataType x)
{
assert(pphead);
assert(pos);
STLNode* newnode=BuyListNode(x);
//找到pos位置
STLNode* posPrev=*pphead;
while(posPrev->next!=pos)
{
posPrev=posPre->next;
}
posPrev->next=newnode;
newnode->next=pos;
}
//指定位置pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//指定位置擦除（從前遍歷之后擦除）
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
/**pphead = pos->next;
free(pos);*/
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);//將pos銷毀 在立案表中pos維護的空間置為隨機值
//pos = NULL;
}
}
//指定pos位置洗掉（pos位置后洗掉）
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;//創建next結構體指標，將pos的下一個位置的結構體交于它維護，目的是找到pos下一個的下一個，以便讓pos直接指向下一個的下一個，然后就可以對pos之后的內容進行洗掉
pos->next = next->next;//用賦值的方式將next結構體指標所維護的空間中的next指標（pos的下一個的下一個）給pos的下一個，對pos的下一個位置進行銷毀
free(next);
//next = NULL;
}
//銷毀
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
//.c檔案 進行test
void Test_list()
{
SLTNode* plist = NULL;
//單鏈表以一個結構體指標開始從而創建出整個鏈表，所以呼應了上述中需要傳遞二級指標來修改一級指標的值，
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
//你可以試一試其他介面函式的呼叫，注意傳遞的引數型別哦！
}
int main()
{
Test_list();
}
小結
對于一個單鏈表來說，不需要在記憶體中連續存盤，實作了存盤的便捷化，但是也由于這種特性不能通過下標對其進行隨機訪問，單鏈表的物體化程序用一個結構體指標來實作，在實作介面函式時，由于頭指標為一個一級指標，若想修改一級指標所維護的空間的值，就需要傳遞一級指標的地址，用二級指標對其進行接收并通過對二級指標解參考操作來修改頭指標維護的結構空間，因為單鏈表的每一個節點通過malloc函式開辟，所以在最后不要忘記對其進行銷毀，防止出現野指標等不可預計錯誤，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344242.html
標籤：其他
上一篇：鏈表OJ題（一）
下一篇：【資料結構】佇列