数组模拟常见数据结构

我们来学习一下用数组模拟常见的数据结构：单链表，双链表，栈，队列。

用数组模拟这些常见的数据结构，需要我们对这些数据结构有一定的了解哈。

单链表请参考：http://t.csdn.cn/SUv8F

用数组模拟实现比STL要快，在做算法题一般习惯使用数组模拟数据结构。这种数组模拟是非常多的奥，比如：邻接表，哈希表的拉链存储，Trie树，堆等。

1. 数组模拟单链表

会用到的变量或者数组：

head：表示头结点的下标。
e[i]：表示节点i的值、。
ne[i]：表示节点i的next指针是多少，数组模拟链表的话ne[i]的值就是下标啦。
idx：表示当前使用到了数组（e数组和ne数组的使用是同步的）的哪个位置(下标)。

可以把以上变量和数组定义成全局变量。

#define ARRAY_SIZE 1010
int head; //头结点的下标
int e[ARRAY_SIZE]; //存储数据的数组，表示节点的值
int ne[ARRAY_SIZE]; //存储下一个节点的数组
int idx; //当前可以使用的数组下标

1.1 单链表的初始化

一开始的时候链表中是没有数据的，我们让头结点的下标为-1即可（类比指针实现单链表的空指针），idx初始化为0，代表从数组下标为0往后的位置的可以使用。

//链表的初始化
void init()
{//初始时链表中没有节点head = -1;//可用的下标为0idx = 0;
}

1.2 链表的头插

在初始化完一个空链表之后。我们尝试来写头插函数：根用指针实现的单链表类似，数组模拟的单链表实现头插需要一下四步：

1：将要插入的值存储到e数组
2：连接原来的头结点
3：更新新的头结点
4：更新可用的下标值

下面是链表中没有数据的情况：

下面是链表中有数据的情况：

通过上面两种情况的分析我们发现无论链表中是否有数据，都可以用这四步来做。那么我们就可以写出头插的代码啦！还有就是通过对指针实现的单链表的理解：尾插的效率是很慢的，所以数组模拟时不再写尾插函数。

//单链表的头插
//假设数组中存储的都是整型数据哈，如果要存其他的数据类型，可以typedef一下
void ListPushFront(int x)
{//存值e[idx] = x;//连接ne[idx] = head;//更新head = idx;idx++;
}

1.3 在下标为k的节点的后面插入值为x的节点

同样通过对指针实现的单链表理解：在一个节点的前面插入节点的时间复杂度很高，我们选择在一个节点之后插入新的节点。数组模拟链表时，就是在下标为k的后面插入新的节点啦！

同样也需要四步操作哈：

1：将要插入的值存储到e数组
2：将新的节点连接到k节点的下一个节点
3：将k这个节点连接到新的节点
4：更新可用的下标值（idx）

同样地，对于尾插这样的四步操作也是没有啥问题的，行，我们就可以写出在在下标为k的节点的后面插入值为x的节点的代码啦！

//指定下标k后面插入x
//调用这个函数你得确保k是合法的才行撒，即k下标是链表中的一个节点
void ListInsertAfter(int k, int x)
{//将要插入的值存储到e数组e[idx] = x;//将新的节点连接到k节点的下一个节点ne[idx] = ne[k];//将k这个节点连接到新的节点ne[k] = idx;//更新可用的下标值（idx）idx++;
}

1.4 将下标为k的节点的后面那个节点删除

同样地，我们不删除前面的节点，时间复杂度太高了哦！在理解了指针版的删除指定位置之后的节点，数组模拟的链表删除指定下标的节点的后面那个节点也是信手拈来好吧！

步骤只有一步哦：

直接让下标为k的节点指向：下标为k的节点的下一个节点的下一个节点就好啦！

是不是很简单 😊

我们发现这个删除只是在逻辑上删除了哈，内存上并没有像指针实现的链表那样删除。也就是说数组模拟的链表被删除的节点理论上还是可以使用的，但实际上并不会再去使用那块空间了，而是使用下标为idx的空间。

//删除指定下标k的后面那个节点
//放到具体的题目中去，k会是合法的哦，直接看代码是有问题的
void ListEraseAfter(int k)
{//连接ne[k] = ne[ne[k]];
}

1.5 链表的打印

和指针实现的单链表类似，只不过结束打印的条件是：i = -1，我们用的是-1代表空节点嘛！

为了好看，打印的函数还是和指针模拟单链表时的打印函数差不多！

//打印链表
void ListPrint()
{//用i遍历链表for (int i = head; i != -1; i = ne[i]){printf("%d->", e[i]);}printf("NULL");
}

2. 数组模拟双链表

会用到的变量或者数组：

e[i]：表示节点i的值、。
l[i]：表示节点i的prev指针是多少，数组模拟链表的话l[i]的值就是下标啦。
r[i]：表示节点i的next指针是多少，数组模拟链表的话r[i]的值就是下标啦
idx：表示当前使用到了数组（e数组和l数组和r数组的使用是同步的）的哪个位置(下标)。

同样你可以把以上变量和数组定义为全局变量：

//数组的大小
#define ARRAY_SIZE 1010
//存节点的值
int e[ARRAY_SIZE];
//存节点的上一个节点
int l[ARRAY_SIZE];
//存节点的下一个节点
int r[ARRAY_SIZE];
//可用的数组下标
int idx;

2.1 链表的初始化

初始化双链表时，我们让双链表有一个小小的结构，有了这个结构能方便我们的插入和删除，可以类比带头双向循环链表中的初始化函数让哨兵位的头结点的next和prev均指向自己，这样做就不用考虑什么头插，尾插，头删，尾删的情况了，即通过哨兵位的头结点能够让插入，删除函数具有普适性。数组模拟双向链表中的初始的小结构，也就是这个目的。

这两个节点并不存储数据的喔，只是方便后续的操作。我们令下标为0的位置代表左侧的那个节点，可以理解为head，下标为1的位置代表右侧的那个节点，可以理解为tail。那么初始化时，idx就得从2这个下标开始咯，并且r[0] = 1，代表head指向tail；l[1] = 0，代表tail指向head。

//链表的初始化，初始化链表的结构
void ListInit()
{//head向右指向tailr[0] = 1;//tail向左指向headl[1] = 0;//因为0代表head，1代表tail所以idx从2开始idx = 2;
}

2.2 在下标为k的节点的后面插入一个新的节点

嘿嘿，双链表的在下标为k的位置左右插入一个新节点可以只写一种插入方式即可哦！

我们先来看看在下标为k的节点的后面插入一个新的节点：

只需要以上4步哦，代码的图解就没啥必要了，原理和单链表的插入一个逻辑。

//在下标为k的节点的后面插入一个值为x的节点
void ListInsertAfter(int k, int x)
{//存储xe[idx] = x;//对应步骤1r[idx] = r[k];//对应步骤2l[idx] = k;//对应步骤3l[r[k]] = idx;//对应步骤4r[k] = idx;//更新可用的下标值idx++;
}

emm，那么我们如果想要在下标为k的节点的前面的插入一个节点呢？当然我们可以用上面向后插的逻辑，重新写一个向前插入的函数。但是没有必要哦！

2.3 删除下标为k的节点

这个操作只需要两步哈：

1：下标为k的节点的前一个节点向右指向下标为k的节点的下一个节点。
2：下标为k的节点的下一个节点向左指向下标为k的节点的上一个节点。

方法：

1：l[k]：找到下标为k的节点的上一个节点；r[k]：找到下标为k的节点的下一个节点；r[l[k]] = r[k]：将找到的上一个节点向右连接到找到的下一个节点。

2：r[k]：找到下标为k的节点的下一个节点；l[k]：找到下标为k的节点的上一个节点；l[r[k]] = l[k]：将找到的下一个节点向左连接到找到的上一个节点。

//删除下标为k的节点
void ListErase(int k)
{//步骤1r[l[k]] = r[k];//步骤2l[r[k]] = l[k];
}

3. 数组模拟栈

数组模拟栈和队列就非常滴简单了啊！应用请参考单调栈：

http://t.csdn.cn/uBst3

我们会用到的变量和数组：

1：stack[N]：用来模拟栈的数组。
2：top：用来表示栈顶的下标。

你同样可以把他们定义成全局变量：

//模拟栈的数组的大小
#define N 1010
//模拟栈的数组
int stack[N];
//用来表示栈顶元素的下标
int top;

3.1 栈的初始化

我们习惯模拟栈的数组是从下标为1的位置开始存储数据的，因为这样很好判断栈是否为空。既然你将top定义成了全局变量，自然就不用初始化了哦！

3.2 添加元素

添加元素是非常的简单啊：先让top++，然后赋值就行了。

//添加元素
void StackPush(int x)
{stack[++top] = x;
}

3.3 删除元素

top--就行。

//弹出栈顶元素
void StackPop()
{//top为0栈为空，不用删if(top)top--;
}

3.4 判断栈是否为空

根据top的值判断即可。

//判断栈是否为空，为空返回true
bool StackEmpty()
{return top > 0;
}

3.5 查看栈顶元素

stack[top] 就行了哈。

4. 数组模拟队列

我们会用到的变量和数组：

1：q[N]：用来模拟队列的数组。
2：hh：用来表示队列队头。
3：tt：用来表示队列的队尾。

我们习惯是hh初始化为0，tt初始化为-1，从下标为0的位置开始存储数据。

下面的是伪代码哈！能传达意思就行。具体的应用请参考单调队列！

//模拟栈的数组
int stack[N];
//用来表示栈顶元素的下标
int top;//模拟队列的数组大小
#define N 1010
//模拟队列的数组
int q[N];
//表示队头
int hh;
//表示队尾
int tt = -1;//插入元素-队尾入元素
q[++tt] = x;//弹出元素，队头出数据
hh++;//判断队列是否为空
if (hh <= tt)not empty;
elseempty;