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

数据结构--顺序表

news 来源：原创 2024/7/7 9:24:01

目录

前言：        

顺序表

动态顺序表的实现

代码总览：

前言：
        

数据结构是由“数据”和“结构”两词组合而来。

        什么是数据？

常见的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等

等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据

        什么是结构？

当我们想要使⽤大量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的方式

简而言之

  1. 能够存储数据（如顺序表、链表等结构）
  2. 存储的数据能够方便查找

那么为什么需要数据结构呢？

假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：

求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是

否要判断数组是否满了，满了还能继续插⼊吗）.....

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：

        最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。

顺序表

线性表

        线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等

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

知识补充：

逻辑结构和物理结构

1.逻辑结构：

所谓逻辑结构就是数据与数据之间的关联关系，准确的说是数据元素之间的关联关系。

注：所有的数据都是由数据元素构成，数据元素是数据的基本构成单位。而数据元素由多个数据项构成。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。也可以统一的分为线性结构和非线性结构。

2.物理结构：

数据的物理结构就是数据存储在磁盘中的方式。官方语言为：数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

而物理结构一般有四种：顺序存储，链式存储，散列，索引

顺序表

顺序表的底层结构就是数组，对数组的封装，实现了常用的增删改查等接口

顺序表可以分为静态顺序表和动态顺序表

        静态顺序表

静态顺序表是使用定长的数组来存储元素

#define N 10
typedef int Type;
//静态顺序表
struct SeqList
{Type arr[N];//定长数组int size;//有效数据个数
};

使用动态顺序表缺陷：空间给小了不够用，空间给多了造成空间浪费

        动态顺序表

动态顺序表的实现

静态顺序表是定长数组，而动态顺序表是可增容的，不会浪费空间也不会出现空间不够的场景，这里来实现动态顺序表存储整形数据：

首先就是顺序表的一些功能

这里将其写入SeqList.h 的头文件中

SeqList.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Type;
typedef struct SeqList//动态顺序表
{Type* arr;int size;int num;
}SL;
//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
int SLFind(SL* p, Type f);

要存储一些数据，顺序表具备以上功能（对于整型）

顺序表初始化

        顺序表初始化，其实就是将动态顺序表中指针置为NULL，有效数据和空间容量置为0；

代码如下：

// 初始化
void SLInit(SL* p)
{p->arr = NULL;p->size = 0;p->num = 0;
}

在初始化完成后s中的数据。

顺序表销毁

        在使用完顺序表后，就要销毁顺序表，因为动态顺序表内存是动态开辟的，所以需要对动态内存进行释放，并将有效数据和空间容量个数置为0；

代码如下：

//销毁
void SLDesTroy(SL* p)
{if (p->arr != NULL){free(p->arr);p->arr = NULL;}p->size = 0;p->num = 0;
}

        顺序表销毁之后，指针置为NULL，有效数据和空间容量的为0；

顺序表输出

        现在如果顺序表中有数据，我们需要查看数据，就要用到顺序表的输出

代码如下：

//输出
void SLPrint(SL* p)
{for (int i = 0; i < p->size; i++){printf("%d ", p->arr[i]);}printf("\n%d %d\n", p->size, p->num);
}

测试看一下输出

        这里将有效数字和空间容量也输出出来以便查看，下面插入数据以后就不在进行输出了

顺序表扩容

        我们要像顺序表中插入数据，这必然会涉及到扩容的问题

代码如下：

//顺序表扩容
void SLExps(SL* p)
{int num = (p->num == 0) ? 4 : 2 * p->num;Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));assert(tmp);p->arr = tmp;p->num = num;
}

如果首次扩容，即p->num等于0，这样习惯给它赋值成4，以后每次扩容以倍数增加（这里使用2倍，也可以使用3倍）。

扩容以后再测试看一下输出结果（查看有效数据和空间容量）

这里首次扩容，空间容量为4。

        注：扩容主要使用在插入数据判断空间大小不够时

顺序表头插

现在需要从顺序表头部（起始位置）插入数据，这里就需要将有效数据向后移动一位，再进行插入数据以防数据丢失。

        当然，再插入数据之前需要判断空间是否足够

代码如下：

//从头部插入数据
void SLAddHand(SL* p, Type x)
{if (p->size >= p->num){SLExps(p);}for (int i = p->size; i > 0; i--){p->arr[i] = p->arr[i - 1];}p->arr[0] = x;p->size++;
}

测试以下代码是否正确

顺序表头删

从起始位置删除数据，就需要把有效数据向前移动一位，并且有效数据个数-1；

代码如下：
 

//从头部删除数据
void SLDelHand(SL* p)
{for (int i = 0; i < p->size - 1; i++){p->arr[i] = p->arr[i + 1];}p->size--;
}

测试：

顺序表尾插

现在从尾部插入数据，很简单直接在数据末尾插入数据，然后有效数据+1；

        当然，也需要进行判断空间是否足够

代码如下：

//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{if (p->size >= p->num){SLExps(p);}p->arr[p->size] = x;p->size++;
}

测试：

顺序表尾删

从尾部删除数据很简单马，可以直接让有效数据个数-1；

代码如下:

//从尾部删除数据
void SLDelEnd(SL* p)
{p->size--;
}

测试：

顺序表任意位置插入

        从任意位置插入数据，需要将指定位置数据以后的有效数据向后移动一位，再进行插入

代码：

//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{if (p->size >= p->num){SLExps(p);}for (int i = p->size; i > t; i--){p->arr[i] = p->arr[i - 1];}p->arr[t] = x;p->size++;
}

这里就不输出有效数字个数和空间容量了

测试：

顺序表任意数据删除

从任意位置删除数据，将该位置后的数据向前移动一位

代码如下：

//从任意位置删除数据
void SLDeleve(SL* p, int t)
{for (int i = t; i < p->size - 1; i++){p->arr[i] = p->arr[i + 1];}p->size--;
}

测试：

顺序表查找

现在我们需要在顺序表中查找数据

这里也可以写函数返回数据的下标

代码：

//查找数据
void SLFind(SL* p, Type f)
{for (int i = 0; i < p->size; i++){if (p->arr[i] == f){printf("查找的数据下标为：%d\n", i);return;}}printf("所查找的数据不存在\n");
}

测试：

到这里，顺序表的知识就完成了，学完这些，我们也要写顺序表的实践，就是通讯录——在下一篇进行实现。

代码总览：

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Type;
typedef struct SeqList//动态顺序表
{Type* arr;int size;int num;
}SL;//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
void SLFind(SL* p, Type f);

SeqList.c

#include"SeqList.h"// 初始化
void SLInit(SL* p)
{p->arr = NULL;p->size = 0;p->num = 0;
}
//销毁
void SLDesTroy(SL* p)
{if (p->arr != NULL){free(p->arr);p->arr = NULL;}p->size = 0;p->num = 0;
}
//输出
void SLPrint(SL* p)
{for (int i = 0; i < p->size; i++){printf("%d ", p->arr[i]);}printf("\n");//printf("%d %d\n", p->size, p->num);
}
//顺序表扩容
void SLExps(SL* p)
{int num = (p->num == 0) ? 4 : 2 * p->num;Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));assert(tmp);p->arr = tmp;p->num = num;
}
//从头部插入数据
void SLAddHand(SL* p, Type x)
{if (p->size >= p->num){SLExps(p);}for (int i = p->size; i > 0; i--){p->arr[i] = p->arr[i - 1];}p->arr[0] = x;p->size++;
}
//从头部删除数据
void SLDelHand(SL* p)
{for (int i = 0; i < p->size - 1; i++){p->arr[i] = p->arr[i + 1];}p->size--;
}
//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{if (p->size >= p->num){SLExps(p);}p->arr[p->size] = x;p->size++;
}
//从尾部删除数据
void SLDelEnd(SL* p)
{p->size--;
}
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{if (p->size >= p->num){SLExps(p);}for (int i = p->size; i > t; i--){p->arr[i] = p->arr[i - 1];}p->arr[t] = x;p->size++;
}
//从任意位置删除数据
void SLDeleve(SL* p, int t)
{for (int i = t; i < p->size - 1; i++){p->arr[i] = p->arr[i + 1];}p->size--;
}
//查找数据
void SLFind(SL* p, Type f)
{for (int i = 0; i < p->size; i++){if (p->arr[i] == f){printf("查找的数据下标为：%d\n", i);return;}}printf("所查找的数据不存在\n");
}

测试代码（test.c）

#include"SeqList.h"void Test()
{SL s;//初始化SLInit(&s);//SLPrint(&s);//打印//扩容//SLExps(&s);//SLPrint(&s);//打印头插//SLAddHand(&s, 520);//SLAddHand(&s, 1314);//SLPrint(&s);//打印头删//SLDelHand(&s);//SLPrint(&s);尾插//SLAddEnd(&s, 1314);//SLAddEnd(&s, 520);//SLPrint(&s);尾删//SLDelEnd(&s);//SLPrint(&s);//头插SLAddHand(&s, 1);SLAddHand(&s, 2);SLAddHand(&s, 3);SLAddHand(&s, 4);//4 3 2 1 //任意位置插入SLAddeve(&s, 9, 2);//4 3 9 2 1SLPrint(&s);//任意位置删除SLDeleve(&s, 2);SLPrint(&s);//4 3 2 1SLFind(&s, 9);SLFind(&s, 2);//销毁SLDesTroy(&s);
}
int main()
{Test();return 0;
}

制作不易，感到有帮助的可以一键三连支持一下，如果有错误的地方，也请指出！！！

相关文章：

  • flink使用StatementSet降低资源浪费
  • 深入探讨JavaScript中的队列，结合leetcode全面解读
  • nvm安装以及idea下vue启动项目过程和注意事项
  • 华为仓颉编程语言
  • SOLID：软件系统设计的五个基本原则
  • [笔记] 高等数学在各工程门类的典型应用场景
  • adb push 报错 ...error: failed to copy...
  • 数据识别概述
  • Linux多进程和多线程(一)-进程的概念和创建
  • CSS Border(边框)
  • IO多路复用学习
  • c++习题09-分离整数的各个数
  • Python特征工程 — 1.3 对数与指数变换
  • 检测水管缺水的好帮手-管道光电液位传感器
  • 最新mysql打开远程访问和修改最大连接数
  • Android 架构优化~MVP 架构改造
  • android图片蒙层
  • axios 和 cookie 的那些事
  • Flex布局到底解决了什么问题
  • gitlab-ci配置详解(一)
  • go append函数以及写入
  • java8 Stream Pipelines 浅析
  • markdown编辑器简评
  • Netty源码解析1-Buffer
  • Promise初体验
  • React的组件模式
  • Swift 中的尾递归和蹦床
  • vue自定义指令实现v-tap插件
  • 编写符合Python风格的对象
  • 理清楚Vue的结构
  • 那些年我们用过的显示性能指标
  • 强力优化Rancher k8s中国区的使用体验
  • 原生 js 实现移动端 Touch 滑动反弹
  • 自定义函数
  • 长三角G60科创走廊智能驾驶产业联盟揭牌成立，近80家企业助力智能驾驶行业发展 ...
  • ​​快速排序（四）——挖坑法，前后指针法与非递归
  • ​软考-高级-系统架构设计师教程（清华第2版）【第1章-绪论-思维导图】​
  • #我与Java虚拟机的故事#连载02：“小蓝”陪伴的日日夜夜
  • $emit传递多个参数_PPC和MIPS指令集下二进制代码中函数参数个数的识别方法
  • $分析了六十多年间100万字的政府工作报告，我看到了这样的变迁
  • (007)XHTML文档之标题——h1~h6
  • （3）选择元素——（17）练习（Exercises）
  • （5）STL算法之复制
  • （第27天）Oracle 数据泵转换分区表
  • (解决办法)ASP.NET导出Excel，打开时提示“您尝试打开文件'XXX.xls'的格式与文件扩展名指定文件不一致
  • （南京观海微电子）——COF介绍
  • （十）c52学习之旅-定时器实验
  • （原创）可支持最大高度的NestedScrollView
  • (转载)CentOS查看系统信息|CentOS查看命令
  • .net core webapi Startup 注入ConfigurePrimaryHttpMessageHandler
  • .net 程序发生了一个不可捕获的异常
  • @GlobalLock注解作用与原理解析
  • @WebServiceClient注解，wsdlLocation 可配置
  • @我的前任是个极品 微博分析
  • [Angular 基础] - 数据绑定(databinding)