1.5PTA集练6-1~6-4，7-3，7-4（6/26）

6-1 顺序表的删除 分数 10

List Delete( List &L, ElementType minD, ElementType maxD ){
    int k=0;
    for(int i=0;i<=L.last;i++){
        if(L.Data[i]<=maxD&&L.Data[i]>=minD){
            L.Data[k++]=L.Data[i];
        }
    }
    L.last=k;
    return L;
}

这个就是注意L需要是用.,而不是用->，不是用箭头，具体为什么，也不清楚

思路是，在原表上进行操作，然后如果满足条件，就加到新数组上，最后更新新数组的长度?

6-2 寻找链表元素的前驱结点 分数 10

ptr pre (ptr h,int x){
    if(!h)return nullptr;//为空，则直接返回
    node* pre=h,*cur=h->next;//不为空的话，则pre一定存在，cur可能一开始就不存在，cur表示要操作的结点，pre表示接收的结点，也可理解为操作完成的结点
    while(cur){//这个迭代条件，就意味着还能继续操作，为空时就是不能继续操作了
        if(cur->data==x){//此时就表示满足要求了，就不需要操作了，找到了，直接返回
            return pre;
        }else{//就是还没找到，继续找
            pre=cur;
            cur=cur->next;
        }//同时向后移动
    }
    return nullptr;//出了循环，就意味着没有可以继续操作的结点，就意味着没找到，就是说不存在，返回空指针
}

链表题的思路比较固定，就是一个指针指向要操作的结点（cur),通过判断语句判断当前结点是否满足要求或操作需求，另一个结点接收操作后的结果

6-3 求叶子结点个数 分数 50

using namespace std;
#include<iostream>
void creat(BiTree &Tree){//创建二叉树
    char t;
    cin>>t;
    if(t=='#'){
        Tree=nullptr;
    }else{
        //Tree =new BiTNode;
        Tree->data=t;
        creat(Tree->lchild);
        creat(Tree->rchild);
    }
}
int countleaf(BiTree Tree){//叶子结点计数
    if(!Tree)return 0;
    if(!Tree->rchild&&!Tree->lchild)return 1;
    return countleaf(Tree->lchild)+countleaf(Tree->rchild);
}

至于主体解体部分，这个思路是判断是不是叶子结点，是的话返回1，不是就返回左右孩子的叶子结点和

抽象起来就是，先判断空不空，空的话直接返回，再看操作条件，满足底层就返回，不然继续向下递归?

尤其需要注意建树的操作

首先，采用&，引用的话，虽然上面那个题是要用.，但这里依然是要用->,所以报错的话，都改改看

其次，建树，建立新节点，即使传进来是引用，也要new一个，在堆区里开一个空间来存储，不然会出问题，猜测原因是，如果不new,此时结点向下传，传入的是空指针，即自然也就没有它的左右孩子的说法，因为本身就是一个空指针，即相当于传入进去的时候就是一个空指针，不存在左右孩子的索引，只有new了一个后，才会存在左右孩子的索引

void型的话，就是要引用，

6-4 求二叉树高度 分数 40

#include<iostream>
using namespace std;

void creat(BiTree &Tree){//构建二叉树
    char t;
    cin>>t;
    if(t=='#'){
        Tree=nullptr;
    }else{
        Tree=new BiTNode;
        Tree->data=t;
        creat(Tree->lchild);
        creat(Tree->rchild);
    }
}
int Depth(BiTree Tree){//求高度
    if(!Tree)return 0;
    else if(!Tree->lchild&&!Tree->rchild)return 1;
    else return max(Depth(Tree->lchild),Depth(Tree->rchild))+1;
}

注意细节，就是函数题可能会没给#include<iostream>以及using……

还有就是引用的，在调用时不需要加&,只是在写函数定义的时候加

解题的主体思路还是，先判断是不是空，然后再判断是不是递归底层，接着再进行递归调用，进行一系列操作，依据递归方程、状态转移方程

7-3 字符串匹配问题(strs) 分数 100

从内到外必须是<,(,[,{,就是说{最大，必须在最外面

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int n;
string s;
int main(){
    cin>>n;
    while(n--){
        cin>>s;
        stack<int>st;
        bool flag=1;
        for(int i=0;i<s.length();i++){
            if(s[i]=='{'){
                if(!st.empty()&&st.top()>1){
                    flag=0;
                    break;
                }else{
                    st.push(1);
                }
            }
            if(s[i]=='['){
                if(!st.empty()&&st.top()>2){
                    flag=0;
                    break;
                }else{
                    st.push(2);
                }
            }
            if(s[i]=='('){
                if(!st.empty()&&st.top()>3){
                    flag=0;
                    break;
                }else{
                    st.push(3);
                }
            }
            if(s[i]=='<'){
                st.push(4);
            }
            if(s[i]=='>'){
                if(st.empty()||st.top()!=4){
                    flag=0;
                    break;
                }else{
                    st.pop();
                }
            }
            if(s[i]==')'){
                if(st.empty()||st.top()!=3){
                    flag=0;
                    break;
                }else{
                    st.pop();
                }
            }
            if(s[i]==']'){
                if(st.empty()||st.top()!=2){
                    flag=0;
                    break;
                }else{
                    st.pop();
                }
            }
            if(s[i]=='}'){
                if(st.empty()||st.top()!=1){
                    flag=0;
                    break;
                }else{
                    st.pop();
                }
            }
        }
        if(flag&&st.empty()){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

为左括号时入栈、为右括号时出栈?

由于大小的限制，在入栈时，判断栈顶元素是不是比自己大，不过需要注意，必要的是在取出栈顶元素时，首先要判断栈是不是空，只有不空时才能取出栈顶元素

在出栈时，判断栈空不空以及栈顶元素和自己匹不匹配

及入栈时判断能不能入栈，出栈时判断能不能出栈，就是这样

最后输出时，不用考虑哪些失败的情况，只需要考虑到正确的情形即可

此为建立映射，通过map

    char a[] = { '{','[','(','<','}',']',')','>' };
    int b[300], n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        stack<int>st;
        bool flag = true;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < 8; j++) {
                if (s[i] == a[j]) {
                    b[i] = j;
                    break;//就是把原来的括号字符串转换为B里的数字数组
                }
            }
        }
        for (int i = 0; i < s.size(); i++) {
            if (b[i] <= 3) {
                if (!st.empty() && b[i] < st.top()) {//用数字代表括号的优先次序，那么能不能继续插入，就是看堆顶的元素的编号和此时自己的关系
                    flag = false;//也就是必须要保证一个递增的顺序，不然就不能继续插入
                    break;
                }
                else {
                    st.push(b[i]);
                }//正常插入
            }
            else if (b[i] >= 4) {
                if (st.empty() || (st.top() + 4) != b[i]) {
                    flag = false;
                    break;
                }
                else {
                    st.pop();//正常的匹配，删除
                }
            }
        }
        if (!st.empty())cout << "no" << endl;
        else if (flag)cout << "yes" << endl;
        else cout << "no" << endl;
    }

7-4 后缀表达式求值 分数 20

首先注意string输入，如果输入的string里有空格，就会被提前终止

直接cin的string只适用于输入的字符串里不含空格的情况，如果含空格，就只能用getline函数来获取getline(cin,s)

接着就是对输入的字符串做处理

首先是数字，

先判断第一个是不是数字，如果是的话，那就while，尝试获取联通的所有数字，即为一整个数字，注意在while的时候，要注意j++

还需要注意的是，当前输入的是不是负数，就是看第一个数字前面的字符，是不是符号，还要注意，在进行这一判断的时候，首先要保证前面是有字符的，即i>0,不然就会越界；依据前面的字符情况加入这个获取到的数字的正数或负数，并且入栈，让栈内元素数量cnt++,并且跳跃i到j的位置，此时跳跃到的位置就刚好不是数字的位置，是第一个脱离此不是数字的位置

但还需要注意，这样直接处理并不大好，就是直接设为第一个位置，因为这里处理完后，后面还要进行i++,这里之所以不会出问题是因为后面跟着的都是空格，空格不参与运算，不然的话，这个第一个不是数字，即第一个不会被处理的位置，在这个i循环结束后，就会被i++,跳过掉，就失去了情况，所以还是要注意一下

对于while迭代处理的理解?

无论是在链表中还是在这里，while在做迭代循环处理时，思路最清晰的理解方式就是，还能不能继续操作，即继续迭代的条件，在这里的话，j表示当前要尝试继续处理的字符，如果满足while，就表示还能继续处理，否则就是不能继续处理

然后用i去接收，num去接收

在这里的话，就是如果满足s[j]>="0"&&s[j]<="9",就表示还能继续处理，即当前的位数上还是数字，如果不满足的话，就是j上的就不是数字，就停止继续处理，并保存当前的位数不动，即此时的while结束后，条件上保存的是第一个不满足迭代条件的数

中间的处理，就是遇到空格，或者数字前面的负号（这个负号就表示不是运算符，而是负号），就先跳过?

接下来就是进行运算符的操作与处理，接一个else，表示接下来处理的都是运算符，而且需要注意，也正是因为这个else，所以在for循环的终止条件里，要写的是而不是i<s.length()

因为如果是后者，==“#”的情况被包含在else里，即会被认为是运算符，所以就导致如果此时cnt<2,就会错误输出Expression Error: ，而#恰好是最后的终止符，所以最后的时候，正确时，cnt应该刚好=1，所以此时正确的输出就一定会被打成错误的

也就是说，这个for的写法其实就是把#排除在外，实际上也就等价于i<s[i].length()-1;

然后cnt是对栈内数量的统计，如果小于2，就是错误条件，就可以提前退出，而且如果此时不退出，一定会报错，因为此时栈内根本就没有两个以上的数字来支持运算符的操作?

只不过这里存在问题的一个点是，cnt<2,可以存在两种情况，即cnt=0=1两种，这里只是考虑=1的情况，而=0的情况就没有考虑，即字符串的第一个元素必定不是运算符?

而且这样可能也满足题目要求，因为是说在cnt<2时，要输出此时栈顶元素，如果=0，那就说明根本没有栈顶元素，就自相矛盾了

?

紧接着在处理运算符时，需要注意的是减法与除法，要考虑顺序问题，即被除数要找对，还有就是除法要额外考虑到除0的问题?

还有就是后缀表达式不需要考虑次序问题，就没有操作符的优先级，遇到就运算，没有先加减后乘除

最后就是处理完了，处理完了的话，栈里应该刚好只有一个元素，如果不是1，都是错误

这里不是1的话，只能是栈内元素多的情况，即数字多而运算符少

如果运算符多而数字少，会在处理字符串时就会处理掉，提前返回

此时到了这里就是字符串处理完了，但栈内可能还有很多数字