|
发表于 2014-12-6 03:34:52
|
显示全部楼层
看了上面的解释,几乎都有错误,尤其是对堆的解释。
而堆和栈是两个不同的东西,任何时候把它们放在一起都感觉怪怪的…………
数据结构中的堆和栈:
堆定义:
n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。
情形1:ki <= k2i 且ki <= k2i+1 (最小化堆或小顶堆)
情形2:ki >= k2i 且ki >= k2i+1 (最大化堆或大顶堆)
其中i=1,2,…,n/2向下取整;
堆可以理解为一个特殊的完全二叉树(但完全二叉树的定义跟堆没关系,只是用树描述比较形象),即有这样一个完全二叉树,树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。
栈定义:
定义:限定仅在表头进行插入和删除操作的线性链表。
一般而言,栈所使用的是单链表,即每个节点只有一个链,用来指向下一个节点(区别于双向链表)。操作时用一个指针指向这个链表的第一个节点,压栈(插入)时将新节点的链(也是指针)指向第一个节点,然后将原来指向第一个节点的指针指向新节点;出栈(删除)时,用一个新指针指向第一个节点,同时访问第一个节点的链并将原来的指针替换为链值(即指向了第二个节点)
堆和栈这两种数据结构最大的意义在于区别于数组这种连续结构,使之可以灵活分配空间,被广泛应用于动态内存分配中。
栈内存一般用来存放局部变量和函数调用地址,以按表达式的顺序操作变量或者使被调用的函数能根据该地址返回到原函数里。 |
|