算法开启小码农双链表血脉"/>
算法开启小码农双链表血脉
文章目录
- ==也欢迎大家能来到我们小伙伴的社区 [慧编程开源俱乐部]()==
- 双链表
- 双链表结构图
- 双链表节点
- 双链表初始化函数ListInit
- 双链表尾插函数ListPushBack
- 双链表打印函数ListPrint
- 双链表尾删函数ListPopBack
- 双链表头插函数ListPushFront
- 获得双链表节点函数BuyListNode
- 双链表头删函数ListPopFront
- 双链表查找函数ListFind
- 双链表插入函数ListInsert(pos之前插入因为c++中就是之前插入的)
- 双链表删除函数ListErase(删除pos)
- 双链表销毁函数ListDestroy(实际上我在这里写报错了,前面一个函数有bug,但是找到了)
- 代码
- DoubleList.h
- DoubleList.c
- test.c
- ==也欢迎大家能来到我们小伙伴的社区 [慧编程开源俱乐部]()==
也欢迎大家能来到我们小伙伴的社区 慧编程开源俱乐部
双链表
双链表结构图
双链表节点
typedef int LTDataType; //C++中的双链表是用list表示的typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
双链表初始化函数ListInit
//双链表初始化函数
LTNode* ListNodeInit()
{//创建一个双链表哨兵位头结点 不存储有效数据 循环LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->next = phead;phead->prev = phead;return phead;
}
双链表尾插函数ListPushBack
//双链表尾插函数
void ListNodePushBack(LTNode* phead, LTDataType x)
{assert(phead);//实际上phead永远也不可能是NULLLTNode* tail = phead->prev;LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
双链表打印函数ListPrint
//双链表打印函数
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
双链表尾删函数ListPopBack
//双链表尾删函数
void ListPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* tail = phead->prev;LTNode* cur = phead->prev;tail = tail->prev;tail->next = phead;phead->prev = tail;free(cur);
}
双链表头插函数ListPushFront
//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* next = phead->next;//在next和phead中间插一个节点/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;*/LTNode* newnode = BuyListNode(x);newnode->next = next;next->prev = newnode;phead->next = newnode;
}
既然我们头插尾插都遇到了添加节点,所以我们把添加节点的部分抽离出来重新封装一下
获得双链表节点函数BuyListNode
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-deIyyV9h-1635520574146)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211029191337400.png)]
//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
双链表头删函数ListPopFront
//双链表头删函数
void ListPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* next = phead->next;phead->next = next->next;next->next->prev = phead;free(next);
}
双链表查找函数ListFind
这个一般是和插入,删除配合使用
//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
双链表插入函数ListInsert(pos之前插入因为c++中就是之前插入的)
//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posprev = pos->prev;newnode->data = x;pos->prev = newnode;newnode->next = pos;newnode->prev = posprev;posprev->next = newnode;
}
双链表删除函数ListErase(删除pos)
//双链表删除函数
void ListErase(LTNode* pos)
{assert(pos && pos->next);LTNode* posnext = pos->next;LTNode* posprev = pos->prev;posnext->prev = posprev;posprev->next = posnext;free(pos);
}
双链表销毁函数ListDestroy(实际上我在这里写报错了,前面一个函数有bug,但是找到了)
//双链表销毁函数
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;while (tail != phead){LTNode* tailprev = tail->next;free(tail);tail = tailprev;}free(phead);phead = NULL;
}
代码
DoubleList.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType; //C++中的双链表是用list表示的typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//双链表初始化函数
extern LTNode* ListInit();
//双链表销毁函数
extern void ListDestroy(LTNode* phead);
//双链表尾插函数
extern void ListPushBack(LTNode* phead, LTDataType x);
//双链表打印函数
extern void ListPrint(LTNode* phead);
//双链表尾删函数
extern void ListPopBack(LTNode* phead);
//获得双链表节点函数
extern LTNode* BuyListNode(LTDataType x);
//双链表头插函数
extern void ListPushFront(LTNode* phead, LTDataType x);
//双链表头删函数
extern void ListPopFront(LTNode* phead);
//双链表查找函数
extern LTNode* ListFind(LTNode* phead, LTDataType x);
//双链表插入函数
extern void ListInsert(LTNode* pos, LTDataType x);
//双链表删除函数
extern void ListErase(LTNode* pos);
DoubleList.c
#define _CRT_SECURE_NO_WARNINGS 1#include "DoubleList.h"//双链表初始化函数
LTNode* ListInit()
{//创建一个双链表哨兵位头结点 不存储有效数据 循环LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->next = phead;phead->prev = phead;return phead;
}
//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
//双链表尾插函数
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);//实际上phead永远也不可能是NULLLTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;*/LTNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
//双链表打印函数
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
//双链表尾删函数
void ListPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* tail = phead->prev;LTNode* cur = phead->prev;tail = tail->prev;tail->next = phead;phead->prev = tail;free(cur);
}//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* next = phead->next;//在next和phead中间插一个节点/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;*/LTNode* newnode = BuyListNode(x);newnode->next = next;next->prev = newnode;phead->next = newnode;
}//双链表头删函数
void ListPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* next = phead->next;phead->next = next->next;next->next->prev = phead;free(next);
}//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posprev = pos->prev;newnode->data = x;pos->prev = newnode;newnode->next = pos;newnode->prev = posprev;posprev->next = newnode;
}
//双链表删除函数
void ListErase(LTNode* pos)
{assert(pos && pos->next);LTNode* posnext = pos->next;LTNode* posprev = pos->prev;posnext->prev = posprev;posprev->next = posnext;free(pos);
}
//双链表销毁函数
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;while (tail != phead){LTNode* tailprev = tail->next;free(tail);tail = tailprev;}free(phead);phead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"
void TestList1()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist, 10);ListPushFront(plist, 20);ListPushFront(plist, 30);ListPrint(plist);LTNode* p1 = ListFind(plist, 10);if (p1){ListInsert(p1, 100);}ListPrint(plist);LTNode* p2 = ListFind(plist, 20);if (p2){ListErase(p2);}ListPrint(plist);ListDestroy(plist);plist = NULL;
}int main()
{TestList1();return 0;
}
也欢迎大家能来到我们小伙伴的社区 慧编程开源俱乐部
更多推荐
算法开启小码农双链表血脉
发布评论