目錄

1.鏈表的概念及結構

2.單鏈表的應用

2.1 打印鏈表

2.2申請新節點

2.3插入（尾刪和頭刪）

2.4刪除（尾刪和頭刪）

2.5查找

2.6任意位置插入

2.7刪除指定位置的元素

2.8 銷毀鏈表

3.總結

---

1.鏈表的概念及結構

（1）概念：鏈表是?種物理存儲結構上?連續、?順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的 。與順序表的區別在于鏈表的空間是要一個給一個，不在是內存空間溢出時將內存空間*2.

（2）結構：

struct SListNode
{int data; //節點數據struct SListNode* next; //指針變量?保存下?個節點的地址
};

鏈表是由節點組成的，節點包含節點數據和下一個節點的地址。按照順序打印結構如下。

2.單鏈表的應用

2.1 打印鏈表

通過while (pcur)來判斷是否到達鏈表結尾NULL,pcur = pcur->next將下一跳的地址賦值到pcur來達到循環。

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2.2申請新節點

定義一個新的結構體指針來完成，用元素的擴容（插入）。

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}

2.3插入（尾刪和頭刪）

為什么要用雙指針（SLTNode** pphead）：
????????使用雙指針 SLTNode** pphead，通過 *pphead = newnode 可以直接修改調用者傳遞的頭指針地址，從而更新鏈表的頭節點。如果使用單指針，只能修改局部變量phead的值，無法修改鏈表的地址。

? ? ? ? 總結就是，pphead只是形參，要想通過修改形參來改變實參就必須傳實參的地址。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;}*pphead = newnode;
}

2.4刪除（尾刪和頭刪）

鏈表重新連接好后要釋放掉刪除部分的地址（free）

//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* pcur = NULL;while (ptail->next){pcur = ptail;ptail = ptail->next;}pcur->next = NULL;free(ptail);ptail = NULL;}
}
//頭刪
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* pcur = ptail->next;free(ptail);ptail = NULL;*pphead = pcur;}
}

2.5查找

通過比對data來找到pos的地址。

這里我調試時出現返回的pos1地址傳到我新建立的結構體指針中，高位不一致，但低位一致，問題產生的主要原因是，頭文件中函數沒有定義，我給注釋掉了。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pos1 = phead;while (pos1 != NULL){if (pos1->data == x){return pos1;}pos1 = pos1->next;}return NULL; // 未找到或鏈表為空時返回 NULL
}

2.6任意位置插入

//在指定位置之前插?數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}
//在指定位置之后插?數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.7刪除指定位置的元素

//刪除pos結點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;
}
//刪除pos之后的結點
void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){printf("POS后沒有元素\n");return;}else{ SLTNode* pcur = pos->next;pos->next = pcur->next;free(pcur);                // 釋放被刪除節點的內存pcur = NULL;               // 防止懸空指針}}

2.8 銷毀鏈表

//銷毀鏈表
void SListDestroy(SLTNode** pphead)
{free(*pphead);*pphead = NULL;
}

3.總結

? ? ? ? 主要完成了單鏈表的插，刪，查等功能，編寫過程中掌握調試的基本方法。原代碼地址在我的gitee倉庫中，有需要可以下載查看。https://gitee.com/lisien123/c_learn/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/25-8-31%E5%8D%95%E9%93%BE%E8%A1%A8