0
0

【数据结构】——双链表的实现（赋源码）

双链表的概念和结构

双链表的全称叫做：带头双向循环链表

它的结构示意图如下

注意：这⾥的“带头”跟前⾯我们说的单链表的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了读者们更好的理解就直接称为单链表的头结点。

带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”也可以认为是用来占位置滴！！！

双链表的实现

首先先在结构体当中输入需要的数据，则有如下的数据是需要的

结构体中的数据

typedef int LTDataType;//方便对数据类型进行统一的替换
typedef struct ListNode ListNode;//对结构体的名称重新命名交ListNode
struct ListNode
{
    LTDataType data;
    ListNode* next;
    ListNode* prev;
};

则上面的图可以变成这样

双链表新结点的创建及双链表的初始化

ListNode* LTBuyNode(LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//一个结构体的大小
    if (newnode == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode;

    return newnode;//返回头结点
}

链表的初始化需要一个创建的新的结点作为哨兵位

//void LTInit(ListNode** pphead)
//{
//    //创建一个头结点即“哨兵位”
//    *pphead = LTBuyNode(-1);
//}

ListNode* LTInit()
{
    ListNode* phead = LTBuyNode(-1);
    return phead;
}

//上面是两种初始化的方法
//第一种需要传递一个二级指针

在上面的代码当中，我们只需要创建一个头结点来保证第一个“头”存在即可。

插入
第一个参数传一级还是二级，要看phead指向的结点会不会改变
如果发生改变，那么pphead的改变要影响实参，传二级
如果不发生改变，pphead不会影响实参，传一级

双链表的尾插

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    //创建需要插入的结点
    //上面初始化的newnode是头结点，这个newnode是尾插的结点
    ListNode* newnode = LTBuyNode(x);

    newnode->next = phead;
    newnode->prev = phead->prev;

    phead->prev->next = newnode;
    phead->prev = newnode;
}

** 上面的顺序是不能改变的，否则无法让新结点找到原来链表的位置**

这边测试一下我们的尾插代码依次插入1 2 3 4

双链表的头插

//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = LTBuyNode(x);

    newnode->next = phead->next;
    newnode->prev = phead;

    phead->next->prev = newnode;
    phead->next = newnode;
}

头插和尾插是类似的 ，不过有一个特殊的地方

头插是头插在哨兵位和第一个真正的结点中间

同样的，上面的顺序位置是不能改变的

测试头插代码

这个代码是在上面尾插代码基础上的操作

双链表的尾删

//尾删
void LTPopBack(ListNode* phead)
{
    assert(phead);
    assert(!Empty(phead));

    ListNode* del = phead->prev;
    ListNode* prev = del->prev;

    prev->next = phead;
    phead->prev = prev;

    free(del);
    del = NULL;
}

这边仍然是在尾插的基础上的操作

这边我们进行了五次尾删，所以代码assert断言了！

将一次尾删注释，下面就是尾删的效果

双链表的头删

//头删
void LTPopFront(ListNode* phead)
{
    assert(phead);
    assert(!Empty(phead));
    ListNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;

    free(del);
    del = NULL;
}

这个仍然是在尾插的基础上操作的，如果继续删除，跟上面的情况一样assert断言报错

以上就是最基础的增删 ，下面开始加大难度！

双链表中查找数据pos

//找相同数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* pcur = phead->next;
    while (pcur != phead)
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

这边我们查找的是数据3，所以我们可以找到

这个在链表中没有数据6，所以我们没有找到相关的数据

在pos之后插入结点

这个和尾插以及头插其实是类似的，这里主要是寻找到pos结点，然后插入想要的数据

//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x)
{
    assert(pos);

    ListNode* newnode = LTBuyNode(x);

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

    pos->next->prev = newnode;
    pos->next = newnode;
}

在3的后面插入数据10

删除pos结点

​//删除指定位置节点
void LTErase(ListNode* pos)
{
    assert(pos);
    // pos->prev  pos   pos->next

    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;

    free(pos);
    pos = NULL;
}

​

双链表的销毁

这里我们提供了两种的销毁方法，两种方法基本是类似的

//销毁
void LTDesTroy(ListNode** pphead)
{
    assert(pphead && *pphead);
    ListNode* pcur = (*pphead)->next;
    while (pcur != *pphead)
    {
        ListNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    //销毁哨兵位结点
    free(*pphead);
    *pphead = NULL;
    pcur = NULL;
}
//为了更好的记忆，我们让销毁也传递一级指针
void LTDesTroy2(ListNode* phead)//传一级，需要手动将plist置为NULL
{
    assert(phead);
    ListNode* pcur = phead->next;
    while (pcur != phead)
    {
        ListNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead);
    phead = pcur = NULL;
}

最后我们将双向链表的源码附上

list.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;
typedef struct ListNode ListNode;
struct ListNode
{
    LTDataType data;
    ListNode* next;
    ListNode* prev;
};

ListNode* LTBuyNode(LTDataType x);
//为了保存接口的一致性
//
//初始化
//void LTInit(ListNode** pphead);
ListNode* LTInit();  

//
void LTPrint(ListNode* phead);

bool Empty(ListNode* phead);

//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级

//尾插
void LTPushBack(ListNode* phead, LTDataType x);

//头插
void LTPushFront(ListNode* phead, LTDataType x);

//尾删
void LTPopBack(ListNode* phead);

//头删
void LTPopFront(ListNode* phead);

//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x);

//删除指定位置的结点
void LTErase(ListNode* pos);

//找数据
ListNode* LTFind(ListNode* phead, LTDataType x);

//销毁
void LTDesTroy(ListNode** pphead);
void LTDesTroy2(ListNode* phead);//传一级，需要手动将plist置为NULL

List.c

#include"List.h"

ListNode* LTBuyNode(LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode;

    return newnode;
}
//初始化

//void LTInit(ListNode** pphead)
//{
//    //创建一个头结点即“哨兵位”
//    *pphead = LTBuyNode(-1);
//}
ListNode* LTInit()
{
    ListNode* phead = LTBuyNode(-1);
    return phead;
}

//打印
void LTPrint(ListNode* phead)
{
    ListNode* pcur = phead->next;
    while (pcur != phead)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

bool Empty(ListNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    //创建需要插入的结点
    ListNode* newnode = LTBuyNode(x);

    newnode->next = phead;
    newnode->prev = phead->prev;

    phead->prev->next = newnode;
    phead->prev = newnode;
}
//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = LTBuyNode(x);

    newnode->next = phead->next;
    newnode->prev = phead;

    phead->next->prev = newnode;
    phead->next = newnode;
}

//尾删
void LTPopBack(ListNode* phead)
{
    assert(phead);
    assert(!Empty(phead));

    ListNode* del = phead->prev;
    ListNode* prev = del->prev;

    prev->next = phead;
    phead->prev = prev;

    free(del);
    del = NULL;
}

//头删
void LTPopFront(ListNode* phead)
{
    assert(phead);
    assert(!Empty(phead));
    ListNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;

    free(del);
    del = NULL;
}
//找相同数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* pcur = phead->next;
    while (pcur != phead)
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x)
{
    assert(pos);

    ListNode* newnode = LTBuyNode(x);

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

    pos->next->prev = newnode;
    pos->next = newnode;
}

//删除指定位置节点
void LTErase(ListNode* pos)
{
    assert(pos);
    // pos->prev  pos   pos->next

    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;

    free(pos);
    pos = NULL;
}

//销毁
void LTDesTroy(ListNode** pphead)
{
    assert(pphead && *pphead);
    ListNode* pcur = (*pphead)->next;
    while (pcur != *pphead)
    {
        ListNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    //销毁哨兵位结点
    free(*pphead);
    *pphead = NULL;
    pcur = NULL;
}

void LTDesTroy2(ListNode* phead)
{
    assert(phead);
    ListNode* pcur = phead->next;
    while (pcur != phead)
    {
        ListNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead);
    phead = pcur = NULL;
}

test.c 

#include"List.h"
void test()
{
    创建双向链表变量
    //ListNode* plist = NULL;
    //LTInit(&plist);
    ListNode* plist = LTInit();

    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);

    ListNode* pos = LTFind(plist, 3);
    LTInsert(pos, 10);
    LTPrint(plist);

    pos = LTFind(plist, 3);
    LTErase(pos);
    LTPrint(plist);

    /*LTPopFront(plist);
    LTPrint(plist);
    LTPopFront(plist);
    LTPrint(plist);
    LTPopFront(plist);
    LTPrint(plist);
    LTPopFront(plist);
    LTPrint(plist);*/

    /*LTPushFront(plist, 1);
    LTPrint(plist);
    LTPushFront(plist, 2);
    LTPrint(plist);
    LTPushFront(plist, 3);
    LTPrint(plist);
    LTPushFront(plist, 4);
    LTPrint(plist);*/

    /*LTPopBack(plist);
    LTPrint(plist);
    LTPopBack(plist);
    LTPrint(plist);
    LTPopBack(plist);
    LTPrint(plist);
    LTPopBack(plist);
    LTPrint(plist);
    LTPopBack(plist);
    LTPrint(plist);*/

    /*if (pos == NULL)
    {
        printf("没有找到\n");
    }
    else
    {
        printf("找到了\n");
    }*/

    LTDesTroy(&plist);
    //LTDesTroy2(plist);
    //plist = NULL;

    
}

int main()
{
    test();
    return 0;
}
标签： 数据结构
本文转载自: https://blog.csdn.net/ZWW_zhangww/article/details/140646341
版权归原作者 酷酷的崽798 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】——双链表的实现（赋源码）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

249基于java ssm springboot安全生产培训管理系统学习课件（源码+文档+运行视频+讲解视频）

【Linux庖丁解牛】—软件安装&vim！

【花雕学编程】Arduino LVGL 之在不同平台创建相同的用户界面

基于电商大数据的商品推荐系统

UE5.4像素流及前端接入

Unity中接入讯飞语音（实时语音转写）WebAPI（非SDK）

springboot实现获取客户端IP地址

文章导航