【数据结构与算法篇】双链表实现

【数据结构与算法篇】双链表实现（近300行实现代码）

🥕个人主页：开敲🍉

🔥所属专栏：数据结构与算法🍅

🌼文章目录🌼

1. List.h 头文件的声明

2. List.c 源文件的定义

3. Test.c 源文件的测试

1. List.h 头文件的声明

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LDataType;

typedef struct ListNode
{
    LDataType val;
    struct ListNode* next;
    struct ListNode* prev;
}LN;

//初始化
LN* LNInit();

//打印
void LNPrint(LN* phead);

//尾插
void LNPushBack(LN* phead, LDataType x);

//头插
void LNPushHead(LN* phead, LDataType x);

//尾删
void LNPopBack(LN* phead);

//头删
void LNPopHead(LN* phead);

//指定插入
void LNPushDesi(LN* head, int y, LDataType x);

//指定删除
void LNPopDesi(LN* phead, int y);

//查找
void LNFind(LN* phead, int y);

//更改
void LNChange(LN* phead, int y, LDataType x);

2. List.c 源文件的定义

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

//初始化
LN* LNInit()
{
    LN* phead = (LN*)malloc(sizeof(LN));
    if (phead == NULL)
    {
        exit(-1);
    }
    phead->val = -1;
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

//创建节点
LN* BuyNode(LDataType x)
{
    LN* pcur = (LN*)malloc(sizeof(LN));
    if (pcur == NULL)
    {
        exit(-1);
    }
    pcur->val = x;
    pcur->next = NULL;
    pcur->prev = NULL;
    return pcur;
}

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

//尾插
void LNPushBack(LN* phead, LDataType x)
{
    assert(phead);
    LN* pcur = BuyNode(x);
    pcur->next = phead;
    phead->prev->next = pcur;
    pcur->prev = phead->prev;
    phead->prev = pcur;
}

//头插
void LNPushHead(LN* phead, LDataType x)
{
    assert(phead);
    LN* pcur = BuyNode(x);
    phead->next->prev = pcur;
    pcur->next = phead->next;
    phead->next = pcur;
    pcur->prev = phead;
}

//尾删
void LNPopBack(LN* phead)
{
    assert(phead && phead->next!=phead);
    LN* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
}

//头删
void LNPopHead(LN* phead)
{
    assert(phead && phead->next!=phead);
    LN* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
}

//查找
LN* NodeFind(LN* phead, int y)
{
    LN* phead1 = phead->next;
    int count = 1;
    if (y == 0)
    {
        return NULL;
    }
    while (phead1 != phead)
    {
        if (count == y)
        {
            return phead1;
        }
        count++;
        phead1 = phead1->next;
    }
    return NULL;
}

//指定插入
void LNPushDesi(LN* phead, int y, LDataType x)
{
    assert(phead);
    LN* pget = NodeFind(phead, y);
    if (pget == NULL)
    {
        printf("无法在此处插入数据！\n");
        exit(-1);
    }
    LN* pcur = BuyNode(x);
    pcur->next = pget;
    pcur->prev = pget->prev;
    pget->prev->next = pcur;
    pget->prev = pcur;
}

//指定删除
void LNPopDesi(LN* phead, int y)
{
    assert(phead && phead->next != phead);
    LN* pget = NodeFind(phead,y);
    if (pget == NULL)
    {
        printf("无法在此处删除数据！\n");
        exit(-1);
    }
    pget->prev->next = pget->next;
    pget->next->prev = pget->prev;
    free(pget);
    pget = NULL;
}

//查找
void LNFind(LN* phead, int y)
{
    assert(phead && phead->next != phead);
    LN* pfind = NodeFind(phead, y);
    if (pfind == NULL)
    {
        printf("查找失败！\n");
    }
    printf("查找成功，该位置数据为:%d\n", pfind->val);
}

//更改
void LNChange(LN* phead, int y, LDataType x)
{
    assert(phead && phead->next != phead);
    LN* pget = NodeFind(phead, y);
    if (pget == NULL)
    {
        printf("更改失败！\n");
    }
    pget->val = x;
}

3. Test.c 源文件的测试

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

void ListTest()
{

    //初始化
    LN* plist = LNInit();

    //尾插
    LNPushBack(plist, 1);
    LNPushBack(plist, 2);
    LNPushBack(plist, 3);
    LNPushBack(plist, 4);
    LNPrint(plist);//打印

    //头插
    LNPushHead(plist, 0);
    LNPrint(plist);

    //尾删
    LNPopBack(plist);
    LNPrint(plist);

    //头删
    LNPopHead(plist);
    LNPrint(plist);

    //指定插入
    LNPushDesi(plist, 3, 10);
    LNPrint(plist);

    //指定删除
    LNPopDesi(plist, 4);
    LNPrint(plist);

    //查找
    LNFind(plist, 3);

    //更改
    LNChange(plist, 3, 1000);
    LNPrint(plist);
}

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