数据结构（双向链表——c语言实现）

embedded/2025/1/29 6:53:35/

双向链表相比于单向链表的优势：

1. 双向遍历的灵活性

  • 双向链表：由于每个节点都包含指向前一个节点和下一个节点的指针，因此可以从头节点遍历到尾节点，也可以从尾节点遍历到头节点。这种双向遍历的灵活性使得在某些算法和操作中，双向链表能够提供更高效的解决方案。

  • 单向链表：只能从头节点开始顺序遍历到尾节点，无法直接访问前驱节点，因此在某些需要双向遍历的场合下，单向链表显得不够灵活。

2. 插入和删除操作的便捷性

  • 双向链表：在双向链表中插入或删除一个节点时，只需要修改相邻节点的前后指针，而不需要遍历整个链表来查找前驱或后继节点。这大大提高了插入和删除操作的效率。

  • 单向链表：在插入或删除节点时，通常需要遍历链表以找到插入或删除位置的前一个节点，这增加了操作的复杂性。

3. 适用于复杂操作

  • 双向链表：由于可以方便地访问前驱和后继节点，双向链表在实现一些复杂操作时（如反转链表、合并链表等）变得更加简单和直观。

  • 单向链表：由于只能单向遍历，因此在实现这些复杂操作时可能需要更多的辅助变量和步骤。

4. 内存开销的考虑

  • 双向链表：每个节点需要额外存储一个指向前驱节点的指针，因此相对于单向链表，双向链表占用更多的内存空间。然而，这种额外的内存开销通常是可以接受的，特别是在需要频繁访问前驱节点的场合下。

  • 单向链表：由于每个节点只存储一个指向后继节点的指针，因此内存开销相对较小。但在需要访问前驱节点的场合下，可能需要通过额外的操作或数据结构来实现。

双向链表：

双向链表跟单向链表最大的区别就在于它的节点里面多了一个指向前一个节点的指针，我们还是约定头结点不存数据，同样还是多文件封装的形式。

#ifndef _DOUBLELINK_H
#define _DOUBLELINK_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>  //fabs头文件#define OUT(A) {printf("%.2f ",A);}
typedef float Type;
#define PRE 0.000001 //精度typedef struct node{Type data;           //存值struct node *front;  //前指针struct node *rear;   //后指针
}list;
//头节点不存数据//创建
list *create_link();
//判空
int empty_link(list *l);
//求长度
int length_link(list *l);
//遍历
void traverse_link(list *l);
//首插
void head_insert_link(list *l,Type data);
//尾插
void tail_insert_link(list *l,Type data);
//查找
list *search_link(list *l,Type data);
//修改
void update_link(list *l,Type oldData,Type newData);
//删除
void delete_link(list *l,Type data);
//初始化
void init_link(list *l);
//回收
void recycle_link(list **l);#endif

       双向链表的结构体里有三个成员，存储数据的变量data，指向上一个节点的指针front和指向下一个节点的指针rear；在这里浮点型数据是有精度的，它只是无限接近于我们输入的值，并不是完全相同，例如输入的是1.2，但是实际存储的数据为1.20000005；因此我将PRE宏定义为精度，这里是精确到6位小数，便于我们后续的查找中使用。 

#include "doublelink.h"//创建
list *create_link()
{list *l = (list *)malloc(sizeof(list));if(NULL == l){perror("create malloc");return NULL;}l->front = NULL;l->rear = NULL;return l;
}
//判空
int empty_link(list *l)
{if(l == NULL){puts("list is NULL");return -1;}return NULL == l->rear?0:1;
}
//求长度
int length_link(list *l)
{
#if 0if(l->rear == NULL) //递归求长度return 0;return 1+length_link(l->rear);
#elseif(l == NULL){puts("list is NULL");return -1;}int n = 0;while(l->rear){n++;l = l->rear;}return n;
#endif
}
//遍历
void traverse_link(list *l)
{if(l == NULL){puts("list is NULL");return;}while(l->rear){l = l->rear;OUT(l->data);}puts("");
}
//首插
void head_insert_link(list *l,Type data)
{if(l == NULL){puts("list is NULL");return;}list *p = (list *)malloc(sizeof(list));if(NULL == p){perror("create malloc");return;}p->data = data;p->front = l;p->rear = l->rear;l->rear = p;if(NULL != p->rear)p->rear->front = p;
}
//尾插
void tail_insert_link(list *l,Type data)
{if(l == NULL){puts("list is NULL");return;}list *p = (list *)malloc(sizeof(list));if(NULL == l){perror("create malloc");return;}while(l->rear){l = l->rear;}p->data = data;l->rear = p;p->front = l;p->rear = NULL;
}
//查找
list *search_link(list *l,Type data)
{if(l == NULL){puts("list is NULL");return NULL;}while(l->rear){l = l->rear;float t = l->data - data;if(fabs(t)<PRE)return l;}return NULL;
}
//修改
void update_link(list *l,Type oldData,Type newData)
{
#if 1if(l == NULL){puts("list is NULL");return;}while(l->rear){l = l->rear;if(oldData == l->data){l->data = newData;}}
#elselist *p = search_link(l,oldData);p->data = newData;
#endif
}
//删除
void delete_link(list *l,Type data)
{
#if 1if(l == NULL){puts("list is NULL");return;}while(l->rear){if(data == l->rear->data){list *p = l->rear;if(NULL != l->rear->rear)l->rear->rear->front = l;l->rear = l->rear->rear;free(p);}elsel = l->rear;}
#elselist *p;while(p=search_link(l,data)){p->front->rear = p->rear;if(p->rear)p->rear->front = p->front;free(p);}
#endif
}
//初始化
void init_link(list *l)
{if(l == NULL){puts("list is NULL");return;}
#if 1while(l->rear){list *p = l->rear;if(NULL != l->rear->rear)l->rear->rear->front = l;l->rear = l->rear->rear;free(p);}
#elsewhile(l->rear){list *p = l->rear;//这里不需要去管要删除节点后一个的前指针，因为所有的都要删除l->rear = p->rear;free(p);}
#endif
}
//回收
void recycle_link(list **l)
{if(l == NULL){puts("list is NULL");return;}init_link(*l);free(*l);*l = NULL;
}

创建：list *create_link()

       创建函数的返回值还是节点的地址，创建头节点之后要让它的两个指针都指向NULL，因为这时只有一个头结点，没有其他节点。

判空：int empty_link(list *l)

       双向链表的判空跟单向链表是一样的，只需要判断头节点的下一个节点是否为空（NULL）即可，空函数返回0，非空函数返回1。

求长度：int length_link(list *l)

       求长度只需要在遍历的时候使用一个变量来统计节点的数量即可；在这里我使用了两种方法来求长度，一种就是遍历计数；另外一种是使用递归函数来求长度，每次调用自己的时候都+1，就变成了有几个节点就是几个1相加  0，这样也可以求长度，而且代码更加简洁。 

遍历：void traverse_link(list *l)

       使用循环来遍历，让L每次往后移动一个节点，直到最后一个节点为止，每次循环都将节点的数据输出，就实现了遍历。

首插（头插）：void head_insert_link(list *l,Type data)

       头部插入我们需要做的事情有给节点data赋值，给节点指针指向，断链；首先创建节点，创建完成之后给data赋值；然后让新节点的front指向头节点，让rear指向头节点的下一个节点，让头节点的rear指向新节点；最后就是让新节点的下一个节点的front指向新节点，但是在这里需要注意一个问题，如果原链表是空链表，那么就不能对新节点的下一个进行p->rear->front = p;操作，因为这时它为空，所以在这里就需要做一个判断，如果新节点的下一个节点不为空，那么才让它的front指向新节点，否则就不需要执行这一步操作。

尾插：void tail_insert_link(list *l,Type data)

       尾部插入相对头部插入就要简单一些，首先是给新节点的data赋值，然后循环遍历找到最后一个节点，让最后一个节点的rear指向新节点，让新节点的front指向最后这个节点，最后让新节点的rear指向NULL即可。

查找：list *search_link(list *l,Type data)

       查找需要返回节点的地址，因此函数为list *类型，同样使用循环的方式，但是在这里不建议使用data == l->data的方式来寻找所需要的节点，因为浮点型数据存储并不是完全与输入的数据相等，因此我们将查找的data与链表节点中的data做一个差，根据这个差值来判断是否是我们寻找的数据，这里就用到了我一开始定义的精度，差值在精度范围内就说明这个数据是我们要寻找的数据；在这里因为差值可能为负数，因此我使用fabs这个函数来将差值转化为绝对值，只要绝对值小于我们的精度，那就返回这个节点的地址，要是循环遍历结束都没有找到这个数据，那就返回一个NULL。

      在这里我使用的是fabs函数而不是abs函数是因为abs在将浮点型数据取绝对值的时候只能将它的整数部分取绝对值，而不能将整个浮点型数据取绝对值，但是fabs就能将整个浮点型数据取绝对值，这一点需要宝子们注意。

abs函数和fabs函数关键的区别：

  1. 数据类型：

    • abs函数用于计算整数的绝对值。它的参数和返回值都是整数类型（int）。

    • fabs函数用于计算浮点数的绝对值。它的参数是浮点类型（double），返回值也是double类型。

  2. 头文件：

    • 要使用abs函数，你需要包含stdlib.h头文件。

    • 要使用fabs函数，你需要包含math.h头文件。

  3. 用途：

    • 当你的数据是整数时，使用abs函数。

    • 当你的数据是浮点数时，使用fabs函数。

修改：void update_link(list *l,Type oldData,Type newData)

       数据的修改就很简单啦，通过循环遍历找到要修改的数据，将它直接修改为要更改的值即可，在这里可以偷懒调用之前的查找函数来帮助我们找到要修改的节点，然后直接修改内容就行，这样就不用再写一遍遍历啦。

删除：void delete_link(list *l,Type data)

       删除节点要做的有两件，释放节点和断链；断链也就是更改删除节点前后节点的指针指向，在这里把要删除的节点叫做目标节点；既然是删除节点，那就需要使用一个指针来指向这个节点，然后让目标节点的前一个节点的rear指向目标节点的下一个节点，在这里同样需要判断目标节点的下一个节点是否为空，如果非空就需要让该节点的front指向目标节点的前一个节点。

初始化：void init_link(list *l)

       双向链表的初始化和单向链表类似，只需要将每一个节点空间都释放掉即可，同样是通过循环遍历的方式；同样的也可以调用之前的删除函数，但是在这里我们可以不需要去管节点的前指针front，因为我们每一个节点都需要删除，将空间释放掉之后front也就不存在了。

回收：void recycle_link(list **l)

       回收函数的传参传的同样是链表头节点的地址，首次是初始化，然后再将头节点也释放，因此可以调用之前的初始化函数，然后再让这个指针指向NULL即可。

测试（主函数）：

#include "doublelink.h"
int main(int agrc,char *agrv[])
{list *p = create_link();puts("尾插");tail_insert_link(p,1.25);tail_insert_link(p,1.2);tail_insert_link(p,1.1);traverse_link(p);puts("头插");head_insert_link(p,1.5);head_insert_link(p,1.10);head_insert_link(p,1.4);traverse_link(p);printf("length=%d\n",length_link(p));puts("将1.10更改为1.6");update_link(p,1.10,1.6);traverse_link(p);puts("删除1.2");delete_link(p,1.2);traverse_link(p);puts("查找1.50，利用找到的节点将它修改为2.00");list *q = search_link(p,1.50);q->data = 2.00;traverse_link(p);puts("初始化");init_link(p);printf("length=%d\n",length_link(p));puts("回收");recycle_link(&p);printf("p=%p\n",p);return 0;
}


http://www.ppmy.cn/embedded/139355.html

相关文章

EDA实验设计-led灯管动态显示；VHDL；Quartus编程

EDA实验设计-led灯管动态显示；VHDL；Quartus编程

EDA实验设计-led灯管动态显示&#xff1b;VHDL&#xff1b;Quartus编程 引脚配置实现代码RTL引脚展示现象记录效果展示 引脚配置 #------------------GLOBAL--------------------# set_global_assignment -name RESERVE_ALL_UNUSED_PINS "AS INPUT TRI-STATED" set_…
阅读更多...
libjpeg库——图像压缩与解压的核心技术

libjpeg库——图像压缩与解压的核心技术

引言 在数字图像处理领域&#xff0c;图像压缩与解压技术扮演着至关重要的角色。随着数字图像的广泛应用&#xff0c;高效地存储和传输图像数据成为了一项关键技术需求。libjpeg库&#xff0c;作为一个开源的图像压缩解压缩库&#xff0c;凭借其丰富的功能和灵活的接口&#x…
阅读更多...
数据库基础（MySQL）

数据库基础（MySQL）

1. 数据库基础 1.1 什么是数据库 存储数据用文件就可以了&#xff0c;为什么还要弄个数据库? 文件保存数据有以下几个缺点&#xff1a; 文件的安全性问题文件不利于数据查询和管理文件不利于存储海量数据文件在程序中控制不方便 数据库存储介质&#xff1a; 磁盘内存 为…
阅读更多...
2024年11月19日Github流行趋势

2024年11月19日Github流行趋势

项目名称&#xff1a;build-your-own-x 项目维护者&#xff1a;danistefanovic, rohitpaulk, sarupbanskota 等项目介绍&#xff1a;通过从零开始重新创建你最喜欢的技术来掌握编程。项目star数&#xff1a;312,081项目fork数&#xff1a;29,004 项目名称&#xff1a;freqtrad…
阅读更多...
tcn 对比 cnn-attension-gru联合模型,时间序列预测，深度神经网络

tcn 对比 cnn-attension-gru联合模型,时间序列预测，深度神经网络

tcn 对比 cnn-attension-gru联合模型,&#xff0c;我们可以从以下几个方面对比TCN&#xff08;Temporal Convolutional Network&#xff09;和CNN-attention-GRU联合模型&#xff1a; 1. **模型结构和功能**&#xff1a; - TCN是一种基于卷积的网络&#xff0c;擅长处理序列…
阅读更多...
[241119] .NET 9.0.0 正式发布 | D2 Emerge 收购 CodeProject，拓展软件开发社区影响力

[241119] .NET 9.0.0 正式发布 | D2 Emerge 收购 CodeProject，拓展软件开发社区影响力

目录 .NET 9.0.0 正式发布下载地址Docker 镜像Visual Studio 兼容性更新的包 D2 Emerge 收购 CodeProject&#xff0c;拓展软件开发社区影响力 .NET 9.0.0 正式发布 .NET 9.0.0 和 .NET SDK 9.0.100 于近日正式发布&#xff01; 本次发布包含安全性和非安全性修复&#xff0c…
阅读更多...
防止DDos的技术方案

防止DDos的技术方案

以基于验证码URL负载请求形成DDos为案例进行详细阐述。 背景 随着技术的发展&#xff0c;人们对于系统安全性和用户体验的要求越来越高。传统的图形验证码虽然在一定程度上能够防止恶意攻击&#xff0c;但用户体验相对较差&#xff0c;且存在被破解的风险。因此&#xff0c;大…
阅读更多...
# 07_ Python基础到实战一飞冲天（二）-python基础（七）--变量类型计算与输入输出

# 07_ Python基础到实战一飞冲天（二）-python基础（七）--变量类型计算与输入输出

07_ Python基础到实战一飞冲天&#xff08;二&#xff09;-python基础&#xff08;七&#xff09;–变量类型计算与输入输出 一、变量的类型-04-Python中的变量类型 1、python 变量的类型 在 Python 中定义变量是 不需要指定类型&#xff08;在其他很多高级语言中都需要&…
阅读更多...
最新文章

Copyright @ 2022~2023