🎇[数据结构]线性表——顺序存储🎇

---

 

🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录🌟

---

🍰 1.线性表

🎆在此之前，我们先来认识一下新的逻辑结构—线性表

☀️1.线性表的定义

💯 线性表是具有相同类型的数据类型的n个数据元素的有限序列，其中n为表长，$n=0$时为空表

$e.g$

这里要注意的是，定义中描述的为数据元素，而非数据项，也就是，存储单元可以是一个结构体，而数据项为里面的成员

✨线性表的特点：

• 表中元素的个数为有限个
• 表中元素具有逻辑上的顺序性，表中元素有其先后顺序
• 表中元素都是数据元素，每一个元素都为单个元素
• 表中元素的数据类型都相同，每个元素占相同的内存空间
• 表中元素具有抽象性，即仅讨论元素之间的逻辑关系，而不考虑具体实现方式

🔑 注意：线性表仅为一种逻辑结构，表示元素之间为一对一的相邻关系，而之后提及的顺序表和链表是指存储结构

☀️2.线性表的基本操作

---

🍰 2.线性表的顺序存储

☀️1.顺序表的定义

🔱线性表的顺序存储，它是用一组连续的存储单元依次存取线性表内的数据元素，从而使在逻辑上相邻的数据元素在物理位置上也相邻

💎顺序表的特点：

1. 表中元素的逻辑顺序与物理顺序相同
2. 内存地址连续，地址易于计算，可随机存储

☀️2.顺序存储的类型描述

💎1. 我们需要定义结构体中存放数据元素的数组 data
2. 还需要记录当前数组长度length

代码实现：

#define Maxsize 10
#define Elemtype int;

typedef struct {
	Elemtype data[Maxsize];
	int length;
}Sqlist;

☀️3.顺序存储的初始化

🔱初始化一个空表，即还未在内存中开辟空间，所以占用的内存为0

初始化：$L.length=0$

代码实现：

#include<iostream>
#define Maxsize 10
using namespace std;

typedef struct {
	int data[Maxsize];
	int length;
}Sqlist;

void InitList(Sqlist& L) {
	L.length = 0; //长度要初始化为0
}

int main() {
	Sqlist L; //声明一个顺序表
	InitList(L); //初始化
	for (int i = 0; i < L.length; i++) { //每次只能到当前数组的最大长度，因此，访问的都是已经处理过的数组元素，所以数组不用初始化为0
		printf("data[%d]=%d\n", i, L.data[i]);
	}
	system("pause");
	return 0;
}

☀️4.顺序存储的定义方式

🔱一维数组可以是静态分配，也可以是动态分配的

1. 静态分配：

💎由于数组的大小和空间固定，一旦空间占满，新加入的数据就会溢出

代码实现：

//1.1静态数组
#include<iostream>
#define Maxsize 10
using namespace std;

typedef struct {
	int data[Maxsize];
	int length;
}Sqlist;

void InitList(Sqlist& L) {
	L.length = 0; //长度要初始化为0
}

int main() {
	Sqlist L; //声明一个顺序表
	InitList(L); //初始化
        //...
	system("pause");
	return 0;
}

2. 动态分配：

🔱而在 动态分配时，存储空间是在执行语句的同时进行分配的，一旦空间占满，程序可以开辟一片更大的空间，用来替换原来的空间，从而达到扩充存储的目的

🔑 要注意：假设原顺序表大小为10，若要增加5的存储容量，则我们需要从内存中申请大小为15的存储空间，因为是转移，而不是在原有基础上增加

$e.g$

💎准备：
1. 加入#include<stdlib.h>头文件，便于使用$malloc/free$来申请内存空间
2. 在结构体内定义指示动态分配数组的指针，每到扩充一次数组的长度，都让data指针指向$malloc$所分配的内存空间
3. 将原空间的数据循环输入到新的内存空间中

代码实现：

//1.2.动态数组
#include<iostream>
#include<stdlib.h>
#define Initsize 10

typedef struct {
	int* data; //指向数组的指针
	int Maxsize; //当前数组最大长度
	int length; //当前的数组长度
}Seqlist;

void Initlist(Seqlist& L) {
	// 用malloc申请一片连续的内存空间
	L.data = (int*)malloc(sizeof(int) * Initsize);//只用申请data中元素的数据类型的大小的空间
	L.length = 0;
	L.Maxsize = Initsize;
}

void IncreaseSize(Seqlist& L, int len) { //len为增加的长度
	int* p = L.data;//定义一个指向数组的另一个指针
	L.data = (int*)malloc(sizeof(int) * (len + L.Maxsize));//这时L.data指向了一段新开辟的内存空间
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];//将原来的值赋到新的上去
		//这里p相当于数组名，可以下标访问
		//data[i+1]=*(data+1)
	}
	L.Maxsize = L.Maxsize + len;
	free(p); //释放p所指向的内存空间（原来的内存空间）
}

int main() {
	Seqlist L;
	Initlist(L);
	//...
	IncreaseSize(L, 5);//增加5个
	system("pause");
	return 0;
}

🎊 🎊总结：

☀️5.顺序存储的基本操作

1. 插入操作

🎊顺序表插入删除的时间复杂度主要由元素位置的移位产生 🎊

最好时间复杂度：插入在表尾，不需要移动元素：$O(1)$
最坏时间复杂度：插入在表头，要移动$n-1$个元素：$O(n)$

代码实现：

//2.1.插入
#include<iostream>
#define Maxsize 10
using namespace std;

typedef struct {
	int data[Maxsize];
	int length;
}Sqlist;


void InitList(Sqlist& L) {
	L.length = 0;
}

bool Listinsert(Sqlist& L, int i, int e) {
	if (i<1 || i>L.length + 1) { //超出了当前数组范围
		return false;
	}
	if (L.length >= Maxsize) {
		return false;
	}
	for (int j = L.length; j >= i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return true;
}

int main() {
	Sqlist L;
	InitList(L);

	for (int i = 0; i < 5; i++) {
		L.data[i] = i;
		L.length++; //更新当前长度
	}
	Listinsert(L, 3, 2);//在位序为3处插入元素2

	for (int i = 0; i < L.length; i++) {
		printf("%d ",L.data[i]);
	}

	system("pause");
	return 0;
}

2. 删除操作

🎊 🎊类似地：

最好时间复杂度：删除在表尾，不需要移动元素：$O(1)$
最坏时间复杂度：删除在表头，要移动$n-1$个元素：$O(n)$

代码实现：

//2.2删除
#include<iostream>
#define Maxsize 10
using namespace std;

typedef struct {
	int data[Maxsize];
	int length;
}Sqlist;

void InitList(Sqlist& L) {
	L.length = 0;
}

bool Listdelete(Sqlist& L, int i, int& e) { //这里要将e的值带回来，所以传引用
	if (i<1 || i> L.length)
		return false;
	e = L.data[i - 1];
	for (int j = i; j < L.length; j++) {
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}

int main() {
	Sqlist L;
	InitList(L);

	for (int i = 0; i < 5; i++) {
		L.data[i] = i;
		L.length++;
	}

	int e = -1; //用e变量（开辟新内存）接收删除值
	Listdelete(L, 3, e);
	cout << "被删掉的元素为：" << e << endl;

	for (int i = 0; i < L.length; i++) {
		printf("%d ", L.data[i]);
	}

	system("pause");
	return 0;
}

3. 查找操作

🎆①按位查找

🎆在表L中找到位序为i的元素

🔑 $注意：位序=下标-1$

代码实现：

#include<iostream>
#define Initsize 10

typedef struct {
	int* data; //指向数组的指针
	int Maxsize; //当前数组最大长度
	int length; //当前的数组长度
}Seqlist;

//1.按位查找
int Localindex(Seqlist& L, int i) {
	return L.data[i - 1]; //i为位序
}

🎆②按值查找：

🎇在表L中找到值为e的元素

代码实现：

int Localelem(Seqlist& L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i == e]) {
			return i + 1;//返回位序
		}
	return 0; //无
	}
}
按位查找
int Localindex(Seqlist& L, int i) {
	return L.data[i - 1]; //i为位序
}

💯3.顺序存储实战应用

技能实战篇：

🌟题目	跳转👇	🌟题目	跳转👇
1.数组逆置	🚀GO	2.合并数组的中位数	🚀GO
3.数组的主元素	🚀GO	4.未出现的最小正整数	🚀GO
5.三元组的最短距离	🚀GO

---

 

🎇本节主要介绍了一种逻辑结构——线性表，以及实现它的一种存储结构——顺序存储，后续还会介绍新的存储结构~🎇

如有错误，欢迎指正~！