详解初阶数据结构之顺序表（SeqList）——单文件实现SeqList的增删查改

目录

一、线性表

二、顺序表

2.1概念及结构

2.2接口实现

2.3动态顺序表的创建

2.3动态顺序表的初始化

2.3.1传值初始化

2.3.2传址初始化

2.4动态顺序表的清空

2.5动态顺序表的扩容

2.6动态顺序表内容的打印

三、动态顺序表的使用

3.1尾插尾删

3.1.1尾插

3.1.2尾删

3.2头插头删

3.2.1头插

3.2.2头删

3.3在pos位置插入x

3.4删除pos位置的值

3.5修改某个位置的值

四、完整代码

一、线性表

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

二、顺序表

2.1概念及结构

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

顺序表一般分为：

静态顺序表：使用定长数组储存元素。

//静态顺序表
#define N 100
struct SeqList
{int a[N];//定长数组int size;//有效数据的个数
};

 

缺点：不是很灵活

动态顺序表：使用动态开辟的数组储存。

2.2接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

所谓动态其实指的这个结构体里的指针是动态内存开辟来的，是可变的，用的时候动态开辟，不够的话继续开辟，程序结束的时候释放。

2.3动态顺序表的创建

typedef int SLDatatype;//将int重命名为SLDatatype
typedef struct SeqList
{SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL;//将结构体SeqList重命名为SL

2.3动态顺序表的初始化

2.3.1传值初始化

//传值初始化
void SLInit(SL s)
{s.a = NULL;s.size = 0;s.capacity = 0;
}

 函数那个章节我们学过形参只是实参的临时拷贝，并没有实际作用，生命周期短，出了函数的作用域就会销毁，我们不考虑这种初始化方式。

2.3.2传址初始化

//传址初始化
void SLInit(SL* ps)
{ps->a = 0;ps->capacity = 0;ps->size = 0;
}
void SLInit(SL* ps)
{ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->capacity = 4;//开辟了空间就要给容量赋值ps->size = 0;
}

上面两种初始化方式都可以给予结构体成员变量赋值，但是我们使用第二种，因为第二种为我们开辟了空间。


2.4动态顺序表的清空

void SLDestr(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;//内存释放，容量清零ps->size = 0;//内存释放，有效数据清零
}

2.5动态顺序表的扩容

void SLCheckcapacity(SL* ps)
{if (ps->size == ps->capacity){SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp == NULL)//判断是否扩容失败{perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;//扩容后修改原来的容量}
}

这就是所谓的动态，当我们空间不够时，就需要开辟新的空间，使用realloc函数要注意是否开辟成功，定义一个中间指针，当开辟成功时将这个指针赋值给动态数组中的指针。 

2.6动态顺序表内容的打印

void SLprint(SL* ps)
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

size为有效数据个数，使用循环打印其中的有效数据。 

三、动态顺序表的使用

3.1尾插尾删

3.1.1尾插

void SLPushBack(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);//检查空间是否足够插入ps->a[ps->size] = x;//赋值ps->size++;//插入一个有效数据，有效数据个数加一
}

 首先一定要检查规矩是否足够，根据上面开辟的空间，容量为4，有效数据为size为0，所以从第一个空间开始插入数据。

3.1.2尾删

//尾删
void SLPopBack(SL* ps)
{assert(ps->size > 0);//判断是否会造成越界if (ps->size == 0){return;}ps->size--;//删除一个数据，有效数据个数减一
}

插入数据后size的大小也会变化，数组中最后一个数字的下标刚好和size的大小一样我们只需要将size减1就行。 

3.2头插头删

3.2.1头插

void SLPushFront(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);//检查空间是否足够int end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];//将前一个数据后移动end--;}ps->a[0] = x;//将x赋给初始位置ps->size++;//加入一个数字，有效数据个数加1
}

 老规矩一定要检查空间是否足够，头部插入数据我们只需要将原来的数据往后移动一格就将第一格的位置空出来，再将数值插入就行，插入一个数据，有效数据加1即可。

3.2.2头删

void SLPopFront(SL* ps)
{assert(ps->size > 0);//防止越界访问if (ps->size==0){return;}int begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin+1];//将后一个数据往前移动begin++;}ps->size--;//减少一个数字，有效数据减1
}

这里的删除并不是真正意义上的删除，我们只需要将原来的数据往前移动一位使后一位的数据覆盖在前一位，这就做到了删除，顺便再将有效数据减1就行。 

3.3在pos位置插入x

void SLInsert(SL* ps, int pos, int x)
{assert(pos >= 0 && pos <= ps->size);//防止越界访问SLCheckcapacity(ps);int end = ps->size;while (end >=pos){ps->a[end] = ps->a[end-1];//和头插的思想差不多，将数据后移end--;}ps->a[pos] = x;//将x赋值给pos位置ps->size++;//有效数据加1
}

我们可以这样理解：将pos看成初始位置，是不是就转化为头插了？按照头插的思想就可以完成在pos位置上插入x。 

3.4删除pos位置的值

void SLErase(SL* ps, int pos)
{assert(pos >= 0 && pos <= ps->size);//防止越界访问SLCheckcapacity(ps);int begin = pos;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];//和头删的思想差不多，将数据前移begin++;}ps->size--;//有效数据减1
}

我们会发现3.4和3.5不仅可以做到某个位置值的插入和删除，也可以做到尾插尾删和头插头删。 

3.5修改某个位置的值

void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{assert(pos >= 0 && pos < ps->size);//防止越界ps->a[pos] = x;
}

 这样修改某个位置的值看起来是挺麻烦，但是是为了安全考虑。

四、完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//静态顺序表
//#define N 100
//struct SeqList
//{
//	int a[N];//定长数组
//	int size;//有效数据的个数
//};//动态顺序表//创建
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL;
//传值初始化
//void SLInit(SL s)
//{
//	s.a = NULL;
//	s.size = 0;
//	s.capacity = 0;
//}
//传址初始化
//void SLInit(SL* ps)
//{
//	ps->a = 0;
//	ps->capacity = 0;
//	ps->size = 0;
//}
void SLInit(SL* ps)
{ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->capacity = 4;ps->size = 0;
}
//清空
void SLDestr(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}
//打印
void SLprint(SL* ps)
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}
//检查容量
void SLCheckcapacity(SL* ps)
{if (ps->size == ps->capacity){SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);ps->a[ps->size] = x;ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{assert(ps->size > 0);if (ps->size == 0){return;}ps->size--;
}
//头插
void SLPushFront(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);int end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];end--;}ps->a[0] = x;ps->size++;
}
//头删
void SLPopFront(SL* ps)
{assert(ps->size > 0);if (ps->size==0){return;}int begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin+1];begin++;}ps->size--;
}
//在pos位置插入x
void SLInsert(SL* ps, int pos, int x)
{assert(pos >= 0 && pos <= ps->size);SLCheckcapacity(ps);int end = ps->size;while (end >=pos){ps->a[end] = ps->a[end-1];end--;}ps->a[pos] = x;ps->size++;
}
//删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(pos >= 0 && pos <= ps->size);SLCheckcapacity(ps);int begin = pos;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}
int SLFind(SL* ps, int x)
{int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}
int main()
{SL s1;//传值初始化//SLInit(s1);//传址初始化SLInit(&s1);//尾插SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPushBack(&s1, 7);//尾插测试printf("尾插:\n");SLprint(&s1);//尾删SLPopBack(&s1);//尾删测试printf("尾删:\n");SLprint(&s1);//头插SLPushFront(&s1,10);//头插测试printf("头插:\n");SLprint(&s1);//头删 SLPopFront(&s1);//头删测试printf("头删:\n");SLprint(&s1);//在pos位置插入xSLInsert(&s1, 0, 100);//pos插入x测试printf("pos位置插入x\n");SLprint(&s1);//删除pos位置的值SLErase(&s1, 0);//测试printf("删除pos位置的值\n");SLprint(&s1);//改SLModify(&s1, 2, 1);printf("修改某个位置上的值:\n");//SLprint(&s1);//清空SLDestr(&s1);return 0;
}

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

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

相关文章

Echarts 雷达图的详细配置过程

Echarts 雷达图的详细配置过程

文章目录 雷达图 简介配置步骤简易示例 雷达图 简介 Echarts雷达图是一种常用的数据可视化图表类型&#xff0c;用于展示多个维度的数据在同一坐标系下的分布情况。雷达图通过不同的坐标轴表示不同的维度&#xff0c;数据点的位置表示了各个维度的数值大小。 Echarts雷达图的…
阅读更多...
微信小程序中 vant weapp 使用外部的icon作为图标的步骤

微信小程序中 vant weapp 使用外部的icon作为图标的步骤

微信小程序中 vant weapp 使用外部的icon作为图标的步骤 1. 在项目中创建静态资源文件夹2. 前往iconfont图标官网&#xff0c;添加图标并拷贝在线链接3. 下载iconfont代码&#xff0c;解压之后拷贝到小程序的目录中4. 修改iconfont.wxss 将本地链接替换为在线链接5. 在项目的ap…
阅读更多...
【Transformer系列】深入浅出理解Tokenization分词技术

【Transformer系列】深入浅出理解Tokenization分词技术

一、参考资料 NLP技术中的Tokenization是什么&#xff1f;核心任务是什么&#xff1f; 二、Tokenization相关介绍 1. Tokenization的概念 NLP技术中Tokenization被称作是“word segmentation”&#xff0c;直译为分词。具体来说&#xff0c;分词是NLP的基础任务&#xff0c…
阅读更多...
机器学习（15）---代价函数、损失函数和目标函数详解

机器学习（15）---代价函数、损失函数和目标函数详解

文章目录 一、各自定义二、各自详解三、代价函数和损失函数区别四、例题理解 一、各自定义 1. 代价函数&#xff1a;代价函数&#xff08;Cost Function&#xff09;是定义在整个训练集上的&#xff0c;是所有样本误差的平均&#xff0c;也就是损失函数的平均。它用于衡量模型在…
阅读更多...
如何应对数字时代的网络安全新挑战？

如何应对数字时代的网络安全新挑战？

随着数字时代的来临&#xff0c;我们迎来了无限的机遇&#xff0c;同时也伴随着网络安全领域新的挑战。网络攻击变得更加智能化和复杂化&#xff0c;威胁也在不断演化。为了应对这些新挑战&#xff0c;我们必须采取创新的网络安全策略和技术。本文将探讨数字时代网络安全的新挑…
阅读更多...
JVM 篇

JVM 篇

一、知识点汇总 其中内存模型&#xff0c;类加载机制&#xff0c;GC是重点方面。性能调优部分更偏向应用&#xff0c;重点突出实践能力。编译器优化和执行模式部分偏向于理论基础&#xff0c;重点掌握知识点。 内存模型&#xff1a;各部分作用&#xff0c;保存哪些数据。类加载…
阅读更多...
go-GMP和Scheduler

go-GMP和Scheduler

GPM模型 G 待执行的goroutine&#xff0c;结构定义在runtime.g M 操作系统中的线程&#xff0c;它由操作系统的调度器 进行 调度和管理, 结构定义在runtime.m P 处理器&#xff0c;是GM的中间件&#xff0c;它通过一个队列绑定了GM&#xff0c;每个P都有一个局部queue&#x…
阅读更多...
Vue.js新手指南：从零开始建立你的第一个应用

Vue.js新手指南：从零开始建立你的第一个应用

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…
阅读更多...
编程获取图像中的圆半径

编程获取图像中的圆半径

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 即将推出EmguCV的教程&#xff0c;请大家还稍作等待。 之前网友咨询如何获得图像中圆形的半径&#xff0c;其中有两个十字作为标定…
阅读更多...
Kotlin文件遍历FileTreeWalk filter

Kotlin文件遍历FileTreeWalk filter

Kotlin文件遍历FileTreeWalk filter import java.io.Filefun main(args: Array<String>) {val filePath "."val file File(filePath)val fileTree: FileTreeWalk file.walk()fileTree//.maxDepth(1) //遍历层级1&#xff0c;不检查子目录.filter {it.isFile…
阅读更多...
中小企业建设数字化工厂，选择集成还是重构

中小企业建设数字化工厂，选择集成还是重构

随着科技的飞速发展和市场竞争的日益激烈&#xff0c;数字化工厂管理系统已成为中小企业未来发展的必经之路。然而&#xff0c;对于许多中小企业来说&#xff0c;建设数字化工厂并非易事。在建设数字化工厂的过程中&#xff0c;企业需要面对许多问题&#xff0c;其中最关键的问…
阅读更多...
如何使用 RunwayML 进行创意 AI 创作

如何使用 RunwayML 进行创意 AI 创作

标题&#xff1a;如何使用 RunwayML 进行创意 AI 创作 介绍 RunwayML 是一个基于浏览器的人工智能创作工具&#xff0c;可让用户使用各种 AI 功能来生成图像、视频、音乐、文字和其他创意内容。RunwayML 的功能包括&#xff1a; * 图像生成&#xff1a;使用生成式对抗网络 (…
阅读更多...
laravel框架 - 开发实战（目录结构，路由，控制器，模型，视图）

laravel框架 - 开发实战（目录结构，路由，控制器，模型，视图）

一、laravel框架的目录结构 app:应用目录&#xff0c;保存项目中的控制器、模型等 bootstrap:保存框架启动的相关文件 config:配置文件目录 database:数据库迁移文件和数据填充文件 public:应用入口文件index.php和前端资源文件&#xff08;如CSS、JavaScript等&#xff09…
阅读更多...
VEX —— Attribute type metadata

VEX —— Attribute type metadata

Houdini几何体属性有一些元数据metadata&#xff0c;用于指定属性中的数据是否表示某种变换transformation&#xff08;如位置或旋转&#xff09;&#xff0c;及几何体本身被变换时是否或如何被修改&#xff1b; Houdini理解以下信息类型值&#xff1a; “none”&#xff0c;无…
阅读更多...
SQL 2008 R2 和vCenter 5.1安装步骤与AQ

SQL 2008 R2 和vCenter 5.1安装步骤与AQ

准备情况&#xff1a; Windows 2008 r2 sp1 64bit操作系统 Sql 2008 完整版安装包&#xff08;名称&#xff1a;SQLFULL_CHS.iso 安装完成会安装managment&#xff09; vCenter完整版安装包&#xff08;名称&#xff1a;VMware-VIMSetupall-5.1.0-799735.iso&#xff09; …
阅读更多...
Matlab图像处理-HSV

Matlab图像处理-HSV

HSV HSV(色调、饱和度、数值)是人们从颜色轮或调色板中挑选颜色(即颜料或油墨)时所用的几种彩色系统之一。这种彩色系统与RGB系统相比&#xff0c;更加接近于人们的经验和描述彩色感觉时所用的方式。在艺术领域&#xff0c;色调、饱和度和数值分别称为色泽、明暗和调色。 HSV…
阅读更多...
无涯教程-JavaScript - IFS函数

无涯教程-JavaScript - IFS函数

描述 IFS函数检查是否满足一个或多个条件,并返回与第一个TRUE条件相对应的值。此功能已在Excel 2016中添加。 语法 IFS (logical_test1, value_if_true1, [logical_test2, value_if_true2], [logical_test3, value_if_true3]…) 争论 Argument描述Required/Optionallogical…
阅读更多...
短视频seo矩阵系统源码开发搭建--代用户发布视频能力

短视频seo矩阵系统源码开发搭建--代用户发布视频能力

短视频SEO矩阵系统源码开发搭建的代用户发布视频能力&#xff0c;主要是指在系统平台上&#xff0c;允许用户将其创作的内容发布到指定的账号或平台&#xff0c;并设置好相关的标题、话题、锚点等信息。 一、搭建步骤及注意事项 确定使用场景。根据业务需求&#xff0c;确定该…
阅读更多...
2022年CCF-CSP考前冲刺

2022年CCF-CSP考前冲刺

202212-1现值计算 思路&#xff1a; 本题很简单&#xff0c;按照题目所给条件输入输出就行。 注意有效数字。 代码&#xff1a; #include<bits/stdc.h> using namespace std; const int N1010; int n; double i; int q[N]; double all;int main(){cin>>n>>…
阅读更多...
山洪灾害预警方案(山洪预警解决方案的组成)

山洪灾害预警方案(山洪预警解决方案的组成)

​ 随着气候变化的不断加剧&#xff0c;山洪灾害在许多地区成为了极具威胁性的自然灾害之一。为了帮助地方政府和居民更好地预防和应对山洪灾害&#xff0c;我们设计了一套基于星创易联的SR600工业路由器和DTU200的山洪灾害预警方案&#xff0c;并成功在某地区进行了部署。 案…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023