当前位置： 首页 > news >正文

数据结构：为什么说链表是顺序表的升级版（c语言实现）

news 来源：原创 2024/9/30 3:27:35
前言：

    我们在之前的几篇文章中详细的讲解了顺序表的特点，增删改查操作和动态顺序表的优点，并使用顺序表的底层结构实现了通讯录项目，似乎顺序表是一个非常完美的数据结构，它可以实现按照需求实现增删查改，对内存的控制也较为合理，空间都是在需要时手动开辟的。但是顺序表真的完美吗？事实上它并不完美，经过我们思考，顺序表还是存在一些问题，例如：（1）顺序表中间/头部的插入删除，时间复杂度为O(N) （ 2） 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 （3）增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们 再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。这些问题都是我们应该考虑的，而我们接下来要介绍的另一种数据结构——链表，就能在实现属性表的各个功能的前提下很好的解决这些问题。

1.链表

1.1 链表的概念及结构

    链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。换句话说，链表就是一块一块的空间由指针像链子一样将它们链接起来了，方便我们去访问链表的每一个节点。

    它的结构像极了图中的小火车：

我们来看看真实链表的结构 ：

      链表是由一个指针指向链表的头节点，每个节点分为两个部分，分别是数据部分和指针部分，数据部分负责存储我们要存储的数据，指针部分负责存储下一个节点的地址，链表的每一个节点都储存着下一个节点的地址，最后一个节点的指针存储的是空指针，这使我们能够很方便的访问整个链表。

链表的特点：

1.从图中可以看出，链表的的结构在逻辑上是连续的，但是在物理上不一定连续。

2.每一个节点一般都是从堆上申请的。

3.从堆上申请的空间，是按照一定的策略分配的，两次申请的空间可能连续，可能不连续

1.2 链表的分类

链表的实际分类种类多达八种：

     链表分为单向和双向链表，带头和不带头链表，循环或者非循环链表，虽然由有这么多种链表，但是我们实际使用时最常用的只有两种：分别是无头单向非循环链表和带头双向循环链表。

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.3 单链表的实现

    我们这一期用c语言代码来实现单链表。与顺序表相同，我们将实现链表的文件分成三个，分别是头文件SList.h文件,SLIst.c方法实现文件和测试文件test.c文件：

1.3.2 链表实现 

     链表由数据和指针两部分组成（前面已经详细解释），由于我们不确定会存储哪种类型的数据，使用typedef来作为我们的数据类型，要更数据类型时只需要更改typedef重命名的数据类型就可以：

 1、无头+单向+非循环链表增删查改实现
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;}SLTNode;

在这里我们使用的是int类型，最后将链表的名字改为SLTNode。

实现一个顺序表要实现许多方法，链表也是如此：

SLTNode* SLTBuyNode(SLTDataType x);//申请一个节点
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾删void SLTPrint(SLTNode* phead);//打印void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插void SLTPosBack(SLTNode** pphead);//尾删void SLTPosFront(SLTNode** pphead);//头删SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//指定位置之前插入void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//指定位置之后插入void SLTErase(SLTNode** pphead, SLTNode* pos);
//指定位置删除void SLTEraseAfter(SLTNode* pos);
//指定位置之后删除void SLTDestory(SLTNode** pphead);
//销毁
（1）申请一个节点 

     增删查改，只有里面有数据才能使用其他三个功能，所以我们首先实现插入功能，每次插入数据又需要申请一块空间，这会使得程序多出许多相同的代码，所以我们将申请空间封装成一个函数，在我们需要插入数据时，调用这个函数就可以了。而实现这个函数也非常的简单，只需要申请一块空间，将我们要插入的数据给它的data，next指针指向空就可以了，执行完这些操作后，返回这块空间：

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");}newnode->data = x;newnode->next = NULL;return newnode;}//申请节点
（2）尾插 

     尾插我们需要考虑到我们要插入数据，传递的是一级指针的地址，就需要用二级指针来接收，传过来的指针不能为空，否则会出现非法访问的错误，如果传过来的是一个空链表，我们直接让头执针指向我们新开辟的空间就可以，如果不是链表，我们定义一个尾指针，让它遍历整个链表最终走到结尾，然后让它指向我们新开辟的节点，实现尾插操作：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
//尾插
（3）头插 

  头插的操作比较简单，只需要申请一个新节点，让它的next指针指向头节点，再让头指针指向它：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//头插
（4）查找

     为什么先讲查找呢？因为我们接下来的指定位置插入和删除需要用到它。我们要先判断传过来的地址和指针是否为空，如果为空，则没有查找的必要，确保地址和指针都不为空的情况下，我们才能进行查找操作。将链表遍历，如果发现数据内容相等，则视为找到了，返回这个节点，如果遍历完整个数组还没有找到这个节点，则说明链表里面没有这个节点，返回空指针：

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函数
（5）指定位置之前插入 

  我们首先要确保传过来的地址和链表不为空，指定的那个节点也不能为空，如果为空，我们就无法执行插入操作，还要考虑如果我们指定的节点就是头节点和指定的节点在后面的情况能不能用同一种方法解决，我们发现这两种情况不能用同一种方法解决，所以如果指定的位置就是头节点，我们就使用头插的方法，如果在后面，就需要找到指定位置的前一个节点，让新节点的next指针指向我们指定的那个节点，然后让指定位置的前一个节点的next指针指向新节点：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (*pphead == pos){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* next = prev->next;newnode->next = next;prev->next = newnode;}}//指定位置之前插入数据
（6）指定位置之后插入

    指定位置之后插入数据需要将它的next指针存储起来，让新节点的next指针存储它的next指针，再将我们指定节点的next指针存储新节点的地址：

void SLTInsertAfter( SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//指定位置后插入
（7）尾删 

      删除操作我们要确保链表不能为空，传过来的地址也不能为空，而链表只有一个节点和多个节点的情况也是不同的，如果链表只有一个节点，我们只要将它置空就可以了，如果有多个节点，我们则需要遍历链表，先将最后一个节点释放，然后将指向它的前一个节点的next指针置空：

void SLTPosBack(SLTNode** pphead)
{(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* pcur = *pphead;SLTNode* prev = *pphead;while (pcur->next != NULL){prev = pcur;pcur = pcur->next;}free(pcur);prev->next = NULL;pcur = prev;}
}//尾删
（8）头删 

    头删的实现也比较简单，只需要将头节点的next指针存起来，然后将头节点指向的空间释放，最后让头节点指向我们存起来的next指针：

void SLTPosFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//头删
（9）指定位置删除 

     删除也要确保地址和指针不能为空，我们指定的节点也不能为空，否则无法进行删除操作，链表内只有一个节点和有多个节点的情况也是不一样的，如果只有一个节点，我们调用头删函数就可以了，如果有多个节点，就需要找到指定位置的前一个节点，将我们指定的节点释放后，再将它的前一个节点的next指针置空：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;if (pos == *pphead){SLTPosFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}
//指定位置删除
（10）指定位置之后删除 

   我们要确保链表不能为空，也要确保链表呢有两个及以上的节点，否则我们无法指定删除某一个节点的后一个节点。先将我们要删除的节点的后一个节点存起来，将我们删除的节点释放后，用它的前一个节点的next指针指向那个存起来的节点，我们就能实现指定位置后删除:

void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//指定位置之后删除
(11)打印链表数据 

   打印链表要先确保链表不为空，为空则无法调用该函数，如果确保不为空，我们只需要遍历打印就可以：

void SLTPrint(SLTNode* phead)
{assert(phead);while (phead){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");
}//打印
（12）销毁链表

   由于链表的空间是使用malloc在堆上开辟的，只有在程序结束之后才会释放，所以我们使用完这些空间后要手动释放：

（13）测试

  实现完所有的方法，我们来测试一下吧：

我们调用这些方法都是没有问题的。 

以上就是这一期单链表的所有内容了，它不需要像顺序表一样插入删除数据时要将数据频繁挪动，空间也是插入一个数据开辟一块空间，毫无疑问它称得上是顺序表的升级版，我将源码放在下面，感兴趣的小伙伴可以试试哦。

SList.h :

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;}SLTNode;SLTNode* SLTBuyNode(SLTDataType x);//申请一个节点
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾删void SLTPrint(SLTNode* phead);//打印void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插void SLTPosBack(SLTNode** pphead);//尾删void SLTPosFront(SLTNode** pphead);//头删SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//指定位置之前插入void SLTInsertAfter( SLTNode* pos, SLTDataType x);
//指定位置之后插入void SLTErase(SLTNode** pphead, SLTNode* pos);
//指定位置删除void SLTEraseAfter(SLTNode* pos);
//指定位置之后删除void SLTDestory(SLTNode** pphead);
//销毁

SList.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");}newnode->data = x;newnode->next = NULL;return newnode;}//申请节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
//尾插void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//头插
void SLTPosBack(SLTNode** pphead)
{(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* pcur = *pphead;SLTNode* prev = *pphead;while (pcur->next != NULL){prev = pcur;pcur = pcur->next;}free(pcur);prev->next = NULL;pcur = prev;}
}//尾删void SLTPosFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//头删SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函数void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (*pphead == pos){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* next = prev->next;newnode->next = next;prev->next = newnode;}}//指定位置之前插入数据void SLTInsertAfter( SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//指定位置后插入
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;if (pos == *pphead){SLTPosFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}
//指定位置删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//指定位置之后删除
void SLTDestory(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}//销毁
void SLTPrint(SLTNode* phead)
{assert(phead);while (phead){printf("%d->", phead->data);phead = phead->next;}printf("NULL\n");
}//打印

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void test02()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTPushFront(&plist, 9);SLTPushFront(&plist, 89);SLTPushFront(&plist, 9);SLTPrint(plist);SLTPosBack(&plist);SLTPrint(plist);SLTPosFront(&plist);/*SLTPosFront(&plist);SLTPosFront(&plist);SLTPosFront(&plist);SLTPosFront(&plist);SLTPosFront(&plist);*/SLTPrint(plist);SLTNode* find = SLTFind(&plist,2);SLTEraseAfter(find);//SLTErase(&plist, find);/*SLTInsertAfter(&plist, find, 32);*/SLTPrint(plist);SLTDestory(&plist);/*SLTInsert(&plist, find, 8);SLTPrint(plist);*//*if (find == NULL){printf("找不到！\n");}else{printf("找到了！\n");}*/
}
int main()
{test02();//test01();return 0;
}

 

 

 

    

相关文章：

  • pgsql给单独数据库制定账号权限
  • Kotlin 中的内联函数
  • AI与音乐：共创未来乐章还是终结艺术的颂歌？
  • Docker容器导出导入
  • Python发送Email的性能怎么样？如何配置？
  • Unity定时（延迟）管理器实现
  • 数据结构-线性表的顺序表示
  • Webstorm vue项目@路径不能跳转到对应资源,提示Cannot find declaration to go to
  • Android记录19-朋友圈动态发布时间计算
  • 事件传播机制 与 责任链模式
  • Matlab 入门学习
  • .net core使用EPPlus设置Excel的页眉和页脚
  • G7易流赋能化工物流，实现安全、环保与效率的共赢
  • Java延迟初始化Logger日志对象
  • 【C++11 之nullptr关键字 用以消除空指针和0歧义】基础知识必须了解
  • 【comparator, comparable】小总结
  • 【跃迁之路】【733天】程序员高效学习方法论探索系列（实验阶段490-2019.2.23）...
  • 03Go 类型总结
  • canvas 高仿 Apple Watch 表盘
  • CentOS7 安装JDK
  • Consul Config 使用Git做版本控制的实现
  • Go 语言编译器的 //go: 详解
  • Java多线程（4）：使用线程池执行定时任务
  • Redis在Web项目中的应用与实践
  • Spring技术内幕笔记（2）：Spring MVC 与 Web
  • Tornado学习笔记（1）
  • 成为一名优秀的Developer的书单
  • 发布国内首个无服务器容器服务，运维效率从未如此高效
  • 开源地图数据可视化库——mapnik
  • 坑！为什么View.startAnimation不起作用？
  • 如何编写一个可升级的智能合约
  • 如何使用 JavaScript 解析 URL
  • 提醒我喝水chrome插件开发指南
  • 项目管理碎碎念系列之一：干系人管理
  • 因为阿里，他们成了“杭漂”
  • 应用生命周期终极 DevOps 工具包
  • 在Mac OS X上安装 Ruby运行环境
  • No resource identifier found for attribute,RxJava之zip操作符
  • 阿里云API、SDK和CLI应用实践方案
  • 宾利慕尚创始人典藏版国内首秀，2025年前实现全系车型电动化 | 2019上海车展 ...
  • 不要一棍子打翻所有黑盒模型，其实可以让它们发挥作用 ...
  • #我与Java虚拟机的故事#连载04：一本让自己没面子的书
  • #我与虚拟机的故事#连载20：周志明虚拟机第 3 版：到底值不值得买？
  • (Qt) 默认QtWidget应用包含什么？
  • (佳作)两轮平衡小车（原理图、PCB、程序源码、BOM等）
  • (简单) HDU 2612 Find a way，BFS。
  • （十）DDRC架构组成、效率Efficiency及功能实现
  • (十六)、把镜像推送到私有化 Docker 仓库
  • （四）TensorRT | 基于 GPU 端的 Python 推理
  • （已解决）什么是vue导航守卫
  • (转)自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
  • .net core Swagger 过滤部分Api
  • .NET 设计模式初探
  • .NET命名规范和开发约定
  • [100天算法】-不同路径 III（day 73）