数据结构---带头双向循环链表

LTNode* BuyLTNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}

node->data = x;
node->next = NULL;
node->prev = NULL;

return node;
}

2、初始化

为什么单链表这里并不需要初始化,而在这里就要进行初始化呢？
因为需要获取到这里的head头结点。

//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;

return phead;
}

同样的在这里我们为了方便测试，顺手把打印实现一下：

//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("phead<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}

3、尾插

//尾插
void LTPushback(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);

newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;

    //附用代码
    //LTInsert(phead, x);

}

4、尾删

//尾删
void LTPopback(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;

free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;

    
    //附用代码
    //LTErase(phead->prev);

}

5、头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{

assert(phead);
    //第一种写法
LTNode* tail = phead->next;
LTNode* newnode = BuyLTNode(x);
newnode->next = tail;
tail->prev = newnode;

phead->next = newnode;
newnode->prev = phead;


    //第二种写法，不建议，这种写法要注意先后顺序
//newnode->next = phead->next;
//phead->next->prev = newnode;

//phead->next = newnode;
//newnode->prev = phead;


    //附用代码
    //LTInsert(phead->next, x);
}

6、头删

//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
LTNode* tailNext = tail->next;

free(tail);
phead->next = tailNext;
tailNext->prev = phead;

    
    //附用代码
    //LTErase(phead->next);

}

7、计算链表长度

//计算链表长度
int LTSize(LTNode* phead)
{
assert(phead);

int size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}

这里顺便实现一个查找：

//查找
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;
}

8、在pos之前插入

//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = BuyLTNode(x);

newnode->next = pos;
pos->prev = newnode;

posPrev->next = newnode;
newnode->prev = posPrev;

}

9、删除pos位置

//删除pos位置
void LTErase(LTNode* pos)
{
assert(pos);

LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;

free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}

在实现了pos位置的插入删除之后，我们就可以对头插头删，尾插尾删进行附用(具体附用代码，在头插头删，尾插尾删的代码最后已给出) 。

10、销毁

//销毁
void LTDestory(LTNode* phead)
{
assert(phead);

LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);

}

三、完整代码

//List.h


#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;

//申请新节点
LTNode* BuyLTNode(LTDataType x);

//初始化
LTNode* LTInit();

//销毁
void LTDestory(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//尾插
void LTPushback(LTNode* phead, LTDataType x);

//尾删
void LTPopback(LTNode* phead);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//头删
void LTPopFront(LTNode* phead);

//计算链表长度
int LTSize(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);

//删除pos位置
void LTErase(LTNode* pos);

//List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//申请新节点
LTNode* BuyLTNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}

node->data = x;
node->next = NULL;
node->prev = NULL;

return node;
}


//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;

return phead;
}

//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("phead<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}

//尾插
void LTPushback(LTNode* phead, LTDataType x)
{
assert(phead);
/*LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);

newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;*/

//附用版本
LTInsert(phead, x);

}

//尾删
void LTPopback(LTNode* phead)
{
assert(phead);
assert(phead->next != 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* tail = phead->next;
//LTNode* newnode = BuyLTNode(x);
//newnode->next = tail;
//tail->prev = newnode;

//phead->next = newnode;
//newnode->prev = phead;

//附用版本
LTInsert(phead->next, x);

//第二种方法，不建议，因为要注意先后顺序
//newnode->next = phead->next;
//phead->next->prev = newnode;

//phead->next = newnode;
//newnode->prev = phead;
}

//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
//LTNode* tail = phead->next;
//LTNode* tailNext = tail->next;

//free(tail);
//phead->next = tailNext;
//tailNext->prev = phead;

//附用版本
LTErase(phead->next);

}

//计算链表长度
int LTSize(LTNode* phead)
{
assert(phead);

int size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}

//查找
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* posPrev = pos->prev;
LTNode* newnode = BuyLTNode(x);

newnode->next = pos;
pos->prev = newnode;

posPrev->next = newnode;
newnode->prev = posPrev;


}

//删除pos位置
void LTErase(LTNode* pos)
{
assert(pos);

LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;

free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}


//销毁
void LTDestory(LTNode* phead)
{
assert(phead);

LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);

}

四、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持：O(1)	不支持：O(N)
任意位置插入或删除元素	可能需要移动元素，效率低 O(N)	只需修改指针指向
插入	动态顺序，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

原文地址：https://blog.csdn.net/m0_73299878/article/details/144325114

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：ROS2 学习笔记系列文章索引
下一篇：VS2019 + Linux 跨平台开发中的 sqlite3 数据库环境配置

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14