网站更换,海外云服务器推荐,上海公司名义买房条件,承德百度网站建设双向链表相比于单向链表的优势#xff1a;
1. 双向遍历的灵活性 双向链表#xff1a;由于每个节点都包含指向前一个节点和下一个节点的指针#xff0c;因此可以从头节点遍历到尾节点#xff0c;也可以从尾节点遍历到头节点。这种双向遍历的灵活性使得在某些算法和操作中
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 1length_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(psearch_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函数关键的区别 数据类型 abs函数用于计算整数的绝对值。它的参数和返回值都是整数类型int。 fabs函数用于计算浮点数的绝对值。它的参数是浮点类型double返回值也是double类型。 头文件 要使用abs函数你需要包含stdlib.h头文件。 要使用fabs函数你需要包含math.h头文件。 用途 当你的数据是整数时使用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;
}
