上一小节我们谈论了栈的顺序存儲结构使用顺序栈,我们可以方便的存取元素不过栈的顺序存储结构要求我们事先申请好固定大小的内存空间用于存储数据,在使用嘚过程中无法再动态地对栈的空间进行扩容这是顺序栈的一大缺点。接下来我们来学习下栈的链式存储结构
栈的链式存储结构,简称為链栈通过指针来关联相邻的元素,允许程序在运行过程中动态地申请内存空间进行扩容可以说,只要内存空间足够链栈就能容纳無数的元素。
我们来看看链栈相关的块链式数据结构构定义:
上面我定义了两个结构体类型第一个是用于表示链栈中的元素结点的类型,烸个结点存储着元素值和指向下一个元素的指针第二个是用来表示链栈结构的,其中用到了链栈结点的类型
【补充提示:我们一般用push表示入栈操作,用pop表示出栈操作】
我们先来看看链栈插入元素的操作实现:
我们再来看看链栈的出栈操作:
链栈的优点就是可以动态扩容对于我们需要使用到栈这种结构的地方,如果无法 确定元素个数的情况可以使用链栈这种结构,不过如果可以确定元素个数那么就使用顺序栈。另外由于顺序栈和链栈都是在栈顶操作元素,所以它们的元素入栈和出栈的时间复杂度都是O(1)
顺序表插入、删除时需要通过移動数据来实现影响了执行效率。
而链表不要求逻辑上相邻的两个数据元素物理上也相邻因此对线性表的插入、删除不需要移动数据元素,只需要修改链
下面介绍带头结点的链式表:
在顺序存储表示的线性表中求表长是一件很容易的事,直接返回Last+1值就可以了但是在链式存储表示中,需要将链表从头到尾遍历一遍;设一个移动的指针p和计数器cnt初始化后,p从表的第一个结点开始往后移同时计数器cnt+1.
对于順序存储,按序号查找是很直接的事要得到第k个元素的值,直接取L->Data[k-1]就可以了而对于链式表就需要采用求表长的思路,从头遍历判断當前结点是否是第K个,若是返回该结点的值,否则继续后一个
//根据指定的位序查找s
4.查找(按值查找Find)
按值查找的方法也是从头到尾遍曆,直到找到为止
带头结点的链式表的插入
删除指定位序i的元素首先需要找到被删除结点的前一个元素,然后再删除结点并释放空间。
//根據指定的位序查找 printf("请输入你要按序号查找的数的序号:\n");
//栈的链式存储结构的实现
//添加链棧元素 并返回其值
//删除链栈元素,并返回其值
加载中请稍候......