初级数据结构——顺序表

目录

  • 前言
  • 一、定义与特点
  • 二、类型
  • 三、基本操作
  • 四、应用场景
  • 五、优缺点
  • 六、元素插入和删除动态图解
    • 插入
    • 删除
  • 七、代码模板
  • 八、使用顺序表的经典例题
    • 1.求奇数的乘积
      • 代码题解
    • 2.数值统计
      • 代码题解
  • 九、总结
  • 结语

前言

顺序表示最基础的数据结构之一，它也是我们学习开始学习数据结构的第一个必须要掌握的数据结构，学习数据结构一定是由浅到深，所以我们最好是先学习简单的在学习有难度的，因为直接学习难的数据结构很容易劝退，让我们来深入了解顺序表。
在这里插入图片描述

一、定义与特点

定义：顺序表（Sequence List）是线性表的一种实现方式，它使用一段地址连续的存储单元依次存储线性表的数据元素。

特点：
1.数据元素在物理存储上是连续的，这使得顺序表在访问元素时具有较高的效率。
2.顺序表支持随机访问，即可以通过索引直接访问表中的任意元素，时间复杂度为O(1)。
3.顺序表的插入和删除操作可能需要移动大量的元素，尤其是在插入或删除中间位置的元素时，时间复杂度为O(N)，其中N是表中元素的数量。

二、类型

静态顺序表：静态顺序表在初始化后，其空间大小就不能更改。这意味着如果空间不足，就无法向表中添加新的元素；而如果空间过大，则可能造成内存的浪费。因此，静态顺序表在实际应用中具有一定的局限性。

动态顺序表：动态顺序表则可以根据需要动态地调整空间大小。当空间不足时，可以自动扩容；当空间过多时，也可以进行缩容（尽管在实际应用中缩容并不常见）。这使得动态顺序表在实际应用中更加灵活和高效

三、基本操作

初始化：为顺序表分配必要的存储空间，并初始化相关参数（如有效数据个数、容量等）。

销毁：释放顺序表所占用的存储空间，以避免内存泄漏。
插入：在顺序表的指定位置插入一个新的元素。这可能需要移动其他元素来腾出位置。

删除：从顺序表中删除指定位置的元素。这同样可能需要移动其他元素来填补位置。

查找：在顺序表中查找指定值的元素，并返回其位置（如果存在）。这通常通过遍历数组来实现。

访问：通过索引直接访问顺序表中的指定元素。这是顺序表的一个主要优点。

四、应用场景

顺序表适用于需要频繁访问元素的场景，因为顺序表支持随机访问，可以在常数时间内访问到表中的任意元素。此外，顺序表也适用于元素个数相对稳定的场景，因为频繁的插入和删除操作可能会导致顺序表的效率下降。

五、优缺点

优点：
支持随机访问，访问速度快。
在物理存储上是连续的，有利于CPU高速缓存的命中率。

缺点：
插入和删除操作可能需要移动大量的元素，效率较低。
在空间不足时需要扩容，扩容操作可能比较耗时且浪费空间（尽管通常采用两倍扩容策略来减少扩容次数）。

六、元素插入和删除动态图解

插入

在这里插入图片描述

删除

在这里插入图片描述

七、代码模板

#include<iostream>
using namespace std;

#define eType int

struct SequentialTable {
	eType* elements;
	int size;
	int capacity;
};

void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表
	list->elements = new eType[capacity];//elements申请内存为eType类型的内存空间，相当于数组容量为capacity
	list->capacity = capacity;
	list->size = 0;

}

void destroyTable(SequentialTable* list) {//销毁顺序表
	delete[] list->elements;//将elements内存空间销毁
}

int getSize(SequentialTable* list) {//顺序表长度
	return list->size;
}

bool isEmpty(SequentialTable* list) {//顺序表是否为空
	return list->size == 0;
}

void insertElement(SequentialTable* list,int index, eType x) {//插入元素 ，index为插入位置，x为插入的元素
	if (index<0 || index>list->size) {
		throw std::invalid_argument("Invalid index");//插入位置非法那么抛出异常
	}
	if (list->size == list->capacity) {//如果顺序表长度大于容量那就扩容
		int newCapacity = 2 * list->capacity;//容量扩大为原来的两倍
		eType* newElements = new eType[newCapacity];
		for (int i = 0; i < list->size; i++) {
			newElements[i] = list->elements[i];
		}
		delete[] list->elements;//释放原来内存空间
		list->elements = newElements;
		list->capacity = newCapacity;
	}
	for (int i = list->size; i > index; i--) {
		list->elements[i] = list->elements[i - 1];
	}
	list->elements[index] = x;
	list->size++;//注意插入元素，长度加一
}

void deleteElement(SequentialTable* list, int index) {
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	if (list->size == 0) {//如果顺序表没有元素那么进行不了删除操作，抛出异常
		throw std::invalid_argument("Invalid index");
	}
	for (int i = index; i < list->size - 1; i++) {
		list->elements[i] = list->elements[i + 1];
	}
	list->size--;//长度减一
}

int findElement(SequentialTable* list, eType x) {//找出元素的索引
	for (int i = 0; i < list->size; i++) {
		if (x == list->elements[i])return i;
	}
	return -1;//找不到返回-1
}

eType getElement(SequentialTable* list, int index) {//返回索引对应的元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	return list->elements[index];
}

void updateElement(SequentialTable* list, int index, eType x) {//更新元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	list->elements[index] = x;
}

int main() {//测试代码
	SequentialTable st;
	initailizeTable(&st, 10);
	for (int i = 0; i < 10; i++) {
		insertElement(&st, i, i * 10);
	}
	deleteElement(&st, 0);
	cout << st.elements[0] << endl;
	insertElement(&st, 0, 0);
	cout << st.elements[0] << endl;
	cout << isEmpty(&st) << endl;
	cout << findElement(&st, 70) << endl;
	cout << getElement(&st, 7) << endl;
	updateElement(&st, 0, 1);
	cout << st.elements[0] << endl;
	return 0;
}

八、使用顺序表的经典例题

1.求奇数的乘积

（帅哥们这个蓝色字体可以点进去看原题）

代码题解

#include<iostream>
using namespace std;

#define eType int

struct SequentialTable {
	eType* elements;
	int size;
	int capacity;
};

void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表
	list->elements = new eType[capacity];//elements申请内存为eType类型的内存空间，相当于数组容量为capacity
	list->capacity = capacity;
	list->size = 0;

}

void destroyTable(SequentialTable* list) {//销毁顺序表
	delete[] list->elements;//将elements内存空间销毁
}

int getSize(SequentialTable* list) {//顺序表长度
	return list->size;
}

bool isEmpty(SequentialTable* list) {//顺序表是否为空
	return list->size == 0;
}

void insertElement(SequentialTable* list,int index, eType x) {//插入元素 ，index为插入位置，x为插入的元素
	if (index<0 || index>list->size) {
		throw std::invalid_argument("Invalid index");//插入位置非法那么抛出异常
	}
	if (list->size == list->capacity) {//如果顺序表长度大于容量那就扩容
		int newCapacity = 2 * list->capacity;//容量扩大为原来的两倍
		eType* newElements = new eType[newCapacity];
		for (int i = 0; i < list->size; i++) {
			newElements[i] = list->elements[i];
		}
		delete[] list->elements;//释放原来内存空间
		list->elements = newElements;
		list->capacity = newCapacity;
	}
	for (int i = list->size; i > index; i--) {
		list->elements[i] = list->elements[i - 1];
	}
	list->elements[index] = x;
	list->size++;//注意插入元素，长度加一
}

void deleteElement(SequentialTable* list, int index) {
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	if (list->size == 0) {//如果顺序表没有元素那么进行不了删除操作，抛出异常
		throw std::invalid_argument("Invalid index");
	}
	for (int i = index; i < list->size - 1; i++) {
		list->elements[i] = list->elements[i + 1];
	}
	list->size--;//长度减一
}

int findElement(SequentialTable* list, eType x) {//找出元素的索引
	for (int i = 0; i < list->size; i++) {
		if (x == list->elements[i])return i;
	}
	return -1;//找不到返回-1
}

eType getElement(SequentialTable* list, int index) {//返回索引对应的元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	return list->elements[index];
}

void updateElement(SequentialTable* list, int index, eType x) {//更新元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	list->elements[index] = x;
}

int main() {//测试代码
	int n;
	while (cin >> n) {
		SequentialTable s;
		initailizeTable(&s, 1);
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			insertElement(&s, i, x);
		}
		int ret = 1;
		for (int i = 0; i < s.size; i++) {
			int val = getElement(&s, i);
			if (val & 1)ret *= val;
		}
		cout << ret << endl;
	}
	
	return 0;
}

2.数值统计

（帅哥们这个蓝色字体可以点进去看原题）

代码题解

#include<iostream>
using namespace std;

#define eType double//元素类型

struct SequentialTable {
	eType* elements;
	int size;
	int capacity;
};

void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表
	list->elements = new eType[capacity];//elements申请内存为eType类型的内存空间，相当于数组容量为capacity
	list->capacity = capacity;
	list->size = 0;

}

void destroyTable(SequentialTable* list) {//销毁顺序表
	delete[] list->elements;//将elements内存空间销毁
}

int getSize(SequentialTable* list) {//顺序表长度
	return list->size;
}

bool isEmpty(SequentialTable* list) {//顺序表是否为空
	return list->size == 0;
}

void insertElement(SequentialTable* list,int index, eType x) {//插入元素 ，index为插入位置，x为插入的元素
	if (index<0 || index>list->size) {
		throw std::invalid_argument("Invalid index");//插入位置非法那么抛出异常
	}
	if (list->size == list->capacity) {//如果顺序表长度大于容量那就扩容
		int newCapacity = 2 * list->capacity;//容量扩大为原来的两倍
		eType* newElements = new eType[newCapacity];
		for (int i = 0; i < list->size; i++) {
			newElements[i] = list->elements[i];
		}
		delete[] list->elements;//释放原来内存空间
		list->elements = newElements;
		list->capacity = newCapacity;
	}
	for (int i = list->size; i > index; i--) {
		list->elements[i] = list->elements[i - 1];
	}
	list->elements[index] = x;
	list->size++;//注意插入元素，长度加一
}

void deleteElement(SequentialTable* list, int index) {
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	if (list->size == 0) {//如果顺序表没有元素那么进行不了删除操作，抛出异常
		throw std::invalid_argument("Invalid index");
	}
	for (int i = index; i < list->size - 1; i++) {
		list->elements[i] = list->elements[i + 1];
	}
	list->size--;//长度减一
}

int findElement(SequentialTable* list, eType x) {//找出元素的索引
	for (int i = 0; i < list->size; i++) {
		if (x == list->elements[i])return i;
	}
	return -1;//找不到返回-1
}

eType getElement(SequentialTable* list, int index) {//返回索引对应的元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	return list->elements[index];
}

void updateElement(SequentialTable* list, int index, eType x) {//更新元素
	if (index < 0 || index >= list->size) {
		throw std::invalid_argument("Invalid index");
	}
	list->elements[index] = x;
}

int main() {//测试代码
	int n;
	while (cin >> n&&n) {
		SequentialTable s;
		initailizeTable(&s, 1);
		for (int i = 0; i < n; i++) {
			eType x;
			cin >> x;
			insertElement(&s, i, x);
		}
		int pcnt = 0, zcont = 0, ncnt = 0;
		for (int i = 0; i < s.size; i++) {
			eType val = getElement(&s, i);
			if (val > 1e-8) pcnt++;
			else if (val < -1e-8) ncnt++;
			else zcont++;
		}
		cout << ncnt << " " << zcont << " " << pcnt << endl;
	}
	
	return 0;
}

九、总结

综上所述，顺序表是一种基于数组实现的线性数据结构，具有随机访问速度快、物理存储连续等优点。然而，它也存在插入和删除操作效率低、扩容操作耗时等缺点。因此，在选择数据结构时，需要根据具体的应用场景和需求来权衡利弊。

结语

学习编程是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，不会的地方就问，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。
在这里插入图片描述
想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家。
在这里插入图片描述

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

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

相关文章

arkUI：遍历数据数组动态渲染（forEach）

arkUI：遍历数据数组动态渲染（forEach）

arkUI&#xff1a;遍历数据数组动态渲染&#xff08;forEach&#xff09; 1 主要内容说明2 相关内容2.1 ForEach 的基本语法2.2 简单遍历数组2.2 多维数组遍历2.4 使用唯一键2.5 源码1的相关说明2.5.1 源码1 &#xff08;遍历数据数组动态渲染&#xff09;2.5.2 源码1运行效果 …
阅读更多...
新的恶意软件活动通过游戏应用程序瞄准 Windows 用户

新的恶意软件活动通过游戏应用程序瞄准 Windows 用户

一种新的恶意软件 Winos4.0 被积极用于网络攻击活动。FortiGuard实验室发现&#xff0c;这种先进的恶意框架是从臭名昭著的 Gh0strat 演变而来的&#xff0c;配备了模块化组件&#xff0c;可在受感染的设备上进行一系列恶意活动。 这些攻击已在游戏相关应用程序中发现&#xf…
阅读更多...
Maven学习——创建Maven的Java和Web工程，并运行在Tomcat上

Maven学习——创建Maven的Java和Web工程，并运行在Tomcat上

一、Maven介绍 Maven 是一款为 Java 项目管理构建、依赖管理的工具&#xff08;软件&#xff09;&#xff0c;使用 Maven 可以自动化构建、测试、打包和发布项目&#xff0c;大大提高了开发效率和质量。 二、Maven安装步骤 1.下载后解压到没有空格、特殊字符和中文的目录中 2…
阅读更多...
【刷题】优选算法

【刷题】优选算法

优选算法 双指针 202. 快乐数 链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 【思路】 第一个实例是快乐数&#xff0c;因为会变为1且不断是1的循环 第二个实例不可能为1&#xff0c;因为会陷入一个没有1的循环 根据两个实例和鸽巢原理可以发现不断的平方和最…
阅读更多...
在unity中实现把普通的照片，图片 变成油画风格的shader实现

在unity中实现把普通的照片，图片 变成油画风格的shader实现

可以通过对shader的Radius的值得设置来改变油画风格的力度&#xff0c;0最小&#xff0c;10是最大。
阅读更多...
【项目开发 | 跨域认证】JSON Web Token（JWT）

【项目开发 | 跨域认证】JSON Web Token（JWT）

未经许可，不得转载。 文章目录 JWT设计背景：跨域认证JWT 原理JWT 结构JWT 使用方式注意JSON Web Token（缩写 JWT）是目前最流行的跨域认证解决方案，本文介绍它的原理、结构及用法。 JWT设计背景：跨域认证 互联网服务的用户认证流程是现代应用中的核心组成部分，通常的流程…
阅读更多...
vue3中如何实现标准元素 拖动 功能 【收藏备用】

vue3中如何实现标准元素 拖动 功能 【收藏备用】

最近在用vue3做一个企业后台管理系统的项目,在登录页面的时候需要用户滑动滑块来获取验证码登录系统 用到了元素拖放 这里也顺便记录一下 如何使用的. 目录 1.功能介绍 2.代码部分 3 实现过程 3.1 设置可拖动元素 3.2 拖动什么 3.3 放到何处 3.4 进行放置 1.功能介绍…
阅读更多...
Linux（CentOS）运行 jar 包

Linux（CentOS）运行 jar 包

1、在本地终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 java -jar tlias-0.0.1-SNAPSHOT.jar 发送请求&#xff0c;成功 关闭终端&#xff08;程序也会终止&#xff09; 发送请求&#xff0c;失败 2、在远程终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 …
阅读更多...
Local Dimming和Mini LED简介

Local Dimming和Mini LED简介

文章目录 Local Dimming和Mini LED的介绍区别和联系联系区别总结 Local Dimming和Mini LED的介绍 电视显示技术中的Local Dimming和Mini LED都是用于提升画面质量的背光技术&#xff0c;主要目的是增强对比度和改善黑色表现。以下是对它们的详细介绍&#xff1a; Local Dimmin…
阅读更多...
数据结构选择题及答案

数据结构选择题及答案

一、选择题 1、下列查找方法中&#xff0c;&#xff08; &#xff09;适用于查找有序单链表。 A&#xff0e;分块查找; B&#xff0e;哈希查找; C&#xff0e;顺序查找; D&#xff0e;二分查找; 2、在有n个结点的二叉树的二叉链表表示中&#xff0c;空指针数为( )。 A&#xf…
阅读更多...
npm完整发包流程（亲测可验证）

npm完整发包流程（亲测可验证）

1. 准备工作 &#xff08;1&#xff09; 在npm官网上注册一个账号 &#xff08;2&#xff09; 注册成功之后&#xff0c;npm会发送一封邮件给你&#xff0c;点击邮件里面的链接&#xff0c;做确认关联操作&#xff08;必需&#xff09; 2. 创建自己的npm包 &#xff08;…
阅读更多...
3.2 软件需求：面对过程分析模型

3.2 软件需求：面对过程分析模型

面对过程分析模型 1. 需求分析的模型概述1.1 面对过程分析模型-结构化分析方法1.2 结构化分析的过程 2. 功能模型&#xff1a;数据流图初步2.1 加工2.2 外部实体&#xff08;数据源点/终点&#xff09;2.3 数据流2.4 数据存储2.5 注意事项 3. 功能模型&#xff1a;数据流图进阶…
阅读更多...
【机器学习】机器学习中用到的高等数学知识-1.线性代数 (Linear Algebra)

【机器学习】机器学习中用到的高等数学知识-1.线性代数 (Linear Algebra)

向量(Vector)和矩阵(Matrix)&#xff1a;用于表示数据集&#xff08;Dataset&#xff09;和特征&#xff08;Feature&#xff09;。矩阵运算&#xff1a;加法、乘法和逆矩阵(Inverse Matrix)等&#xff0c;用于计算模型参数。特征值(Eigenvalues)和特征向量(Eigenvectors)&…
阅读更多...
向量数据库PGVECTOR安装

向量数据库PGVECTOR安装

文章目录 前提向量数据库介绍PGVECTOR安装1、pgvector下载2、编译安装3、创建vector扩展 前提 已经安装好了pg14版本。 其他版本也可以。 pg安装教程&#xff1a;https://blog.csdn.net/yushaoyyds/article/details/138855306?spm1001.2014.3001.5502 向量数据库介绍 向量数…
阅读更多...
头歌网络安全（11.12）

头歌网络安全（11.12）

头歌禁止复制解决 必须先下篡改猴&#xff01;&#xff01;&#xff01;&#xff01; 头歌复制助手 Educoder Copy Helperhttps://scriptcat.org/zh-CN/script-show-page/1860 Java生成验证码 第1关&#xff1a;使用Servlet生成验证码 任务描述 本关任务&#xff1a;使用se…
阅读更多...
技术栈1：nginx基础入门

技术栈1：nginx基础入门

目录 1.nginx概述 2.正向代理与反向代理 3.负载均衡 4.动静分离 5.nginx反向代理配置 1.nginx概述 Nginx (engine x)是一个高性能的HTTP和反向代理Web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔赛索耶夫为俄罗斯访问量第二的Rambler.ru站点开发…
阅读更多...
Centos7利用testdisk简单恢复文档文件和磁盘分区

Centos7利用testdisk简单恢复文档文件和磁盘分区

阅读更多...
自建CDN是否适合您的企业？

自建CDN是否适合您的企业？

在信息化加速发展的今天&#xff0c;CDN&#xff08;内容分发网络&#xff09;对于优化内容传输速度、提升用户体验的重要性已不容忽视。企业在选择CDN方案时&#xff0c;常常面临两个选择&#xff1a;自建CDN或租用CDN服务。自建CDN让企业拥有高度的自主权和灵活性&#xff0c…
阅读更多...
aws xray通过设置采样规则对请求进行过滤

aws xray通过设置采样规则对请求进行过滤

参考资料 https://github.com/aws/aws-xray-sdk-pythonpython api reference&#xff0c;https://docs.aws.amazon.com/xray-sdk-for-python/latest/reference/node api reference&#xff0c;https://docs.aws.amazon.com/xray-sdk-for-nodejs/latest/reference/ 初始化环境…
阅读更多...
特色3D打印stm32迷你8轴双核心主板

特色3D打印stm32迷你8轴双核心主板

我自己设计的3D打印机主板 1. 这是一块迷你的8轴主板, 主板尺寸为100mm*75mm, 使用一个8cm静音风扇散热足够了2. 这是一个带有保护的板子, 驱动上的gpio具有过压保护功能, 能够直接抗住24V的冲击, 意味着一个驱动炸了, 板子不烧, 并且其他的驱动也没事, 主板支持自动关机3. 8…
阅读更多...
最新文章

Copyright @ 2022~2023