以图明志

数据结构

[专题] 链栈的出栈操作

其实就是删除结点而已
前面讨论了链栈的进栈操作,这里接下来讨论链栈的出栈操作。至于链栈的出栈pop操作,也是很简单的三句操作。假设变量p用来存储要删除 的栈顶结点,将栈顶指针下移一位,最后释放p即可。首先设定一个工作结点 p,并且将栈顶结点赋值给它。然后将栈顶指针下移一位,指向下一结点。代码表示为 S->top=S->top->next;

数据结构

[专题] 链栈的初始化与遍历

链栈的基本操作
我们在定义完一个数据结构的结构体之后,需要初始化才能使用。比如顺序栈的初始化,也就是构造一个空栈就行了。那么链栈如何初始化呢?链栈初始化的目标也是要构造一个空栈。根据结构体定义,空栈是什么一个状况呢?就是栈的count = 0,并且栈的 top 为 null。所以知道这两点,我们就可以写出链栈的初始化函数了。

数据结构

[专题] 链栈的进栈操作

两个步骤即可完成
链栈的操作绝大部分都和单链表类似,只是在插入和删除上,特殊一些。假设元素值为e的新结点是s, top为桟顶指针……那么我分析下过程,首先开辟一个内存空间给 s,然后 s的data就是e,再将新结点s 的后继赋值为当前结点 S->top。最后将栈顶指针指向结点 s。

数据结构

[专题] 链栈:栈的链式存储结构

链栈的结构体定义
前面讲完了栈的顺序存储结构,我们现在来看看栈的链式存储结构,简称为链栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。单链表有头指针,而栈顶指针也是必须的,那干吗不让它俩合二为一呢,所以比较好的办法是把栈顶放在单链表的头部。

数据结构

[专题] 获取顺序栈的栈顶元素

判断栈是否为空与置空栈
根据前面定义的栈ADT,我们还有几个操作要完成。比如获取顺序栈的栈顶元素 GetTop (S,*e):若栈存在且非空,用e返回S的栈顶元素。这个操作的函数设计思路如何呢?参考之前线性表的话,就是设一个存储栈顶的变量 e,然后通过地址传递,用 *e 来保存指针为 top 的数组元素。

数据结构

[专题] 顺序栈的出栈操作

与进栈相反的操作
昨天我们讲了顺序栈的进栈操作,那么今天我们来看一下与进栈相对应的出栈操作吧。进栈是先自增再赋值,出栈则反过来。先把要出栈的元素获取到,然后再指针自减,把空间释放出来。

数据结构

[专题] 顺序栈的进栈操作

外加栈的初始化与遍历
对于栈来说,最重要的操作之一就是进栈。我们今天来看看如何实现顺序栈的进栈操作。进栈操作push大概分为两步。栈顶指针 S->top 先自增1,给需要进栈的元素腾出内存空间。再赋值。就是给对应的数组元素赋值:S->data[S->top]=e

数据结构

[专题] 顺序栈:栈的顺序存储结构

栈的结构体定义
既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化,我们将其简称为顺序栈。线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组哪一端来作为栈顶和栈底比较好?下标为0的一端作为栈底比较好,因为首元素都存在栈底,变化最小,所以让它作栈底。

数据结构

[专题] 栈的抽象数据类型ADT

定义我们需要实现的栈的操作
对于栈来讲,理论上线性表的操作特性它都具备,可由于它的特殊性,所以针对它在操作上会有些变化。特别是插入和删除操作,我们改名为push和pop,英文直译的话是压和弹,更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了,我们一般叫进栈和出栈。

数据结构

[专题] 栈的定义与大概理解

什么是栈
栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIF0结构。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指找顶,而不是栈底。

数据结构

[专题] 删除单链表中的重复元素

遍历与比较
刚我在网上看到一个面试题,如何删除单链表中重复的元素。今天我们试着解决这个问题吧。建立三个工作指针p,q,r,然后p遍历全表。p每到一个结点,q就从这个结点往后遍历,并与p的数值比较,相同的话就free掉那个结点。思路也蛮简单的。

数据结构

[专题] 单链表建环,无环链表变有环

设计一个链表建环函数
我们能否给一个无环链表建环呢?其实貌似也不很难,只要找到最后一个结点 tail,让它指向环的入口就行。所以问题分解为:找到环入口点 cur,把最后的指针 tail 指向 cur即可。首先找到环入口,也就是参数 num。定义工作指针 LinkList cur = *L; 让它遍历到 num 的位置。这个时候让第二个工作指针 tail 接替 cur 遍历到末尾。

数据结构

[专题] 如何判断链表是否有环的存在

“快慢指针”的使用
有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。如何判断一个单链表是否有环呢?这个可以用昨天提到的“快慢指针”来解决吧?设两个工作指针,一个快一个慢,如果有环的话,它们会必然在某点相遇。

数据结构

[专题] 用标尺法快速找到单链表的中间结点

工作指针与标尺
昨天我们了解到“距离-标尺”的典型问题,再之前也学习了“工作指针”的概念,现在可以来解决一个腾讯的面试题了:如何快速找到未知长度单链表的中间结点。能否再优化一下这个时间复杂度呢?有一个很巧妙的方法:设置两个工作指针*search、*mid都指向单链表的头节点。其中* search的移动速度是*mid的2倍。当*search指向末尾节点的时候,mid正好就在中间了。这也是标尺的思想。

数据结构

[专题] 求单链表倒数第N个数

“距离-标尺”问题
不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。如果我们用两个指针,并保持他们的距离为n,那么当这个线段的右端指向末尾节点时,左端节点就指向倒数第n个节点。

数据结构

[专题] 单链表反转/逆序的第三种方法

建立一个新表来拷贝每个元素
昨天介绍了单链表逆序的两种方法,后来我又想到了第三种。我们就是要深入地研究每个细节嘛。这个方法比较简单,这里就直接上函数了。重新建立一个单链表newList,每次将list中的第一个结点放到newList后面。注释比较详细,所以就不具体说了。
3 / 10 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: