0
0

双向链表(数据结构)(C语言)

概念

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其它结点。

带头双向循环链表的实现

前情提示

**List.h **用于 引用的头文件、双向链表的定义、函数的声明。

**List.c **用于 函数的定义。

**Test.c **用于 双向链表功能的测试。

双向链表的结构体定义

在List.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突

//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;//假设结点的数据域类型为 int
//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
//（比如我晚点想存double类型的数据，我就直接将 int 改为 double )

// 带哨兵位双向循环链表的结构体定义
typedef struct ListNode
{
    struct ListNode* prev;//前驱指针域:存放上一个结点的地址
    struct ListNode* next;//后继指针域:存放下一个结点的地址
    LTDataType data;//数据域
}LTNode;
//struct 关键字和 ListNode 一起构成了这个结构类型
//typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode 
//现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量

双向链表的初始化

在List.h下

// 双向链表的初始化

// 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化
// 即：LTNode* plist = NULL;
// 那为什么顺序表、带头双向循环链表有呢？
// 因为顺序表、带头双向循环链表的结构并不简单，
// 如:    顺序表顺序表为空size要为0,还要看capacity是否要开空间,
// 若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
//          带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
LTNode* LTInit();

在List.c下

#include"List.h"//别忘了

//动态申请一个结点
LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)//如果malloc失败
    {
        perror("malloc fail");
        return NULL;
    }
    //如果malloc成功
    //初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误
    node->next = NULL;
    node->prev = NULL;
    node->data = x;

    return node;
}

// 双向链表的初始化
LTNode* LTInit()
{
    LTNode* phead = BuyListNode(-1);//创建哨兵位
    //自己指向自己
    phead->next = phead;
    phead->prev = phead;

    return phead;
}

关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考

无头单向非循环链表结构太简单了，初始化只需直接赋空指针，无需单独写一个函数进行初始化。

即：LTNode* plist = NULL;

那为什么顺序表、带头双向循环链表有单独写一个函数进行初始化呢？
因为顺序表、带头双向循环链表的结构并不简单。
如:

顺序表顺序表为空size要为0,还要看capacity是否要开空间,若不开空间capacity=0,指针要给空，若开空间,还要检查malloc是否成功。

带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己。

顺序表和双向循环链表的初始化有点复杂,最好构建一个函数。

双向链表在pos位置之前插入x

在List.h下

// 双向链表在pos位置之前进行插入
void LTInsert(LTNode* pos, LTDataType x);

在List.c下

// 双向链表在pos位置之前进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);//pos肯定不为空

    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点

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

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

双向链表的打印

在List.h下

// 双向链表打印
void LTPrint(LTNode* phead);

在List.c下

// 双向链表打印
void LTPrint(LTNode* phead)
{
    assert(phead);//有哨兵位
    printf("<=>phead<=>");
    LTNode* cur = phead->next;//cur指向第一个要打印的结点
    while (cur != phead)//cur等于头结点时打印就结束了
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

在Test.c下

#include"List.h"//别忘了

//测试函数
void TestList1()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);
}

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

双链表删除pos位置的结点

在List.h下

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

在List.c下

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
    assert(pos);//pos肯定不为空

    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;

    posprev->next = posnext;
    posnext->prev = posprev;

    free(pos);
    pos = NULL;
    //这个置空其实已经没有意义了，形参的改变不会改变实参
}

在Test.c下

//测试函数
void TestList1()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTErase(plist->next);
    LTPrint(plist);

}

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

双向链表的尾插

在List.h下

//双向链表优于单链表的点——不需要找尾、二级指针
//（我们改的不是结构体的指针，改的是结构体的变量）
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);

在List.c下

**法一:（便于新手更好地理解双向链表的尾插） **

// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位
    
    //法一:(便于新手更好地理解双向链表的尾插)
    //一步就可完成链表为空/不为空的尾插——因为有哨兵位
    LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
    LTNode* tail = phead->prev;

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

法二：函数复用（简单方便）

// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    //法二:函数复用（简单方便）
    LTInsert(phead, x);
}

关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考

单链表改变的是结构体的指针，双向链表改变的是结构体的变量

二级指针和一级指针的区别在于指针所指向变量的层级不同，一级指针指向的是结构体的变量，而二级指针指向的是结构体指针的地址。
单链表中，在进行链表结点的删除或插入操作时，需要更新结点之间的指针指向。若使用一级指针，则操作会直接改变指向结点的指针，很难实现目标。因此需要传递二级指针，让函数能够修改指向结点指针的地址，也就是修改之前结点指针变量存放的地址。
而双向链表中，每个结点除了保存指向下一结点的指针外，还有保存指向上一结点的指针，结点之间的双向指针关系使得结点的插入和删除操作更加方便。双向链表不需要传递二级指针，因为在结点的删除和插入操作中，只需要先修改当前结点前后结点的指针，无需直接改变前后结点指针变量存放的地址。
综上所述，单链表只有指向下一结点的指针，通过传递二级指针来修改结点之间的指针关系，使得操作更加灵活；而双向链表的结点之间有双向指针关系，无需直接改变前后结点指针变量存放的地址，因此只需要传递一级指针即可。

单链表（对比）：

在Test.c下

//测试函数
void TestList2()
{
    LTNode* plist = LTInit();
    LTPushBack(plist, 5);
    LTPushBack(plist, 6);
    LTPushBack(plist, 7);
    LTPushBack(plist, 8);
    LTPrint(plist);
}

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

双向链表的判空

在尾删/头删之前，我们要先判断链表是否为空。

在List.h下

// 双向链表的判空
bool LTEmpty(LTNode* phead);

在List.c下

// 双向链表的判空
bool LTEmpty(LTNode* phead)
{
    assert(phead);

    return phead->next == phead;
    //两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
}

双向链表的尾删

在List.h下

// 双向链表的尾删
void LTPopBack(LTNode* phead);

在List.c下

法一：（便于新手更好地理解双向链表的尾删）

// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
    assert(phead);//有哨兵位
    assert(!LTEmpty(phead));//判空

    //法一：（便于新手更好地理解双向链表的尾删）
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;

    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

法二：函数复用（简单方便）

// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
    assert(phead);//有哨兵位
    assert(!LTEmpty(phead));//判空
    
    //法二:函数复用
    LTErase(phead->prev);
}

在Test.c下

//测试函数
void TestList2()
{
    LTNode* plist = LTInit();
    LTPushBack(plist, 5);
    LTPushBack(plist, 6);
    LTPushBack(plist, 7);
    LTPushBack(plist, 8);
    LTPrint(plist);

    LTPopBack(plist);
    LTPopBack(plist);
    LTPrint(plist);
}

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

双向链表的头插

在List.h下

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);

在List.c下

法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
    
    //法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）
    //顺序很重要！！！
    newnode->next = phead->next;
    phead->next->prev = newnode;

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

法二:多用了first记录第一个结点的位置（便于新手更好地理解双向链表的头插）

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);//哨兵位

    LTNode* newnode = BuyListNode(x);//创建一个要插入的结点

    //法二：多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）
    LTNode* first = phead->next;
    phead->next = newnode;
    newnode->prev = phead;

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

法三:函数复用（简单方便）

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位
    
    //法三:函数复用（简单方便）
    LTInsert(phead->next, x);
}

在Test.c下

//测试函数
void TestList3()
{
    LTNode* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPrint(plist);
}

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

双向链表的头删

在List.h下

// 双向链表头删
void LTPopFront(LTNode* phead);

在List.c下

法一:（便于新手更好地理解双向链表的头删）

// 双向链表头删
void LTPopFront(LTNode* phead)
{
    assert(phead);//有哨兵位
    assert(!LTEmpty(phead));//判空
    
    //法一:（便于新手更好地理解双向链表的头删）
    LTNode* head = phead->next;
    LTNode* headnext = head->next;

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

    free(head);
    head = NULL;
}

**法二:函数复用（简单方便） **

// 双向链表头删
void LTPopFront(LTNode* phead)
{
    assert(phead);//有哨兵位
    assert(!LTEmpty(phead));//判空
    
    //法二:函数复用（简单方便）
    LTErase(phead->next);
}

在Test.c下

//测试函数
void TestList3()
{
    LTNode* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPrint(plist);

    LTPopFront(plist);
    LTPopFront(plist);
    LTPrint(plist);
}

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

双向链表查找值为x的结点

在List.h下

// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x);

在List.c下

// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    LTNode* cur = phead->next;
    while (cur != phead)//让cur去遍历
    {
        if (cur->data == x)//如果找到
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//如果没找到
}

在Test.c下

//测试函数
TestList4()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTNode* pos = LTFind(plist, 3);
    if (pos)
    {
        LTErase(pos);
        pos = NULL;
    }

    LTPrint(plist);
}

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

双向链表的销毁

在List.h下

// 双向链表的销毁
void LTDestory(LTNode* phead);

在List.c下

// 双向链表的销毁
void LTDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;//让cur遍历
    while (cur != phead)
    {
        LTNode* curnext = cur->next;
        free(cur);
        cur = curnext;
    }
    free(phead);
    phead = NULL;
    //这个置空其实已经没有意义了，形参的改变不会改变实参
    //我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
}

在Test.c下

//测试函数
TestList4()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTNode* pos = LTFind(plist, 3);
    if (pos)
    {
        LTErase(pos);
        pos = NULL;
    }
    LTPrint(plist);

    LTDestory(plist);
    plist = NULL;//在这里置空
}

双向链表的修改

在List.h下

// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x);

在List.c下

// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x)
{
    assert(pos);
    pos->data = x;
}

在Test.c下

//测试函数
TestList5()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTModify(plist->next,5);
    LTPrint(plist);
}

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

双向链表删除值为x的结点

在List.h下

// 双向链表删除值为x的结点
void LTRemove(LTNode* phead,LTDataType x);

在List.c下

// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位
    LTNode* pos = phead->next;
    while (pos != phead)
    {
        pos = LTFind(phead, x);
        if (pos == NULL)//如果遍历完
        {
            return NULL;
        }
        LTErase(pos);
        pos = pos->next;
    }
}

在Test.c下

TestList6()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 3);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTInsert(plist, 3);
    LTPrint(plist);

    LTRemove(plist, 3);
    LTPrint(plist);
}

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

双向链表计算结点总数(不计phead)

在List.h下

// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead);

在List.c下

// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead)
{
    assert(phead);//有哨兵位

    int count = 0;//count来计数
    LTNode* cur = phead->next;//让cur去遍历
    while (cur != phead)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

在Test.c下

TestList6()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 3);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTInsert(plist, 3);
    LTPrint(plist);

    LTRemove(plist, 3);
    LTPrint(plist);

    printf("%d\n", LTTotal(plist));
}

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

双向链表获取第i位置的结点

在List.h下

// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i);

在List.c下

// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i)
{
    assert(phead);//有哨兵位

    int length = LTTotal(phead);
    LTNode* cur = phead->next;
    if (i == 0)
    {
        return phead;
    }
    else if (i<0 || i>length)//位置不合法
    {
        return NULL;
    }
    else if (i <= (length / 2))//从表头开始遍历
    {
        cur = phead->next;
        for (int count = 1; count < i; count++)
        {
            cur = cur->next;
        }
    }
    else//从表尾开始遍历
    {
        cur = phead->prev;
        for (int count = 1; count <= length - i; count++)
        {
            cur = cur->prev;
        }
    }
    return cur;
}

在Test.c下

//测试函数
TestList7()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 5);
    LTInsert(plist, 6);
    LTInsert(plist, 7);
    LTInsert(plist, 8);
    LTInsert(plist, 9);
    LTPrint(plist);

    LTNode* pos = LTGet(plist,3);
    if (pos)
    {
        LTErase(pos);
        pos = NULL;
    }
    LTPrint(plist);
}

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

双向链表的清空

在List.h下

// 双向链表的清空
void LTClean(LTNode* phead);

在List.c下

// 双向链表的清空
void LTClear(LTNode* phead)
{
    assert(phead);//有哨兵位

    while (!LTEmpty(phead))//如果不为空就一直头删
    {
        LTPopFront(phead);
    }
}

在Test.c下

//测试函数
TestList8()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 5);
    LTInsert(plist, 6);
    LTInsert(plist, 7);
    LTInsert(plist, 8);
    LTInsert(plist, 9);
    LTPrint(plist);

    LTClear(plist);
    LTPrint(plist);
}

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

总代码（想直接看结果的可以看这里）

在List.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突

//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;//假设结点的数据域类型为 int
//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
//（比如我晚点想存double类型的数据，我就直接将 int 改为 double )

// 带哨兵位双向循环链表的结构体定义
typedef struct ListNode
{
    struct ListNode* prev;//前驱指针域:存放上一个结点的地址
    struct ListNode* next;//后继指针域:存放下一个结点的地址
    LTDataType data;//数据域
}LTNode;
//struct 关键字和 ListNode 一起构成了这个结构类型
//typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode 
//现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量

// 双向链表的初始化

// 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化
// 即：LTNode* plist = NULL;
// 那为什么顺序表、带头双向循环链表有呢？
// 因为顺序表、带头双向循环链表的结构并不简单，
// 如:顺序表顺序表为空size要为0,还要看capacity是否要开空间,
//若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
// 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
LTNode* LTInit();

// 双向链表在pos位置之前进行插入x
void LTInsert(LTNode* pos, LTDataType x);

// 双向链表的打印
void LTPrint(LTNode* phead);

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

//双向链表优于单链表的点——不需要找尾、二级指针
// （我们改的不是结构体的指针，改的是结构体的变量）
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);

// 双向链表的判空
bool LTEmpty(LTNode* phead);

// 双向链表的尾删
void LTPopBack(LTNode* phead);

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);

// 双向链表头删
void LTPopFront(LTNode* phead);

// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x);

// 双向链表的销毁
void LTDestory(LTNode* phead);

// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x);

// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x);

// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead);

// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i);

// 双向链表的清空
void LTClear(LTNode* phead);

在List.c下

#include"List.h"

//动态申请一个结点
LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)//如果malloc失败
    {
        perror("malloc fail");
        return NULL;
    }
    //如果malloc成功
    //初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误
    node->next = NULL;
    node->prev = NULL;
    node->data = x;

    return node;
}

// 双向链表的初始化
LTNode* LTInit()
{
    LTNode* phead = BuyListNode(-1);
    //自己指向自己
    phead->next = phead;
    phead->prev = phead;

    return phead;
}

// 双向链表在pos位置之前进行插入x
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);//pos肯定不为空

    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点

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

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

// 双向链表的打印
void LTPrint(LTNode* phead)
{
    assert(phead);//有哨兵位
    printf("<=>phead<=>");
    LTNode* cur = phead->next;//cur指向第一个要打印的结点
    while (cur != phead)//cur等于头结点时打印就结束了
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
    assert(pos);//pos肯定不为空

    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;

    posprev->next = posnext;
    posnext->prev = posprev;

    free(pos);
    pos = NULL;
    //这个置空其实已经没有意义了，形参的改变不会改变实参
}

// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    //法一:（便于新手更好地理解双向链表的尾插）
    //一步就可完成链表为空/不为空的尾插
    //LTNode* newnode = BuyListNode(x);
    //LTNode* tail = phead->prev;

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

    //法二:函数复用（简单方便）
    LTInsert(phead, x);
}

// 双向链表的判空
bool LTEmpty(LTNode* phead)
{
    assert(phead);

    return phead->next == phead;
    //两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
}

// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
    assert(phead);//有哨兵位

    //法一:（便于新手更好地理解双向链表的尾删）
    //assert(!LTEmpty(phead));//判空

    //LTNode* tail = phead->prev;
    //LTNode* tailPrev = tail->prev;

    //tailPrev->next = phead;
    //phead->prev = tailPrev;
    //free(tail);
    //tail = NULL;

    //法二:函数复用
    LTErase(phead->prev);
}

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    //LTNode* newnode = BuyListNode(x);//创建一个要插入的结点

    //法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）
    //newnode->next = phead->next;
    //phead->next->prev = newnode;

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

    //法二:多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）
    //LTNode* first = phead->next;
    //phead->next = newnode;
    //newnode->prev = phead;

    //newnode->next = first;
    //first->prev = newnode;

    //法三:函数复用(简单方便)
    LTInsert(phead->next, x);
}

// 双向链表头删
void LTPopFront(LTNode* phead)
{
    assert(phead);//有哨兵位
    assert(!LTEmpty(phead));//判空

    //法一:（便于新手更好地理解双向链表的头删）
    //LTNode* head = phead->next;
    //LTNode* headnext = head->next;

    //phead->next = headnext;
    //headnext->prev = phead;

    //free(head);
    //head = NULL;

    //法二:函数复用（简单方便）
    LTErase(phead->next);
}

// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位

    LTNode* cur = phead->next;
    while (cur != phead)//让cur去遍历
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 双向链表的销毁
void LTDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* curnext = cur->next;
        free(cur);
        cur = curnext;
    }
    free(phead);
    phead = NULL;
    //这个置空其实已经没有意义了，形参的改变不会改变实参
    //我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
}

// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x)
{
    assert(pos);//pos肯定不为空
    pos->data = x;
}

// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x)
{
    assert(phead);//有哨兵位
    LTNode* pos = phead->next;
    while (pos != phead)
    {
        pos = LTFind(phead, x);
        if (pos == NULL)//如果遍历完
        {
            return NULL;
        }
        LTErase(pos);
        pos = pos->next;
    }
}

// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead)
{
    assert(phead);//有哨兵位

    int count = 0;//count来计数
    LTNode* cur = phead->next;//让cur去遍历
    while (cur != phead)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i)
{
    assert(phead);//有哨兵位

    int length = LTTotal(phead);
    LTNode* cur = phead->next;
    if (i == 0)
    {
        return phead;
    }
    else if (i<0 || i>length)//位置不合法
    {
        return NULL;
    }
    else if (i <= (length / 2))//从表头开始遍历
    {
        cur = phead->next;
        for (int count = 1; count < i; count++)
        {
            cur = cur->next;
        }
    }
    else//从表尾开始遍历
    {
        cur = phead->prev;
        for (int count = 1; count <= length - i; count++)
        {
            cur = cur->prev;
        }
    }
    return cur;
}

// 双向链表的清空
void LTClear(LTNode* phead)
{
    assert(phead);//有哨兵位

    while (!LTEmpty(phead))//如果不为空就一直头删
    {
        LTPopFront(phead);
    }
}

在Test.c下

#include"List.h"

//测试函数
void TestList1()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTErase(plist->next);
    LTPrint(plist);

}

//测试函数
void TestList2()
{
    LTNode* plist = LTInit();
    LTPushBack(plist, 5);
    LTPushBack(plist, 6);
    LTPushBack(plist, 7);
    LTPushBack(plist, 8);
    LTPrint(plist);

    LTPopBack(plist);
    LTPopBack(plist);
    LTPrint(plist);

}

//测试函数
void TestList3()
{
    LTNode* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPrint(plist);

    LTPopFront(plist);
    LTPopFront(plist);
    LTPrint(plist);
}

//测试函数
TestList4()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTNode* pos = LTFind(plist, 3);
    if (pos)
    {
        LTErase(pos);
        pos = NULL;
    }
    LTPrint(plist);

    LTDestory(plist);
    plist = NULL;//在这里置空
}

//测试函数
TestList5()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 2);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTPrint(plist);

    LTModify(plist->next, 5);
    LTPrint(plist);

}

TestList6()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 1);
    LTInsert(plist, 3);
    LTInsert(plist, 3);
    LTInsert(plist, 4);
    LTInsert(plist, 3);
    LTPrint(plist);

    LTRemove(plist, 3);
    LTPrint(plist);

    printf("%d\n", LTTotal(plist));
}

//测试函数
TestList7()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 5);
    LTInsert(plist, 6);
    LTInsert(plist, 7);
    LTInsert(plist, 8);
    LTInsert(plist, 9);
    LTPrint(plist);

    LTNode* pos = LTGet(plist, 3);
    if (pos)
    {
        LTErase(pos);
        pos = NULL;
    }
    LTPrint(plist);

    LTClear(plist);
    LTPrint(plist);
}

//测试函数
TestList8()
{
    LTNode* plist = LTInit();
    LTInsert(plist, 5);
    LTInsert(plist, 6);
    LTInsert(plist, 7);
    LTInsert(plist, 8);
    LTInsert(plist, 9);
    LTPrint(plist);

    LTClear(plist);
    LTPrint(plist);
}

int main()
{
    //TestList1();
    //TestList2();
    //TestList3();
    //TestList4();
    //TestList5();
    //TestList6();
    //TestList7();
    TestList8();
    return 0;
}

欢迎指正❀

标签： 链表 数据结构 c语言
本文转载自: https://blog.csdn.net/outdated_socks/article/details/130413379
版权归原作者 outdated_socks 所有， 如有侵权，请联系我们删除。
登录后发布评论

“双向链表(数据结构)(C语言)”的评论:

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

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航