1.5PTA集练6-1~6-4,7-3,7-4(6/26)

发布时间:2024年01月08日

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的话,只能是栈内元素多的情况,即数字多而运算符少

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

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

文章来源:https://blog.csdn.net/m0_73553411/article/details/135419233
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。