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

news/2024/11/17 14:34:18/

链式存储的优缺点：

优点：

1、动态分配内存：

链式存储不需要在数据插入之前分配固定大小的数组或内存块，因此它更适合存储动态变化的数据

2、高效的插入和删除操作：

在链表中插入或删除元素只需要调整相邻节点的指针，不需要移动大量数据，因此时间复杂度通常为O(1)（在已知位置时）或O(n)（在未知位置需要遍历链表时）。

3、节省内存：

链表中的每个节点只需要存储数据和指向下一个节点的指针，没有额外的空间浪费（如数组中的空闲空间）。

4、灵活性

链表可以以多种方式实现，如单向链表、双向链表、循环链表等，可以根据具体需求选择合适的结构。

缺点：

1、访问速度慢：

链表不支持像数组那样的随机访问，访问某个元素需要从头节点开始遍历，时间复杂度为O(n)。

2、额外的空间开销：

每个节点除了存储数据以外，还需要存储指针，增加了内存的开销。

3、内存碎片化：

链表中的节点可能在内存的不同位置分配内存，可能导致内存碎片化，影响性能。

4、管理复杂：

链表的管理（如内存分配和释放）相对复杂，容易出现内存泄露或指针错误等问题。

单向链表

单向链表（Singly Linked List）是一种链式存储结构的数据结构，它包含一系列节点（Node），每个节点都包含两个部分：数据域（存储节点的数据）和指针域（存储指向下一个节点的引用或指针）。单向链表的特点是链表中的节点只能单向遍历，即只能从链表的头部开始，依次访问每个节点，直到链表的尾部。

在我的链表中，我在定义时就给它一个规定：头节点不存数据，数据从头节点的下一个节点开始存储。

#ifndef _LINKLIST_H
#define _LINKLIST_H#include <stdio.h>
#include <stdlib.h>#define OUT(A) {printf("%c\n",A);}
typedef char Type;       //为了方便修改存储数据的类型//约定头节点不存数据
typedef struct node{Type data;         //节点中用于存储值struct node *next; //下一个节点的地址
}list;                 //声明了节点结构体类型//创建
list *create_link();
//判空
int null_link(list *l);
//求长度
int length_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 updata_link(list *l,Type oldData,Type newData);
//删除
void delete_link(list *l,Type data);
//遍历
void traverse_link(list *l);
//初始化
void init_link(list *l);
//回收
void free_link(list **l);#endif

       还是跟顺序表一样，使用多文件封装的形式来存储，在.h文件中定义结构体，结构体包括存数据的变量data和指向下一个结构体的指针next；在这里定义结构体的时候node不能省略，因为在结构体里面需要定义一个指向这个结构体类型的指针，因此需要用到这个结构体类型来定义指针。

#include "linklist.h"//创建
list *create_link()
{list *l = (list *)malloc(sizeof(list));if(NULL == l){perror("create malloc");return NULL;}l->next = NULL;return l;
}
//判空
int null_link(list *l)
{if(NULL == l){puts("listlink is NULL");return -1;}return l->next == NULL?0:1;
}
//求长度
int length_link(list *l)
{if(NULL == l){puts("listlink is NULL");return -1;}int n = 0;while(l->next){n++;l = l->next;}return n;
}
//尾插
void tail_insert_link(list *l,Type data)
{if(NULL == l){puts("listlink is NULL");return;}//找表尾while(l->next) //l->next != NULL{l = l->next;}//创建新节点list *p=(list *)malloc(sizeof(list));if(NULL == l){perror("tail_insert malloc");}p->data = data; p->next = NULL;//把节点连接到链表中l->next = p;
}
//首插
void head_insert_link(list *l,Type data)
{if(NULL == l){puts("listlink is NULL");return;}list *p = (list *)malloc(sizeof(list));if(NULL == l){perror("head-insert malloc");return;}p->data = data;p->next = l->next;l->next = p;}
//查找
list *search_link(list *l,Type data)
{if(NULL == l){puts("listlink is NULL");return NULL;}while(l->next){/*if(l->next->data == data){return l->data;l = l->next;}*/l = l->next;if(data == l->data)return l;}return NULL;
}
//更新
void updata_link(list *l,Type oldData,Type newData)
{if(NULL == l){puts("listlink is NULL");return;}while(l->next){l = l->next;if(oldData == l->data){l->data = newData;}}  
}
//删除
void delete_link(list *l,Type data)
{if(NULL == l){puts("listlink is NULL");return;}
#if 1while(l->next){if(l->next->data == data){list *p = l->next;l->next = p->next;free(p);p = NULL;//continue;   //用else不用continue}else      l = l->next;}
#elif 0list *p = l;while(l->next){if(data != l->data)p = l;l = l->next;if(data == l->data){list *q = l;l = l->next;p->next = l;free(q);break;}}/*if(data == l->data) //注释break，加上最后的if为全删{p->next = NULL;free(l);}*/
#endif
}
//遍历
void traverse_link(list *l)
{
#if 0printf("head->");while(l->next){printf("%c->",l->next->data);l = l->next;}puts("NULL");
#elif 1list *p = l->next;while(p){printf("%c ",p->data);p = p->next;}puts("");
#endif
}
//初始化
void init_link(list *l)
{if(NULL == l){puts("listlink is NULL");return;}
#if 1while(l->next){list *p = l->next;l->next = p->next;free(p);}
#elselist *p = l->next;while(p){list *n = p;p = p->next;free(n);}l->next = NULL;
#endif
}
//回收
void free_link(list **l)
{if(NULL == *l){puts("listlink is NULL");return;}while((*l)->next){list *p = (*l)->next;(*l) = p->next;free(p);}*l = NULL;
}

创建：list *create_link()

       创建之后我们需要拿到头节点的地址，因此函数返回值为结构体指针类型，同样是在堆区开辟空间，因为约定了头节点不存数据，因此这里的data不用管，但是指向下一个节点的指针需要把它赋值为NULL，防止野指针出现。

判空：int null_link(list *l)

       因为链表中有指向下一个节点的指针，但是要是链表为空，那么就只有一个头节点，头节点里面的指针指向的是NULL，因此我们可以通过判断头节点里面的指针指向的下一个节点是否为空来判断链表是否为空；空函数返回0，非空返回1。

求长度：int length_link(list *l)

       单向链表的节点是通过指针连接在一起的，因此求长度只需要从头节点开始遍历到最后一个节点，遍历时使用一个变量计数，最后函数返回这个计数变量即可；循环条件为l->next，当循环到最后一个节点时，下一个为NULL，就会结束循环；在循环里每次让指针L往后移动一个节点。

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

       尾插也就是在链表最后插入一个新的节点，首先我们传参传的是链表的头节点，因此需要先遍历找到链表的最后一个节点，然后用一个结构体指针来接收新创建节点的地址，这里也需要判断一下节点创建是否成功，创建成功之后让节点的data等于我们要添加的值，然后让新节点里面的指针指向NULL，最后还需要更改插入新节点之前链表最后一个节点中指针的指向，让这个指针指向我们新加入的节点。

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

       头插相比尾插要复杂一点，但是这里我们就不需要遍历链表了，因为我们拿到的参数就是头节点，首先也是需要创建新节点，然后给节点里的data赋值，然后让新节点里的指针next指向头节点的下一个，再让头节点的next指向我们新插入的节点；在这里头插函数中最后两条语句的顺序能更改，更改之后我们就无法正确将新节点的next指向头节点的下一个节点了。

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

        查找只需要循环遍历链表，然后将需要查找的数据与节点中的data比较即可，只要找到这个data，就将该data所在节点的地址返回就OK啦。

更新：void updata_link(list *l,Type oldData,Type newData)

       更新也就是将链表中某一个值修改为我们想改的值，传入的参数就有三个，表，原数据和更新的数据，也是通过循环遍历的方式来寻找我们需要更改的数据，找到之后直接修改即可，在代码中我的更新是将所有的要修改的那个原数据都改变，例如原来链表中有3个a，我要将a修改为b，那么就会将这三个a都修改为b，如果只想修改找到的第一个a的话就只需要在l->data = newData;语句后面加一个break，直接结束循环即可。

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

       删除和插入是类似的操作，只不过一个是增加节点，另一个是删除节点，首先是将要删除的数据当做参数传入函数，然后通过遍历的方式来查找需要删除的节点，找到节点之后用一个指针来指向这个节点，然后就是断链，将与它相连的前面一条链断开；在这里使用一个指针来指向这个节点是因为要把这个节点的空间释放掉，我们在找到这个节点之后就可以让它的前一个节点的next去指向要删除节点的下一个节点，再把要删除的节点空间释放掉，最后再让指针p指向NULL即可。在这里删除有删一个和删全部的区别，在代码中如果只想删除找到的第一个对应的字母，那就在p=NULL后语句之后加一个break结束循环即可。

遍历：void traverse_link(list *l)

        链表的遍历也就是通过循环来让L从头节点往后移动一直到最后一个节点，然后将每一个节点的data输出即可。 

初始化：void init_link(list *l)

       链表的初始化我们需要把除了头结点以外的节点都释放掉，同样还是使用循环遍历的方式，初始化跟删除是一样的操作，但是初始化是将所有节点都删除，跟删除差不多的我就不多说啦。

回收：void free_link(list **l)

       链表的回收就是先将链表初始化然后再把头节点也释放，最后再让指向头节点的指针指向空即可。

测试：（主函数）

#include "linklist.h"
int main(int agrc,char *agrv[])
{list *p = create_link(); tail_insert_link(p,'a');tail_insert_link(p,'b');tail_insert_link(p,'b');tail_insert_link(p,'f');printf("尾插后链表内容：");traverse_link(p);head_insert_link(p,'b');head_insert_link(p,'c');head_insert_link(p,'d');printf("头插后链表内容：");traverse_link(p);printf("此时链表长度为：%d\n",length_link(p));list *q = search_link(p,'d');OUT(q->data);q->data = 'a';printf("将查找到的d改为a后：");traverse_link(p);updata_link(p,'a','b');printf("将第一个a更新为b：");traverse_link(p);delete_link(p,'b');printf("删除第一个b后：");traverse_link(p);init_link(p);printf("此时链表长度为：%d\n",length_link(p));free_link(&p);printf("回收后p的指向：%p\n",p);return 0;
}


http://www.ppmy.cn/news/1547738.html

相关文章

.NET 9 中 IFormFile 的详细使用讲解

.NET 9 中 IFormFile 的详细使用讲解

在.NET应用程序中&#xff0c;处理文件上传是一个常见的需求。.NET 9 提供了 IFormFile 接口&#xff0c;它可以帮助我们轻松地处理来自客户端的文件上传。以下是 IFormFile 的详细使用讲解。 IFormFile 接口简介 IFormFile 是一个表示上传文件的接口&#xff0c;它提供了以下…
阅读更多...
何为Jenkins

何为Jenkins

何为Jenkins Jenkins Jenkins 是一个开源的自动化服务器&#xff0c;广泛用于 持续集成&#xff08;CI&#xff09; 和 持续交付&#xff08;CD&#xff09; 的场景。它可以自动化软件开发中的构建、测试、部署等任务&#xff0c;从而提高开发效率、确保代码质量&#xff0c;…
阅读更多...
大数据技术之HBase中的HRegion

大数据技术之HBase中的HRegion

如果你正在学习大数据&#xff0c;你应该知道HBase是一个列式存储的NoSQL分布式数据库&#xff0c;可以配合Hadoop来使用。今天自己简单做了几页PPT&#xff0c;解释了一下HBase当中HRegion的基本概念&#xff0c;很多初学者在学习的时候对HRegion这个概念一直懵懵懂懂&#xf…
阅读更多...
网络延迟对Python爬虫速度的影响分析

网络延迟对Python爬虫速度的影响分析

Python爬虫因其强大的数据处理能力和灵活性而被广泛应用于数据抓取和网络信息收集。然而&#xff0c;网络延迟是影响爬虫效率的重要因素之一。本文将深入探讨网络延迟对Python爬虫速度的影响&#xff0c;并提供相应的代码实现过程&#xff0c;以帮助开发者优化爬虫性能。 网络…
阅读更多...
【第四课】rust声明式宏理解与实战

【第四课】rust声明式宏理解与实战

目录 前言 理解宏 实战宏 前言 上一课在介绍vector时，我们再一次提到了rust中的宏，在初始化vector时使用了vec!宏，当时补了一句有机会会好好说明一下rust中的宏，并且写一个hashmap宏来初始化hashmap。想了想一直介绍基本语法还是比较枯燥乏味的，所以这节课我们介绍一点…
阅读更多...
MATLAB蒙特卡洛仿真计算投资组合的VaR(Value at Risk )

MATLAB蒙特卡洛仿真计算投资组合的VaR(Value at Risk )

1. 计算VaR简介 VaR&#xff08;Value at Risk&#xff09;&#xff0c;一般被称为“风险价值”或“在险价值”&#xff0c;是指在一定的置信水平下&#xff0c;某一金融资产&#xff08;或证券组合&#xff09;在未来特定的一段时间内的最大可能损失。VaR提供了一个具体的数值…
阅读更多...
自定义菜单栏实现点击添加按钮打开渲染进程的Dialog.vue模态框

自定义菜单栏实现点击添加按钮打开渲染进程的Dialog.vue模态框

实现思路&#xff1a;渲染进程页面初始化后就通知主进程&#xff0c;然后把event事件保存在该js文件外&#xff0c;当点击添加时因为是在其他位置&#xff0c;所以才要这样使用。然后点击添加后由主进程主动向渲染进程传递参数通知要做的操作。 代码如下&#xff1a; // 第一步…
阅读更多...
探索KubeVirt：如何利用InfiniBand提升虚拟机性能

探索KubeVirt：如何利用InfiniBand提升虚拟机性能

在高性能计算&#xff08;HPC&#xff09;中&#xff0c;网络性能对于集群效率起着至关重要的作用。为了支持大规模并行计算&#xff0c;HPC集群通常依赖高带宽、低延迟的网络&#xff0c;而InfiniBand&#xff08;IB&#xff09;正是其中的首选技术。它能够提供超过100Gbps的带…
阅读更多...
最新文章

Copyright @ 2022~2023