目錄

前言

頭文件

動態(tài)申請一個結(jié)點

單鏈表打印?

單鏈表尾插?

單鏈表的頭插

單鏈表的尾刪

單鏈表頭刪

單鏈表查找

單鏈表在pos位置之后插入x

單鏈表刪除pos位置之后的值

在pos的前面插入

刪除pos位置

銷毀順序表

---

前言

本文將介紹鏈表常見的功能的實現(xiàn)

頭文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDateType;
typedef struct SListNode
{SLTDateType val;struct SListNode* next;
}SListNode;// 動態(tài)申請一個結(jié)點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？
void SListEraseAfter(SListNode* pos);
// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
//銷毀順序表
void SLTDestroy(SListNode** pphead);

動態(tài)申請一個結(jié)點

原理：鏈表的結(jié)點所代表的是一個內(nèi)存塊，里面包含著該節(jié)點的值以及指向下一個結(jié)點地址的指針，用動態(tài)申請的方式更加方便，插入時只需要將前一個結(jié)點里的指針指向自己即可，但新結(jié)點剛創(chuàng)建時，里面的指針指向空，不要變?yōu)橐爸羔槨?/p>

SListNode* BuySListNode(SLTDateType x)
{SListNode* ans = (SListNode*)malloc(sizeof(SListNode));if (ans == NULL){perror("malloc fail");return NULL;}ans->val = x;ans->next = NULL;return ans;
}

單鏈表打印?

原理：遍歷輸出即可，但鏈表的遍歷不同于順序表的遍歷在于需要將遍歷指針指向下一個結(jié)點（順序表是下標(biāo)++遍歷），遇到空為止。

void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur){printf("%d->", cur->val);cur = cur->next;}printf("NULL");
}

單鏈表尾插?

原理：鏈表的唯一缺點是不能通過下標(biāo)去尋找對應(yīng)結(jié)點，只能通過從頭結(jié)點遍歷到指定結(jié)點（因為一個結(jié)點只能通過上一個結(jié)點的指針找到，它們在內(nèi)存里的存儲位置不是連續(xù)的），所以，定義一個指針，從頭結(jié)點開始，這里要考慮到兩種情況：

1.當(dāng)頭結(jié)點為空時，意味著這是鏈表剛創(chuàng)建，直接將頭結(jié)點指向空即可；

2.當(dāng)頭結(jié)點不為空時，意味著這是一個好的鏈表，需要遍歷到該鏈表的末結(jié)點，將末結(jié)點的指針指向新結(jié)點完成尾插。遍歷終止的條件時當(dāng)前指針的下一個指針指向空，如果該指針指向空的話，遍歷到末尾時會進(jìn)一次循環(huán)，走到空，此時會丟失之前結(jié)點的地址。

void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);//用x創(chuàng)建新結(jié)點if ((*pplist) == NULL){(*pplist) = newnode;}else{SListNode* cur = *pplist;while (cur->next){cur = cur->next;}cur->next = newnode;}
}

單鏈表的頭插

原理：當(dāng)頭結(jié)點為空時，和尾插一樣，要講的是不為空的情況：

創(chuàng)建好新結(jié)點后，將新結(jié)點的下一個指針指向頭結(jié)點指向的結(jié)點，然后頭結(jié)點指向新結(jié)點。順序不能對調(diào)，會丟失頭結(jié)點原本指向的結(jié)點地址。

void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{newnode->next = (*pplist);*pplist = newnode;}
}

單鏈表的尾刪

原理：動態(tài)申請的內(nèi)存如果需要刪除的話是需要通過free函數(shù)進(jìn)行釋放的。

這里也要考慮兩種情況，因為單一的方法不適用于所有情況。

1.當(dāng)鏈表有兩個以上的結(jié)點時，遍歷到末尾結(jié)點的前驅(qū)結(jié)點，然后釋放掉下一個指針指向的結(jié)點，再置為空即可，如果遍歷到刪除結(jié)點的話，你釋放時就會丟失掉前一個結(jié)點的地址，那個結(jié)點的指針就會變成野指針。

2.當(dāng)鏈表為空或是只有一個結(jié)點時，直接釋放即可，當(dāng)然，為什么頭結(jié)點為空時也能進(jìn)行釋放？不會構(gòu)成對空指針的引用嗎？我們來看看Cplusplus上面的描述：

最后一句：如果指針為空，該功能不做任何改變（因為釋放完后還是為空，人為操作）。

根據(jù)free的特性，可以將空和單個結(jié)點的情況考慮進(jìn)去。

void SListPopBack(SListNode** pplist)
{if ((*pplist) == NULL || (*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* cur = *pplist;while (cur->next->next){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

單鏈表頭刪

頭刪和尾刪一樣，同樣也要考慮一個結(jié)點和多個結(jié)點的情況：

1.只有一個結(jié)點或為空時，和尾刪一樣，直接free掉即可。

2.當(dāng)有多個結(jié)點時，我們需要保留頭結(jié)點的下一個指針，在刪除頭結(jié)點后，將頭結(jié)點指向剛剛保留的指針即可。

void SListPopFront(SListNode** pplist)
{if ((*pplist == NULL) || (*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;}
}

單鏈表查找

直接遍歷定位即可，返回該值的結(jié)點而不是該值。

SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->val == x){return cur;}cur = cur->next;}return NULL;}

單鏈表在pos位置之后插入x

定位到pos位置后，將pos進(jìn)行頭插即可。

void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);SListNode* next = pos->next;pos->next = newnode;newnode->next = next;
}

單鏈表刪除pos位置之后的值

和插入相反，只是進(jìn)行頭刪即可，pos在頭結(jié)點上情況也一樣。

void SListEraseAfter(SListNode* pos)
{assert(pos);SListNode* next = pos->next;if (next != NULL){SListNode* nextnext = next->next;free(next);pos->next = nextnext;}
}

在pos的前面插入

首先這里得考慮pos的位置，因為如果在頭結(jié)點上的話就得單獨考慮。

1.如果pos在頭結(jié)點上的話，直接頭插

2.否則，用一個前驅(qū)指針保留pos位置的前驅(qū)指針，再做插入操作。

這里斷言一下，以防傳來的pos和頭結(jié)點為空

void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{//不允許*pphead和pos一者為空，要么都為空，要么都不空assert(*pphead);assert(pos);assert(pphead);SListNode* newnode = BuySListNode(x);if (pos == *pphead){SListPushFront(pphead, x);}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}

刪除pos位置

和上面一樣，如果pos位置是頭結(jié)點的話就頭刪，否則保留pos位置的前驅(qū)和后繼指針，free掉pos后，兩個指針鏈接。

void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SListPopFront(pphead);}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SListNode* next = pos->next;free(pos);prev->next = next;pos = NULL;}
}

銷毀順序表

從頭結(jié)點開始，一個個結(jié)點往下遍歷釋放，最后頭結(jié)點置空即可。

void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* cur = *pphead;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}

?