王道机试指南数据结构二

发表于 2021-01-27 更新于 2021-02-04 分类于考研复试

例题10.1二叉树遍历（清华大学上机）

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
struct node{//定义结点
    char data;
    node* lchild;
    node* rchild;
    node(char(c)) : data(c), lchild(NULL), rchild(NULL){}//可以简化写法
};
node* create(int& pos, string str){//创建一课树
    char c = str[pos++];
    if(c == '#') return NULL;
    node* root = new node(c);//创建一个新的结点
    root->lchild = create(pos, str);//创建左子树 
    root->rchild = create(pos, str);//创建右子树 
    return root;//递归回溯之后，返回根一定是最开始 定义的第一个根节点 
}
void inorder(node* root){//都是通过根节点进行第一个访问 
    if(root == NULL) return;
    inorder(root->lchild);
    cout << root->data << " ";
    inorder(root->rchild);
}
int main(){
    string s;
    while(cin >> s){
        int pos = 0;
        node* root = create(pos, s);//定义一个node类型的名字叫root的指针 
        inorder(root);//进行中序遍历 
        cout << endl;
    }
    return 0;
}

例题10.2二叉树的遍历（华中科技大学上机）

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
char pre[28], in[28];
void post(int root, int start, int end){//root为前序中当前根节点的下标
    if(start > end) return;//表示递归出口 
    int i = start;//i表示当前的根在中序的位置，从start开始找 
    while(i < end && in[i] != pre[root]) i++;//找到先序的根在中序遍历的位置
    post(root + 1, start, i - 1);//相当于从前序中依次遍历
    post(root + 1 + i - start, i + 1, end);
    cout << pre[root];
}
int main(){
    string pres, ins;
    int n;
    while(cin >> pres >> ins){
        n = pres.size();//n为用例的长度 
        for(int i = 0; i < n; i++) pre[i] = pres[i];//将字符转换为char类型的数组来存储 
        for(int i = 0; i < n; i++) in[i] = ins[i];
        post(0, 0, n - 1); //end为下标，所以应该从n - 1开始 
        cout << endl; 
    }
    return 0;
}

例题10.3二叉排序树（华中科技大学上机）

 #include<iostream>
#include<cstdio>
using namespace std;
struct TreeNode{
    int data;
    TreeNode *lchild;
    TreeNode *rchild; 
    TreeNode(int x) : data(x), lchild(NULL), rchild(NULL){}
};
void insert(TreeNode* &root, int x, int pre){
    if(root == NULL){
        root = new TreeNode(x);//返回的是上一层的root->child 
        cout << pre << endl;
        return;
    }else if(x < root->data){
        insert(root->lchild, x, root->data);
    }else insert(root->rchild, x, root->data);
}
int main(){
    int n, x;
    while(cin >> n){
        TreeNode *root = NULL;
        for(int i = 0; i < n; i++){
            cin >> x;
            insert(root, x, -1);
        }
    }
    return 0;
}

例题10.4 二叉排序树（华中科技上机）

#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
map<int, int> flag;
struct node{
    int data;
    node* lchild;
    node* rchild;
    node(int x) : data(x), lchild(NULL), rchild(NULL){}
};
void create(node* &root, int x){
    if(root == NULL){
        root = new node(x);
        return;
    }
    if(x < root->data) create(root->lchild, x);
    else create(root->rchild, x);
}
void preorder(node* root){
    if(root == NULL) return;
    cout << root->data << " ";
    preorder(root->lchild);
    preorder(root->rchild);
}
void inorder(node* root){
    if(root == NULL) return;
    inorder(root->lchild);
    cout << root->data << " ";
    inorder(root->rchild);
}
void postorder(node* root){
    if(root == NULL) return;
    postorder(root->lchild);
    postorder(root->rchild);
    cout << root->data << " ";
}
int main(){
    int n, x;
    while(cin >> n){
        node* root = NULL;
        for(int i = 0; i < n ;i++){
            cin >> x;
            if(flag[x] != 1){
                flag[x] = 1;
                create(root, x);
            } 
        }
        flag.clear();
        preorder(root);
        cout << endl;
        flag.clear();
        inorder(root);
        cout << endl;
        flag.clear();
        postorder(root);
        cout << endl;
    }
    return 0;
}

习题10.1二叉搜索树（浙江大学复试上机）

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
vector<int> pre, in, pretest, intest;
struct node{//定义树的结点
    int data;
    node* lchild;
    node* rchild;
    node(int x) : data(x), lchild(NULL), rchild(NULL){}
};
void insert(node* &root, int x){//用插入法创建一棵树
    if(root == NULL){
        root = new node(x);
        return;
    }
    if(x > root->data) insert(root->rchild, x);
    else insert(root->lchild, x);
}
void preorder(node* root, vector<int> &a){//先序遍历的序列输入到容器a，注意容器用引用 
    if(root == NULL) return;
    a.push_back(root->data);
    preorder(root->lchild, a);
    preorder(root->rchild, a);
}
void inorder(node* root, vector<int> &a){//中序遍历的序列输入到容器a
    if(root == NULL) return;
    inorder(root->lchild, a);
    a.push_back(root->data);
    inorder(root->rchild, a);
}
bool judge(vector<int> a, vector<int> b){//判断容器内元素是否相同
    for(int i = 0; i < a.size(); i++){
        if(a[i] != b[i]) return false;
    }
    return true;
}
int main(){
    int n;
    string str;
    while(cin >> n && n != 0){//注意这种输入的方法
        cin >> str;
        node* root = NULL;
        for(int i = 0; i < str.size(); i++){
            insert(root, str[i] - '0');
        }
        preorder(root, pre);//进行前序遍历，将结果存入
        inorder(root, in);//进行中序遍历，将结果存入
        for(int i = 0; i < n; i++){//进行n次的循环 
            pretest.clear();//将用于存前序序列的容器清空
            intest.clear();//将用于存中序序列的容器清空
            string temp;//设置一个临时temp，用来接收输入的字符串
            cin >> temp;
            node* roottest = NULL;//定义一个空树
            for(int j = 0; j < temp.size(); j++){//字符串变成整型，插入法建树
                insert(roottest, temp[j] - '0');
            }
            preorder(roottest, pretest);//前序遍历结果存入pretest 
            inorder(roottest, intest);//中序遍历结果存入intest 
            if(judge(pre, pretest) && judge(in, intest)) cout <<"YES"<<endl;//判断并且输出
            else cout << "NO" << endl;
        }
    }
    return 0;
}

例题10.5 复数集合（北京邮电大学）

#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct complex{
    int real, imag;
    complex(int a, int b) : real(a), imag(b){}
    friend bool operator < (complex c1, complex c2){
        if(c1.imag*c1.imag + c1.real*c1.real== c2.imag*c2.imag + c2.real*c2.real){
            return c1.real < c2.real;
        }else{
            return c1.imag*c1.imag + c1.real*c1.real < c2.imag*c2.imag + c2.real*c2.real;
        }
    }
};
int main(){
    int n;
    string str;
    while(cin >> n){
        priority_queue<complex> q;
        for(int i = 0; i < n; i++){
            cin >> str;
            if(str == "Pop"){
                if(!q.empty()){
                    cout << q.top().real <<"+i" << q.top().imag << endl;
                    q.pop();
                    cout << "SIZE = " << q.size() << endl; 
                }else cout << "empty" << endl;
            }else if(str == "Insert"){
                int ta, tb;
                scanf("%d+i%d", &ta, &tb);
                q.push(complex(ta, tb));
                cout << "SIZE = " << q.size() << endl;
            } 
        }   
    }
    return 0;
}

例题10.6 哈夫曼树（北京邮电大学）

#include<iostream>
#include<queue>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        priority_queue<int, vector<int>, greater<int> > q;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int temp;
            cin >> temp;
            q.push(temp);
        }
        while(q.size() > 1){
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            q.push(x + y);
            ans += x + y;
        }
        cout << ans << endl;
    }
    return 0;
}

习题10.2 查找第K小的数（北京邮电大学上机）

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
int main(){
    int n, k;
    while(cin >> n){
        map<int, int> flag;
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < n; i++){
            int temp; 
            cin >> temp;
            if(flag[temp] != 1){
                flag[temp] = 1;
                q.push(temp);
            }
        }
        cin >> k;
        for(int i = 0 ; i < k - 1; i++){
            q.pop();
        }
        cout << q.top() << endl;
    }
}

习题10.3 搬水果（吉林大学上机）

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
int main(){
    int n, k;
    while(cin >> n){
        map<int, int> flag;
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < n; i++){
            int temp; 
            cin >> temp;
            if(flag[temp] != 1){
                flag[temp] = 1;
                q.push(temp);
            }
        }
        cin >> k;
        for(int i = 0 ; i < k - 1; i++){
            q.pop();
        }
        cout << q.top() << endl;
    }
}

例题10.7查找学生信息

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
struct inf{
    string name, sex;
    int age;
};
int main(){
    int n, m;
    map<string, inf> mp;//建立学号和信息之间的映射
    cin >> n;
    for(int  i = 0; i < n; i++){
        string num, name, sex;
        int age;
        cin >> num >> name >> sex >> age;
        mp[num].name = name;
        mp[num].sex = sex;
        mp[num].age = age;
    }
    cin >> m;
     while(m > 0){
         m--;
         string tempnum;
         cin >> tempnum;
         if(mp[tempnum].name == "") cout << "No Answer!" << endl;
         else cout << tempnum << " " << mp[tempnum].name << " " << mp[tempnum].sex << " " << mp[tempnum].age << " "<< endl;
     }
    return 0;
}

例题10.8 魔咒词典（浙江大学）

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    string s, s1, s2;
    map<string, string> mp0;
    map<string, string> mp1;
    while(getline(cin, s) && s != "@END@"){
        auto it = s.find(']');
        s1 = s.substr(0, it+1);
        s2 = s.substr(it + 2, s.size() - s1.size() - 1);
        mp0[s1] = s2;
        mp1[s2] = s1;
    }
    int n;
    cin >> n;
    getchar();
    for(int i = 0; i < n; i++){
        string temp;
        getline(cin, temp); 
        if(mp0[temp] != "") cout << mp0[temp] << endl;
        else if(mp1[temp] != ""){//去掉 【  】
            string s00;
            s00 = mp1[temp].substr(1, mp1[temp].size() - 2);
            cout << s00 << endl;
        }
        else cout << "what?" << endl;
    }
    return 0;
}

例题10.9子串计算（北京大学复试上机）

注意这里面如何截取一个字符串的所有子串

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
int main(){
    string str;
    while(cin >> str){
        map<string, int> mp;
        for(int i = 0; i <= str.size(); i++){
            for(int j = 0; j < i; j++){
                string s = str.substr(j, i - j);
                mp[s]++;
            }
        }
        for(auto it = mp.begin(); it != mp.end(); it++){
            if(it->second > 1) cout << it->first << " " << it->second << endl;
        }
    }
    return 0;
}

习题10.4 统计同成绩的学生（浙江大学上机）

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int main(){
    int n;
    while(cin >> n && n != 0){
        map<int, int> mp;
        for(int i = 0; i < n; i++){
            int temp;
            cin >> temp;
            mp[temp]++;
        }
        int testnum;
        cin >> testnum;
        cout << mp[testnum] << endl;
    }
}

习题10.5 开门人和关门人

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int toSecond(int hour, int min, int sec){
    return hour * 3600 + min * 60 + sec;
}
int main(){
    int n, opentime = 24*3600, closetime = 0;
    string tempnum, opennum, closenum;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> tempnum;
        int hour, min, sec;
        scanf("%d:%d:%d", &hour, &min, &sec);
        if(toSecond(hour, min, sec) < opentime){
            opennum = tempnum;
            opentime = toSecond(hour, min, sec);
        }
        scanf("%d:%d:%d", &hour, &min, &sec);
        if( toSecond(hour, min, sec) > closetime){
            closenum = tempnum;
            closetime = toSecond(hour, min, sec);
        }
    }
    cout << opennum << " " << closenum << endl;
    return 0;
}

习题10.6 谁是你潜在的朋友（北京大学复试上机）

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    map<int, int> book;//用于记录i号书的读者数
    int reader[201];
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        book[temp]++;
        reader[i] = temp;
    }
    for(int i = 0; i < n; i++){
        if(book[reader[i]] > 1) cout << book[reader[i]] - 1 << endl;
        else cout << "BeiJu" << endl;
    }
}