- 双链表结构图
- 双链表节点
- 双链表初始化函数ListInit
- 双链表尾插函数ListPushBack
- 双链表打印函数ListPrint
- 双链表尾删函数ListPopBack
- 双链表头插函数ListPushFront
- 获得双链表节点函数BuyListNode
- 双链表头删函数ListPopFront
- 双链表查找函数ListFind
- 双链表插入函数ListInsert（pos之前插入因为c++中就是之前插入的）
- 双链表删除函数ListErase（删除pos）
- 双链表销毁函数ListDestroy(实际上我在这里写报错了，前面一个函数有bug，但是找到了)
双链表
双链表结构图
双链表节点
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永远也不可能是NULL LTNode* 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永远也不可能是NULL LTNode* 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; }
