链表（7.27）

3.3 链表的实现

3.3.1头插

原理图：

newnode为新创建的节点

实现：

//头插
//让新节点指向原来的头指针（节点），即新节点位于开头
newnode->next = plist;
//再让头指针（节点）指向新节点，新节点就成为了头节点
plist = newnode;

此操作在链表为空的情况下也能正常运行。

3.3.2尾插

原理：创建一个新节点，先通过局部变量 tail 遍历找到指向的下一个节点为空的节点（即倒数第二个节点），然后将该节点与新节点链接起来。

初步实现：

// 单链表尾插
//第一个参数为头指针的拷贝（形参）
void SListPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;//创建要插入的新节点SLTNode* newnode = BuySListNode(x);//遍历下一个节点指向为空的节点while (tail->next != NULL){tail = tail->next;}//将该节点与新节点链接起来tail->next = newnode;
}

phead,tail,newnode为局部变量，出了作用域就会自动销毁，而链表的节点存在于堆上，不会自动销毁。

上面的步骤是在原有链表的前提下进行的，如果链表为空呢？

需要让新节点充当头节点，也就是要让 plist（结构体指针）（头指针） 指向新节点,因此我们尝试将新创建的节点赋给头指针

if (phead == NULL){phead = newnode;}

但这个做法对吗，显然不对，形参是实参的一份临时拷贝，改变形参不影响实参，出了这个作用域，这两个指针就销毁了，plist也没有改变。

plist 是结构体类型的指针，要改变它的值，在函数中就需要传它的地址，也就是指针的地址。

//第一个参数为头指针的拷贝（形参）
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);//如果链表为空//*pphead==plistif (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;//创建要插入的新节点//遍历下一个节点指向为空的节点while (tail->next != NULL){tail = tail->next;}//将该节点与新节点链接起来tail->next = newnode;}
}

 总结：

改变结构体用结构体指针；

改变结构体指针用结构体二级指针；

3.3.3头插

本篇开头已经在函数外实现过了，现在在函数中实现一次。

每一次头插都要改变 plist 头指针，因此也需要传二重指针

// 单链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

3.3.4尾删

根据剩余节点的不同，分3种情况

1.链表为空

这是一种异常的情况，我们需要使用断言对参数加以限制，以防传空指针情况的出现。

assert(*pphead);

2.链表只剩一个节点

再删掉就为空，这时候就需要释放节点的空间，并将头指针置空，就涉及到了头指针的改变，需要引用二级指针。

    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }

3.链表中包含>1个节点

用 tail 找到末尾节点并将其删除，将倒数第二个节点置空，该情况下不需要二级指针。

原理图：

SLTNode* tailPre = NULL;
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tailPre = tail;
            tail = tail->next;
        }
        free(tail);
        tailPre->next = NULL;

3.3.5头删

让头指针指向第二个节点，将第一个节点释放。

// 单链表头删
void SListPopFront(SLTNode** pphead)
{assert(*pphead);//第二个节点SLTNode* newhead = (*pphead)->next;//释放第一个节点free(*pphead);//让第二个节点成为新的头节点*pphead = newhead;
}

3.3.6查找

在链表中查找值 x ，从头遍历一遍即可，遇到空节点停止。

// 单链表查找
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为节点的指针

根据插入的位置分在第一个节点之前插入（头插）和其余的正常插入：

头插：由于我们之前写过头插，这里我们可以直接复用，需要注意参数的传递和头插函数的参数保持一致，即我们需要改变的是头指针 plist，因此传它的地址（二级指针）；

正常插入：单链表的在某节点之前插入相对双链表是比较麻烦的，我们需要先通过遍历找到 pos 之前节点的指针 prev，即 prev->next==pos，然后再将代插入的节点和 prev 以及 pos 链接起来。

//在pos之前插入X,pos为节点的指针
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;}//待插入的新节点SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

3.3.8 在pos之后插入X 

 相比在 pos 前插入就容易多了，直接将待插入的新节点和 pos 以及 pos 后面的节点 pos->next 链接起来即可，链接的时候需要注意顺序，先链接后者，再链接前者，否则 pos->next 就被新节点覆盖，找不到了。

//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);//先链接新节点与pos之后的节点newnode->next = pos->next;//再链接pos与新节点pos->next = newnode;
}

 3.3.9 删除pos位置的值

仅仅头删比较特别，需要将目标节点释放掉，让头指针指向下一个节点。

其余情况下先遍历找到上一个节点 prev，然后释放掉 pos 节点，让 prev 指向下一个节点。

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos为头节点if (pos == *pphead){//直接复用，参数为二级指针SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next == pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

3.3.10 删除 pos 的下一个

 这个方法不能删除头节点，也不能删除尾节点。

//删除pos的后一个
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不能删尾assert(pos->next);//将pos的下一个节点保存下来SLTNode* posNext = pos->next;//将pos和下下个节点链接起来pos->next = posNext->next;//释放pos的下一个节点free(posNext);
}

3.3.11 顺序表的销毁

依旧使用一个 cur 指针来遍历，在释放节点的时候有两种方式

创建一个 next 指针来指向下一个节点，然后释放 cur，再让 cur 指向 next

记录前一个节点 del ，cur 移动到后一个节点之后，释放 del

// 顺序表销毁
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}//销毁完毕，将头指针置空*pphead = NULL;
}

例题：

给定一个无头单链表，要求删除 pos 位置的节点，该如何实现？

常规的方法行不通，我们需要另辟蹊径

 即用替换法，将 pos 下一个节点的值赋给 pos ，然后删除下一个节点，不过该方法存在一个缺陷是无法用来删除尾节点。

完整代码：

头文件

#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);
//开辟一个节点并赋值
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为节点的指针
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("请依次输入每个节点的值\n");//创建头指针SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val = 0;scanf("%d", &val);//开辟新节点SLTNode* newnode = BuySLTNode(val);//头插//让新节点指向原来的头指针（节点），即新节点位于开头newnode->next = plist;//再让头指针（节点）指向新节点，新节点就成为了头节点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;
}

实现文件

#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;}//结束，打印空printf("NULL\n");
}
//开辟节点并赋值
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;
}
// 单链表尾插
//第一个参数为头指针的拷贝（形参）
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);//如果链表为空//*pphead==plistif (*pphead == NULL){//改变结构体指针，用结构体二级指针*pphead = newnode;}else{SLTNode* tail = *pphead;//创建要插入的新节点//遍历下一个节点指向为空的节点while (tail->next != NULL){tail = tail->next;}//改变结构体用结构体指针，将该节点与新节点链接起来tail->next = newnode;}
}
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{//限制参数不为空assert(*pphead);//仅有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//有两个及以上节点的情况else{//尾节点的前一个节点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);//第二个节点SLTNode* newhead = (*pphead)->next;//释放第一个节点free(*pphead);//让第二个节点成为新的头节点*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为节点的指针
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;}//待插入的新节点SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);//先链接新节点与pos之后的节点newnode->next = pos->next;//再链接pos与新节点pos->next = newnode;
}
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos为头节点if (pos == *pphead){//直接复用，参数为二级指针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的下一个节点保存下来SLTNode* posNext = pos->next;//将pos和下下个节点链接起来pos->next = posNext->next;//释放pos的下一个节点free(posNext);
}
// 顺序表销毁
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}//销毁完毕，将头指针置空*pphead = NULL;
}