【数据结构】实现顺序表

大家好，我是苏貝，本篇博客带大家了解顺序表，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️
在这里插入图片描述

目录

  • 一.概念及结构
  • 二.接口实现
    • 2.1 创建顺序表结构体
    • 2.2 初始化顺序表
    • 2.3 销毁顺序表
    • 2.4 打印顺序表
    • 2.5 尾插
    • 2.6 头插
    • 2.7 尾删
    • 2.8 头删
    • 2.9 任意位置插入
    • 2.10 任意位置删除
    • 2.11 查找并返回下标
  • 三.模块化代码实现
    • 3.1 SeqList.h
    • 3.2 SeqList.c
    • 3.3 test.c
    • 3.4 结果演示

一.概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1.静态顺序表：使用定长数组存储元素。
在这里插入图片描述

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

在这里插入图片描述

二.接口实现

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

首先在编译器中建立3个文件：SeqList.h文件，即一个头文件，用来声明；SeqList.c文件，用来实现顺序表的增删查改基本功能；test.c文件，用来测试代码

2.1 创建顺序表结构体

因为顺序表信息包括一个动态数组、数据个数和数组容量，后两者都是int型，数组的类型不确定，而且它们所占空间大小不同，所以我们想到创建一个顺序表结构体，为了书写方便，我们将struct SeqList重命名为SL

因为我们不知道多态数组的类型，所以将它的类型定为SLDataType，如果我们后来知道了动态数组的类型，比如是int型，只要将int重命名为SLDataType即可

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据个数
	int capacity;//数组的容量
}SL;

2.2 初始化顺序表

因为初始化顺序表会改变顺序表，所以不能采用传值调用，只能传址，即将顺序表的地址传过来。因为顺序表结构体不能为NULL，所以对它断言，接口都需要使用顺序表结构体，所以每个接口都需要对它断言。
注意：size是最后一个有效数据的下一个索引，因为初始化的时候还没有有效数据，所以size置为0

void SLInit(SL* s)
{
	assert(s);

	s->a = NULL;
	s->size = 0;
	s->capacity = 0;
}

2.3 销毁顺序表

因为我们开辟的是动态数组，所以需要在程序结束前将数组所占空间释放，再让指向该数组的指针a置为NULL

void SLDestroy(SL* s)
{
	assert(s);
	if (s->a != NULL)
	{
		free(s->a);
		s->size = 0;
		s->capacity = 0;
		s->a = NULL;
	}
}

2.4 打印顺序表

打印顺序表不需要改变顺序表，为什么我们还是采用传址调用呢？因为相较于传值调用，两者都可以实现该接口，但是因为函数传参的时候，参数是需要压栈的。如果传递一个结构体对象的时候，结构体过大，参数压栈的的系统开销比较大，所以会导致性能的下降 。简单来讲就是因为形参是实参的一份临时拷贝，若实参（即结构体）过大，那么形参也会较大，这样就会导致效率降低。但传结构体变量的地址的话，形参的大小只是4个或8个字节，效率较传结构体更高。所以我们还是采用传址调用

void SLPrint(SL* s)
{
	assert(s);

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

2.5 尾插

尾插即在动态数组的最后一个有效数据后面插入一个数据。在插入数据之前，我们要判断是否需要增容，增容的条件是有效数据个数size>=数组容量capacity。增容时我们一般将新的容量置为原来容量的2倍，因为我们初始化的时候将初始容量置为0，所以先要对容量判断，如果=0就将新的容量置为4，如果不为0则将新的容量置为原来容量的2倍。因为要增加容量，所以数组的大小会改变，所以用realloc来动态开辟数组，返回值是调整后起始位置的地址。但realloc也可能开辟空间失败，此时它的返回值是NULL，所以我们先要对它的返回值判断，如果为NULL，返回错误信息，不为NULL，将返回值赋值给指向数组的指针a

因为我们准备写的插入接口包含尾插、头插和在任意位置插入，插入时都要判断是否需要增容，所以不妨将增容的代码封装为一个函数

void SLCheckCapacity(SL* s)
{
	if (s->size >= s->capacity)
	{
		int newcapacity = (s->capacity == 0 ? 4 : s->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->a = tmp;
		s->capacity = newcapacity;
	}
}

插入成功后，将有效数据个数size++

void SLPushBack(SL* s, SLDataType x)
{
	assert(s);
  
    //判断是否需要增容
	SLCheckCapacity(s);
	s->a[s->size] = x;
	s->size++;
}

2.6 头插

头插时我们要将所有数据都向后挪一位，再将要插入的数据放在数组索引为0的位置上，不要忘记将有效数据个数size++

void SLPushFront(SL* s, SLDataType x)
{
	assert(s);

	//判断是否需要增容
	SLCheckCapacity(s);
	
	for (int i = s->size-1; i >=0; i--)
	{
		s->a[i + 1] = s->a[i];
	}
	s->a[0] = x;
	s->size++;
}

2.7 尾删

尾删即将最后一个有效数据删除，在删除前要保证有效数据的个数>=1，所以最后一个有效数据的索引>=0，所以要size>0，对它断言。尾删只需要将size- -

void SLPopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);

	s->size--;
}

2.8 头删

头删即将第一个有效数据删除，然后将所有的有效数据都向前挪一位。头删也需要对size断言，删除成功后记得将size- -

void SLPopFront(SL* s)
{
	assert(s);
	assert(s->size > 0);

	for (int i = 1; i < s->size; i++)
	{
		s->a[i - 1] = s->a[i];
	}
	s->size--;
}

2.9 任意位置插入

这个接口需要的形参有指向顺序表结构体的指针，插入位置的下标以及插入的元素。pos要>=0并且要<=size，pos=0时即头插，pos=size时即尾插，对pos断言。最后size++

void SLInsert(SL* s, int pos, SLDataType x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);

	SLCheckCapacity(s);
	for (int i = s->size-1; i >=pos; i--)
	{
		s->a[i + 1] = s->a[i];
	}
	s->a[pos] = x;
	s->size++;
}

2.10 任意位置删除

要使用3个断言，将要删除位置下标之后的元素都向前挪一位，最后size- -

void SLErase(SL* s,int pos)
{
	assert(s);
	assert(s->size > 0);
	assert(pos >= 0 && pos <= s->size);

	for (int i = pos; i < s->size; i++)
	{
		s->a[i] = s->a[i + 1];
	}
	s->size--;
}

2.11 查找并返回下标

对动态数组遍历，如果有要查找的元素，返回其下标，否则返回-1

int SLFind(SL* s, SLDataType x)
{
	assert(s);

	for (int i = 0; i < s->size; i++)
	{
		if (s->a[i] == x)
			return i;
	}
	return -1;
}

三.模块化代码实现

3.1 SeqList.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>


typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;

//初始化顺序表
void SLInit(SL* s);
//打印
void SLPrint(SL* s);
//销毁
void SLDestroy(SL* s);
//头插
void SLPushFront(SL* s, SLDataType x);
//尾插
void SLPushBack(SL* s, SLDataType x);
//头删
void SLPopFront(SL* s);
//尾删
void SLPopBack(SL* s);
//任意位置插入
void SLInsert(SL* s, int pos, SLDataType x);
//任意位置删除
void SLErase(SL* s, int pos);
//查找并返回下标
int SLFind(SL* s, SLDataType x);

3.2 SeqList.c

#include"SeqList.h"

//初始化顺序表
void SLInit(SL* s)
{
	assert(s);

	s->a = NULL;
	s->size = 0;
	s->capacity = 0;
}


//打印
void SLPrint(SL* s)
{
	assert(s);

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


//销毁
void SLDestroy(SL* s)
{
	assert(s);
	if (s->a != NULL)
	{
		free(s->a);
		s->size = 0;
		s->capacity = 0;
		s->a = NULL;
	}
}


//增容
void SLCheckCapacity(SL* s)
{
	if (s->size >= s->capacity)
	{
		int newcapacity = (s->capacity == 0 ? 4 : s->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->a = tmp;
		s->capacity = newcapacity;
	}
}


//头插
void SLPushFront(SL* s, SLDataType x)
{
	assert(s);

	//判断是否需要增容
	SLCheckCapacity(s);
	
	for (int i = s->size-1; i >=0; i--)
	{
		s->a[i + 1] = s->a[i];
	}
	s->a[0] = x;
	s->size++;
}


//尾插
void SLPushBack(SL* s, SLDataType x)
{
	assert(s);

	SLCheckCapacity(s);
	s->a[s->size] = x;
	s->size++;
}


//头删
void SLPopFront(SL* s)
{
	assert(s);
	assert(s->size > 0);

	for (int i = 1; i < s->size; i++)
	{
		s->a[i - 1] = s->a[i];
	}
	s->size--;
}


//尾删
void SLPopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);

	s->size--;
}


//任意位置插入
void SLInsert(SL* s, int pos, SLDataType x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);

	SLCheckCapacity(s);
	for (int i = s->size-1; i >=pos; i--)
	{
		s->a[i + 1] = s->a[i];
	}
	s->a[pos] = x;
	s->size++;
}


//任意位置删除
void SLErase(SL* s,int pos)
{
	assert(s);
	assert(s->size > 0);
	assert(pos >= 0 && pos <= s->size);

	for (int i = pos; i < s->size; i++)
	{
		s->a[i] = s->a[i + 1];
	}
	s->size--;
}


//查找并返回下标
int SLFind(SL* s, SLDataType x)
{
	assert(s);

	for (int i = 0; i < s->size; i++)
	{
		if (s->a[i] == x)
			return i;
	}
	return -1;
}

3.3 test.c

#include"SeqList.h"



void test1()
{
	SL s1;
	SLInit(&s1);
	SLPushFront(&s1, 1);
	SLPushFront(&s1, 2);
	SLPushFront(&s1, 3);
	SLPushFront(&s1, 4);
	SLPrint(&s1);

	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(&s1);

	SLPopFront(&s1);
	SLPopFront(&s1);	
	SLPrint(&s1);

	SLPopBack(&s1);
	SLPopBack(&s1);
	SLPrint(&s1);

	SLDestroy(&s1);
}


void test2()
{
	SL s1;
	SLInit(&s1);
	SLPushFront(&s1, 1);
	SLPushFront(&s1, 2);
	SLPushFront(&s1, 3);
	SLPushFront(&s1, 4);
	SLPrint(&s1);

	SLInsert(&s1, 1, 10);
	SLInsert(&s1, 0, 10);
	SLPrint(&s1);

	SLErase(&s1, 3);
	SLErase(&s1, 2);
	SLPrint(&s1);

	SLDestroy(&s1);
}


void test3()
{
	SL s1;
	SLInit(&s1);
	SLPushFront(&s1, 1);
	SLPushFront(&s1, 2);
	SLPushFront(&s1, 3);
	SLPushFront(&s1, 4);
	SLPrint(&s1);

	int ret=SLFind(&s1, 3);
	printf("%d\n", ret);

	SLDestroy(&s1);
}


int main()
{
	test3();
	return 0;
}

3.4 结果演示

1.test1
在这里插入图片描述

2.test2
在这里插入图片描述

3.test3
在这里插入图片描述

好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

力扣面试150 只出现一次的数字Ⅱ 哈希 统计数位 DFA有穷自动机

力扣面试150 只出现一次的数字Ⅱ 哈希 统计数位 DFA有穷自动机

Problem: 137. 只出现一次的数字 II 文章目录 思路&#x1f496; 哈希&#x1f496; 位数统计&#x1f496; DFA 状态机 思路 &#x1f468;‍&#x1f3eb; 参考 &#x1f496; 哈希 ⏰ 时间复杂度: O ( n ) O(n) O(n) &#x1f30e; 空间复杂度: O ( n ) O(n) O(n) cl…
阅读更多...
从领域外到领域内：LLM在Text-to-SQL任务中的演进之路

从领域外到领域内：LLM在Text-to-SQL任务中的演进之路

导语 本文介绍了ODIS框架&#xff0c;这是一种新颖的Text-to-SQL方法&#xff0c;它结合了领域外示例和合成生成的领域内示例&#xff0c;以提升大型语言模型在In-context Learning中的性能。 标题&#xff1a;Selective Demonstrations for Cross-domain Text-to-SQL会议&am…
阅读更多...
深度学习系列57: 清华大模型MiniCPM上手

深度学习系列57: 清华大模型MiniCPM上手

MiniCPM 是面壁智能与清华大学自然语言处理实验室共同开源的系列端侧大模型&#xff0c;主体语言模型 MiniCPM-2B 仅有 24亿&#xff08;2.4B&#xff09;的非词嵌入参数量 1. 上手对比测试 mps比cpu大概快了9倍左右。 也可以在modelspore上测试&#xff1a;
阅读更多...
XUbuntu22.04之如何创建、切换多个工作区(二百零九)

XUbuntu22.04之如何创建、切换多个工作区(二百零九)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
《最新出炉》系列初窥篇-Python+Playwright自动化测试-13-playwright操作iframe-下篇

《最新出炉》系列初窥篇-Python+Playwright自动化测试-13-playwright操作iframe-下篇

1.简介 通过前边两篇的学习&#xff0c;想必大家已经对iframe有了一定的认识和了解&#xff0c;今天这一篇主要是对iframe做一个总结&#xff0c;主要从iframe的操作&#xff08;输入框、点击等等&#xff09;和定位两个方面进行总结。 2.iframe是什么&#xff1f; iframe 简…
阅读更多...
【Simulink系列】——动态系统仿真 之 离散系统线性离散系统

【Simulink系列】——动态系统仿真 之 离散系统线性离散系统

一、离散系统定义 离散系统是指系统的输入与输出仅在离散的时间上取值&#xff0c;而且离散的时间具有相同的时间间隔。满足下列条件&#xff1a; ①系统&#xff08;的输入输出&#xff09;每隔固定时间间隔才更新一次。固定时间间隔称为采样时间。 ②系统的输出依赖当前的…
阅读更多...
python+flask人口普查数据的应用研究及实现django

python+flask人口普查数据的应用研究及实现django

作为一款人口普查数据的应用研究及实现&#xff0c;面向的是大多数学者&#xff0c;软件的界面设计简洁清晰&#xff0c;用户可轻松掌握使用技巧。在调查之后&#xff0c;获得用户以下需求&#xff1a; &#xff08;1&#xff09;用户注册登录后&#xff0c;可进入系统解锁更多…
阅读更多...
C语言第十八弹---指针(二)

C语言第十八弹---指针(二)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1、const修饰指针 1.1、const修饰变量 1.2、const修饰指针变量 2、指针运算 2.1、指针- 整数 2.2、指针-指针 2.3、指针的关系运算 3、野指针 3.1、…
阅读更多...
【数据结构】----先来聊聊【排序】（先导片）

【数据结构】----先来聊聊【排序】（先导片）

作为一名对技术充满热情的学习者&#xff0c;我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代&#xff0c;我远非专家&#xff0c;而是一位不断追求进步的旅行者。通过这篇博客&#xff0c;我想分享我在某个领域的学习经验&#xff0c;与大家共同探讨、共…
阅读更多...
Vite+Vue3使用Vue-i18n笔记

Vite+Vue3使用Vue-i18n笔记

一、下载依赖 vue-i18n yarn add vue-i18n创建存放语言文件的目录 以及配置文件的配置 我是在src/lang 新建index.ts、cn.ts、en.ts以及test文件夹其中再分别新建cn.ts以及en.ts /lang/index.ts 用于导出vue-i18n需要的配置对象 import en from "./en.ts"; import…
阅读更多...
C#验证字符串是否包含汉字：用正则表达式 vs 用ASCII码 vs 用汉字的 Unicode 编码

C#验证字符串是否包含汉字：用正则表达式 vs 用ASCII码 vs 用汉字的 Unicode 编码

目录 一、使用的方法 1.使用正则表达式验证字符串 2.使用正则表达式验证字符 3.用ASCII码判断 4.用汉字的 Unicode 编码范围判断 二、实例 1.源码 2.生成效果 验证一个字符串是否是纯汉字或者包含有汉字的前提&#xff0c;是VS编辑器的默认编码格式设置为&#xff1a;选…
阅读更多...
项目02《游戏-05-开发》Unity3D

项目02《游戏-05-开发》Unity3D

基于 项目02《游戏-04-开发》Unity3D &#xff0c; 【任务】UI背包系统&#xff0c; 首先将Game窗口设置成1920 * 1080&#xff0c; 设置Canvas的缩放模式&#xff0c;&#xff1a;这样设置能让窗口在任意分辨率下都以一个正确的方式显示&#xff0c; 设置数值&…
阅读更多...
Apollo

Apollo

一. 部署说明 apollo配置中心由三个组件组成&#xff1a; ConfigService 配置中心&#xff0c;客户端从这个服务拉配置&#xff0c;同时内置了Eureka、MetaService。每个环境要有一个 AdminService 配置管理服务&#xff0c;管理数据库配置&#xff0c;Portal调这个服务修改、…
阅读更多...
缓存的概念

缓存的概念

文章目录 一、系统缓存buffer与cachecache 的保存位置cache 的特性 二、用户层缓存DNS缓存 三、浏览器缓存过期机制最后修改时间Etag标记过期时间 expires混合使用和缓存刷新缓存刷新 cookie和session 四、CDN缓存什么是CDN用户请求CDN流程利用 302 实现转发请求重定向至最优服…
阅读更多...
引流技术-通过文件中增加联系方式并传播

引流技术-通过文件中增加联系方式并传播

文章目录 前言文档增加联系方式扩散网盘扩散自建网站借力 注意 前言 很多人在找资料的时候可能都遇到过下图情况&#xff1a; 1、文档最后面留一个自己的联系方式&#xff1b; 2、找的一堆文件中都有相同的情况&#xff1b; 3、一段时间全网搜到的很多相同文件也有这个联系方式…
阅读更多...
Zookeeper分布式队列实战

Zookeeper分布式队列实战

目录 Zookeeper分布式队列 普通方式实现 设计思路 具体实现 使用Curator实现 具体实现 注意事项 Zookeeper分布式队列 常见的消息队列有:RabbitMQ&#xff0c;RocketMQ&#xff0c;Kafka等。Zookeeper作为一个分布式的小文件管理系统&#xff0c;同样能实现简单的队列功…
阅读更多...
【LeetCode: 2670. 找出不同元素数目差数组 + 哈希表 + 前后缀处理】

【LeetCode: 2670. 找出不同元素数目差数组 + 哈希表 + 前后缀处理】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
使用PHPStudy搭建Cloudreve网盘服务

使用PHPStudy搭建Cloudreve网盘服务

文章目录 1、前言2、本地网站搭建2.1 环境使用2.2 支持组件选择2.3 网页安装2.4 测试和使用2.5 问题解决 3、本地网页发布3.1 cpolar云端设置3.2 cpolar本地设置 4、公网访问测试5、结语 1、前言 自云存储概念兴起已经有段时间了&#xff0c;各互联网大厂也纷纷加入战局&#…
阅读更多...
问题：下列哪些属于历史文化资源的特征( ). #学习方法#学习方法

问题：下列哪些属于历史文化资源的特征( ). #学习方法#学习方法

问题&#xff1a;下列哪些属于历史文化资源的特征( ). A、稀缺性 B、脆弱性 C、可再生性 D、多样性 参考答案如图所示
阅读更多...
Apple Vision Pro：新的隐私噩梦？

Apple Vision Pro：新的隐私噩梦？

长期以来&#xff0c;苹果被誉为最注重隐私的科技公司之一&#xff0c;但如今&#xff0c;凭借售价 3499 美元的 Vision Pro&#xff0c;苹果可能已经打造出了一款终极监控机器。 作为苹果首款头戴式“空间计算”显示设备&#xff0c;号称将打造数字世界与物理世界交汇的新空间…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站