你真的了解线性表中的顺序表了吗?(静态与动态顺序)

2024-02-12 03:20

本文主要是介绍你真的了解线性表中的顺序表了吗?(静态与动态顺序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 今天开启我们数据结构中的第二篇文章了,过了几天我们今天就来了解了解我们常说的顺序表。

在这之前我们也先了解一下线性表。

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构,常见的线性表:顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物 理上存储时,通常以数组和链式结构的形式存储。

那么我们今天就来学习一下顺序表!!!

目录

顺序表的概念

静态顺序表功能的简单实现

动态顺序表的功能简单实现



顺序表的概念

顺序表是一种常见的数据结构,它是将数据元素按照一定的顺序依次存储在连续的存储空间中。
 
顺序表的基本思想是使用一块连续的内存空间来存储数据元素,每个元素按照特定的顺序依次排列。通常,元素在顺序表中的位置可以通过索引来访问,索引从 0 开始递增。
 
顺序表的优点包括:
 
1. 实现简单:顺序表的实现相对简单,易于理解和操作。
2. 随机访问:可以通过索引快速地访问任意位置的元素,具有较高的访问效率。
3. 内存效率:由于元素连续存储,所以可以有效地利用内存空间。

 
然而,顺序表也有一些限制和缺点:
 
1. 插入和删除操作:在顺序表中进行插入和删除操作可能需要移动其他元素,导致较高的时间复杂度。
2. 固定大小:顺序表的大小通常是固定的,在需要扩展时可能需要重新分配内存并复制元素。
3. 内存需求:顺序表需要连续的内存空间,如果数据量较大,可能会受到内存限制。
 

为了克服顺序表的一些限制,可以使用链式结构(如链表)或其他更复杂的数据结构来实现。具体选择取决于具体的应用场景和对数据操作的需求。
 
顺序表在许多编程语言中都有直接的实现,例如数组。它们在需要快速随机访问和顺序处理数据的情况下非常有用,例如在排序、查找、遍历等操作中。


静态顺序表功能的简单实现

根据上方的描述其实在像C语言中的数组也是一个顺序表。 那么下面我们就用数组和代码实现一个顺序表的增,删,查,改函数接口。

 

顺序表的静态储存

struct SEQlist
{int arr[MAXSIZE];int size;};

这里因为数据不同,我们需要创建一个结构体,我们现在使用整形数组来举例。这里的size是指顺序表里有的有效数据,MAXSIZE为宏定义的最大元素数。 

注:这里把结构体命名为SL ,详情如头尾文件定义如下:

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 10typedef struct SEQlist SL;
void Init(SL* s);
void Print(SL* s);
void pushFront(SL* s, int x);

 静态顺序表的格式化接口函数

void Init(SL* s)
{memset(s->arr, 0, sizeof(int) * MAXSIZE);s->size = 0;}

 

这里格式化我们就把数组中的数据都格式化为0,size也格式化为0,格式化我们可以用循环来进行赋值,但是这里我们就用了一个函数进行赋值。函数为memset.

关于memset的介绍各位可以看一下这里:

这里显示了他的头文件和用法,已经被我给圈起来了。 

void * memset ( void * ptr, int value, size_t num );其中num是内容字节大小。

静态顺序表的头插接口函数

 

void pushFront(SL* s, int x)
{int end = s->size - 1;for (int i = end; i >= 0; --i){s->arr[i + 1] = s->arr[i];}s->arr[0] = x;s->size++;}

头插功能即在顺序表开头插上数据。


静态顺序表打印接口

 

void Print(SL* s)
{for (int i = 0; i < s->size; i++){printf("%d ", s->arr[i]);}

 就将数据打印完出来。

 

总结:静态顺序表的缺点还是很明显的,不能够灵活运用数据的大小是固定的,即MAXSIZE,给少了不够用,给多了就用不完。那么接下来我们就弄一个静态的顺序表。


动态顺序表的功能简单实现

这里我们在创建一个结构体,不同的是,因为我们要实现一个动态的顺序表,所以我们不再创建数组,而设置一个指针来实现动态。

struct SQ
{int* a;int size;int capacity};

后面我把此结构SEQ。


动态顺序表的格式化插口

void Init(SEQ* s)
{s->a = NULL;s->size = 0;         // 表示数组中存储了多少个数据s->capacity = 0;   数组实际能存数据的空间容量是多大 }

这里我们将a 指向一个空指针。


动态顺序表的检查与扩容插口函数

void CheckCapacity(SEQ* s)
{// 如果没有空间或者空间不足,那么我们就扩容if (s->size == s->capacity){int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;int* tmp = (int*)realloc(s->a, newcapacity*sizeof(int));if (tmp == NULL){printf("realloc 失败\n");exit(-1);}s->a = tmp;s->capacity = newcapacity;}
}

 这里我们首先检查有没有空间和空间是否足够,如不够则进行扩容,这里扩容我们用到realloc 函数,函数具体使用方法和头文件详情请看下图。

 动态顺序表的尾插和尾删插口函数

void SeqListPushBack(SEQ* s, int x)
{CheckCapacity(s);s->a[s->size] = x;s->size++;
}void SeqListPopBack(SEQ* s)
{// 暴力处理方式assert(s->size > 0);s->size--;
}

 这里就是简单的增加删减,需要注意在尾插时先进行检查容量是否充足。即先调用CheckCapacity函数。

删的时候只要将数据size减1,在打印数据时也只打印前size位数据,所以减减后也可以当作删除了尾部数据。


 动态顺序表的头插和头删函数

 

void SeqListPushFront(SEQ* s, int x)
{CheckCapacity(ps);// 挪动数据int end = s->size - 1;while (end >= 0){s->a[end + 1] = s->a[end];--end;}s->a[0] = x;s->size++;
}void SeqListPopFront(SEQ* s)
{assert(s->size > 0);// 挪动数据int begin = 1;while (begin < s->size){s->a[begin - 1] = s->a[begin];++ begin;}s->size--;
}

也是像上面一样简单增删就不过多解释了 。


动态顺序表的销毁插口

所为销毁也就是令指针销毁,然后让数据和容量位0.

void SeqListDestory(SEQ* s)
{free(s->a);s->a = NULL;s->capacity = s->size = 0;
}

下面给大家看一下插口函数效果。


头插几个数据 

int main()
{Init(&s);SeqListPushFront(&s, 1);SeqListPushFront(&s, 2);SeqListPushFront(&s, 3);SeqListPushFront(&s, 4);SeqListPushFront(&s, 11);Print(&s);return 0;
}

 


再头删几个数据

int main()
{Init(&s);SeqListPushFront(&s, 1);SeqListPushFront(&s, 2);SeqListPushFront(&s, 3);SeqListPushFront(&s, 4);SeqListPushFront(&s, 11);Print(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);Print(&s);return 0;
}


下面就是尾插和尾删了

我们尾插55,95,22,然后又尾删掉三个数据

int main()
{Init(&s);SeqListPushFront(&s, 1);SeqListPushFront(&s, 2);SeqListPushFront(&s, 3);SeqListPushFront(&s, 4);SeqListPushFront(&s, 11);Print(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);Print(&s);SeqListPushBack(&s,55);SeqListPushBack(&s,95);SeqListPushBack(&s,22);Print(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPopBack(&s);Print(&s);return 0;
}

 

 


好了今天到这就结束了。

这篇关于你真的了解线性表中的顺序表了吗?(静态与动态顺序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/701553

相关文章

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot中配置文件的加载顺序解读

《SpringBoot中配置文件的加载顺序解读》:本文主要介绍SpringBoot中配置文件的加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot配置文件的加载顺序1、命令⾏参数2、Java系统属性3、操作系统环境变量5、项目【外部】的ap

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio