初级数据结构——顺序表

🕗 发布于 2024-11-09 10:25 数据结构

前言

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

一、定义与特点

定义：顺序表（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;
}

九、总结

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

结语

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

原文地址：https://blog.csdn.net/ycs66/article/details/143631445

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：OpenCV视觉分析之目标跟踪(10)估计两个点集之间的刚性变换函数estimateRigidTransform的使用
下一篇：报名开启|开放原子大赛“Rust数据结构与算法学习赛”

Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
阅读更多2024-11-23
解决vm虚拟机中ctrl键粘滞问题（一直处于按下状态）
虚拟机中点击鼠标左键没有问题，单独按下键盘也没有问题，但是如果按下键盘的同时在按下鼠标左键就会卡住。而且100%稳定复现。发现问题原因：vm版本的问题，我的版本是17.5.0，升级成17.5.2 bu
阅读更多2024-11-23
第十章 JavaScript的应用
10.1.1 JavaScript简介1 简单性JavaScript 设计之初就考虑到了非专业程序员的使用，因此它的语法相对简单，容易上手。2 动态性JavaScript 是一种解释型语言，代码可以在
阅读更多2024-11-23
非root用户安装CUDA
4.下载完成后执行.run文件，需要添加两个参数，一个是--override，用于跳过某些检查或限制；另一个是--toolkitpath，它表示安装路径，必须是自己目录下面的路径，如果是根目录就会安装
阅读更多2024-11-23
Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
【代码】## Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
阅读更多2024-11-23
【通俗理解】Jensen不等式与变分分布q(z)在积分计算中的应用
Jensen不等式 #变分分布 #积分计算 #期望 #凸函数 #优化问题 #下界估计 #机器学习。
阅读更多2024-11-23
「Mac玩转仓颉内测版27」基础篇7 - 字符串类型详解
本篇将介绍 Cangjie 中的字符串类型，包括字符串的定义、字面量形式、插值表达、常用操作及应用场景，帮助开发者熟练掌握字符串的使用。
阅读更多2024-11-23
数据科学与SQL：组距分组分析 | 区间分布问题
绝对值分布分析也可以理解为组距分组分析。对于某个指标而言，一个记录对应的指标值的绝对值，肯定落在所有指标值的绝对值的最小值和最大值构成的区间内，根据一定的算法，在把这个区间划分为等距离的几个小区间，，
阅读更多2024-11-23
c++编译报C1004错误的原因及解决办法
可能是你的代码文件最后没有正确的结束符，或者是缺少了一些必要的头文件或语句。默认磁盘驱动器没有足够的空间用于临时文件，需要大约两倍于源文件的空间。编译器到达了源文件尾但未解析构造。计算结果为假的 #i
阅读更多2024-11-23
mysql 去重补全取出重复变量函数和存储过程
mysql 去重补全取出重复变量函数和存储过程
阅读更多2024-11-23

初级数据结构——顺序表

目录

前言

一、定义与特点

二、类型

三、基本操作

四、应用场景

五、优缺点

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

插入

删除

七、代码模板

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

1.求奇数的乘积

代码题解

2.数值统计

代码题解

九、总结

结语

相关文章