线性表之顺序表

 目录

  一   线性表

             1概念:

              2分类

              3特点

二     顺序表

              1概念

              2结构

              3分类

              4静态线性表(使用定长数组存储元素

                                   4.1结构

                                  4.2 静态顺序表缺陷

              5  动态顺序表(利用动态内存管理实现内存的变化)

                                  5.1结构【因为动态顺序表的空间是变化的所以这里相当于静态顺序表多了一个用于存储空间大小的变量】    

                                  5.2动态顺序表中涉及到的方法:【初始化和销毁头/部插⼊删除 / 尾部插⼊删除///指定位置之前插⼊/删除/打印数据】         

一     线性表

          1概念:线性表是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使 ⽤的数据结构。【这里的相同特性指的是在物理结构和逻辑结构】
          2分类:常⻅的线性表:顺序表、链表、栈、队列、字符串...
          3特点:线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储

二     顺序表

           1概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构,⼀般情况下采⽤数组存储。【因为数组在物理地址上是连续的】

既然顺序表是由数组组成的那么顺序表与数组的区别?

顺序表的底层结构是数组,它只是对数组进行了封装,从而实现了常⽤的增删改查等接⼝
          2结构:

         

        3分类:因为数组的大小分为固定的和可以改变大小的,所以顺序表分为静态顺序表(底层数组的大小是固定的)和动态顺序表 (底层数组的大小是可以改变大小的)。
       4静态线性表(使用定长数组存储元素
       4.1结构

这里我们分别对结构体和其中存储元素类型进行取了别名

对结构体取别名的原因:方便我们后续的调用

对结构体中存储元素类型取别名的原因:因为在后续我们不知道我们存储元素的类型如果我们存储的数据类型不是整型那么我们就要对各个涉及的类型进行更改很是麻烦

代码实现

typedef int SLDatatype;#define N 9typedef struct SeqList
{SLDatatype a[N];	//定长数组int size;			//有效数据个数
}SL;

4.2 静态顺序表缺陷

因为静态顺序表的空间是固定的那么存在空间给大/和给小其带来的缺陷

1空间给少:空间给少了不够⽤

2空间给多:空间给多了造成空间浪费

5  动态顺序表(利用动态内存管理实现内存的变化)
    5.1结构【因为动态顺序表的空间是变化的所以这里相当于静态顺序表多了一个用于存储空间大小的变量】

代码实现

typedef int SLDatatype;typedef struct SeqList
{SLDatatype* a;int size;		//有效数据个数int capacity;	//空间容量
}SL;

5.2动态顺序表中涉及到的方法:【初始化和销毁头/部插⼊删除 / 尾部插⼊删除///指定位置之前插⼊/删除/打印数据】

这里我们一般用到三个文件一个头文件(用于函数的声明和定义)和两个源文件(分别用于函数的实现和测试)

SeqList.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;//typedef struct SeqList SL;//初始化
void SLInit(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//头插
void SLPushFront(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps); //查找数据找到了返回下标,找不到返回小于0的数
void SLFind(SL* ps, SLDataType x);//指定位置之前插入数据
void SLErase(SL* ps, int pos, SLDataType x);//指定位删除数据
void SLInsert(SL* ps, int pos);//销毁
void SLDesTroy(SL* ps);//打印
void SLPrint(SL s);判断空间是否满了【扩容】
void SLCheckCapacity(SL* ps);

SeqList.c

#include "SeqList.h"//初始化这里我们要考虑的是我们传参时是传参还是传址因为我们要对顺序表中的变量值进行改变所以我们这里用传址
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//判断空间是否满了【扩容】因为不管是什么有关插入的操作都要判断空间是否满了
// 所以我们把它用于一个函数包装方便后续调用
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity)//判断空间是否满了的条件即当顺序表中的有效数据个数==总的数据个数//但是我们这里要注意一种情况(当顺序表中的有效数据个数==总的数据个数==0时所带来的问题){int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//保证变量的个数!=0SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));//这里我们需要注意几个问题//1用realloc扩容时第二个参数的单位是字节所以我们要用变量的个数与变量的空间大小乘积用于空间的扩容且要保证变量的个数!=0//2用realloc扩容时可能失败所以后续我们要检查是否扩容成功//3扩容的倍数扩:若每次增加的空间较小,可能导致频繁扩容,效率低下//若每次开辟的空间较大,可能存在空间浪费-- > 扩容一般成倍数增加内存[一般成2倍]if (tmp == NULL)//检验是否扩容成功{perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = NewCapacity;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//这里我们防止顺序表是空的所以我们运用断言//判断空间是否满了SLCheckCapacity(ps);ps->arr[ps->size++] = x;}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);//这里顺序表不能为空所以我们要判断有效数据个数是否为0保证有数据可删--ps->size;/*不需要给ps->arr[size - 1]修改值ps->size--后,ps->arr[size - 1]的值并不会影响其他操作*/
}//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}//查找 
// 找到了,返回下标没找到,返回 - 1
void SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}//指定位置之前插入数据
void SLErase(SL* ps, int pos, SLDataType x)
{/*pos可以直接输入值,也可以为SLFind的返回值0 <= pos < size所以我们后面要判断pos的范围*/assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}//指定位置删除数据
void SLInsert(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}//打印
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}
}//销毁(原因记住有借不还再借就难有借有还再借就不难)
void SLDesTroy(SL* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;}

本篇文章就到此结束,欢迎大家订阅我的专栏,欢迎大家指正,希望有所能帮到读者更好了线性表之顺序表相关知识 ,觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识,我们下期再见。

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

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

相关文章

IoTDB 常见问题 QA 第五期

关于 IoTDB 的 Q & A 情人节之际&#xff0c;让 IoTDB Q&A 陪您一起共度解惑&#xff01;我们将定期汇总我们将定期汇总社区讨论频繁的问题&#xff0c;并展开进行详细回答&#xff0c;通过积累常见问题“小百科”&#xff0c;方便大家使用 IoTDB。 Q1&#xff1a;导入…

【NLP】文本预处理

目录 一、文本处理的基本方法 1.1 分词 1.2 命名体实体识别 1.3 词性标注 二、文本张量的表示形式 2.1 one-hot编码 2.2 word2vec 模型 2.2.1 CBOW模式 2.2.2 skipgram模式 2.3 词嵌入word embedding 三、文本数据分析 3.1 标签数量分布 3.2 句子长度分布 3.3 词…

1-16 tortoiseGit分支与Git操作

1-1 创建分支 什么时候需要开分支&#xff1f; - 隔离线上版本和开发版本 - 大功能开发&#xff0c;不想影响到其他人&#xff0c;自己独立开个分支去开发 SVN经典目录结构&#xff1a; - trunk-------------------------开发中的文件 - bran…

4090单卡挑战DeepSeek r1 671b:尝试量化后的心得的分享

引言&#xff1a; 最近&#xff0c;DeepSeek-R1在完全开源的背景下&#xff0c;与OpenAI的O1推理模型展开了激烈竞争&#xff0c;引发了广泛关注。为了让更多本地用户能够运行DeepSeek&#xff0c;我们成功将R1 671B参数模型从720GB压缩至131GB&#xff0c;减少了80%&#xff…

frp与云服务器内网穿透

最近想使用一个便宜的云服务器进行内网穿透&#xff0c;访问到本地电脑 之前使用ssh一直没成功&#xff0c;原因还没分析出来&#xff0c;后来换了一种方法&#xff0c;使用frp来进行内网穿透 frp内网穿透搭建 frp简介 frp 是一个专注于内网穿透的高性能的反向代理应用&…

题海拾贝:英语作文(map)

Hello大家好&#xff01;很高兴我们又见面啦&#xff01;给生活添点passion&#xff0c;开始今天的编程之路&#xff01; 我的博客&#xff1a;<但凡. 我的专栏&#xff1a;《编程之路》、《数据结构与算法之美》、《题海拾贝》 欢迎点赞&#xff0c;关注&#xff01; 1、题…

matlab欠驱动船舶模型预测控制

1、内容简介 matlab135-欠驱动船舶模型预测控制 可以交流、咨询、答疑 2、内容说明 略 针对在风 、 浪 、 流时变干扰下欠驱动水面船舶的轨迹跟踪控制问题 &#xff0c; 设计了一种基于模型 预测控制的轨迹跟踪控制器 &#xff0e; 考虑到欠驱动船舶在没有横向驱动力情况下…

2025年-数据库排名

2025年-数据库排名 https://db-engines.com/en/ranking RADB 完整排名 TOP 10 向量 DBMS 的 DB-Engines 排名 关系型 DBMS 的 DB-Engines 排名 搜索引擎的 DB-Engines 排名 键值存储的 DB-Engines 排名 文档存储的 DB-Engines 排名 图形 DBMS 的 DB-Engines 排名 时间序列 DBM…

sib报错:com.*.xctrunner is not in your device!

1、问题描述 在使用sonic集成IOS设备的时候,我们需要通过sonic-agent服务去识别IOS设备。但是在识别的时候提示如下问题: 本质就是在你这个设备中找不到这个设备也就是找不到WebDriverAgentRunner,但是确实安装了,甚至appium可以正常的调用。 或执行如下命令的时候报错:…

rabbitmq五种模式的总结——附java-se实现(详细)

rabbitmq五种模式的总结 完整项目地址&#xff1a;https://github.com/9lucifer/rabbitmq4j-learning 一、简单模式 &#xff08;一&#xff09;简单模式概述 RabbitMQ 的简单模式是最基础的消息队列模式&#xff0c;包含以下两个角色&#xff1a; 生产者&#xff1a;负责发…

LangChain大模型应用开发:提示词工程应用与实践

介绍 大家好&#xff0c;博主又来给大家分享知识了。今天给大家分享的内容是LangChain提示词工程应用与实践。 在如今火热的大语言模型应用领域里&#xff0c;LangChain可是一个相当强大且实用的工具。而其中的提示词(Prompt)&#xff0c;更是我们与语言模型进行有效沟通的关…

4.buuctf [SWPU2019]Web1及知识点

进入题目页面如下 猜测是二次注入 先注册一个账号 再登录&#xff0c;页面如下 点击申请发布广告 页面如上&#xff0c;存在注入点&#xff0c;尝试 判读是整数型注入还是字符型注入 猜解字段数&#xff0c;尝试发现or,#,空格等被过滤了&#xff0c;只能一个一个试 使用联合…

Lua笔记

Lua语法 --注释 #字符串长度、table从1开始连续元素的长度 ..字符串拼接 逻辑运算符 and or not 条件语句 if xxx then elseif yyy then else end 循环语句 for i1,xxx do end xLua AppDomain does not contain a definition for DefineDynamicAssembly&#xff…

开业盛典活动策划方案拆解

道叔来给大家详细剖析咱们方案库里刚收录的这份《蜀大侠火锅店武侠风开业盛典活动策划方案》了&#xff0c;保证让你看完直呼过瘾&#xff0c;收获满满&#xff01; 一、主题创意&#xff1a;武侠风&#xff0c;直击人心 首先&#xff0c;咱们得夸一下这活动的主题——“XXX‘…

三、Unity基础(主要框架)

一、Unity场景概念 如果把游戏运行过程理解成表演&#xff0c;那么场景就是舞台&#xff1b; 场景本质上是一个配置文件&#xff0c;这个配置文件决定了场景中有哪些东西&#xff1b; 二、Scene和Game窗口 1、Scene 滚轮缩放、拖动 单独选中也可以 最下面这个是全能工具…

微软官方出品GPT大模型编排工具:7个开源项目

今天一起盘点下&#xff0c;12月份推荐的7个.Net开源项目&#xff08;点击标题查看详情&#xff09;。 1、一个浏览器自动化操作的.Net开源库 这是一个基于 Google 开源的 Node.js 库 Puppeteer 的 .NET 开源库&#xff0c;方便开发人员使用无头 Web 浏览器抓取 Web、检索 Ja…

C++笔记之类型大小、变量大小,vector与string在栈上内存、堆上内存和总内存的关系

C++笔记之类型大小、变量大小,vector与string在栈上内存、堆上内存和总内存的关系 code review! 文章目录 C++笔记之类型大小、变量大小,vector与string在栈上内存、堆上内存和总内存的关系1.`std::vector<float>` 的内存占用2.`std::vector<float>` 的 `capaci…

华为昇腾920b服务器部署DeepSeek翻车现场

最近到祸一台HUAWEI Kunpeng 920 5250&#xff0c;先看看配置。之前是部署的讯飞大模型&#xff0c;发现资源利用率太低了。把5台减少到3台&#xff0c;就出了他 硬件配置信息 基本硬件信息 按照惯例先来看看配置。一共3块盘&#xff0c;500G的系统盘&#xff0c; 2块3T固态…

【工具变量】ZF引导基金合集(1900-2024年)

政府引导基金是以股权或债权等方式投资于创业风险投资机构或新设的创业风险投资基金&#xff0c;主要用于支持创业企业的发展。根据不同类型的基金&#xff0c;基金出资结构有所不同&#xff0c;可能由政府全额或部分出资&#xff0c;并吸引社会资本和金融机构的参与。 一、政府…

【Java 面试 八股文】常见集合篇

常见集合篇 1. 常见集合有哪些2. ArrayList底层实现的原理是什么&#xff1f;3. ArrayList listnew ArrayList(10)中的list扩容几次4. 如何实现数组和List之间的转换5. ArrayList和LinkedList的区别是什么&#xff1f;6. 说一下HashMap的实现原理&#xff1f;7. HashMap的jdk1.…