| 【数据结构】线性表 | 您所在的位置：网站首页 › 文件链接结构的缺点是 › 【数据结构】线性表 |
【数据结构】线性表
|
文章目录
带头双向循环链表带头双向循环链表主体结构带头双向循环链表操作函数介绍带头双向循环链表操作函数实现带头双向循环链表的初始化函数：打印函数带头双向循环链表插入函数：指定结点后插入和查找函数头插尾插
带头双向循环链表删除函数指定结点删除头删尾删
带头双向循环链表修改函数销毁带头双向循环链表
源代码文件test.cDList.cDLlist.h
撒花
带头双向循环链表
带头双向循环链表的优点
1.支持任意位置时间复杂度为O(1)的插入和删除。 2.按照需求申请释放空间，无需担心空间不够用，无需担心浪费。 3.带头可以省去链表为空时的判断，可以使代码更加简约 带头双向循环链表的缺点1.不可以进行下标随机访问。 2.缓存利用率低 带头双向循环链表是线性表的一种，带头双向循环链表是链式存储的线性表，不同于顺序表，链表在内存空间中不连续。 带头：带头就是带哨兵位，可以省链表为空时进行的判断。 双向：由结构体内的next指针下一条数据进行链接，由prev对前一条数据进行链接🧐。 循环：以循环方式进行链接，头的（前一个）prev是尾，尾的next（后一个）是头。 PS:需要源码直接通过目录跳转到最后 带头双向循环链表主体结构默认大小与扩容大小还有类型都可以是任意大小或类型 typedef int DListDataType; //数据类型 typedef struct ListNode { DListDataType data; struct ListNode* prev; //指针指向前一个结点 struct ListNode* next; //指针指向后一个结点 }LTNode;
为了代码方便阅读，将带头双向循环链表操作函数全部放在LinkedList.c文件中，将头文件放在LinkedList.h，测试文件test.c 😮 带头双向循环链表操作函数实现为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试。 带头双向循环链表的初始化函数： LTNode* Phead = InitLTNode(); //初始化哨兵位 LTNode* BuyNewNode(DListDataType x) //开辟一个新结点 { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } LTNode* InitLTNode() { LTNode* phead = BuyNewNode(-1); phead->next = phead; phead->prev = phead; return phead; }必须先进行初始化哨兵位，将哨兵位指向自己形成循环 打印函数先写出打印函数，方便进行调试 void print(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("head"); while (cur!=phead) { printf("->%d", cur->data); cur = cur->next; } printf("\n"); } 带头双向循环链表插入函数： 指定结点后插入和查找函数两个函数可以配合使用，使用LTFind查找到需要插入的位置，然后使用ListInsert进行更改 LTNode* LTFind(LTNode* phead, DListDataType x) { assert(phead); LTNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } LTNode* BuyNewNode(DListDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } void ListInsert(LTNode* pos,DListDataType x) { assert(pos); LTNode* newnode = BuyNewNode(x); LTNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
头插将新结点插入到哨兵位后面的结点 这里面有一种简单的写法，就是直接复用ListInsert，将哨兵位后面的结点传过去，也是头插的效果 void ListPushFront(LTNode* phead, DListDataType x) { assert(phead); //第一种方法 //ListInsert(phead->next,x); //第二种方法 LTNode* newnode = BuyNewNode(x); LTNode* secound = phead->next; newnode->next = secound; secound->prev = newnode; phead->next = newnode; newnode->prev = phead; } 尾插从最后一个结点后面插入新结点 尾插也可以复用ListInsert函数 尾插也会用到申请新结点的函数，这里不重复了 void ListPushBack(LTNode* phead, DListDataType x) { assert(phead); //第一种办法 //ListInsert(phead,x); //第二种办法 LTNode* newnode = BuyNewNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } 带头双向循环链表删除函数 指定结点删除删除指定结点，配合STFInd使用，将指定节点前一个结点的next连接到指定结点后一个结点，再将指定结点后面结点的prev连接到指定指定结点前一个结点。 void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); } 头删记得进行断言，当只有一个哨兵位时与头结点为空都无法进行删除 可以对STErase进行复用 void ListPopFront(LTNode* phead) { assert(phead); assert(phead != phead->next); //第一种方法 //ListErase(phead->next); //第二种 LTNode* secound = phead->next; phead->next = secound->next; secound->next->prev = phead; free(secound); } 尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead != phead->next); //第一种方法 //ListErase(phead->prev); //第二种方法 LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); } 带头双向循环链表修改函数配合LTFind函数使用 LTNode* LTFind(LTNode* phead, DListDataType x) { assert(phead); LTNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } LTNode* LTModify(LTNode* phead, DListDataType x) { LTNode* pos = LTFind(phead, x); int y; scanf("%d", &y); pos->data = y; } 销毁带头双向循环链表将每个结点依次释放。最后将哨兵位释放。 void LTDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); } 源代码文件🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理 test.c测试文件 #include "DList.h" void test1() { LTNode* Phead = InitLTNode(); ListPushBack(Phead, 666); ListPushBack(Phead, 777); ListPushBack(Phead, 9999); ListPushBack(Phead, 888); print(Phead); ListPopBack(Phead); print(Phead); ListPopFront(Phead); print(Phead); ListPopFront(Phead); ListPopFront(Phead); print(Phead); ListPushFront(Phead,111); print(Phead); ListPushFront(Phead, 112); print(Phead); LTDestory(Phead); Phead = NULL; } int main() { test1(); } DList.ci将所有函数封装在此文件下 #include "DList.h" LTNode* BuyNewNode(DListDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } LTNode* InitLTNode() { LTNode* phead = BuyNewNode(-1); phead->next = phead; phead->prev = phead; return phead; } void ListInsert(LTNode* pos,DListDataType x) { assert(pos); LTNode* newnode = BuyNewNode(x); LTNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } void ListPushBack(LTNode* phead, DListDataType x) { //ListInsert(phead,x); assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void ListPushFront(LTNode* phead, DListDataType x) { //ListInsert(phead->next,x); assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* secound = phead->next; newnode->next = secound; secound->prev = newnode; phead->next = newnode; newnode->prev = phead; } void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); } void ListPopBack(LTNode* phead) { //ListErase(phead->prev); assert(phead); assert(phead != phead->next); LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); } void ListPopFront(LTNode* phead) { assert(phead); assert(phead != phead->next); //ListErase(phead->next); LTNode* secound = phead->next; phead->next = secound->next; secound->next->prev = phead; free(secound); } void print(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("head"); while (cur!=phead) { printf("->%d", cur->data); cur = cur->next; } printf("\n"); } LTNode* LTFind(LTNode* phead, DListDataType x) { assert(phead); LTNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } LTNode* LTModify(LTNode* phead, DListDataType x) { LTNode* pos = LTFind(phead, x); int y; scanf("%d", &y); pos->data = y; } void LTDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); } DLlist.h将主程序所需要的函数全部在头文件中声明，增加代码阅读性 #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include typedef int DListDataType; typedef struct ListNode { DListDataType data; struct ListNode* prev; struct ListNode* next; }LTNode; LTNode* InitLTNode(); void ListInsert(LTNode* pos, DListDataType x); void ListPushBack(LTNode* phead, DListDataType x); void ListPushFront(LTNode* phead, DListDataType x); void print(LTNode* phead); void ListErase(LTNode* pos); void ListPopBack(LTNode* phead); void ListPopFront(LTNode* phead); LTNode* LTModify(LTNode* phead, DListDataType x); LTNode* LTFind(LTNode* phead, DListDataType x); void LTDestory(LTNode* phead); 撒花这就是实现带头双向循环链表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！ |
【本文地址】
公司简介
联系我们