上文我们通过结构体的结构实现了队列、以及循环队列的实现我们或许在其他老师的教学中只学到了用结构体的形式来实现链表、队列、栈等数据结构本文我想告诉你的是我们可以使用数组的结构实现链表、单调栈、单调队列

目录

前言

一、用数组结构的好处

1.数组的优缺点

2.链表的优缺点

3.总结

二、用数组实现链表

1.认识构造、初始化

2.将x插入到头结点

3.将x插入到第k次插入数值之后的位置

4.删除第k次插入的结点

三、完整代码演示

四、数组实现双向链表

1.初始化

2.在第k次插入的点的右边插入x

3.删除第k个点

五、完整代码

---

前言

你之前实现链表的形式是不是这一种结构来实现

typedef struct ListNode {
	int data;
	struct ListNode* next;
}List;

但是我如果告诉你只需要这样两个数组就能模拟实现链表你相信吗

head	表示头节点
e[N]	表示存储结点数值的数组
ne[N]	表示结点的下一个结点的位置
idx   表示当前存储元素的位置   当前存储到哪里了就是

 接下来我们来实现单链表以及双向链表

一、用数组结构的好处

我们在日常学习的过程中老师教授给我们的都是以结构体的形式实现的链表但是呢比如我们要创建100000个结点这样的话 用结构体的话时间太长空间太大反观数组就显得很有优势了。

1.在搞算法的时候使用数组的形式去模拟链表会使得运算速度变快更加适合写算法打比赛的小朋友。

2.在笔试的适合会更快的创建实现链表的基础功能进行插入删除元素并根据下标直接找到所需元素等

我们在来了解一下数组和链表的优缺点吧

1.数组的优缺点

认识数组

数组是一种线性结构存储的空间是内存连续的物理连续每当创建一个数组的时候就必须先申请好一段指定大小的空间。一次申请即可指定大小的空间

优点

由于内存连续这一特征数组的访问速度很快直到索引下标之后可以实现O(1)的时间复杂度的访问。

缺点

1.在任意位置删除和插入操作的时候就会涉及到部分元素的移动这样的话我们对于数组的任意位置的删除和插入的操作的时间复杂度为O(n)。

比如

1>在i点后面插入数据那么就需要i+1位置以及之后的元素整体后移一位for循环操作然后再将插入的数据放在i+1的位置上

2>在i点之后删除元素那么就需要将i+1以及之后的元素整体前移一位总元素个数减一

以上是数组的优缺点可以快速访问达到O(1)但是在任意删除和插入元素的时候会耗时间达到O(n)。

2.链表的优缺点

认识链表

1.链表也是一种线性结构但是他存储空间是不连续的物理不连续逻辑连续链表的长度是不确定且支持动态扩展的。每次插入元素的时候都需要进行申请新节点然后赋值插入链表中。

优点
在插入数据或者删除数据的时候只需要改变指针的指向即可不需要类似于数组那样部分整体移动整个过程不涉及元素的迁移因此链表的插入和删除操作时间复杂度为O(1)

缺点

在查找任意位置的结点的数值域的时候需要遍历时间复杂度为O(n)

但是我们在任意位置插入或者删除元素的时候需要查找这个指定的元素的结点位置所以综合起来链表的插入和删除仍为O(n)。

3.总结

无论数组还是链表查找的时间复杂度都是O(n)查找都要挨个遍历直到找到满足的条件的数据为止所以对于链表如果没有给定指针的地址只是要插入删除第N位元素的时候加上查找综合起来时间复杂度为O(n)。

但是我们如果以数组的形式来实现链表那么插入删除指定元素位置的时候是不是就更加简便了呢在第N位插入删除元素的时候直接以O(1)的时间复杂度找到该位置结点然后再由于链表的删除插入都是O(1)的所以整个删除或插入操作综合时间复杂度为O(1),比普通链表快很多。

二、用数组实现链表

1.认识构造、初始化

我们先由图示了解初始化的时候的准备工作

我们使用c++会更加方便理解因为c++支持用变量来定义数组

初始化代码

//使用c++更简单先用c++的形式实现
const int N = 100010;
int head, e[N], ne[N], idx; //全局变量
void init() {
	head = -1;
	idx = 0;//进行初始化的操作idx为当前链表中数组最后一个元素末尾下标位置
}

2.将x插入到头结点

就是所谓的链表中的头部插入

图示

实际上和普通链表的头插一样只是流程next指针换成了ne[N]数组的形式记录的是下一结点的数值。

代码如下

void add_to_head(int x) {
	e[idx] = x;//将x数值存入到e[]数组中
	ne[idx] = ne[head];//将idx新插入的结点的下一个位置存储到ne[idx]中  全局变量 ne以及n数组初始化为0
	head = idx;
	idx++;
}

3.将x插入到第k次插入数值之后的位置

图示

我们要说明一个问题ne[N]这个数组存放的数值是不需要管的因为不管是add还是remove插入还是删除结点都不会重复实际上e[ne[head]]是得到head结点下一个结点的数值ne[]数组只作为下标使用。 

我们是在第k次插入的之后的位置插入x但是与此同时 此时的idx成为新的第k次插入数据下标也就是说再次对第k次插入数值之后的位置插入的x实际上是在上一次的新插入的结点之后进行插入

图示

代码如下

//在第k个插入的数字之后插入数据
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}

4.删除第k次插入的结点

//将下标为k的点后面的点删掉
void remove(int k, int ne[]) {
	ne[k] = ne[ne[k]];//表示k的下一个位置ne为下一个位置的下一个位置这样跳过了原来的ne[k]结点
}//使用的时候应该是  删除的是k之后的点

直接跳过即可和链表类似

三、完整代码演示

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>


const int N = 100010;
int n, e[N], ne[N], idx, head;


//初始化
void init() {
	head = -1;
	idx = 0;
}

//头插
void add_to_head(int x) {
	e[idx] = x;
	ne[idx] = head;
	head = idx;
	idx++;
}

//在第k个插入的数字之后插入数据
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}
//删除第k的插入的数据
void remove(int k) {
	ne[k] = ne[ne[k]];
}

int main()
{
	init();
	add_to_head(1);
	add_to_head(2);
	add_to_head(3);
	add_to_head(4);
	add_to_head(5);
	add(2-1, 10);
	add(2-1, 2);
	add(2-1, 3);
	add(2-1, 4);
	add(2-1, 5);
	add_to_head(50);
	for (int i = head; i != -1; i=ne[i]) {
		printf("%d ", e[i]);
	}
	printf("\n");
	for (int i = head; i != -1; i = ne[i]) {
		printf("%d ", ne[i]);
	}
	return 0;
}

四、数组实现双向链表

1.初始化

//初始化
// e[]表示节点的值l[]表示节点的左指针r[]表示节点的右指针idx表示当前用到了哪个节点
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示为左端点1表示为右端点
	r[0] = 1;
	l[1] = 0;
	idx = 2;//从2开始
}

我们设定用e[N]数组来记录数据在用 l[N] 、 r[N]数组表示结点的左右指针一开始0表示为左端点1表示右端点然后r、l两个数组记录数值下标从2开始

e[]表示节点的值l[]表示节点的左指针r[]表示节点的右指针idx表示当前用到了哪个节点

2.在第k次插入的点的右边插入x

//在第k次插入的点的右边插入x

void add(int k, int x) {
	e[idx] = x;//数值x给当前idx位置的e数组存储
	r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后将k的右端点的左端点连接idx
	r[k] = idx;//最后将k的右端点连接idx
}

3.删除第k个点

//删除第k个点
void remove(int k) {
	//就是将k的左端点和右端点相互连接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}

五、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
//使用数组的形式实现双向链表


//e[N]	表示存储结点的数值
//l[N]	表示当前结点的左结点位置
//r[N]	表示当前结点的右节点位置
//idx	表示当前结点存储的位置

//初始化
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示为左端点1表示为右端点
	r[0] = 1;
	l[1] = 0;
	idx = 2;//从2开始
}

//在第k次插入的点的右边插入x

void add(int k, int x) {
	e[idx] = x;//数值x给当前idx位置的e数组存储
	r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后将k的右端点的左端点连接idx
	r[k] = idx;//最后将k的右端点连接idx
}

//删除第k个点
void remove(int k) {
	//就是将k的左端点和右端点相互连接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}