一些基本操作

• 栈
  • 头文件 #include<stack>
  • 声明: stack<type> S
  • 入栈: S.push(value）
  • 出栈: S.pop()
  • 取栈顶: S.top()

括号匹配问题

解题思路

• 遇到"(“入栈，遇到”)"出栈，若空，则有问题。
• 字符串输入结束后，栈中的所有"("都有问题。

一些注意事项

• 栈中的基本类型可以为结构体，当结构体只有两个元素。可以使用pair
  • 声明： typedef pair<int ,int> def_type;
  • stack<def_type> S
  • def_type ob(1,2)
  • S.push(ob)
• puts(x) 和 scanf("%s" , x)效果一样。

#include <stdio.h>
#include <string.h>
int main(){
    char xx[20];
    // scanf("%s", xx);
    scanf("%s",xx);
    char ch;
    printf("string length is: %d\n", strlen(xx));
    printf("the last is %d\n", xx[strlen(xx)]);
    printf("11%d11", '\0');

}


 //输入
123142
--------------------------------
//输出
string length is: 6
the last is 0
11011

表达式求值问题

• 为什么使用栈的思想，因为后来的运算符若优先级更高，则会先算
• 如何简便，在开始和结尾都插入一个人为的最低等级的运算符
• gets读入包括空格的一行输入，并且扔掉缓冲区中的回车符
• 引用传递的理解。
• c字符串最后的默认为‘\0’,若装换为整数，则为0
• 使用双栈解此类问题

哈夫曼树

• 声明有限队列方法
  • #include<queue> using namespace std;
  • 小顶堆 priority_queue<int, vector<int>, greater<int> > Q;

二叉树

• 两种建树的方式，给前序和终序， 只给前序（含有#号）
• 使用一个数组，并且用create封装
• 真正的建树写在build中。
• 遍历时非空继续遍历，打印按顺序写
• 还有一个二分查找的例子。二分使用[0,num-1]

二叉排序树，二叉搜索树

• 树如何建立，使用插入方法建立。
• 如何判断两棵树是否一样，包括中序遍历在内的两种遍历方式一样即可。