【(数据结构)- 顺序表的实现】

顺序表的实现

  • 一.数据结构的相关概念
    • 1、什么是数据结构
    • 2、为什么需要数据结构?
  • 二.顺序表
    • 1.顺序表的概念及结构
      • 1.1 线性表
    • 2、顺序表分类
    • 3、动态顺序表的实现
      • (1)头文件 —— (顺序结构的创建和相关操作函数的定义)
      • (2) 源文件 —— (顺序表相关函数的实现)
      • (3) 源文件 —— (顺序表的测试)
    • 4.顺序表相关操作运行结果展示
      • (1)操作(1)运行结果展示
      • (2) 操作(1)和操作(2)运行结果展示
      • (3)操作(1)和 操作(3)运行结果展示

一.数据结构的相关概念

1、什么是数据结构

先来看两张图片

在这里插入图片描述
在这里插入图片描述
数据结构是由“数据”和“结构”两词组合⽽来。
什么是数据?
常见的数值1、2、3、4…、教务系统里保存的用户信息(姓名、性别、年龄、学历等等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据
什么是结构?
当我们想要使用大量使用同⼀类型的数据时,通过手动定义大量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在⼀起,结构也可以理解为组织数据的方式。
想要找到草原上名叫“咩咩”的羊很难,但是从羊圈里找到1号羊就很简单,羊圈这样的结构有效将羊群组织起来。

概念 数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成,即数据由那部分构成,以什么方式构成,以及数据元素之间呈现的结构。

总结:

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

2、为什么需要数据结构?

还是先来看一张图片

在这里插入图片描述

如图中所⽰,不借助排队的⽅式来管理客⼾,会导致客⼾就餐感受差、等餐时间⻓、餐厅营业混乱等情况。同理,程序中如果不对数据进⾏管理,可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构,能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操作。

最基础的数据结构:数组。
在这里插入图片描述

【思考】有了数组,为什么还要学习其他的数据结构?
假定数组有10个空间,已经使⽤了5个,向数组中插⼊数据步骤:
求数组的⻓度,求数组的有效数据个数,向下标为数据有效个数的位置插⼊数据(注意:这⾥是否要判断数组是否满了,满了还能继续插⼊吗)…
假设数据量⾮常庞⼤,频繁的获取数组有效数据个数会影响程序执⾏效率。
结论: 最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。

二.顺序表

1.顺序表的概念及结构

1.1 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
案例:蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合
如何理解逻辑结构和物理结构?

2、顺序表分类

• 顺序表和数组的区别
◦ 顺序表的底层结构是数组,对数组的封装,实现了常⽤的增删改查等接⼝
• 顺序表分类
◦ 静态顺序表

概念:使用定长数组存储元素
在这里插入图片描述
静态顺序表缺陷:空间给少了不够⽤,给多了造成空间浪费

◦ 动态顺序表

在这里插入图片描述

3、动态顺序表的实现

(1)头文件 —— (顺序结构的创建和相关操作函数的定义)

SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int SLDataType;
//创建循序表结构
typedef struct SeqList
{SLDataType* a;int size;//当前顺序表中的数据有效个数int capacity;//顺序表的当前空间的大小
}SL;
//typedef struct SeqList SL;//对顺序表进行初始化
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//头部/尾部/插入/删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//任意位置/插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);//打印
void SLPrint(SL* ps);
bool SLIsEmpty(SL* ps);//查找
bool SLFind(SL* ps, SLDataType x);

(2) 源文件 —— (顺序表相关函数的实现)

SeqList.c
#include"SeqList.h"//初始化顺序表
void SLInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{if (ps->a)free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;}void SLCheckCapacity(SL* ps)
{//空间不足以插入一个数据,需要扩容if (ps->size == ps->capacity){//扩容SLDataType newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc Fail!\n");return 1;}ps->a = tmp;ps->capacity = newCapacity;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//判断顺序表是否为空//assert(ps->a = NULL);//暴力方式assert(ps);//柔和的方式/*if (ps->a == NULL)return;*///1)空间足够,直接插入//2)空间不够,需要扩容SLCheckCapacity(ps);//空间足够,直接插入ps->a[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//空间足够,历史数据后移一位;for (size_t i = ps->size; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;
}
//尾删
void SLPopBack(SL* ps) 
{assert(ps);assert(!SLIsEmpty(ps));//ps->a[ps->size - 1] = 0;ps->size--;
}//头删
void SLPopFront(SL* ps)
{assert(ps);assert(!SLIsEmpty(ps));for (size_t i = 1; i < ps->size-1; i++){//最后一次进来的是ps->a[ps->size-2]ps->a[i] = ps->a[i+1];//pa->a[ps->size-2]=ps->a[ps->size-1]}ps->size--;
}//任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//判断插入的位置是否在范围内assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//空间足够,把pos的位置及以后的数据往后移一位//此处i<ps->size和ps->size-1都可以,但是后面的不步骤需要对应for (size_t i = ps->size; i > pos; i--){ps->a[i] = ps->a[i-1];}/*for (size_t i = ps->size - 1; i > pos; i--){ps->a[i+1] = ps->a[i];}*/ps->a[pos] = x;ps->size++;}
//任意位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(!SLIsEmpty(ps));assert(pos >= 0 && pos < ps->size);//pos位置及以后的数据往前移动一位for (size_t i = pos; i < ps->size-1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;}void SLPrint(SL* ps)
{for (size_t i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}
bool SLIsEmpty(SL* ps)
{assert(ps);//这样是不对的,这只是判断空间是否足够//return ps->size = ps->capacity;return ps->size == 0;
}bool SLFind(SL* ps, SLDataType x)
{scanf("%d", &x);for (size_t i = 0; i < ps->size; i++){if (ps->a[i] == x){return true;}}return false;
}

(3) 源文件 —— (顺序表的测试)

test.c
#include"SeqList.h"void SLtest()
{SL sl;SLInit(&sl);//顺序表的具体操作//尾插//操作(1)SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//头插SLPushFront(&sl, 5);SLPushFront(&sl, 6);SLPushFront(&sl, 7);SLPushFront(&sl, 8);SLPrint(&sl);//尾删//操作(2)SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPrint(&sl);//头删SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPrint(&sl);//任意位置插入删除//操作(3)SLInsert(&sl, 0, 9);SLPrint(&sl);SLErase(&sl, 8);SLPrint(&sl);bool ret =SLFind(&sl, 9);if (ret)printf("找到了\n");elseprintf("没找到\n");SLDestroy(&sl);}
int main()
{SLtest();return 0;
}

4.顺序表相关操作运行结果展示

(1)操作(1)运行结果展示

在这里插入图片描述

(2) 操作(1)和操作(2)运行结果展示

在这里插入图片描述

(3)操作(1)和 操作(3)运行结果展示

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160312.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DCDC Buck电路地弹造成的影响

很多读者都应该听过地弹&#xff0c;但是实际遇到的地弹的问题应该很少。本案例就是一个地弹现象导致电源芯片工作不正常的案例。 問題描述 如下图1 &#xff0c;产品其中一个供电是12V转3.3V的电路&#xff0c;产品发货50K左右以后&#xff0c;大约有1%的产品无法启动&#…

图解Dubbo,Dubbo 服务治理详解

目录 一、介绍1、介绍 Dubbo 服务治理的基本概念和重要性2、阐述 Dubbo 服务治理的实现方式和应用场景 二、Dubbo 服务治理的原理1、Dubbo 服务治理的架构设计2、Dubbo 服务治理的注册与发现机制3、Dubbo 服务治理的负载均衡算法 三、Dubbo 服务治理的实现方式1、基于 Docker 容…

基于Vue+webpack之H5打包资源优化

前言 基于公司的业务以及今年接触到的项目大部分都是APP混合开发&#xff0c;即原生Android/ios H5页面开发APP。项目从产品需求的评审到方案的评审再到开发提测...这一套流程下来让我收货颇多。总想找个时间好好记录一番&#xff0c;大概还是自己懒惰了&#xff0c;一直拖到现…

【OpenCV-PyQt5-PyGame-imutils】探索Python中的图像和视频捕获:性能分析与选择指南

前言 随着计算机视觉和多媒体应用的不断发展&#xff0c;图像和视频捕获变得越来越重要。在Python中&#xff0c;有多种库和工具可供选择&#xff0c;用于打开摄像头、捕获图像、以及处理视频流。本文旨在为读者提供对这些捕获方法的全面了解&#xff0c;并介绍如何计算平均帧…

JVM类装载器详解

目录 一、类装载的过程 1.1 装载(Load) 1.2 链接(Link) 1.2.1 验证(Varify) 二、类装载器组成 1. JVM 中内置了三个重要的 ClassLoader&#xff0c;同时按如下顺序进行加载&#xff1a; 2、图解 3、加载原则 所谓的双亲委派 类加载器负责在运行时将Java类动态加载到Java虚拟机&…

零售数据分析模板鉴赏-品类销售结构报表

不管是服装零售&#xff0c;还是连锁超市或者其他&#xff0c;只要是零售行业就绕不过商品数据分析&#xff0c;那么商品数据分析该怎么做&#xff1f;奥威BI的零售数据分析方案早早就预设好相关报表模板&#xff0c;点击应用后&#xff0c;一键替换数据源&#xff0c;立得新报…

论文阅读:Segment Any Point Cloud Sequences by Distilling Vision Foundation Models

目录 概要 Motivation 整体架构流程 技术细节 小结 论文地址&#xff1a;[2306.09347] Segment Any Point Cloud Sequences by Distilling Vision Foundation Models (arxiv.org) 代码地址&#xff1a;GitHub - youquanl/Segment-Any-Point-Cloud: [NeurIPS23 Spotlight]…

学生用什么样的台灯比较好?分享最合适学生使用的台灯

随着现在生活水平的提高&#xff0c;越来越多人重视健康的问题。尤其是对于孩子&#xff0c;很多家长对其可谓是百般担心、千般呵护&#xff0c;害怕出现什么问题&#xff0c;其中最主要的就是近视。而如今&#xff0c;我国青少年儿童的近视率可不低的&#xff0c;达到了52.7%&…

字符与数字的相互转换

一、字符转数字 char类型字符转换为数字&#xff0c;其实是转换为ASCII码值 有两种方式&#xff1a; 1.强制类型转换&#xff0c;结果为对应的ASCII码值 char v1 a;char v2 z;char v3 1;char v4 9;int num1 (int)v1;int num2 (int)v2;int num3 (int)v3;int num4 (int)v…

如果Domino上的邮件无法直接发送到@outlook.com

大家好&#xff0c;才是真的好。 目前将Domino仅仅作为邮件服务器的企业用户还不少。如果Domino服务器版本比较新&#xff08;例如版本为11.0.x、12.0.x等&#xff09;&#xff0c;外发邮件时&#xff0c;没有通过邮件网关中转邮件&#xff0c;而是直接发送到Internet互联网上…

部署k8s dashboard(这里使用Kubepi)

9. 部署k8s dashboard&#xff08;这里使用Kubepi&#xff09; Kubepi是一个简单高效的k8s集群图形化管理工具&#xff0c;方便日常管理K8S集群&#xff0c;高效快速的查询日志定位问题的工具 部署KubePI&#xff08;随便在哪个节点部署&#xff0c;我这里在主节点部署&#…

Leetcode刷题详解——有效三角形的个数

1.题目链接&#xff1a;有效三角形的个数 2.题目描述&#xff1a; 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3示…

kafka 相关概念

1 kafka 生产者 kafka 用push的方式把消息推送到topic 每个topic下可以有多个分区&#xff0c; 可以用hash 也可以用轮询的方式指定分区 每个分区内部是可以保证顺序的&#xff0c;但是整体无法保证顺序&#xff0c;除非设置成一个topic只有一个分区。 kafka这种多分区的设置 带…

在vs code中创建一个名为 “django_env“ 的虚拟环境报错?!以下方法可以解决

# vs code 终端窗口中运行&#xff1a; mkvirtualenv django_env # 拓展&#xff1a; mkvirtualenv django_env 是一个命令&#xff0c;用于创建一个名为 "django_env" 的虚拟环境。虚拟环境是一种用于隔离不同Python项目所需依赖的工具。通过创建虚拟环境&#x…

AC/DC电源模块工作效率的特点

BOSHIDA AC/DC电源模块工作效率的特点 AC/DC电源模块是一种用来将交流电转换为直流电的设备&#xff0c;在各种电子设备中应用广泛。其中&#xff0c;工作效率是评价AC/DC电源模块性能的关键指标之一。下面将从工作效率的特点方面进行阐述&#xff0c;以帮助读者更好地理解AC/…

小程序开发平台源码系统+ 带前后端完整搭建教程

大家好&#xff0c;给大家分享一个小程序开发平台源码系统。这款小程序开发平台中有很多功能&#xff0c;今天主要来给大家介绍一下洗车行业小程序制作的功能。以下是部分核心代码图&#xff1a; 系统特色功能&#xff1a; LBS定位&#xff1a;小程序能够自动显示附近的共享洗…

mysql面试题50:500台数据库,如何在最快时间之内重启

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:500台db,如何在最快时间之内重启呢? 如果需要在最快时间内重启500台数据库,可以考虑采用并行化和自动化的方法来提高效率。比如: 编写自动化脚…

Window 窗口函数 (Spark Sql)

在 Spark SQL 中&#xff0c;Window 函数是一种用于在查询结果集中执行聚合、排序和分析操作的强大工具。它允许你在查询中创建一个窗口&#xff0c;然后对窗口内的数据进行聚合计算。 import org.apache.spark.sql.expressions.Window import org.apache.spark.sql.functions…

Python+高光谱数据预处理-机器学习-深度学习-图像分类-参数回归

涵盖高光谱遥感数据处理的基础、python开发基础、机器学习和应用实践。重点解释高光谱数据处理所涉及的基本概念和理论&#xff0c;旨在帮助学员深入理解科学原理。结合Python编程工具&#xff0c;专注于解决高光谱数据读取、数据预处理、高光谱数据机器学习等技术难题&#xf…

FPGA基于1G/2.5G Ethernet PCS/PMA or SGMII实现 UDP 网络视频传输,提供工程和QT上位机源码加技术支持

目录 1、前言版本更新说明免责声明 2、我这里已有的以太网方案3、设计思路框架视频源选择OV5640摄像头配置及采集动态彩条UDP协议栈UDP视频数据组包UDP协议栈数据发送UDP协议栈数据缓冲IP地址、端口号的修改Tri Mode Ethernet MAC1G/2.5G Ethernet PCS/PMA or SGMIIQT上位机和源…