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

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

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;
}