鏈表的概念
鏈表是一種物理存儲結(jié)構(gòu)上非聯(lián)系，非順序的存儲結(jié)構(gòu)，但數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實現(xiàn)的
邏輯結(jié)構(gòu)：
實際物理結(jié)構(gòu)：
每個鏈表節(jié)點都有自己的地址，鏈表的物理結(jié)構(gòu)實際上是前一個結(jié)點保存著下一個結(jié)點的地址
所以從上面圖中可以看出：
1.鏈表在邏輯上是連續(xù)的，但在物理上不是連續(xù)的
2.現(xiàn)實中，每個結(jié)點都是從堆中申請的
3.在堆中申請空間，按照一定規(guī)則進行分配，所以兩次連續(xù)的開辟空間可以連續(xù)，可能不連續(xù)
鏈表的分類
實際中的鏈表有多種結(jié)構(gòu)
分別為：
- 帶頭節(jié)點或不帶頭結(jié)點
- 單向或雙向
- 循環(huán)或不循環(huán)
所以鏈表一共有8種結(jié)構(gòu)
但是常用的只有：不帶頭節(jié)點非循環(huán)單鏈表 和 帶頭循環(huán)雙向鏈表兩種
單鏈表的實現(xiàn)
這里我們介紹的是不帶頭節(jié)點非循環(huán)單鏈表
單鏈表的結(jié)構(gòu)
一個節(jié)點即存放了元素的值，也存放了下一個節(jié)點的地址，所以在結(jié)構(gòu)體中，定義一個SLTDataType類型的data，以及結(jié)構(gòu)體的自引用：struct SListNode* next作為指向下一個節(jié)點的指針
所以結(jié)構(gòu)體如下：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
到這里，我們知道了可以通過一個節(jié)點找到下一個節(jié)點，但是我們?nèi)绾握业筋^節(jié)點呢？
解決辦法就是用一個結(jié)構(gòu)體類型的指針去指向頭節(jié)點，也解釋存放頭節(jié)點的地址。
所以在接下來的函數(shù)中，傳這個頭指針就可以了
單鏈表的接口函數(shù)
創(chuàng)建節(jié)點函數(shù)
因為每個節(jié)點都需要在堆中開辟，所以可以封裝成一個函數(shù)，需要調(diào)用malloc去開辟空間
同時，在這個函數(shù)中，將data的值存放到節(jié)點中，因為不知道當前下一個節(jié)點的地址，所以next指針賦為NULL，最后返回這個節(jié)點的地址
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
if (new == NULL)
{
perror("malloc fail");
return;
}
new->next = NULL;
new->data = x;
return new;
}
打印函數(shù)
從頭節(jié)點開始，直到NULL，遍歷鏈表，并且打印出來
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur!= NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾插函數(shù)
在實現(xiàn)尾插函數(shù)前，如果此時頭指針指向的為NULL，在尾插函數(shù)中便會改變頭指針的指向，也就是改變頭指針的值，如果這個函數(shù)是傳的一級指針的話，雖然在尾插函數(shù)中改變了頭指針的指向，但在主函數(shù)中，頭指針的改變并沒有改變
傳一級指針的情況圖如下
所以這樣的情況下，就需要傳二級指針，將頭節(jié)點的二級指針pphead傳過去，讓后通過解引用*pphead去改變頭指針的指向
所以在后面的會改變頭指針指向的函數(shù)中，都需要傳二級指針
接下來，實現(xiàn)尾插函數(shù)
我們應(yīng)先創(chuàng)建節(jié)點，調(diào)用
SLTBuyNode函數(shù)
接下來還有一點要注意的：
如果此時頭指針是空，就說明它后面沒有任何節(jié)點，所以需要把newnode的節(jié)點地址賦值給頭指針
如果不為空，找到尾節(jié)點，在尾節(jié)點的后面插入新節(jié)點
這里還需要注意的一個點是：二級指針是頭指針的地址，這個地址一定不能為空，如果為空就出問題了，所以在函數(shù)開始應(yīng)用assert斷言判斷一下pphead是否為空
頭節(jié)點的值可能為NULL，所以不用斷言判斷*pphead
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
頭插函數(shù)
頭插函數(shù)在頭部插入，所以一點會改變頭指針的指向，所以仍需傳二級指針
然后靈newnode->next等于*pphead，然會再將newnode的值賦給頭指針
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
頭刪函數(shù)
頭刪函數(shù)一定會改變頭指針指向，所以需要傳二級指針
頭刪，一定必須是鏈表中有節(jié)點，如果沒有節(jié)點，則頭刪沒有意義，如果鏈表為空，那么頭指針的值就為null，所以我們可以通過斷言判斷*pphead是否為空，同時仍需判斷pphead，所以這個函數(shù)的開頭需要斷言2次
因為節(jié)點都是動態(tài)開辟出來的，所以要用free函數(shù)釋放，如果直接直接free*pphead，那么后面的節(jié)點都找不到了，因為也free掉了next的值
所以可以定義一個head變量指向第一個節(jié)點，然后先將head->next賦給*pphead，接下來再free掉head就可以了
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* head = *pphead;
*pphead = head->next;
free(head);
head = NULL;
}
尾刪函數(shù)
和頭刪同樣，需要傳二級指針，以及斷言2次
尾刪，找到尾節(jié)點很簡單，但是刪除尾節(jié)點后還需要把尾節(jié)點前一個結(jié)點的next指針賦為NULL,但是如何找到這個倒數(shù)第二個結(jié)點是個問題
這里我們有2種放法：
1.利用tail->next->next找，當tail->next->next==NULL時，就找到了新的尾結(jié)點
2.定義一個prev指針，讓prev一直在tail指針的前面，當tail到達尾時，prev也自然是倒數(shù)第二個結(jié)點了
起始時：
逐漸向后移動：
最后：
這里我們使用第一種方法，接著我們還會發(fā)現(xiàn)一個問題：當只有一個節(jié)點時，cur->next已經(jīng)為空了。cur->next->next就錯了
所以還需分類運算當只有一個節(jié)點的情況
void SLTPophBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
查找函數(shù)
遍歷鏈表，如果找到則返回這個節(jié)點的地址，否則返回NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pos = phead;
while (pos != NULL)
{
if (pos->data == x)
{
return pos;
}
else
{
pos = pos->next;
}
}
return NULL;
}
pos位置前插入
這個pos是通過SLTFind尋找返回的節(jié)點地址，這個地址不會為空，所以可以斷言判斷一下
如果想在pos位置前插入，就需要直到pos前一個位置，所以這里就需要遍歷尋找pos的前一個結(jié)點prev，然后將prev，newndoe和pos鏈接在一起
如果這個pos等于*pphead，就是在頭節(jié)點前插入，也就是頭插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos==*pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//想要插入pos前，就要知道pos前的節(jié)點，就需要遍歷，所以單鏈表不適合在前面插入
{
prev = prev->next;
}
SLTNode* newnode = SLTBuyNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
因為在pos前插入，所以這個函數(shù)是不會做到尾插功能的
下面考慮一個問題：如果只給pos，不給頭指針，怎么在pos前插入？
在pos后面插入，再交換pos和pos后面節(jié)點中的data值就做到了在pos前面插入
刪除pos位置節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
只給pos，不給頭指針，也可以刪除pos位置節(jié)點：交換pos和pos->next的data值，保存pos->next->next的值為nex，然后刪除pos->next,最后鏈接pos和nex
但是這種方法不適用尾刪
pos位置后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
因為在pos后面插入，所以不需要傳頭指針，同時還需要assert斷言判斷pos是否為空
在pos后面插入，所以這個函數(shù)實現(xiàn)不了頭插
pos位置后面刪除
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
在pos后面刪除，不僅到斷言pos還需要斷言pos->next
其余邏輯很簡單
銷毀函數(shù)
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* del = *pphead;
SLTNode* next = NULL;
while (del != NULL)
{
next = del->next;
free(del);
del = next;
}
*pphead = NULL;
}
因為銷毀會改變頭指針的指向，所以需要傳二級指針
如果鏈表為空，就不必銷毀了，所以需要斷言*pphead
銷毀鏈表，是一個一個結(jié)點得釋放，在釋放當前節(jié)點前，需要保存下一個節(jié)點的地址，然后再銷毀當前節(jié)點，再刪除下一個節(jié)點
最后還需要把*pphead也就是頭節(jié)點賦值為空*pphead = NULL
單鏈表的問題
從上面的代碼中可以看出，對于單鏈表想要尾插，就需要找尾，想要尾刪就需要找到尾和尾的前一個結(jié)點
并且在某個位置插入刪除，需要找到這個位置的前一個結(jié)點
這些操作都需要遍歷鏈表，效率低文章來源：http://www.zghlxwxcb.cn/news/detail-738824.html
這也正是單鏈表的問題，而這些問題放到帶頭循環(huán)雙向鏈表就是小菜一碟了文章來源地址http://www.zghlxwxcb.cn/news/detail-738824.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——單鏈表(不帶頭節(jié)點)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
