数据结构-顺序表

数据结构-顺序表

  • 线性表
  • 顺序表的概念和结构
    • 静态顺序表和动态顺序表
  • 接口的实现
    • 顺序表的初始化
    • 顺序表的打印
    • 顺序表的销毁
    • 顺序表的增容
    • 顺序表的尾插
    • 顺序表的尾删
    • 顺序表的头插
    • 顺序表的头删
    • 顺序表的任意位置插入
    • 顺序表的任意位置删除
    • 顺序表中元素的查找
  • 完整代码

线性表

线性表是n个具有相同特性的数据元素的有限序列。它是一种数据结构。常见的线性表有：顺序表，链表，栈，队列，字符串等。线性表在逻辑上是线性结构，也就是说，从逻辑的角度来看，它是连续的一条直线。但是在物理结构上不一定是连续的，通常以数组和链式结构的形式存储。这里我们主要了解顺序表。

顺序表的概念和结构

顺序表是用一段物理地址连续的存储单元依次存储元素的线性结构。一般情况下采用数组的形式进行存储。在数组上完成数组的增删查改。
在这里插入图片描述

顺序表一般可以分为静态顺序表和动态顺序表。

静态顺序表和动态顺序表

静态顺序表的数组长度是固定的。如下：

#define N 10000
typedef int SLDataType;
struct SeqList
{
	SLDataType a[N];
	int size;
};

这里#define 对数组的长度10000用N来替换；typedef对int数据类型重新定义为一个新的名字SLDataType；SeqList就是我们的顺序表，它包括数组和当前的数据表的长度size。

由于静态顺序表的数组大小是固定的，当数组大小不大时，数据增加，可能存放不下；当数组大小大的时候，又会造成空间的浪费。因此，静态顺序表不常用。常用动态顺序表，如下：

//动态
typedef int SLDataType;
#define INIT_CAPACITY 4


typedef struct SeqList
{
	SLDataType* a;
	int size;//当前数据的个数
	int capacity;//容量
}SL;

这里typedef对int数据类型重新定义为一个新的名字SLDataType；SeqList就是我们的顺序表，它包括SLDataType* a指针和当前的数据的个数size，顺序表的容量capacity；对顺序表struct SeqList数据类型重新定义为一个新的名字SL。

接口的实现

顺序表的初始化

初始化：malloc函数申请空间为数组所占用的空间，size置零，给定初始容量为4
这里我们采用指针进行函数传参。

#define INIT_CAPACITY 4

void SLInit(SL* ps)
{
	ps->a = (SLDataType*)malloc(sizeof(SLDataType*) * INIT_CAPACITY);
	if(ps->a == NULL)
	{
		perror("malloc fail");
		return ;
	}

	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

顺序表的打印

顺序表的打印就是打印出数组中的元素

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

顺序表的销毁

动态空间释放，指针置NULL；变量归0

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

顺序表的增容

当元素个数size大于等于顺序表中的capacity时，就需要增容。
我们使用realloc函数对其增容，增容后，指针需要重新赋值，capacity变量值需要改变。

void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
}

顺序表的尾插

尾插比较简单，只需要size++后，给数组赋值即可。

void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->capacity==ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}//这里也可以直接调用SLCheckCapacity函数
	ps->a[ps->size++] = x;
}

顺序表的尾删

这里只需要size–动作，不需要去计较最后一个元素是否已从内存中清空；但是需要检查size，即顺序表中要存在数据。

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

顺序表的头插

在顺序表的头部插入数据，就是意为着所有的元素都要后移1位。如果从前面的元素开始移动数据，则会覆盖掉后面的元素。因此，我们从最后一个元素向后移动数据，一直到指针end指向0。动画如下：
在这里插入图片描述

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;


	//SLInsert(ps, 0, x);
}

顺序表的头删

在顺序表的头部删除数据，只需要将后面的元素逐步覆盖掉前一个元素，指针从1开始，到size-1结束。动画如下：
在这里插入图片描述

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size>0);
	int begin = 1;
	while (begin<ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;


	//SLErase(ps, 0);
}

顺序表的任意位置插入

和头插的思想一样，在被插入的位置和以后的位置的元素都要后移1位，仍然是从最后一个元素后移，指针由size-1变化到pos。动画如下：
在这里插入图片描述

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos>=0&&pos<=ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

因为是任意位置的插入，因此，对于头插和尾插都可以用SLInsert函数实现，如下：

SLInsert(ps,ps->size,x);//尾插
SLInsert(ps, 0, x);//头插

顺序表的任意位置删除

与头删的思想一样，只需要将被删除位置后面的元素依次覆盖掉前面的元素。动画如下：
在这里插入图片描述

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos>=0&&pos<ps->size);
	int begin = pos + 1;
	while (begin<ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

因为是任意位置的删除，所以头删和尾删也可以用SLErase函数表示，如下：

SLErase(ps,ps->size-1);//尾删
SLErase(ps, 0);//头删

顺序表中元素的查找

这里采用遍历的方法来查找元素，如下：

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i=0;i<ps->size;i++)
	{
		if (ps->a[i]==x)
		{
			return i;
		}
	}

	return -1;
}

完整代码

主程序：

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void TestSeList1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 4);
	SLPushBack(&s, 6);
	SLPushBack(&s, 8);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);

	SLPushFront(&s, -1);
	SLPushFront(&s, -2);
	SLPushFront(&s, -3);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);

	SLInsert(&s, 1, 11);
	SLInsert(&s, 2, 12);
	SLErase(&s, 2);
	SLErase(&s, 1);

	SLPushBack(&s, 100);
	SLPushFront(&s, -100);
	SLPopBack(&s);
	SLPopFront(&s);

	int ret=SLFind(&s,1);
	printf("%d\n",ret);


	SLPrint(&s);
	SLDestroy(&s);

}
int main()
{
	TestSeList1();

	return 0;
}

函数的定义

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void SLInit(SL* ps)
{
	ps->a = (SLDataType*)malloc(sizeof(SLDataType*) * INIT_CAPACITY);
	if(ps->a == NULL)
	{
		perror("malloc fail");
		return ;
	}

	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

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

void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
}


void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->capacity==ps->size)
	{
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType*) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
	ps->a[ps->size++] = x;


	//SLInsert(ps,ps->size,x);
}

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


	//SLErase(ps,ps->size-1);
}


void SLPushFront(SL* ps, SLDataType x)
{
	//assert(ps);
	//SLCheckCapacity(ps);
	//int end = ps->size - 1;
	//while (end>=0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}
	//ps->a[0] = x;
	//ps->size++;


	SLInsert(ps, 0, x);
}

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size>0);
	int begin = 1;
	while (begin<ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;


	//SLErase(ps, 0);
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos>=0&&pos<=ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos>=0&&pos<ps->size);
	int begin = pos + 1;
	while (begin<ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i=0;i<ps->size;i++)
	{
		if (ps->a[i]==x)
		{
			return i;
		}
	}

	return -1;
}

函数的声明

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//静态
//#define N 10000
//typedef int SLDataType;
//struct SeqList
//{
//	SLDataType a[N];
//	int size;
//};

//动态
typedef int SLDataType;
#define INIT_CAPACITY 4


typedef struct SeqList
{
	SLDataType* a;
	int size;//当前数据的个数
	int capacity;//容量
}SL;

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);


void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPopBack(SL* ps);//尾删
void SLPushFront(SL* ps,SLDataType x);//头插
void SLPopFront(SL* ps);//头删
void SLInsert(SL* ps,int pos,SLDataType x);//任意位置的插入
void SLErase(SL* ps,int pos);//任意位置的删除
int SLFind(SL* ps, SLDataType x);//查找元素

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

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

相关文章

MyBatis 环境搭建+基本使用

MyBatis 环境搭建+基本使用

目录 MyBatis创建MyBatis环境搭建MyBatis模式开发MyBatis 获取动态参数&#xff08;查询操作&#xff09;${} 直接替换#{} 占位符模式替换like查询&#xff08;模糊查询&#xff09;多表查询一对一的表映射一对多的表映射 增、删、改操作改操作删除操作增加操作添加用户添加用户…
阅读更多...
JVM学习（十三）：面试中绕不开的String

JVM学习（十三）：面试中绕不开的String

目录 一、String 的基本特性 1.1 String类的声明 1.2 String的存储方式在jdk9中的变更 1.3 Stirng 的不可变性 二、String的内存分配 2.1 字符串常量池是什么 2.2 底层原理与默认值 2.3 字符串常量池所在位置 三、字符串的拼接操作 3.1 拼接操作结果存放位置 …
阅读更多...
es elasticsearch 九 索引index 定制分词器 type结构后期弃用原因 定制动态映射 动态映射模板 零停机重建索引

es elasticsearch 九 索引index 定制分词器 type结构后期弃用原因 定制动态映射 动态映射模板 零停机重建索引

目录 索引index 定制分词器 Type底层结构及弃用原因 定制 dynamic mapping 定制dynamic mapping template 动态映射模板 零停机重建索引 生产环境应该度别名数据 索引index Put /index Stings 分片 Mapping 映射 Aliases 别名 增加 Put my_index2 { "se…
阅读更多...
软考A计划-试题模拟含答案解析-卷七

软考A计划-试题模拟含答案解析-卷七

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&am…
阅读更多...
从C语言到C++_12(string相关OJ题)(leetcode力扣)

从C语言到C++_12(string相关OJ题)(leetcode力扣)

上一篇已经讲了string类的接口函数&#xff0c;然后根据查文档刷了牛客和力扣58最后一个单词的长度&#xff0c; 还有力扣415字符串相加&#xff0c;这篇继续跟着查文档来刷力扣题&#xff0c;体会C刷题的方便。 目录 917. 仅仅反转字母 - 力扣&#xff08;LeetCode&#xf…
阅读更多...
Linux 实操篇-组管理和权限管理

Linux 实操篇-组管理和权限管理

Linux 实操篇-组管理和权限管理 Linux 组基本介绍 在linux 中的每个用户必须属于一个组&#xff0c;不能独立于组外。在linux 中每个文件有所有者、所在组、其它组的概念。 所有者所在组其它组改变用户所在的组 文件/目录所有者 一般为文件的创建者,谁创建了该文件&#x…
阅读更多...
计算机视觉：卷积核的运行过程

计算机视觉：卷积核的运行过程

本文重点 我们前面从直观角度理解了卷积神经网络的卷积在特征提取的作用，本节课程我们从数学角度来看一下，卷积是如何计算的？ 计算步骤 1. 将卷积核与输入图像的某一部分进行逐元素相乘。 2. 将相乘后的结果求和，得到卷积核在该部分的输出值。 3. 重复以上步骤，将卷积核…
阅读更多...
【shiro】shiro整合JWT——3.执行流程

【shiro】shiro整合JWT——3.执行流程

前言 shiro整合JWT系列&#xff0c;主要记录核心思路–如何在shiroredis整合JWTToken。 上一篇中&#xff0c;主要讲如何在shiro框架中配置Jwt&#xff0c;以及token执行的流程。 该篇主要梳理整个代码的执行流程。 ps&#xff1a;本文主要以记录核心思路为主&#xff0c;以下…
阅读更多...
uCOSii消息邮箱管理

uCOSii消息邮箱管理

uCOSii消息邮箱管理 (MESSAGE MAILBOX MANAGEMENT) 消息邮箱主要用于中断和任务之间进行邮件传递&#xff0c;或者是在任务与任务之间进行邮件交换。 我个人觉得&#xff0c;了解uCOSii消息邮箱的几个重要函数&#xff0c;还是有必要的。不是所有人都给我们测试案例。 1、重…
阅读更多...
R语言混合效应（多水平/层次/嵌套）模型及贝叶斯实现技术

R语言混合效应（多水平/层次/嵌套）模型及贝叶斯实现技术

回归分析是科学研究中十分重要的数据分析工具。随着现代统计技术发展&#xff0c;回归分析方法得到了极大改进。混合效应模型&#xff08;Mixed effect model&#xff09;&#xff0c;即多水平模型&#xff08;Multilevel model&#xff09;/分层模型(Hierarchical Model)/嵌套…
阅读更多...
如何快速运用R语言实现生物群落（生态）数据统计分析与绘图

如何快速运用R语言实现生物群落（生态）数据统计分析与绘图

R 语言作的开源、自由、免费等特点使其广泛应用于生物群落数据统计分析。生物群落数据多样而复杂&#xff0c;涉及众多统计分析方法。本次以生物群落数据分析中的最常用的统计方法回归和混合效应模型、多元统计分析技术及结构方程等数量分析方法为主线&#xff0c;通过多个来自…
阅读更多...
Linux：查看进程。

Linux：查看进程。

Linux&#xff1a;查看进程。 windows linux TTY如果是&#xff1f;说明是不是终端(控制台)启动的&#xff0c;而是系统内部自己启动的。 TIME是启动Linux后&#xff0c;这个进程一共占用了cpu多少时间00…
阅读更多...
QT 设计ROS GUI界面订阅和发布话题

QT 设计ROS GUI界面订阅和发布话题

QT 设计ROS GUI界面订阅和发布话题 主要参考下面的博客 ROS项目开发实战&#xff08;三&#xff09;——使用QT进行ROS的GUI界面设计&#xff08;详细教程附代码&#xff01;&#xff01;&#xff01;&#xff09; Qt ROS 相关配置请看上一篇博客 首先建立工作空间和功能包&a…
阅读更多...
【探索】机器指令翻译成 JavaScript

【探索】机器指令翻译成 JavaScript

前言 前些时候研究脚本混淆时&#xff0c;打算先学一些「程序流程」相关的概念。为了不因太枯燥而放弃&#xff0c;决定想一个有趣的案例&#xff0c;可以边探索边学。 于是想了一个话题&#xff1a;尝试将机器指令 1:1 翻译 成 JavaScript&#xff0c;这样就能在浏览器中&am…
阅读更多...
Java程序设计入门教程-- if 条件语句

Java程序设计入门教程-- if 条件语句

目录 单分支选择语句&#xff08;if&#xff09; 双分支选择语句&#xff08;if…else&#xff09; 嵌套if语句 单分支选择语句&#xff08;if&#xff09; 情形 当判断条件满足时&#xff0c;执行语句体S&#xff0c;而不满足则什么都不做。 格式 if &#xff08;条件判断表…
阅读更多...
【计算机视觉 | 目标检测】术语理解6：ViT 变种（ ViT-H、ViT-L ViT-B）、bbox（边界框）、边界框的绘制（含源代码）

【计算机视觉 | 目标检测】术语理解6：ViT 变种（ ViT-H、ViT-L ViT-B）、bbox（边界框）、边界框的绘制（含源代码）

文章目录 一、ViT & ViT变种1.1 ViT的介绍1.2 ViT 的变种 二、bbox&#xff08;边界框&#xff09;三、边界框的绘制 一、ViT & ViT变种 1.1 ViT的介绍 ViT&#xff0c;全称为Vision Transformer&#xff0c;是一种基于Transformer架构的视觉处理模型。传统的计算机视…
阅读更多...
java企业工程项目管理系统平台源码（三控：进度组织、质量安全、预算资金成本、二平台：招采、设计管理）

java企业工程项目管理系统平台源码（三控：进度组织、质量安全、预算资金成本、二平台：招采、设计管理）

工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#…
阅读更多...
回调函数与钩子函数的区别,另QT中connect函数的实现，lambda的使用

回调函数与钩子函数的区别,另QT中connect函数的实现，lambda的使用

1、钩子函数是回调函数的一种 广泛来说两者都是一样的 严格来说 钩子函数的函数名早已被定义好&#xff0c;只是函数内部需要用户在应用层来定义&#xff0c; 1&#xff09;可以完全通过宏来实现系统是否调用该函数&#xff08;底层不封闭&#xff0c;修改宏的参数实现是否编…
阅读更多...
【2023 · CANN训练营第一季】MindSpore模型快速调优攻略 第二章——MindSpore调试调优

【2023 · CANN训练营第一季】MindSpore模型快速调优攻略 第二章——MindSpore调试调优

1.生态迁移 生态迁移工具使用示例 生态迁移工具技术方案 不同框架间模型定义前端表达差别巨大(相同算子的API技术难点 、 算子功能、模型构建方式差别较大)&#xff1b; 对于同一框架&#xff0c;不管前端表达差异如何&#xff0c;最终对应的计算 图是相似的。因此提出&#x…
阅读更多...
Kubernetes部署+kubesphere管理平台安装

Kubernetes部署+kubesphere管理平台安装

Kubernetes官网&#xff1b;kubesphere官网 不论是Kubernetes官网还是找的其它部署步骤&#xff0c;基本都是推荐搭建集群的方式&#xff0c;是为了实现高可用.....等等&#xff0c;这样一来至少需要两台或三台的服务器来搭建&#xff0c;这样对我们的成本也是非常大的&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023