首页 > 其他分享 >初级数据结构——顺序表

初级数据结构——顺序表

时间:2024-11-09 09:18:35浏览次数:3  
标签:SequentialTable index 顺序 int list 初级 elements 数据结构 size

目录

前言

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

一、定义与特点

定义:顺序表(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;
}

九、总结

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

结语

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

标签:SequentialTable,index,顺序,int,list,初级,elements,数据结构,size
From: https://blog.csdn.net/ycs66/article/details/143631445

相关文章

  • 7-8 数据结构实验二 二叉树的遍历
    以二叉链表作存储结构,建立一棵二叉树。输出该二叉树的先序、中序、后序遍历序列,求出该二叉树的深度,并统计其叶子结点数。二叉链表的类型描述:typedefcharElemType;typedefstructBiNode{ElemTypedata;structBiNode*lchild,*rchild;}BiNode,*BiTree;......
  • 数据结构实验(串的实现)
    实验串的实现一、实验目的1.掌握串的基本概念;2.理解串的几种存储表示及其特点;3.掌握串的常用操作的实现。二、实验环境硬件:计算机一台;软件:VisualStudio。三、实验内容串分别采用顺序存储方式的前提下,完成如下两个任务:1.串比较操作:编写一个比较串s和串t两个串是否相......
  • huawei初级网络工程师综合实验
    本章为总结练习,只提供思路以及验证结果,和比较有难度的命令并且在我的其他章节对本练习中出现的所有都有介绍这里就不重复解释了拓扑图以及实验要求:sw1充当2层交换机sw-2(undoportswitch)充当三册交换机R-3连接外网1.基本ip配置略2.sw-2和R-2间开启rip协议R-2R-3......
  • JS数据结构之树和二叉树
    一、树树(Tree)是一种非常常见的数据结构,它模拟了自然界中树的结构,由节点(或称为顶点)组成,并且具有层次化的组织形式。树结构在计算机科学中广泛应用,例如在组织数据、管理信息层次以及算法设计中。1.基本概念节点(Node)根节点(Root):树的最顶端节点,没有父节点。内部节点(InternalNod......
  • 第八章: 8.10将一个5*5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(四个角的元
    第八章:8.10将一个5*5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(四个角的元素的顺序是从左到右,从上到下,依次从小到大存放)思考:1.输入矩阵的值inta[5][5]={0};   inti=0,j=0;   printf("请输入一个5*5的数组:\n");   for(i=0;i<5;......
  • 二叉树 (王道数据结构 C语言版)
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 数据结构 --树
    定义树是n(n>=0)个结点的有限集。n=0时,称为空树。在任意一棵树非空树中应满足:(1)有且仅有一个特定的称为根(root)的结点(2)当时,其余结点可分为个互不相交的有限集,其中每一个集合本身又是一颗树,并且称为根的子树。基本概念结点的度:一个结点拥有的子树的数目叶子结点:度为0......
  • 数据结构学习笔记---线性表:顺序表(插入)
    顺序表的基本操作——插入首先,静态分配一个顺序表#include<stdio.h>#include<stdlib.h>#defineMaxSize5//定义队列的最大长度typedefstruct{ intdata[MaxSize]; intlength;}SqList;然后实现插入方法,for循环我们提前插入了四个元素,顺序排放原理是以i为......
  • 数据结构-关键技术分享
    书:pan.baidu.com/s/1tIHXj9HmIYojAHqje09DTA?pwd=jqso数据结构与算法基础:介绍数据结构与算法的基本概念、重要性和应用场景,为读者打下坚实的基础。数据项与数据对象:详细解释数据项作为数据不可分割的最小单位,以及数据对象作为性质相同的数据元素的集合的概念。逻辑结构与物理......
  • Pwn之初级ROP
            NX保护开启后,不能直接向堆栈上注入代码运行,因此需要采用返回返回导向编程 (ReturnOrientedProgramming)来绕过保护。ROP主要思想是在 栈缓冲区溢出的基础上,利用程序中已有的小片段(gadgets)来改变某些寄存器或者变量的值,从而控制程序的执行流程。gadgets......