【数据结构】——顺序表（增删查改）

 

目录

 前言：

顺序表： 

1、概念及分类 

1.1顺序表分类

静态顺序表

动态顺序表

 2、接口实现

2.1功能要求

2.2功能实现 

💡初始化顺序表

 💡销毁顺序表

 💡顺序表尾插入

💡检查是否扩容 

💡打印顺序表 

 💡顺序表头插入

💡顺序表头删除

💡顺序表尾删除

💡顺序表pos位置插入值

 💡顺序表删除pos的位置

 总代码

test.c

 SeqList.c

 SeqList.h

 

 前言：

数据结构是计算机存储、组织数据的方式。 

数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

能够存储数据（如顺序表、链表等结构）
存储的数据能够方便查找

顺序表： 

数据结构分为：线性表和非线性表，

        顺序表就是线性表中的一个小类。

何为线性表：线性表是指n个具有相同性质的数据元素的有限序列，

        常见的线性表有：顺序表、链表、栈、队列、字符串等等。

注：线性表的物理结构不一定是线性的，它在逻辑结构上一定是线性的（这个很好理解，等我们学完顺序表和单链表这对黄金搭档，就明白这句话的含义了。（逻辑结构类似于想象的，比如箭头这种东西在内存中是存在的））

顺序表是线性表，顺序表在逻辑结构和物理结构上都是线性的。 

 

1、概念及分类 

顺序表（SeqList）：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（连续存储数据，不能跳跃）。 

类似于数组，但是顺序表是连续的（只能从头开始连续），数组不需要连续；

1.1顺序表分类

静态顺序表

概念：使用定长数组存储元素

缺陷：空间给少了不够⽤，给多了造成空间浪费

//静态顺序表
typedef int SLDataType;
#define N 7
struct SeqList
{
    SLDataType arr[N];  //定长数组
    int size;       //有效数据个数
}SL;

 

动态顺序表

概念：使用动态开辟的数组存储。 

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
    SLDateType* array;  //指向动态开辟的数组
    size_t size;  //数据中存储的数据
    size_t capacity;   //数组的容量
}SeqList;

 

建议用动态顺序表，比起静态顺序表，动态的更加好调整顺序表的大小。接下来，我也会以动态顺序表为例，介绍如何实现动态顺序表的增删查改。 

 2、接口实现

2.1功能要求

#pragma once
#include<stdio.h>
#include<assert.h>

//对顺序表的初始化
void SeqListInit(SL* ps);

//对顺序表的销毁
void SeqListDestroy(SL* ps);

//对顺序表的打印
void SeqListPrint(SL* ps);

//对顺序表的尾插入
void SeqListPushBack(SL* ps, SLDataType x);

//对顺序表的头插入
void SeqListPushFront(SL* ps, SLDataType x);

//对顺序表头删除
void SeqListPopFront(SL* ps);

//对顺序表的尾删除
void SeqListPopBack(SL* ps);

// 顺序表查找
//int SeqListFind(SeqList* ps, SLDateType x);
 
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);


// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);

2.2功能实现 

💡初始化顺序表

没啥好说的，在【C语言】系列都讲过了，3 2 1 上链接

//初始化
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->arry = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
 💡销毁顺序表
//销毁
void SeqListDestroy(SL* ps)
{
	assert(ps);
	if (ps->arry != NULL)
	{
		free(ps->arry);
		ps->arry = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}
 💡顺序表尾插入

这里需要检查是否需要扩容，我们还需要提前封装一个函数

//对顺序表的尾插入
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//检查是否需要扩容
	CheckCapacity(ps);
	ps->arry[ps->size] = x;
	ps->size++;
}
💡检查是否扩容 

在这里需要注意的就是，我们初始化的时候，capacity是0，如果用常规*2方式扩容，0*2还是0；

所以这里可以用上一个三目操作符来避免；realloc可以对空指针进行开辟空间，相当于malloc

 

//检查是否需要扩容
void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)	//需要扩容
	{
		int new =ps->capacity == 0 ? 4 :ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arry, sizeof(SLDataType)*new);
		//检查是否扩容成功
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->arry = tmp;
		ps->capacity = new;
		printf("扩容成功\n");
	}
}
💡打印顺序表 
//打印顺序表
void SeqListPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arry[i]);
	}
	printf("\n");
}
 💡顺序表头插入

不管是头插入还是尾插入以及后面的任意位置插入，都需要检查是否需要扩容，

头插入就相当于先将数据往右边移动，头位置空出来，然后将新数据插入即可

//头插入
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int begin = ps->size;
	while (begin>0)
	{
		ps->arry[begin] = ps->arry[begin - 1];
		begin--;
	}
	ps->arry[0] = x;
	ps->size++;
}
💡顺序表头删除

 因为顺序表的逻辑结构和物理结构一致，数据前后紧密相连的，所以可以直接将数据往前覆盖

//头删除
void SeqListPopFront(SL* ps)
{
	assert(ps);
	int begin = 1;
	while (begin > 0 &&  begin < ps->size )
	{
		ps->arry[begin - 1] = ps->arry[begin];
		begin++;
	}
	ps->size--;
}
💡顺序表尾删除

需要注意的就说size跑到负数去，我们采取“七匹狼式警告”，直接“竹条炒肉”

//尾删除
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//对size检查 防止越界
	assert(ps->size > 0);
	ps->size--;
}
💡顺序表pos位置插入值

在容量内任意位置插入，将该位置后的数据往后移，将新元素赋值

// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int begin = ps->size;
	while (begin > pos)
	{
		ps->arry[begin] = ps->arry[begin - 1];
		begin--;
	}
	ps->arry[pos] = x;
	ps->size++;
}
 💡顺序表删除pos的位置
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	int begin = pos;
	while (begin < ps->size)
	{
		ps->arry[begin] = ps->arry[begin + 1];
		begin++;
	}
	ps->size--;
}

 总代码

注意，我们完成每个功能实现，最好都单独测试一下，不要留到最后，不然就会这样

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//11-4ݽṹ
#include<stdio.h>

void test1()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1,1);
	SeqListPrint(&s1);

	SeqListDestroy(&s1);
}

void test2()
{
	SL s2;
	SeqListInit(&s2);
	SeqListPushBack(&s2, 1);
	SeqListPushBack(&s2, 2);
	SeqListPushBack(&s2, 3);
	SeqListPushBack(&s2, 4);
	SeqListPushBack(&s2, 5);

	SeqListPushFront(&s2,10);
	SeqListPrint(&s2);
	
}

//void test3()
//{
//	SL s3;
//	SeqListInit(&s3);
//	SeqListPushBack(&s3, 1);
//	SeqListPushBack(&s3, 2);
//	SeqListPushBack(&s3, 3);
//	SeqListPushBack(&s3, 4);
//	SeqListPushBack(&s3, 5);
//	SeqListPrint(&s3);
//
//	SeqListPopFront(&s3);
//	SeqListPrint(&s3);
//}

void test4()
{
	SL s4;
	SeqListInit(&s4);
	SeqListPushBack(&s4, 1);
	SeqListPushBack(&s4, 2);
	SeqListPushBack(&s4, 3);
	SeqListPushBack(&s4, 4);
	SeqListPushBack(&s4, 5);
	SeqListPrint(&s4);

	SeqListInsert(&s4, 2, 66);
	SeqListPrint(&s4);
}
void test5()
{
	SL s5;
	SeqListInit(&s5);
	SeqListPushBack(&s5, 1);
	SeqListPushBack(&s5, 2);
	SeqListPushBack(&s5, 3);
	SeqListPushBack(&s5, 4);
	SeqListPushBack(&s5, 5);
	SeqListPrint(&s5);
	SeqListErase(&s5, 2);
	SeqListPrint(&s5);
}
int main()
{ 
	//test1();
	//test2();
	//test3();
	//test4();
	test5();
	return 0;
}

 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//初始化
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->arry = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//销毁
void SeqListDestroy(SL* ps)
{
	assert(ps);
	if (ps->arry != NULL)
	{
		free(ps->arry);
		ps->arry = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}
//检查是否需要扩容
void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)	//需要扩容
	{
		int new =ps->capacity == 0 ? 4 :ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arry, sizeof(SLDataType)*new);
		//检查是否扩容成功
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->arry = tmp;
		ps->capacity = new;
		printf("扩容成功\n");
	}
	
}
//对顺序表的尾插入
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//检查是否需要扩容
	CheckCapacity(ps);
	ps->arry[ps->size] = x;
	ps->size++;
}
//打印顺序表
void SeqListPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arry[i]);
	}
	printf("\n");
}
//头插入
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int begin = ps->size;
	while (begin>0)
	{
		ps->arry[begin] = ps->arry[begin - 1];
		begin--;
	}
	ps->arry[0] = x;
	ps->size++;
}
//头删除
void SeqListPopFront(SL* ps)
{
	assert(ps);
	int begin = 1;
	while (begin > 0 &&  begin < ps->size )
	{
		ps->arry[begin - 1] = ps->arry[begin];
		begin++;
	}
	ps->size--;
}
//尾删除
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//对size检查 防止越界
	assert(ps->size > 0);
	ps->size--;
}

// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int begin = ps->size;
	while (begin > pos)
	{
		ps->arry[begin] = ps->arry[begin - 1];
		begin--;
	}
	ps->arry[pos] = x;
	ps->size++;
}

// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	int begin = pos;
	while (begin < ps->size)
	{
		ps->arry[begin] = ps->arry[begin + 1];
		begin++;
	}
	ps->size--;

 SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arry;	//动态开辟的数组
	int size;	//记录个数
	int capacity;	//记录容量
}SL;



//对顺序表的初始化
void SeqListInit(SL* ps);

//对顺序表的销毁
void SeqListDestroy(SL* ps);

//对顺序表的打印
void SeqListPrint(SL* ps);

//对顺序表的尾插入
void SeqListPushBack(SL* ps, SLDataType x);

//对顺序表的头插入
void SeqListPushFront(SL* ps, SLDataType x);

//对顺序表头删除
void SeqListPopFront(SL* ps);

//对顺序表的尾删除
void SeqListPopBack(SL* ps);

// 顺序表查找
//int SeqListFind(SeqList* ps, SLDateType x);
 
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);


// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);

 

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

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

相关文章

php实现钉钉机器人推送消息和图片内容(完整版)

php实现钉钉机器人推送消息和图片内容(完整版)

先来看下实现效果: 代码如下: function send_dingtalk_markdown($webhook , $title , $message "", $atMobiles [], $atUserIds []) {$data ["msgtype" > "markdown","markdown" > ["title" > $title,&quo…
阅读更多...
ZZ308 物联网应用与服务赛题第H套

ZZ308 物联网应用与服务赛题第H套

2023年全国职业院校技能大赛 中职组 物联网应用与服务 任 务 书 &#xff08;H卷&#xff09; 赛位号&#xff1a;______________ 竞赛须知 一、注意事项 1.检查硬件设备、电脑设备是否正常。检查竞赛所需的各项设备、软件和竞赛材料等&#xff1b; 2.竞赛任务中所使用的…
阅读更多...
QT实现的一个MVP设计模式demo

QT实现的一个MVP设计模式demo

最近做qt 项目,发现网上基于MVP设计模式的QT例程很少&#xff0c;这里写一个demo示例可作为参考&#xff1a; 一、简要概述 MVP是由MVC发展而来&#xff0c;总体目的与作用相同。都是为了软件构架有层次之分&#xff0c;使得核心逻辑、界面控制、数据这三者分层清晰明了。减少…
阅读更多...
CentOS/RHEL7环境下更改网卡名称为CentOS6的传统命名规则

CentOS/RHEL7环境下更改网卡名称为CentOS6的传统命名规则

图片 CentOS/RHEL7网卡命名规则介绍 图片 传统的Linux服务器网卡的名称命名方式是从eth0,eth1,eth2....这种方式命名的&#xff0c;但是这个编号往往不一定准确对应网卡接口的物理顺序&#xff0c;常规模式下我们使用的服务器设备可能只有一张网卡&#xff0c;若网卡较多的情…
阅读更多...
SpringCloud 微服务全栈体系（十二）

SpringCloud 微服务全栈体系（十二）

第十一章 分布式搜索引擎 elasticsearch 一、初识 elasticsearch 1. 了解 ES 1.1 elasticsearch 的作用 elasticsearch 是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff0c;可以帮助我们从海量数据中快速找到需要的内容 例如&#xff1a; 在 GitHub 搜…
阅读更多...
新能源汽车高压线束是如何快速连接到测试设备上进行电性能测试的

新能源汽车高压线束是如何快速连接到测试设备上进行电性能测试的

快速连接形成稳定的电测试在新能源行业里面是很常见的测试场景&#xff0c;比如说在新能源汽车行业的电池包、电机、电控制器的电性能测试中会有很多高压线束&#xff0c;需要将这些线束和电池包、电控制器、电机与测试设备快速连接在一起进行相关的EOL/DCR测试。 新能源汽车高…
阅读更多...
UML/SysML建模工具更新（2023.10）（1）StarUML、Software Ideas Modeler

UML/SysML建模工具更新（2023.10）（1）StarUML、Software Ideas Modeler

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 工具最新版本&#xff1a;Software Ideas Modeler 14.02 更新时间&#xff1a;2023年10月9日 工具简介 轻量级建模工具&#xff0c;支持UML、BPMN、SysML。 平台&#xff1a;Windo…
阅读更多...
如何在搜索引擎中应用AI大语言模型，提高企业生产力？

如何在搜索引擎中应用AI大语言模型，提高企业生产力？

人工智能尤其是大型语言模型的应用&#xff0c;重塑了我们与信息交互的方式&#xff0c;也为企业带来了重大的变革。将基于大模型的检索增强生成&#xff08;RAG&#xff09;集成到业务实践中&#xff0c;不仅是一种趋势&#xff0c;更是一种必要。它有助于实现数据驱动型决策&…
阅读更多...
如何做好测试管理岗？深度分析职业规划

如何做好测试管理岗？深度分析职业规划

经常就有同学说&#xff1a;我以后要做管理岗&#xff01;其实对于很多刚入行的同学&#xff0c;可能说这句话的时候并没有真正理解管理岗需要做什么事&#xff0c;以及需要具备什么样的技能。所以&#xff0c;作为资深测试经理&#xff0c;我来跟大家分享一下管理岗需要具备的…
阅读更多...
了解web3，什么是web3

了解web3，什么是web3

Web3是指下一代互联网&#xff0c;它基于区块链技术&#xff0c;将各种在线活动更加安全、透明和去中心化。Web3是一个广义的概念&#xff0c;它包括了很多方面&#xff0c;如数字货币、去中心化应用、智能合约等等。听不懂且大多数人听到这个东西&#xff0c;直觉感觉就像骗子…
阅读更多...
SpringBoot整合Mybatis-plus代码生成器

SpringBoot整合Mybatis-plus代码生成器

整合代码生成器过程中,发现好多博主提供的无法使用,自己整合了一套,没有花里胡哨,直接可用 备注:常规的依赖自己导入,提供的这套,默认已经导入了mybatis-plus,srpingboot等依赖了. 1.maven依赖导入,版本号要与自己的版本号想同 <!--代码生成器依赖--><dependency>…
阅读更多...
python基础（Python高级特性（切片、列表生成式）、字符串的正则表达式、函数、模块、Python常用内置函数、错误处理）培训讲义

python基础（Python高级特性（切片、列表生成式）、字符串的正则表达式、函数、模块、Python常用内置函数、错误处理）培训讲义

文章目录 1. Python高级特性&#xff08;切片、列表生成式&#xff09;a) 切片的概念、列表/元组/字符串的切片切片的概念列表切片基本索引简单切片超出有效索引范围缺省 扩展切片step为正数step为负数 b) 列表生成式以及使用列表生成式需要注意的地方概念举例说明1. 生成一个列…
阅读更多...
数据结构：AVL树的旋转（平衡搜索二叉树）

数据结构：AVL树的旋转（平衡搜索二叉树）

1、AVL树简介 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1&#xff0c;所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis&#xff0c;他们…
阅读更多...
双11购物节想入手一款音画好的智能电视，大家推荐一下吧？

双11购物节想入手一款音画好的智能电视，大家推荐一下吧？

智能家电更新太快,不想三五年后就淘汰,那就入手东芝电视Z700吧,Z700这次把观影体验和音箱效果做到哇塞,既然要享受生活那就要享受高品质的体验。东芝电视拥有70余年的原色调校技术,每款产品都有专属的日本调校工程师匠心打造,可以真实还原画面色彩,而且还有火箭炮音响系统,也是…
阅读更多...
C++ 图解二叉树非递归后序 + 实战力扣题

C++ 图解二叉树非递归后序 + 实战力扣题

145.二叉树的后序遍历 145. 二叉树的后序遍历 - 力扣&#xff08;LeetCode&#xff09; class Solution { public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> vec;if(root NULL) return vec;TreeNode* guard root…
阅读更多...
大型企业是否有必要进行数字化转型？_数据治理平台_光点科技

大型企业是否有必要进行数字化转型？_数据治理平台_光点科技

数字化转型是大型企业在现代商业环境中保持竞争力的关键。一开始我们要明确数字化转型指的是利用数字技术来改变企业的业务模式和企业文化&#xff0c;以提高效率和效益。对于大型企业而言&#xff0c;进行数字化转型有着多重必要性。 1.数字化转型可以帮助企业优化内部流程&am…
阅读更多...
记一次经典SQL双写绕过题目[极客大挑战 2019]BabySQL 1

记一次经典SQL双写绕过题目[极客大挑战 2019]BabySQL 1

题目环境&#xff1a; 作者已经描述进行了严格的过滤 做好心理准备进行迎接 判断注入类型 admin 1’ 字符型注入万能密码注入 admin 1’ or ‘1’1 报错 已经是字符型注入了&#xff0c;所以的话只有or这里存在了过滤 联想到buuctf里面还没有碰到双写绕过的题目 所以这里斗胆试…
阅读更多...
ESXi配置两个不同网段虚拟机互通

ESXi配置两个不同网段虚拟机互通

ESXi配置两个不同网段虚拟机互通 拓扑图&#xff1a; 步骤 在ESXi上新建一个虚拟交换机新建两个端口组&#xff0c;VLAN ID分别为30和31&#xff0c;添加到新建的虚拟交换机上创建两个虚拟机&#xff0c;网络适配器分别使用新建的端口组30和31对新建的虚拟机配置IP在物理交换…
阅读更多...
【计算机组成】实模式/保护模式下地址分段（基段地址+偏移地址）的原因

【计算机组成】实模式/保护模式下地址分段（基段地址+偏移地址）的原因

一.硬编码/静态重定向 我们先来观察下没有地址分段时代CPU是怎么和内存们打交道&#xff0c;在8086CPU以前的老大哥们&#xff0c;访问内存时通常就是实打实的“指哪打哪”&#xff0c;程序指定要放在哪个地址&#xff0c;那就老老实实地放在哪个地址&#xff0c;比如程序A要放…
阅读更多...
微信小程序案例3-1 比较数字

微信小程序案例3-1 比较数字

文章目录 一、运行效果二、知识储备&#xff08;一&#xff09;Page()函数&#xff08;二&#xff09;数据绑定&#xff08;三&#xff09;事件绑定&#xff08;四&#xff09;事件对象&#xff08;五&#xff09;this关键字&#xff08;六&#xff09;setData()方法&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023