目錄

（一）單鏈表的結構定義及初始化

(二)單鏈表的尾插，頭插

?

(三)單鏈表的尾刪，頭刪

(四)單鏈表的查找，刪除，銷毀

---

單鏈表是數據結構課程里的第二個數據結構。單鏈表在邏輯結構是連續的，在物理結構不一定連續。因為在單鏈表的每一個結點的內存是在堆區動態開辟的，由操作系統來決定是否連續開辟在相同的區域。

---

（一）單鏈表的結構定義及初始化

#define SLDataType int//單鏈表的結構定義
typedef struct SingleList
{SLDataType val;struct SingleList* next;
}SL;

單鏈表的每一個節點都有其數值域和指針域。數值域是當前結點所存儲的數值，指針域是存儲指向下一個結點的指針。這里我們定義一個宏，把SLDataType 替換成int,以后想換存儲的數據類型就方便多了。我們再把單鏈表的數據類型struct SingleList重命名為SL。

//單鏈表的初始化
void InitSingleList(SL* phead)
{assert(phead);phead->val = 0;phead->next = NULL;
}

(二)單鏈表的尾插，頭插

單鏈表的尾插是指在單鏈表的結尾插進去一個新結點。我們可以創建一個函數專門封裝創建一個新結點的過程

//創建一個新結點
SL* BuyNewNode(SLDataType x)
{SL* NewNode = (SL*)malloc(sizeof(SL));if (NewNode == NULL){perror("malloc fail!\n");eixt(1);    }//走到這說明新結點的內存創建成功NewNode->val = x;NewNode->next = NULL;return NewNode;
}

每次創建結點的時候必須要檢查結點是否創建失敗，而且要記得要釋放空間。我們這里通過malloc申請了一片SL大小的空間。并將申請的空間解釋為SL*類型，把SL里面的值賦值為x，下一個結點指向為NULL指針。

//單鏈表的尾插
void SingleListPushBack(SL** pphead, SLDataType x)
{//這里需要用二級指針，因為可能傳進來的指針沒有結點，尾插變成頭插，需要對頭結點的地址進行賦值。assert(pphead);SL* phead = *pphead;if (phead == NULL){//說明單鏈表沒有一個結點，需要修改頭結點的地址phead = BuyNewNode(x);}else{//需要遍歷鏈表找到尾結點SL* pcur = phead;while (pcur){pcur = pcur->next;}//我們要讓鏈表后面的順序為   pcur  ->  NewNodepcur->next = BuyNewNode(x);}
}

//單鏈表的頭插
void SingleListPushFront(SL** pphead, SLDataType x)
{   assert(pphead);//同樣的頭插就更需要傳二級指針了SL* phead = *pphead;//NewNode  -> phead;SL* NewNode = BuyNewNode(x);NewNode->next = phead;phead = NewNode;
}

(三)單鏈表的尾刪，頭刪

同樣的操作

//單鏈表的尾刪
void SingleListPopBack(SL** pphead)
{assert(pphead && *phead);SL* phead = *pphead;//如果單鏈表只有一個結點if (phead-> next == NULL){free(phead);phead = NULL;}else{//需要遍歷查找鏈表尾部SL* pcur = phead;SL* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}//  pcur  pcur->nextprev->next = NULL;free(pcur->next);pcur->next = NULL;}
}

//單鏈表的頭刪
void SingleListPopFront(SL** pphead)
{   assert(pphead && *pphead);SL* phead = *pphead;// phead phead->next;SL* next = phead->next;free(phead);phead = next;
}

(四)單鏈表的查找，刪除，銷毀

//單鏈表的查找
SL* FindSingleList(SL* phead, SLDataType x)
{assert(phead);SL* pcur = phead;while (pcur){    if (pcur->val == x)return pcur;pcur = pcur->next;}return NULL;
}

//刪除pos結點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//pos就是頭結點if (pos == *pphead){SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

//單鏈表的銷毀
void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}