算法与数据结构 --- 栈的表示和操作的实现

第一部分 --- 栈的表示和操作的实现（1，2）

 

1.销毁栈是直接将存储栈的内存空间释放掉，栈将不存在；而清空栈则是将栈中的元素都删除掉，栈依然存在（对于顺序表而言删除元素不会改变其内存空间，对于链表而言由于是动态存储删除元素所以会改变内存空间，但由于头结点的存在，所以栈依然存在）

top指针指向的是最后一个元素之后

 

 （两个相同类型的指针相减得到的是这两个指针之间的按照它们的步长划分出的内存空间的个数）注意这个栈满标志只有在顺序表中成立（也只有顺序表会出现栈满的清空，链表是动态存储，所以不会出现栈满的情况）

 1.出现上溢的时候是压栈错误，出现下溢的时候则表示出栈结束

---

第二部分 --- 栈的表示和操作的实现（3，4）

1.staticsize：栈可用的最大容量，其实就是栈中最多可存储的元素个数

 

1.在堆区中创建一个数组，然后将new后的地址传给用引用的方式传入的栈的base指针，

2.接着判断指针是否为空，若为空的话则堆区中数组创建失败，返回栈溢出错误

3.若创建成功，则让传进来的栈的top指针等于base指针，并让栈的staticsize等于MAXSIZE

 

1.top指针和base指针的差就等于从栈顶到栈底的栈中的元素个数

1.令top指针等于base指针就能跟实现栈的清空了（原来的值在插入新值后会被直接覆盖掉）

1.base指针接收着new后的地址，管理着在堆区中创建的数组，如果要销毁栈的话就相当于销毁掉数组，此时用 delete + 指针的方式销毁

2.销毁后栈的容量置为0，top指针和base指针都置为空指针（NULL）

 1.入栈算法最关键的两步：1.将入栈的数据插入到top指针指向的位置；2.将top指针上移

（注意！！能够入栈的前提是栈没有满，如果栈满了还要入栈的话就需要我们进行报错提醒）

2.先判断栈是否满（top - base == staticsize )，如果栈满了报错，如果没满的话就正常压栈

---

第三部分 --- 栈的表示和操作的实现（5，6）

1.判断栈是否为空（top == base），若为空的话报错（下溢问题），若不为空的话正常出栈

2.出栈时先让top指针 -- ，然后将top指针解引用并将解引用的值赋值给存储数据的变量，此时出栈完毕（原来的数据会在压栈的时候被直接覆盖掉）

（下面这一部分讲的是栈的链式表示和实现）

1.链栈的头指针指向的就是栈顶

2.对于链栈而言，只有内存空间全被占完时才会出现栈满的情况

3.当头指针为空指针的时候，链栈为空栈

1.创建空栈的步骤：在函数外创建一个头指针（指针类型是链栈类型），然后将头指针以引用的方式传到算法中，并在算法中给这个头指针赋值NULL使其成为空指针，这样我们就创建好一个空链栈了

1.当链栈的头指针为空指针的时候，链栈为空栈

1.链栈也是一个单链表，所以链栈的栈名就等于头指针的指针名

1.第一步判断链栈是否为空，若为空，出栈失败返回错误（下溢问题），若不为空则将出栈的数据存储到通过引用传入的变量中

2.第二步创建一个指针P来存储出栈结点的地址，使得这个指针P指向被删除结点

3.第三步：让头指针指向新的栈顶

4.第四步：将出栈结点的内存空间释放掉 --- 通过我们之前创建的保存了被删除结点地址的指针P + delete来进行释放

---

第四部分 --- 栈和递归

 

 

若要求第一个就要调用函数求第二个，若要求第二个就要调用函数求第三个....这样不停的递归下去直到到达递归终点就是一个完整的递归过程。

 

 

1.用递归解决问题的本质是：分治法

2.下面那个必备的三个条件指的是使用递归所必须的三个条件

递归：将一个问题不停的转化为更为简单的且解法相同或类似的子问题，当这个子问题得解时（递归终点）原问题就得解了。

1.满足递归临界条件后执行的语句是基本项，没满足递归临界条件执行的语句是归纳项

 

函数的嵌套调用满足栈的数据结构：先调用的函数先入栈，后调用的函数先出栈

 

1.ri（i = 1,2,3,4....）是返回地址

2.如果递归函数中有实参，返回地址和局部变量的话，那么我们的递归工作栈中就要存储对应的数据（如果没有的话就不需要存储），上面这个fact递归函数只有实参和返回地址，所以我们只要存储这两个就可以了

1.递归程序易读，简洁，但是由于每一次调用递归函数都需要将函数的工作信息入栈（递归工作栈），调用完后还要将工作信息出栈，整个递归流程需要的时间开销大

2.如果我们想减少时间开销的话就需要将递归程序改为非递归程序

第一种尾递归转换为循环：其实就是将原来的递归语句改为等价的循环程序

（当递归语句的调用是整个函数体中最后执行的语句，且只有一个递归调用语句的时候与就是尾递归）

第二种是单向递归变为循环

1.Fib(n-1)是一次递归调用语句，Fib(n - 2)又是一次递归调用语句

2.单向递归：1.有一个以上的递归语句；2.所有递归语句都是在算法的最后执行的；3.所有递归语句之间没有参数关系，它们的参数只和主函数有关