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

【数据结构】——顺序表与链表

news 来源：原创 2024/9/30 9:27:16

顺序表与链表

  • 线性表
  • 顺序表
  • 链表
    • 链表的概念
    • 链表的分类
    • 不带头单向非循环链表的实现
    • 带头双向循环链表的实现
    • 顺序表与链表的区别

线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

  • 常见的线性结构：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就是说是连续的一条直线，但是在物理结构上并不一定是连续的，线性表在物理存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表从开始连续存储size个

顺序表时用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组数据存储，在数组上完成数组的增删查改。

顺序表一般分为：
1.静态顺序表

缺点：保存数据的数组较小不够使用，较大浪费

//静态顺序表
typedef int SLDateType;
#define N 10
struct Seqlist
{SLDateType a[N];int size;
};

2.动态顺序表

可以实现按需申请

  • 此时，如果free出现问题，原因可能是指针为野指针，指针未从初始地址释放或者指针越界
//动态顺序表
typedef int SLDateType;
struct Seqlist
{SLDateType* a;int size;int capacity;
};
  • 使用顺序表完成增删查改

seqlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1	
//头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>静态顺序表
//typedef int SLDateType;
//#define N 10
//struct Seqlist
//{
//	SLDateType a[N];
//	int size;
//};//动态顺序表
//定义类型
typedef int SLDataType;
//设置初始容量
#define INIT_CAPACITY 5typedef struct Seqlist
{SLDataType* a;//有效数据个数int size;//容量int capacity;
}SL;//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//增
//后增
void SLPushBack(SL* ps, SLDataType X);
//前增
void SLPushFront(SL* ps, SLDataType X);
//插入
void SLInsert(SL* ps, int pos, SLDataType X);
//删
//后删
void SLPopBack(SL* ps);
//前删
void SLPopFront(SL* ps);
//中间删除
void SLErase(SL* ps, int pos);
//查
int SLFind(SL* ps, SLDataType X);
//改
int SLChange(SL* ps, SLDataType X,SLDataType Y);
//扩容
void SLCheckCap

seqlist.c文件

#include"seqlist.h"//初始化顺序表
void SLInit(SL* ps)
{assert(ps->a);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("Malloc fail");}ps->size = 0;ps->capacity = INIT_CAPACITY;
}//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps->a);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}//打印顺序表
void SLPrint(SL* ps)
{assert(ps->a);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ",ps->a[i]);}printf("\n");
}//后增
void SLPushBack(SL* ps, SLDataType X)
{assert(ps->a);SLCheckCapacity(ps);ps->a[ps->size] = X;ps->size++;
}//后删
void SLPopBack(SL* ps)
{assert(ps->a);assert(ps->size>0);/*if (ps->size == 0){return;}*/ps->size--;
}//前增
void SLPushFront(SL* ps, SLDataType X)
{assert(ps->a);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = X;ps->size++;
}//前删
void SLPopFront(SL* ps)
{assert(ps->a);int begin = 0;while (begin >= 0 && begin < ps->size){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}//中间插入
void SLInsert(SL* ps, int pos, SLDataType X)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = X;ps->size++;
}//中间删除
void SLErase(SL* ps, int pos)
{assert(ps->a);assert(pos >= 0 && pos <= ps->size);int begin = pos;while (begin >= pos && begin <= ps->size){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}//查找
int SLFind(SL* ps, SLDataType X)
{assert(ps->a);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == X){return i;}}return -1;
}//改
int SLChange(SL* ps, SLDataType X , SLDataType Y)
{assert(ps->a);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == X){ps->a[i] = Y;return 0;}}return -1;
}//扩容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){SLDataType* p = (SLDataType*)realloc((void*)ps->a, ps->capacity * sizeof(SLDataType)*2);if (p == NULL){printf("Realloc fail");return;}ps->a = p;p = NULL;ps->capacity *= 2;}
}

main.c文件

#include"seqlist.h"//测试顺序表
void TestSeqlist1()
{//定义顺序表SL s;//初始化顺序表SLInit(&s);//后增SLPushBack(&s,1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);//后删SLPopBack(&s);//打印SLPrint(&s);//前增SLPushFront(&s, 10);SLPushFront(&s, 20);SLPushFront(&s, 40);//打印SLPrint(&s);//前删SLPopFront(&s);//打印SLPrint(&s);//中间插入SLInsert(&s, 1, 6);//打印SLPrint(&s);//中间删除SLErase(&s, 2);//打印SLPrint(&s);//改SLChange(&s, 2, 9);//打印SLPrint(&s);//销毁顺序表SLDestroy(&s);
}int main(void)
{//测试顺序表TestSeqlist1();return 0;
}

链表

了解完顺序表之后，可以明显发现顺序的缺点：

  • 中间与头部的插入删除，时间复杂度为O(N)
  • 增容需要申请空间，拷贝数据，释放旧空间，会有不小的消耗
  • 增容一般是呈2倍增长，会有一定的空间浪费

链表的概念

链表是一种物理存储的结构上非连续，非顺序的存储结构，数据元素的逻辑是通过链表中的指针链接次序实现的

注意：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续。
2.现实中的结点一边拿都是从堆上申请出来的
3.从堆上申请的空间是按照一定的策略来分配的，俩次申请的空间可能连续，也可能不连续
在这里插入图片描述

链表的分类

  • 链表的分类大致分为：
    1.单向或者双向
    在这里插入图片描述

2.带头或者不带头
在这里插入图片描述

3.循环或者非循环
在这里插入图片描述

其中最常用的是不带头单向非循环链表与带头双向循环链表

  • 不带头单向非循环链表：

结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等

  • 带头双向循环链表：

结构最复杂，一般用来单独存储数据，实际中使用的链表数据结构，都是双向循环链表

不带头单向非循环链表的实现

  • slist.h文件
#define  _CRT_SECURE_NO_WARNINGS 1	
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDatatype;typedef struct SLinklistNode
{SLTDatatype date;struct SLinklistNode* next;
}SLTNode;//增加结点
SLTNode* SLTNewNode(SLTDatatype X);//打印
void SLTPrintf(SLTNode* phead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X);
//头删 
void SLTPopFront(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype X);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X);
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos ,SLTDatatype X);
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X);
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//销毁
void SLTDestory(SLTNode** pphead);
  • slist.c文件
#include"slist.h"//打印
void SLTPrintf(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->date);cur = cur->next;}printf("NULL\n");
}//新增加一个结点
SLTNode* SLTNewNode( SLTDatatype X)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->date = X;newnode->next = NULL;return newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X)
{//动态增加一个结点SLTNode* newnode = SLTNewNode(X);newnode->next = *pphead;*pphead = newnode;
}//头删
void SLTPopFront(SLTNode** pphead)
{//温柔/*if (*pphead == NULL){return;}*///断言assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}//尾删
void SLTPopBack(SLTNode** pphead)
{if (*pphead == NULL){return;}assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}//尾增
void SLTPushBack(SLTNode** pphead, SLTDatatype X)
{//新增一个结点SLTNode* newnode = SLTNewNode(X);SLTNode* tail = *pphead;if (*pphead == NULL){*pphead = newnode;}else{while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X)
{SLTNode* cur = pphead;while (cur){if (cur->date == X){return cur;}cur = cur->next;}return NULL;
}//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{assert(pos);assert(pphead);if (*pphead == pos){SLTPushFront(pphead, X);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = SLTNewNode(X);prev->next = newnode;newnode->next = pos;}
}//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead == pos){SLTPopFront(pphead);}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);
}//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{assert(pos);SLTNode* newnode = SLTNewNode(X);newnode->next = pos->next;pos->next = newnode;
}//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
//销毁
void SLTDestory(SLTNode** pphead)
{SLTNode* cur = *pphead;while(cur){SLTNode* tmp = cur->NEXT;free(cur);cur = tmp;}*pphead = NULL;
}

带头双向循环链表的实现

Dlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1	
//带头双向循环链表的增删查改
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义类型
typedef int LTDataType;//定义结构体
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//创建一个返回链表的头结点（哨兵）
ListNode* ListCreate();//双向链表的销毁
void ListDestory(ListNode* phead);//双向链表的打印
void ListPrintf(ListNode* phead);//创造一个newnode
ListNode* ListNewNode(LTDataType x);//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x);//双向链表的尾删
void ListPopBack(ListNode* phead);//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x);//双向链表的头删
void ListPopFront(ListNode* phead);//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x);//双向链表在pos前插入
void ListInsert(ListNode* phead, LTDataType x);//双向链表在pos删除
void ListErase(ListNode* pos);

Dlist.c文件

#include"DList.h"
//创建一个返回链表的头结点（哨兵）
ListNode* ListCreate()
{ListNode* phead = ListNewNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//双向链表的销毁(需自行释放哨兵头)
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* tail = cur;cur = cur->next;free(tail);tail = NULL;}
}//双向链表的打印
void ListPrintf(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;printf("->NULL->");while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}//创造一个newnode
ListNode* ListNewNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = ListNewNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//双向链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;phead->prev = tail->prev;tail->prev->next = phead;free(tail);tail = NULL;
}//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = ListNewNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//双向链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* first = phead->next;phead->next = first->next;first->next->prev = phead;free(first);first = NULL;
}//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//双向链表在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = ListNewNode(x);ListNode* front = pos->prev;newnode->prev = front;newnode->next = pos;front->next = newnode;pos->prev = newnode;
}//双向链表在pos删除(自行释放指针)
void ListErase(ListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}

顺序表与链表的区别

不同点顺序表链表
存储空间上物理上连续逻辑上连续，物理上不一定连续
随机访问支持：O(1)不支持：O(N)
任意位置插入或者删除元素可能需要移动元素，效率低O(N)只需要修改指针指向
插入动态顺序表，空间不够需要扩容没有容量的概念
应用场景元素高效访问，频繁访问任意位置插入和删除频繁
缓存利用率高低

利用率

相关文章：

  • C++ RPC ORM 高速解析
  • pycharm 关闭项目卡死
  • 软件测试/测试开发丨学习笔记之Allure2测试报告
  • 探索Ollama——入门：如何在本地环境中搭建和自定义大型语言模型
  • 【跟着例子学MySQL】多表关联 -- 一对一关系
  • 深入解析Java中的Calendar类
  • ❤ vue2 使用 Element和 vue3 使用 ElementPlus报错
  • 鸿蒙应用开发系列 篇六：鸿蒙系统应用生态与发布、推广
  • GD32F407入坑指南 第三章
  • nssctf（Web刷题）
  • ffmpeg-webrtc(metartc)给ffmpeg添加webrtc协议
  • 如何申请免费域名级SSL证书，实现HTTPS访问
  • AI大模型探索之路-实战篇4：DB-GPT数据应用开发框架调研实践
  • 谷歌快速收录怎么做？
  • 如何选择序列化协议：关键因素与场景分析
  • 实现windows 窗体的自己画，网上摘抄的，学习了
  • [NodeJS] 关于Buffer
  • chrome扩展demo1-小时钟
  • CSS盒模型深入
  • el-input获取焦点 input输入框为空时高亮 el-input值非法时
  • Flex布局到底解决了什么问题
  • magento 货币换算
  • ng6--错误信息小结（持续更新）
  • oldjun 检测网站的经验
  • PAT A1050
  • PAT A1120
  • Python 反序列化安全问题（二）
  • React+TypeScript入门
  • React系列之 Redux 架构模式
  • Spring Boot快速入门（一）：Hello Spring Boot
  • SQLServer插入数据
  • Terraform入门 - 1. 安装Terraform
  • uva 10370 Above Average
  • 创建一个Struts2项目maven 方式
  • 缓存与缓冲
  • 那些被忽略的 JavaScript 数组方法细节
  • 深入浏览器事件循环的本质
  • 使用 Docker 部署 Spring Boot项目
  • 使用 Node.js 的 nodemailer 模块发送邮件（支持 QQ、163 等、支持附件）
  • 突破自己的技术思维
  • 一个JAVA程序员成长之路分享
  • 用简单代码看卷积组块发展
  • 再次简单明了总结flex布局，一看就懂...
  • HanLP分词命名实体提取详解
  • Nginx实现动静分离
  • puppet连载22：define用法
  • 扩展资源服务器解决oauth2 性能瓶颈
  • #Datawhale AI夏令营第4期#AIGC方向 文生图 Task2
  • #基础#使用Jupyter进行Notebook的转换 .ipynb文件导出为.md文件
  • （+4）2.2UML建模图
  • （3）llvm ir转换过程
  • (C11) 泛型表达式
  • （k8s中）docker netty OOM问题记录
  • （备忘）Java Map 遍历
  • （代码示例）使用setTimeout来延迟加载JS脚本文件