以图明志

数据结构

[专题] 关于循环队列的一些讲解

循环队列的长度与队满情况
前面讲到了队列的“假溢出”,解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。比如昨天的例子,rear可以改为指向下标为0的位置,这样就不会造成指针指向不明的问题了。

数据结构

[专题] 队列顺序存储结构的不足

引入循环队列的概念
所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为0(1)。与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头(也就是下标为0的位置)不为空,此时的时间复杂度为0(n)。

数据结构

[专题] 顺序队列置空与判断操作

判断空队列
关于顺序队列,还有些ADT里的操作没有实现,今天实现下吧。比如置空顺序队列。置空顺序队列操作比较简单,只要让队头指针与队尾指针相等即可。判断队列是否为空,可以借鉴上面的函数。如果队头指针与队尾指针相等,那么队列就是为空。注意函数里传入的是实体对象,实体对象需要用实心点来指向成员,所以判断条件写成 Q.front==Q.rear。

数据结构

[专题] 顺序队列的出队操作

将队头指针向后移动一位即可
昨天我们谈论了顺序队列的入队操作,那么今天我们就看看如何出队吧。出队其实就是删除队列(线性表)的队头元素咯。貌似只要将队头指针向后移动一位就可以完成出队了 Q->front=(Q->front+1)%MAXSIZE; ,哦,在这之前需要用 e 来保存出队的元素。

数据结构

[专题] 顺序队列的入队操作

可以假想军训的时候理解
昨天我们定义了顺序队列的ADT,还写了顺序队列的初始化函数。那么现在我们马上来看队列的一个重要的基础操作:入队。想想,入队的算法应该怎么写?如何判断一个队列是否满的?假设我们在军训中排队,每个人报数。一个队列只能站10个人,从1报到10,队就满了。

数据结构

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

顺序队列的结构体定义和初始化
线性表分为顺序存储和链式存储,栈是线性表,所以也有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。我们先来看队列的顺序存储结构。要用程序来了解队列,先要定义队列的结构体。那么如何设计队列的结构体呢?我们一直都是用数组来实现顺序存储的,顺序队列也不例外。

数据结构

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

定义我们需要实现的队列的操作
因为队列同样是线性表,所以队列也有类似线性表的各种操作,不同的就是插入数据只能在队尾进行,删除数据只能在队头进行。简单来说,队列就是后面装入数据,前面取出数据。用途:保障时间的顺序,比如用户事务操作。链队列:链式存储的队列,长度没限制啊。顺序队列:顺序存储的队列。

数据结构

[专题] 开始学习队列这个数据结构

队列的基本认识
你在用电脑时有没有经历过这样的事?机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。

数据结构

[专题] 将中缀表达式转化为后缀表达式

也是使用栈这个数据结构
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

数据结构

[专题] 图解后缀表达式的计算过程

了解后缀表达式的工作原理
为了解释后缀表达式的好处,我们先来看看,计算机如何应用后缀表达式计算出最终的结果20的。后缀表达式:9 3 1-3*+ 10 2/+,规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

数据结构

[专题] 接触后缀表达式(逆波兰表示法)

逆波兰表示法的起因
栈的现实应用也很多,我们再来重点讲一个比较常见的应用:数学表达式的求值。20世纪50年代,波兰逻辑学家Jan tukasiewicz想到了一种不需要括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Notation, RPN)表示。这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

数据结构

鸟瞰数据结构的知识点全貌

扯扯数据结构的概念点
数据结构是算法的基石,算法是软件灵魂。数据结构的很多概念真的是很莫名其妙,很多坑爹的定义,笔者开始很搞不明白,为什么学数据结构?为什么用哪个拗口词语?这些概念到底用在什么地方?笔者试图用自己简单的话来阐述这些问题,希望能对这些感觉不是很好理解的同学有帮助。

数据结构

[专题] 栈是如何实现递归的

递归与栈一些不得不说的事
在高级语言中,调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。

数据结构

[专题] 递归,栈的重要应用之一

了解递归的一些细节
栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个 “化身”。一连串的“像中像” 这是一种递归现象。

数据结构

[专题] 为什么要使用栈这种数据结构

缩小思考范围,聚焦问题核心
栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题核心。反之,像数组等,因为要分散精力去考虑数组的下标增减等细节问题,反而掩盖了问题的本质。所以现在的许多高级语言,比如Java、C#等都有对栈结构的封装,你可以不用关注它的实现细节,就可以直接使用Stack的push和pop方法,非常方便。

数据结构

[专题] 链栈的置空操作与判断链栈是否为空

与单链表的置空操作相同
判断链栈是否为空很简单,还记得结构体定义时的那个 count 吗?如果那个 count 为0,就说明链栈为空。置空链栈就没有置空顺序栈那么简单了。置空顺序栈只要一步 S->top=-1; 即可,但是对于链栈却不是那么回事了。方法是设置两个工作结点,开始循环。在释放p之前,让q成为p的后继。还是那个比喻,在皇帝死之前,册封皇子。free(p); 皇帝死了,p=q; 皇子就成了新皇帝。
2 / 10 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: