往期
1 -> 带头+双向+循环链表(双链表)
1.1 -> 接口声明
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct LTNode { LTDataType data; struct LTNode* next; struct LTNode* prev; }LTNode; // 双向链表初始化 LTNode* LTInit(); // 动态申请一个结点 LTNode* BuyLTNode(LTDataType x); // 双向链表销毁 void LTDestory(LTNode* phead); // 双向链表打印 void LTPrint(LTNode* phead); // 双向链表判空 bool LTEmpty(LTNode* phead); // 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x); // 双向链表尾删 void LTPopBack(LTNode* phead); // 双向链表头插 void LTPushFront(LTNode* phead, LTDataType x); // 双向链表头删 void LTPopFront(LTNode* phead); // 双向链表查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void LTErase(LTNode* pos);
1.2 -> 接口实现
1.2.1 -> 双向链表初始化
// 双向链表初始化 LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
1.2.2 -> 动态申请一个结点
// 动态申请一个结点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
1.2.3 -> 双向链表销毁
// 双向链表销毁 void LTDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
1.2.4 -> 双向链表打印
// 双向链表打印 void LTPrint(LTNode* phead) { assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); }
1.2.5 -> 双向链表判空
// 双向链表判空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }
1.2.6 -> 双向链表尾插
// 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; // 复用 // LTInsert(phead, x); }
// 尾插测试 void Test1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTDestory(plist); plist = NULL; }
1.2.7 -> 双向链表尾删
// 双向链表尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; // 复用 // LTErase(phead->prev); }
// 尾删测试 void Test2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTDestory(plist); plist = NULL; }
1.2.8 -> 双向链表头插
// 双向链表头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; // 复用 // LTInsert(phead->next, x); }
// 头插测试 void Test3() { LTNode* plist = LTInit(); LTPushFront(plist, 1); LTPushFront(plist, 2); LTPushFront(plist, 3); LTPushFront(plist, 4); LTPushFront(plist, 5); LTPrint(plist); LTDestory(plist); plist = NULL; }
1.2.9 -> 双向链表头删
// 双向链表头删 void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); // 复用 // LTErase(phead->next); }
// 头删测试 void Test4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTDestory(plist); plist = NULL; }
1.2.10 -> 双向链表查找
// 双向链表查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
1.2.11 -> 双向链表在pos的前面进行插入
// 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyLTNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
// 查找插入测试 void Test5() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTNode* pos = LTFind(plist, 3); if (pos) LTInsert(pos, 99); LTPrint(plist); LTDestory(plist); plist = NULL; }
1.2.12 -> 双向链表删除pos位置的节点
// 双向链表删除pos位置的节点 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
2 -> 顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持:O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
注：缓存利用率参考存储体系结构以及局部原理性。
3 -> 完整代码
3.1 -> List.c
#include "List.h" // 双向链表初始化 LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } // 动态申请一个结点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } // 双向链表销毁 void LTDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); } // 双向链表打印 void LTPrint(LTNode* phead) { assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); } // 双向链表判空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; } // 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; // 复用 // LTInsert(phead, x); } // 双向链表尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; // 复用 // LTErase(phead->prev); } // 双向链表头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; // 复用 // LTInsert(phead->next, x); } // 双向链表头删 void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); // 复用 // LTErase(phead->next); } // 双向链表查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyLTNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
3.2 -> List.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct LTNode { LTDataType data; struct LTNode* next; struct LTNode* prev; }LTNode; // 双向链表初始化 LTNode* LTInit(); // 动态申请一个结点 LTNode* BuyLTNode(LTDataType x); // 双向链表销毁 void LTDestory(LTNode* phead); // 双向链表打印 void LTPrint(LTNode* phead); // 双向链表判空 bool LTEmpty(LTNode* phead); // 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x); // 双向链表尾删 void LTPopBack(LTNode* phead); // 双向链表头插 void LTPushFront(LTNode* phead, LTDataType x); // 双向链表头删 void LTPopFront(LTNode* phead); // 双向链表查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void LTErase(LTNode* pos);
3.3 -> Test.c
#include "List.h" // 尾插测试 void Test1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTDestory(plist); plist = NULL; } // 尾删测试 void Test2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTDestory(plist); plist = NULL; } // 头插测试 void Test3() { LTNode* plist = LTInit(); LTPushFront(plist, 1); LTPushFront(plist, 2); LTPushFront(plist, 3); LTPushFront(plist, 4); LTPushFront(plist, 5); LTPrint(plist); LTDestory(plist); plist = NULL; } // 头删测试 void Test4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTDestory(plist); plist = NULL; } // 查找插入测试 void Test5() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTNode* pos = LTFind(plist, 3); if (pos) LTInsert(pos, 99); LTPrint(plist); LTDestory(plist); plist = NULL; } int main() { return 0; }
感谢大佬们支持！！！
互三啦！！！
