建网站培训学校,厦门建网站公司,被骗去国外做网站网站推广,中山网站建设模板招商目录
往期
1 - 带头双向循环链表(双链表)
1.1 - 接口声明
1.2 - 接口实现
1.2.1 - 双向链表初始化
1.2.2 - 动态申请一个结点
1.2.3 - 双向链表销毁
1.2.4 - 双向链表打印
1.2.5 - 双向链表判空
1.2.6 - 双向链表尾插
1.2.7 - 带头双向循环链表(双链表)
1.1 - 接口声明
1.2 - 接口实现
1.2.1 - 双向链表初始化
1.2.2 - 动态申请一个结点
1.2.3 - 双向链表销毁
1.2.4 - 双向链表打印
1.2.5 - 双向链表判空
1.2.6 - 双向链表尾插
1.2.7 - 双向链表尾删
1.2.8 - 双向链表头插
1.2.9 - 双向链表头删
1.2.10 - 双向链表查找
1.2.11 - 双向链表在pos的前面进行插入
1.2.12 - 双向链表删除pos位置的节点
2 - 顺序表和链表的区别
3 - 完整代码
3.1 - List.c
3.2 - List.h
3.3 - Test.c 往期
链表-单链表
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;
} 感谢大佬们支持
互三啦
