栈

)

顺序栈

top指针指栈顶元素再往后一个位置（只操作该指针）

• 为嘛？方便操作！

base指针指栈底（不操作该指针）

一些重要操作

• base==top此时栈空
• stacksize==top-base（栈有多少个元素）
• 这里涉及到了指针运算。指向同一数组的两个指针可以做算术运算(两指针相加相减等），此时相减就是差多少个元素（实际上是下标运算）不是指向同一数组的两个指针，不可做算术运算

上溢

• 栈满了你还往里头搁
• 要发生上溢，就报错，提醒栈要上溢了

下溢

• 栈空了你还要删元素
• 这个不报错，作为结束条件，即问题处理结束

结构

• base指针（栈底指针）S.base
• top指针（栈顶指针，注意这个指向栈数组最后一个元素的下一个元素）S.top
• 存放大小的int型变量S.stacksize

算法

• 初始化

  • 给栈底指针base new一个内存
  • 如果new不出来就异常处理，exit掉
  • 让top指针被base指针赋值，这也表明此时栈空
  • stacksize（栈的大小变量）赋值成MAXSIZE，表明栈可以存MAXSIZE个元素
  • 初始化完毕返回OK
  • 参数&S

• 栈空

  • 利用重要操作，如果top指针==base指针，返回true，否则返回false
  • 参数&S

• 求栈的长度

  • 利用重要操作，栈顶指针-栈底指针就是栈长
  • 参数&S

• 清空顺序栈

  • 如果栈底指针有，也就是栈存在的话，让栈底指针赋值给栈顶指针，把栈顶指针拉下来跟栈底指针在一起，这不就是栈空的条件了吗？
  • 返回OK
  • 不用管栈里的元素，爱是什么是什么。你当初创建（初始化）栈的时候，你知道顺序栈里面各下标对应的元素是什么吗？随机数!
  • 参数&S

• 销毁栈

• 清空栈和销毁栈的区别和注意

  • 销毁栈，栈的个数设置为0，因为你内存中不再分配一块空间给栈了，而清空不一样，
  • 清空栈，栈的空间还是有的，你还可以存最多stacksize个元素。
  • 销毁栈的delete语句还是需要有的，因为你要把这块空间销毁掉扔进内存池里。
  • 同时销毁后别让base指针和top指针成为野指针

• 入栈

  • 思路：先判栈满，栈没满，栈顶指针指的位置添元素，然后栈顶指针往后（或说往上）走

  • 判断栈是不是满的，即top指针-base指针等不等于stacksize，是，返回错误，不是，继续执行入栈操作

  • *S.top++=e;可拆分为

    • *S.top=e;
    • S.top++;

  • 返回OK，自己脑子里过一遍入栈过程即可明白

  • 参数&S,e

• 出栈

  • 思路：判栈空，栈没空，栈顶指针往下走一格，然后获取栈顶指针指向的数据元素，然后OK

  • 如果top指针==base指针，证明栈空，返回错误，否则继续执行出栈操作

  • *- -S.top=e;可拆分为

    • - -S.top;
    • *e=S.top;别写反了。。。

  • 返回OK，脑子里过一遍这个出栈过程就能明白

  • 参数&S，&e

链栈

结点结构

• 数据域
• next域
• 结构体定义结点和链表（链栈）

表示：

• 头指针指向最后一个元素，即栈顶元素，链栈本是链表，只不过是反向链表，头指针指向末尾元素，然后存放顺序是an—a1反着来的。所以注意链栈中指针的方向和链表是反着的！！！这也符合栈的定义
• 头指针即为栈顶，头指针名即为栈名
• 不需要头结点
• 不会栈满
• 空栈，即为头指针指向空
• 增删操作只能在栈顶处执行

算法

• 初始化

  • 令栈顶指针（头指针）S指向空
  • 返回OK
  • 参数&S

• 判断栈空

  • 如果栈顶指针指向空，证明栈空，返回true，否则栈非空，返回false
  • 参数&S

• 入栈

  • 思路：生成一个新结点p，然后填充p的数据域，然让新结点next域指向栈顶指针S（入栈只能栈顶入），然后p再赋值给S让S指向新结点
  • new一个栈结点，赋值给指针p
  • p->data=e;
  • p->next=S;因为链栈的链表方向是反向的，和普通链表方向相反，也符合栈的定义，且顺应顺序栈的操作
  • S=p;
  • 返回OK
  • 因为只能在栈顶入栈，所以没有循环，操作很简单，自己脑子里走遍过程，就能明白
  • 参数&S，&e

• 出栈

  • 思路：首要判断栈空不空，栈空返回错误，栈不空，执行出栈操作。先让e取出栈顶指针（头指针）S指向的栈结点的数据域，然后定义一个p指针指向S指向的栈结点，栈顶指针S往下走一个，然后删除p结点，完事
  • 如果栈空，返回错误，栈不空，执行出栈操作
  • e=S->data;
  • p=S;
  • S=S->next;因为链栈链表方向和普通链表方向相反
  • delete p;
  • 返回ok
  • 参数&S，&e

• 取栈顶元素

  • 如果栈空，返回错误，栈不空，直接return S->data;别再多写一个形参e并传入e了没必要！
  • 注意判断栈空的时候写if(S!=NULL)可以省else，省去工作量。
  • 参数&S

递归

定义

• 对象部分包含自己
• 或者自己给自己定义，则称该对象是递归的
• 如果过程（或函数）直接或间接地调用自己，称该过程是递归的过程，该函数称为递归函数

分治法求解递归算法的一般形式

函数调用过程

• 调用前，系统完成

  • 让主调函数把实参，和返回地址传给被调用函数
  • 给函数的局部变量分配内存
  • 程序步步执行该函数

• 调用后，系统完成

  • 把计算结果通过返回地址返回给主调函数
  • 函数的局部变量都被释放（释放被调函数的数据区）
  • 依照传给被调函数的返回地址让程序继续步步执行主调函数

• 上面这两个系统的操作叫做记录现场

• 可以和单片机的中断系统对比着来理解

举例：求解阶乘n！的过程 （实参和返回地址均存在系统栈里）

递归函数调用的实现

• 层次：主函数第0层，第一次发生调用的函数为第一层，以此类推，第i次发生调用的函数为第i层

• 递归工作栈

  • 递归程序运行期间使用的数据存储区

• 工作记录

  • 实参，局部变量，返回地址

• 举例：根据上面的举例，进行fact(4)调用系统栈的变化状态
  

优点与缺点

• 优点：结构清晰，程序易读
• 缺点：耗费时间多，让程序运行变慢

单项递归

• 虽然有好几处递归，但各次递归调用语句的参数和只和主函数有关，几处递归调用的参数相互之间没有关系，并且这几处递归调用语句处于算法最后。