网站服务器管理 硬件,旅游网站网页设计模板代码,wordpress编辑文章怎么开头空两行,wordpress 图片懒加载我们来学习一下用数组模拟常见的数据结构#xff1a;单链表#xff0c;双链表#xff0c;栈#xff0c;队列。用数组模拟这些常见的数据结构#xff0c;需要我们对这些数据结构有一定的了解哈。单链表请参考#xff1a;http://t.csdn.cn/SUv8F 用数组模拟实现比STL要快单链表双链表栈队列。用数组模拟这些常见的数据结构需要我们对这些数据结构有一定的了解哈。单链表请参考http://t.csdn.cn/SUv8F 用数组模拟实现比STL要快在做算法题一般习惯使用数组模拟数据结构。这种数组模拟是非常多的奥比如邻接表哈希表的拉链存储Trie树堆等。数组模拟单链表会用到的变量或者数组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;//更新可用的下标值idxidx;
}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);
}数组模拟双链表会用到的变量或者数组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指向taill[1] 0代表tail指向head。//链表的初始化初始化链表的结构
void ListInit()
{//head向右指向tailr[0] 1;//tail向左指向headl[1] 0;//因为0代表head1代表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的节点的上一个节点。方法1l[k]找到下标为k的节点的上一个节点r[k]找到下标为k的节点的下一个节点r[l[k]] r[k]将找到的上一个节点向右连接到找到的下一个节点。2r[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 我们会用到的变量和数组1stack[N]用来模拟栈的数组。2top用来表示栈顶的下标。你同样可以把他们定义成全局变量//模拟栈的数组的大小
#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. 数组模拟队列我们会用到的变量和数组1q[N]用来模拟队列的数组。2hh用来表示队列队头。3tt用来表示队列的队尾。我们习惯是hh初始化为0tt初始化为-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;
