哪個網(wǎng)站可以免費學(xué)設(shè)計百度平臺商家客服電話
3.3 鏈表的實現(xiàn)
3.3.1頭插
原理圖：
newnode為新創(chuàng)建的節(jié)點
實現(xiàn)：
//頭插
//讓新節(jié)點指向原來的頭指針（節(jié)點），即新節(jié)點位于開頭
newnode->next = plist;
//再讓頭指針（節(jié)點）指向新節(jié)點，新節(jié)點就成為了頭節(jié)點
plist = newnode;此操作在鏈表為空的情況下也能正常運行。
3.3.2尾插
原理：創(chuàng)建一個新節(jié)點，先通過局部變量 tail 遍歷找到指向的下一個節(jié)點為空的節(jié)點（即倒數(shù)第二個節(jié)點），然后將該節(jié)點與新節(jié)點鏈接起來。
初步實現(xiàn)：
// 單鏈表尾插
//第一個參數(shù)為頭指針的拷貝（形參）
void SListPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;//創(chuàng)建要插入的新節(jié)點SLTNode* newnode = BuySListNode(x);//遍歷下一個節(jié)點指向為空的節(jié)點while (tail->next != NULL){tail = tail->next;}//將該節(jié)點與新節(jié)點鏈接起來tail->next = newnode;
}phead,tail,newnode為局部變量，出了作用域就會自動銷毀，而鏈表的節(jié)點存在于堆上，不會自動銷毀。
上面的步驟是在原有鏈表的前提下進(jìn)行的，如果鏈表為空呢？
需要讓新節(jié)點充當(dāng)頭節(jié)點，也就是要讓?plist（結(jié)構(gòu)體指針）（頭指針）?指向新節(jié)點,因此我們嘗試將新創(chuàng)建的節(jié)點賦給頭指針
if (phead == NULL){phead = newnode;}但這個做法對嗎，顯然不對，形參是實參的一份臨時拷貝，改變形參不影響實參，出了這個作用域，這兩個指針就銷毀了，plist也沒有改變。
plist 是結(jié)構(gòu)體類型的指針，要改變它的值，在函數(shù)中就需要傳它的地址，也就是指針的地址。
//第一個參數(shù)為頭指針的拷貝（形參）
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);//如果鏈表為空//*pphead==plistif (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;//創(chuàng)建要插入的新節(jié)點//遍歷下一個節(jié)點指向為空的節(jié)點while (tail->next != NULL){tail = tail->next;}//將該節(jié)點與新節(jié)點鏈接起來tail->next = newnode;}
}?總結(jié)：
改變結(jié)構(gòu)體用結(jié)構(gòu)體指針；
改變結(jié)構(gòu)體指針用結(jié)構(gòu)體二級指針；
3.3.3頭插
本篇開頭已經(jīng)在函數(shù)外實現(xiàn)過了，現(xiàn)在在函數(shù)中實現(xiàn)一次。
每一次頭插都要改變 plist 頭指針，因此也需要傳二重指針
// 單鏈表的頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}3.3.4尾刪
根據(jù)剩余節(jié)點的不同，分3種情況
1.鏈表為空
這是一種異常的情況，我們需要使用斷言對參數(shù)加以限制，以防傳空指針情況的出現(xiàn)。
assert(*pphead);
2.鏈表只剩一個節(jié)點
再刪掉就為空，這時候就需要釋放節(jié)點的空間，并將頭指針置空，就涉及到了頭指針的改變，需要引用二級指針。
?? ?if ((*pphead)->next == NULL)
?? ?{
?? ??? ?free(*pphead);
?? ??? ?*pphead = NULL;
?? ?}
3.鏈表中包含>1個節(jié)點
用 tail 找到末尾節(jié)點并將其刪除，將倒數(shù)第二個節(jié)點置空，該情況下不需要二級指針。
原理圖：
SLTNode* tailPre = NULL;
?? ??? ?SLTNode* tail = *pphead;
?? ??? ?while (tail->next != NULL)
?? ??? ?{
?? ??? ??? ?tailPre = tail;
?? ??? ??? ?tail = tail->next;
?? ??? ?}
?? ??? ?free(tail);
?? ??? ?tailPre->next = NULL;
3.3.5頭刪
讓頭指針指向第二個節(jié)點，將第一個節(jié)點釋放。
// 單鏈表頭刪
void SListPopFront(SLTNode** pphead)
{assert(*pphead);//第二個節(jié)點SLTNode* newhead = (*pphead)->next;//釋放第一個節(jié)點free(*pphead);//讓第二個節(jié)點成為新的頭節(jié)點*pphead = newhead;
}3.3.6查找
在鏈表中查找值 x ，從頭遍歷一遍即可，遇到空節(jié)點停止。
// 單鏈表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{SLTNode* cur = plist;while (cur){//找到了就返回地址if (cur->data == x){return cur;}cur = cur->next;}//遍歷完了還沒找到return NULL;
}3.3.7?在pos之前插入X,pos為節(jié)點的指針
根據(jù)插入的位置分在第一個節(jié)點之前插入（頭插）和其余的正常插入：
頭插：由于我們之前寫過頭插，這里我們可以直接復(fù)用，需要注意參數(shù)的傳遞和頭插函數(shù)的參數(shù)保持一致，即我們需要改變的是頭指針 plist，因此傳它的地址（二級指針）；
正常插入：單鏈表的在某節(jié)點之前插入相對雙鏈表是比較麻煩的，我們需要先通過遍歷找到 pos 之前節(jié)點的指針 prev，即 prev->next==pos，然后再將代插入的節(jié)點和 prev 以及 pos 鏈接起來。
//在pos之前插入X,pos為節(jié)點的指針
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//pos不能為空assert(pos);//如果為頭插if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next ！= pos){prev = prev->next;}//待插入的新節(jié)點SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}3.3.8 在pos之后插入X?
?相比在 pos 前插入就容易多了，直接將待插入的新節(jié)點和 pos 以及 pos 后面的節(jié)點 pos->next 鏈接起來即可，鏈接的時候需要注意順序，先鏈接后者，再鏈接前者，否則 pos->next 就被新節(jié)點覆蓋，找不到了。
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);//先鏈接新節(jié)點與pos之后的節(jié)點newnode->next = pos->next;//再鏈接pos與新節(jié)點pos->next = newnode;
}?3.3.9 刪除pos位置的值
僅僅頭刪比較特別，需要將目標(biāo)節(jié)點釋放掉，讓頭指針指向下一個節(jié)點。
其余情況下先遍歷找到上一個節(jié)點 prev，然后釋放掉 pos 節(jié)點，讓 prev 指向下一個節(jié)點。
//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos為頭節(jié)點if (pos == *pphead){//直接復(fù)用，參數(shù)為二級指針SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next == pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}3.3.10 刪除 pos 的下一個
?這個方法不能刪除頭節(jié)點，也不能刪除尾節(jié)點。
//刪除pos的后一個
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不能刪尾assert(pos->next);//將pos的下一個節(jié)點保存下來SLTNode* posNext = pos->next;//將pos和下下個節(jié)點鏈接起來pos->next = posNext->next;//釋放pos的下一個節(jié)點free(posNext);
}3.3.11 順序表的銷毀
依舊使用一個 cur 指針來遍歷，在釋放節(jié)點的時候有兩種方式
創(chuàng)建一個 next 指針來指向下一個節(jié)點，然后釋放 cur，再讓 cur 指向 next
記錄前一個節(jié)點 del ，cur 移動到后一個節(jié)點之后，釋放 del
// 順序表銷毀
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}//銷毀完畢，將頭指針置空*pphead = NULL;
}
例題：
給定一個無頭單鏈表，要求刪除 pos 位置的節(jié)點，該如何實現(xiàn)？
常規(guī)的方法行不通，我們需要另辟蹊徑
?即用替換法，將 pos 下一個節(jié)點的值賦給 pos ，然后刪除下一個節(jié)點，不過該方法存在一個缺陷是無法用來刪除尾節(jié)點。
完整代碼：
頭文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
//打印鏈表
void SLTPrint(SLTNode* pahead);
//開辟一個節(jié)點并賦值
SLTNode* BuySLTNode(SLTDataType X);
// 單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
// 單鏈表的尾刪
void SLTPopBack(SLTNode** pphead);
// 單鏈表頭刪
void SLTPopFront(SLTNode** pphead);
//在pos之前插入X,pos為節(jié)點的指針
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x);
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos的后一個
void SLTEraseAfter(SLTNode* pos);
// 單鏈表查找
SLTNode* SLTFind(SLTNode* plist, SLTDataType x);
// 順序表銷毀
void SLTDestory(SLTNode** pphead);?測試文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void TestSList1()
{int n = 0;printf("請輸入鏈表的長度\n");scanf("%d", &n);printf("請依次輸入每個節(jié)點的值\n");//創(chuàng)建頭指針SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val = 0;scanf("%d", &val);//開辟新節(jié)點SLTNode* newnode = BuySLTNode(val);//頭插//讓新節(jié)點指向原來的頭指針（節(jié)點），即新節(jié)點位于開頭newnode->next = plist;//再讓頭指針（節(jié)點）指向新節(jié)點，新節(jié)點就成為了頭節(jié)點plist = newnode;}SLTPushBack(&plist, 100);SLTPrint(plist);
}
void TestSList2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);
}
void TestSList3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);// SLTPopBack(&plist);// SLTPrint(plist);
}
void TestSList4()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);//SLTPopFront(&plist);SLTPrint(plist);
}
void TestSList5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 3);SLTInsert(&plist, pos, 30);SLTPrint(plist);
}
void TestSList6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);
}void TestSList7()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){//SLTErase(&plist, pos);SLTEraseAfter(pos);pos = NULL;}SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);}
int main()
{//TestSList1();//TestSList2();//TestSList3();//TestSList4();//TestSList5();//TestSList5();TestSList7();return 0;
}實現(xiàn)文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}//結(jié)束，打印空printf("NULL\n");
}
//開辟節(jié)點并賦值
SLTNode* BuySLTNode(SLTDataType X)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = X;newnode->next = NULL;return newnode;
}
// 單鏈表尾插
//第一個參數(shù)為頭指針的拷貝（形參）
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);//如果鏈表為空//*pphead==plistif (*pphead == NULL){//改變結(jié)構(gòu)體指針，用結(jié)構(gòu)體二級指針*pphead = newnode;}else{SLTNode* tail = *pphead;//創(chuàng)建要插入的新節(jié)點//遍歷下一個節(jié)點指向為空的節(jié)點while (tail->next != NULL){tail = tail->next;}//改變結(jié)構(gòu)體用結(jié)構(gòu)體指針，將該節(jié)點與新節(jié)點鏈接起來tail->next = newnode;}
}
// 單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
// 單鏈表的尾刪
void SLTPopBack(SLTNode** pphead)
{//限制參數(shù)不為空assert(*pphead);//僅有一個節(jié)點的情況if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//有兩個及以上節(jié)點的情況else{//尾節(jié)點的前一個節(jié)點SLTNode* tailPre = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailPre = tail;//tail往后走之前賦給前一個指針tail = tail->next;}free(tail);tailPre->next = NULL;}
}
// 單鏈表頭刪
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);//第二個節(jié)點SLTNode* newhead = (*pphead)->next;//釋放第一個節(jié)點free(*pphead);//讓第二個節(jié)點成為新的頭節(jié)點*pphead = newhead;
}
// 單鏈表查找
SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{SLTNode* cur = plist;while (cur){//找到了就返回地址if (cur->data == x){return cur;}cur = cur->next;}//遍歷完了還沒找到return NULL;
}
//在pos之前插入X,pos為節(jié)點的指針
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//pos不能為空assert(pos);//如果為頭插if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//待插入的新節(jié)點SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);//先鏈接新節(jié)點與pos之后的節(jié)點newnode->next = pos->next;//再鏈接pos與新節(jié)點pos->next = newnode;
}
//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos為頭節(jié)點if (pos == *pphead){//直接復(fù)用，參數(shù)為二級指針SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next == pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}
//刪除pos的后一個
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不能刪尾assert(pos->next);//將pos的下一個節(jié)點保存下來SLTNode* posNext = pos->next;//將pos和下下個節(jié)點鏈接起來pos->next = posNext->next;//釋放pos的下一個節(jié)點free(posNext);
}
// 順序表銷毀
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}//銷毀完畢，將頭指針置空*pphead = NULL;
}