数据结构--顺序表（图文）

顺序表的概念和特点

顺序表是一种线性数据结构，它由一组数据元素构成，这些元素具有相同的特性，并按照一定的顺序排列。在顺序表中，数据元素通常存储在连续的内存空间中，这使得通过索引可以直接访问到表中的任意元素。

顺序表的特点如下：

  1. 连续的存储空间：顺序表中的元素在内存中占据一段连续的空间，这使得访问任何一个元素的时间复杂度都为O(1)，即访问速度快。

  2. 动态性：顺序表可以是静态的，也可以是动态的。静态顺序表一旦初始化后，其空间大小就不能更改；而动态顺序表则可以根据需要动态地调整空间大小，即在空间不足时可以自动扩容，空间过多时可以缩容。

  3. 随机访问：由于元素存储是连续的，顺序表支持随机访问，即可以直接通过索引来访问元素，这一点与链表不同，链表需要遍历才能访问到指定位置的元素。

  4. 插入和删除操作：顺序表的插入和删除操作可能需要移动大量的元素，尤其是在插入或删除中间的元素时，时间复杂度为O(N)，其中N是表中元素的数量。因此，顺序表在执行插入和删除操作时效率较低，这是它的一个缺点。

  5. 内存预分配与动态调整：在动态顺序表中，内存可以根据需要预先分配或动态调整。预分配指的是在创建顺序表时指定一个初始大小，后续根据实际情况可能进行扩容；动态调整则是在运行时根据需要增大或减小内存空间。

顺序表的实现

对比静态顺序表，动态顺序表更有优势，同样在项目中，动态顺序表的应用远远大于静态顺序表，下面我们就来实现动态顺序表。
首先创建三个文件：

  • SeqList.h —— 用于声明函数的头文件
  • SeqList.c —— 顺序表主要函数的实现
  • test.c——测试顺序表。

创建顺序表

typedef int SLDataType;//方便后续使用更改类型
typedef struct SeqList
{
	SLDataType* arr;//数组指针
	int size;//记录当前有效的数组大小
	int capacity;//记录当前总空间大小
}SL;

对顺序表初始化

void InitSeqList(SL* ps)//初始化顺序表
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

顺序表的销毁

void SLDestroy(SL* ps)//销毁顺序表
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

打印顺序表

void SLPrint(const SL* ps)//打印顺序表的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d", ps->arr[i]);
	}
}

在给数据表增加数据前，我们先封装一个函数，用来判断顺序表是否已满，如果满则需要开辟新空间。

判断扩容

void SLCheckCapacity(SL* ps)//判断是否需要增容
{
	assert(ps);
	if (ps->capacity == ps->size)//数组已满
	{
		int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;//如果空间为0则开辟4个空间，否则开辟原空间二倍
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}

}

头插

在这里插入图片描述

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 SLPushBack(SL* ps, SLDataType x)//在顺序表的末尾插入数据
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

指定位置插入

在这里插入图片描述

void SLInsert(SL* ps, int pos, SLDataType x)//在指定位置插入数据
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

头删

在这里插入图片描述

void SLPopFront(SL* ps)//删除顺序表头部的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

尾删

直接size–就可以了

void SLPopBack(SL* ps)//删除顺序表尾部的数据
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

删除指定位置

在这里插入图片描述

void SLErase(SL* ps, int pos)//删除指定位置的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

查找数据

直接遍历数组找相等

int SLFind(SL* ps, SLDataType x)//在顺序表中查找数据，返回数组下标，没找到返回-1
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

顺序表源码

SeqList.c

#pragma once
#include"SeqList.h"

void InitSeqList(SL* ps)//初始化顺序表
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLDestroy(SL* ps)//销毁顺序表
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
void SLPrint(const SL* ps)//打印顺序表的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d", ps->arr[i]);
	}
}

void SLCheckCapacity(SL* ps)//判断是否需要增容
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}

}
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 SLPushBack(SL* ps, SLDataType x)//在顺序表的末尾插入数据
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
void SLInsert(SL* ps, int pos, SLDataType x)//在指定位置插入数据
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
void SLPopFront(SL* ps)//删除顺序表头部的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
void SLPopBack(SL* ps)//删除顺序表尾部的数据
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
void SLErase(SL* ps, int pos)//删除指定位置的数据
{
	assert(ps);
	assert(ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
int SLFind(SL* ps, SLDataType x)//在顺序表中查找数据，返回数组下标，没找到返回-1
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到

}

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;


void InitSeqList(SL* ps);//初始化顺序表

void SLDestroy(SL* ps);//销毁顺序表

void SLPrint(const SL* ps);//打印顺序表的数据

void SLPushFront(SL* ps, SLDataType x);//在顺序表的头部插入数据

void SLPushBack(SL* ps, SLDataType x);//在顺序表的末尾插入数据

void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据

void SLPopFront(SL* ps);//删除顺序表头部的数据

void SLPopBack(SL* ps);//删除顺序表尾部的数据

void SLErase(SL* ps, int pos);//删除指定位置的数据

int SLFind(SL* ps, SLDataType x);//在顺序表中查找数据，返回数组下标，没找到返回-1

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

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

相关文章

scratch3编程02-使用克隆来编写小游戏

scratch3编程02-使用克隆来编写小游戏

目录 1&#xff0c;游戏效果 2&#xff0c;游戏代码块 1&#xff09;玩家 2&#xff09;障碍物 ​ 3&#xff09;箭头 ​ 4&#xff09;关卡图片 3&#xff0c;scratch文件 1&#xff0c;游戏效果 使用克隆 在这个游戏中&#xff1a; 程序开始&#xff1a;只要点击“…
阅读更多...
开放式耳机哪个牌子好？2024五大闭眼入开放式耳机推荐！

开放式耳机哪个牌子好？2024五大闭眼入开放式耳机推荐！

想要购买开放式耳机&#xff0c;但面对很多品牌和型号&#xff0c;是否感到无从下手&#xff1f;别担心&#xff0c;作为耳机发烧友和测评专家&#xff0c;我为大家带来了几款热门开放式耳机的横向对比。从各个方面进行详细对比&#xff0c;还有我自己觉得还不错的五款开放式耳…
阅读更多...
行列式和矩阵的区别

行列式和矩阵的区别

目录 一、行列式 1. 行列式的定义 2. (全)排列 3. 逆序数 二、矩阵 1. 矩阵的定义 三、行列式和矩阵的区别 四、参考书目 一、行列式 1. 行列式的定义 2. (全)排列 3. 逆序数 二、矩阵 1. 矩阵的定义 三、行列式和矩阵的区别 四、参考书目 同济大学数学系. 工程数学…
阅读更多...
【代码随想录】【算法训练营】【第43天】 [518]零钱兑换II [377]组合总和IV [卡码57]爬楼梯

【代码随想录】【算法训练营】【第43天】 [518]零钱兑换II [377]组合总和IV [卡码57]爬楼梯

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 部分题目来自卡码网。 day 43&#xff0c;极其困难的周三~ 题目详情 [518] 零钱兑换II 题目描述 518 零钱兑换II 解题思路 前提&#xff1a;假设每一种面额的硬币有无限个&#xff0c;求组合数…
阅读更多...
大模型技术如何构建金融领域的创新生态？

大模型技术如何构建金融领域的创新生态？

前言 近年来&#xff0c;人工智能技术不断迭代与突破&#xff0c;助力各行各业加速迈向智能化&#xff0c;其中在金融领域的运用逐渐加深&#xff0c;为银行、保险、基金、券商等金融机构实现数智化转型提供引擎动能。而大模型时代的到来&#xff0c;则为金融智能的发展引入了…
阅读更多...
vue3-openlayers 点击多边形弹框，高亮多边形，自定义属性传递，鼠标悬浮多边形上动态修改鼠标样式

vue3-openlayers 点击多边形弹框，高亮多边形，自定义属性传递，鼠标悬浮多边形上动态修改鼠标样式

本篇介绍一下使用vue3-openlayers点击多边形弹框&#xff0c;高亮多边形&#xff0c;自定义属性传递&#xff0c;鼠标悬浮多边形上动态修改鼠标样式 1 需求 加载天地图&#xff0c;polygon传递自定义属性标悬浮在polygon上&#xff0c;根据自定义属性&#xff0c;动态修改鼠标…
阅读更多...
【深度学习】sdwebui A1111 加速方案对比，xformers vs Flash Attention 2

【深度学习】sdwebui A1111 加速方案对比，xformers vs Flash Attention 2

文章目录 资料支撑资料结论sdwebui A1111 速度对比测试sdxlxformers 用contorlnet sdxlsdpa&#xff08;--opt-sdp-no-mem-attention&#xff09; 用contorlnet sdxlsdpa(--opt-sdp-attention) 用contorlnet sdxl不用xformers或者sdpa ,用contorlnet sdxl不用xformers或者sdpa …
阅读更多...
35 Debian如何配置Postfix+Dovecot实现邮件加密

35 Debian如何配置Postfix+Dovecot实现邮件加密

作者：网络傅老师 特别提示：未经作者允许，不得转载任何内容。违者必究！ Debian如何配置Postfix+Dovecot实现邮件加密 《傅老师Debian知识库系列之35》——原创 ==前言== 傅老师Debian知识库特点： 1、拆解Debian实用技能； 2、所有操作在VMware虚拟机实测完成； 3、致力于…
阅读更多...
Neo4j 创建关系

Neo4j 创建关系

Neo4j 创建关系 在 Noe4j 中&#xff0c;关系是我们用来连接图的两个节点的元素。 这些关系具有数据的方向、类型和形式模式。 本章教你如何 建立关系在现有节点之间创建关系使用标签和属性创建关系 建立关系 我们可以使用 CREATE 子句创建关系。 我们将在方括号[]中指定关系…
阅读更多...
工业自动化中OBC充电机测试负载箱的应用

工业自动化中OBC充电机测试负载箱的应用

在工业自动化中&#xff0c;OBC充电机是电动汽车和混合动力汽车的重要组成部分。它的主要功能是为电动汽车的电池组提供电能&#xff0c;保证车辆的正常运行。为了保证OBC充电机的性能和安全性&#xff0c;通常需要对其进行严格的测试。在这个过程中&#xff0c;负载箱是一种非…
阅读更多...
PySide（PyQt）的特殊按钮（互锁、自锁、独占模式）

PySide（PyQt）的特殊按钮（互锁、自锁、独占模式）

界面图： Qt Designer中创建窗口，放置一个QGroupBox，命名为btnStation，这就是自定义的按钮站，按钮站里放置6个按钮。自锁按钮相当于电器中的自锁功能的按钮，每按一次状态反转并保持不变。独占按钮也是自锁功能的按钮，不同的是当独占按钮为ON时，其余所有按钮均被置为OFF…
阅读更多...
点亮LED灯（TMS570LS31HDK）

点亮LED灯（TMS570LS31HDK）

一、安装Code Composer studio&#xff08;CCS&#xff09; 1.ccs下载地址 2.ccs安装 学习文档 二、安装Hal Code Generator 下载地址 三、创建新的CCS项目&#xff08;TMDS570LS31HDK&#xff09; 详细步骤学习博客&#xff08;推荐这里学习&#xff09; 以下是大致步骤…
阅读更多...
工业 web4.0，UI 风格令人赞叹

工业 web4.0，UI 风格令人赞叹

工业 web4.0&#xff0c;UI 风格令人赞叹
阅读更多...
Fastjson 结合 jdk 原生反序列化的利用手法 ( Aliyun CTF )

Fastjson 结合 jdk 原生反序列化的利用手法 ( Aliyun CTF )

2023 Aliyun CTF ezbean是一道CTF java反序列化题目。 题目的目的是让选手通过一个java原生反序列化入口&#xff0c;最终达成RCE。本文对题目的几种解法做了具体的分析&#xff0c;主要分为预期解法和非预期解法两种思路。通过对Fastjson在反序列化的行为分析&#xff0c;从两…
阅读更多...
GIT----使用技巧之保存现场回退新建分支继续开发

GIT----使用技巧之保存现场回退新建分支继续开发

GIT----使用技巧之保存现场回退新建分支继续开发 前言&#xff1a; 故事是这样的&#xff0c;有一个比较复杂的项目使用的是STM32F103VCT6&#xff08;资源flash-256k,RAM-48k&#xff09;,开发到一半发现RAM不够用了&#xff0c;换容量更大的芯片STM32F103VGT6&#xff08;资源…
阅读更多...
0.4 隔行扫描（Interlaced Scan）简介

0.4 隔行扫描（Interlaced Scan）简介

0.4 隔行扫描简介 隔行扫描&#xff08;Interlaced Scan&#xff09;是一种将图像显示在扫描式的显示设备上的方法&#xff0c;例如阴极射线管&#xff08;CRT&#xff09;。 隔行扫描设备交替扫描图像的奇场&#xff08;图像的所有奇数行&#xff0c;1、3、5&#xff09;和偶…
阅读更多...
Excel 找出最大值及其相邻的 N 个成员

Excel 找出最大值及其相邻的 N 个成员

某列都是数值&#xff1a; A1132213464215496973482396101113712491342144015151631171718114719182030212222423252419251326272738283029163012312332333233419351436463723383739384028 请找出最大值及其相邻的 10 个成员&#xff0c;注意越界检查&#xff0c;实际符合条件…
阅读更多...
银行数仓项目实战（四）--了解银行业务（存款）

银行数仓项目实战（四）--了解银行业务（存款）

文章目录 项目准备存款活期定期整存整取零存整取存本取息教育储蓄定活两便通知存款 对公存款对公账户协议存款 利率 项目准备 &#xff08;贴源层不必写到项目文档&#xff0c;因为没啥操作没啥技术&#xff0c;只是数据。&#xff09; 可以看到&#xff0c;银行的贴源层并不紧…
阅读更多...
Fisnar Liquid Control 操作维修手LC Pump Manual Twinmixer Maintenance 中文

Fisnar Liquid Control 操作维修手LC Pump Manual Twinmixer Maintenance 中文

Fisnar Liquid Control 操作维修手LC Pump Manual Twinmixer Maintenance 中文
阅读更多...
基于springboot实现交通管理在线服务系统项目【项目源码+论文说明】

基于springboot实现交通管理在线服务系统项目【项目源码+论文说明】

基于springboot实现交通管理在线服务系统演示 摘要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装交通管理在线服…
阅读更多...
最新文章

Copyright @ 2022~2023