（数据结构）链表

1.单向链表

1.1单链表的认识

#pragma once
#include<stdio.h>
//SList.h
typedef int SLTDateType;

typedef struct SListNode
{
    SLTDateType data;
    struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);

定义一个struct SListNode类型的结构体，这个结构体的变量名是SLTNode，这个结构体（节点）有两个成员，一个用来存放SLTDateType（这里是int类型，可以根据实际需求更改）类型的数据，另一个成员是一个struct SListNode类型的指针，存放下一个节点的地址，就是指向下一个struct SListNode类型的结构体，下一个结构体也有一个指向下下个结构体的指针。

打印链表：

首先定义一个STList类型的指针cur存放头节点（链表第一个结构体）的地址，通过cur指针可以找到头节点存放的数据以及下一个节点的地址，这样就可以打印出链表的数据，最后一个节点的地址为空。

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//SList.c
void SListPrint(SLTNode* phead)
{
        SLTNode* cur = phead;
        while (cur != NULL)
        {
                printf("%d->", cur->data);
                cur = cur->next;
        }
}

1.2尾插

在链表尾部插入一个节点：

1.首先找到要插入链表的最后一个节点，此时tail->next=NULL

2.新开辟一个节点，初始化这个节点，这个新节点的指针域指向NULL

3.令原先的最后一个节点指向这个新节点

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode* phead, SLTDateType x)
{
        SLTNode* tail = phead;
        while (tail->next != NULL)
        {
                tail=tail->next;
        }
        
        SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
        newnode->data = x;
        newnode->next = NULL;

        tail->next = newnode;
}

需要注意

plist的值拷贝给phead，但是phead的改变不会影响plist，他们不是同一块空间，phead出了函数之后被销毁，plist还是空指针

要改变int*，要传int**。

通俗一点来说就是，如果我有一个int类型的变量a，我想通过函数传参的方式改变a的值，因为形参是实参的临时拷贝,如果形参直接传int类型，形参相当于是内存新开一块空间拷贝实参的内容，你所定义的函数操作的实际上是操作这块新空间；

所以我们如果想改变实参，需要传实参的地址，现在形参相当于是内存新开一块空间存放实参的地址，我们在函数中对这个地址进行解引用就能找到实参；

使用实例：

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
        SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
        newnode->data = x;
        newnode->next = NULL;

        if (*pphead == NULL)
        {
                *pphead = newnode;
        }
        else
        {
                //找到最后一个节点
                SLTNode* tail = *pphead;
                while (tail->next != NULL)
                {
                        tail = tail->next;
                }        
                tail->next = newnode;
        }
}

void test1()
{
        SLTNode* plist=NULL;
        SListPushBack(&plist, 1);
        SListPushBack(&plist, 2);
        SListPushBack(&plist, 3);
        SListPushBack(&plist, 4);
        SListPrint(plist);
}

int main()
{
        test1();
        return 0;
}

下面我再举一个例子加深一下对这个问题的理解：

情况1：这相当于把p存的地址的值传给形参，形参相当于实参的临时拷贝，会再开一块空间存形参，函数相当于把形参的值改为NULL但是不影响实参

情况2：

//情况2
void x(int* j)
{
        *j = NULL;
}

int main()
{
        int* p = 0x1234;
        x(p);
}

而对形参j解引用就找到了这块空间，而*j=NULL相当于把j指向这块空间的值置为0

情况3：

//情况3
void x(int** j)
{
        *j = NULL;
}

int main()
{
        int* p = 0x1234;
        x(&p);
}

地址是假设的）这次传的是p的地址，对j解引用 就可以找到p，从而改变p

1.3头插

新建一个节点，这个节点的指针指向这个链表的头节点

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
        //新建一个节点
        SLTNode* newnode = BuySTLNode(x);//这个是新建节点的函数
        if (newnode == NULL)
        {
                exit(-1);
        }
        newnode->next = *pphead;
        *pphead = newnode;        
}

1.4尾删

先看一下存在问题的写法

//尾删
void SListPopBack(SLTNode** pphead)
{
        SLTNode* tail = *pphead;
        //while(tail->next) 两种写法是等价的
        while (tail->next != NULL)
        {
                tail = tail->next;
        } 
        free(tail);
        tail = NULL;
}

没有把前一个节点的指针置空，造成野指针问题

除此之外，我们还要考虑如果链表为空，或者只有一个节点的情况

//尾删
void SListPopBack(SLTNode** pphead)
{
        assert(*pphead != NULL);//满足括号中的条件才可以继续往下执行

        if ((*pphead)->next == NULL)
        {
                free(*pphead);
                *pphead = NULL;
        }
        else
        {
                SLTNode* tail = *pphead;
                SLTNode* prev = NULL;//再定义一个指针
                //while(tail->next) 两种写法是等价的
                while (tail->next != NULL)
                {
                        prev = tail;//tail指向下一个节点之前，存放上一个节点的地址
                        tail = tail->next;
                }
                free(tail);
                tail = NULL;

                prev->next = NULL;//把前一个节点的指针置空
        }

        //这样写就可以少定义一个变量
        /*SLTNode* tail = *pphead;
        while (tail->next->next)
        {
                tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;*/
}

1.6寻找节点

//寻找数据x的节点
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
        SLTNode* cur = phead;
        while (cur)
        {
                if (cur->data == x)
                {
                        return cur;
                }
                else
                        cur = cur->next;
        }
        return NULL;
}

1.7在pos位置之前插入一个节点

//在pos位置之前插入一个节点
void SListInsert_Front(SLTNode** pphead, SLTDateType* pos, SLTDateType x)
{
        SLTNode* newnode = BuySTLNode(x);
        SLTNode* posPrev = *pphead;
        if (*pphead == pos)//单独分析pos是头节点的情况
        {
                newnode->next = *pphead;
                *pphead = newnode;
        }
        else
        {
         //找到pos的前一个位置
                while (posPrev->next != pos)
                        {
                                posPrev = posPrev->next;
                        }
                posPrev->next = newnode;
                newnode->next = pos;
        }        
}

1.8在pos位置之后插入一个节点

//在pos位置之后插入一个节点
void SListInsert_Afert(SLTNode* pos, SLTDateType x)
{
        SLTNode* newnode = BuySTLNode(x);

        newnode->next = pos->next;
        pos->next = newnode;

}

2.双向链表

链表的结构

哨兵位的头节点不存储有效数据

1.无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

LTNode* ListInit()
{
        //哨兵位头节点，单单改变形参不能让plist拿到头节点，可以用二级指针，也可以返回地址
        LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
        phead->next = phead;
        phead->prev = phead;

        return phead;
}

void ListPushBack(LTNode* phead, LTDateType x)
{
        assert(phead);

        LTNode* tail = phead->prev;//画图理解
        LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
        newnode->data = x;

        tail->next = newnode; //前一个节点的尾指向新节点
        newnode->prev = tail; //新节点的头指向前一个节点的尾
        newnode->next = phead; //新节点的尾指针指向哨兵位
        phead->prev = newnode; //哨兵位的头指针指向新节点
} 

这里指针指向的都是结构体（即节点），不是结构体的某个成员，如tail->next = newnode; 意思是前一个节点的尾指向新节点，而不是新节点的前节点指针域newnode->prev；

不改变phead，不用传二级指针

以下是双向链表的尾插，头插，尾删，头删等操作，和单向链表相差无几，重要的是学会画图分析

//List.h
typedef int LTDateType;

typedef struct ListNode
{
        LTDateType data;
        struct ListNode* next;
        struct ListNode* prev;
}LTNode;
//双向链表初始化
LTNode* ListInit();
//打印双向链表，从哨兵位的下一个节点开始打印，到哨兵位结束打印
void ListPrint(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//头删
void ListPopFront(LTNode* phead);
//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x);
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);
//删除pos位置
void ListErase(LTNode* pos);
void ListDestroy(LTNode* phead)；

//尾删
void ListPopBack(LTNode* phead)
{
        assert(phead);

        LTNode* tail = phead->prev;
        LTNode* tailnode = tail;

        tail = tail->prev;
        phead->prev = tail;
        tail->next = phead;
        free(tailnode);
}
//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
        LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
        newnode->data = x;

        newnode->next = phead->next;
        phead->next->prev = newnode;
        phead->next = newnode;
        newnode->prev = phead;
}
//头删
void ListPopFront(LTNode* phead)
{
        //记录头节点地址
        LTNode* headnode = phead->next;

        headnode->next->prev = phead;
        phead->next = headnode->next;
        free(headnode);
}

//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x)
{
        assert(phead);
        LTNode* cur = phead->next;
        while (cur != phead)
        {
                if (cur->data == x)
                {
                        return cur;
                }
        }
        return NULL;
}
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{
        LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
        newnode->data = x;

        pos->prev->next = newnode;
        newnode->prev = pos->prev;
        pos->prev = newnode;
        newnode->next = pos;
}
//删除pos位置
void ListErase(LTNode* pos)
{
        LTNode* prevnode = pos->prev;

        prevnode->next = pos->next;
        pos->next->prev = prevnode;
        free(pos);
}
void ListDestroy(LTNode* phead)
{
        assert(phead);

        LTNode* cur = phead->next;
        while (cur != phead)
        {
                LTNode* next = cur->next;
                free(cur);
                cur = next;
        }
        free(phead);
        phead = NULL;
}

有错误欢迎在评论区指出。

上一篇：

（数据结构）顺序表实现-增删查改-CSDN博客