【数据结构与算法篇】双链表实现（近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;
}
