机试-数据结构

王道机试
算法
发布日期:   2018-07-15
文章字数:   2k

一.栈的应用

堆栈是一种数据项按序排列的数据结构，使用 stack 标准模版需要加上头文件 #include ，并使用标准命名空间。

  • 用 stack S，定义一个保存元素类型为int的堆栈 S
  • S.push(i) 向堆栈中压进一个数值为 i 的元素
  • int x = S.top()，读取栈顶元素
  • S.pop() 弹出栈顶元素
  • 例3.1 括号匹配

我们按照从左到右顺序遍历字符串，将所有遇到的左括号放入堆栈中等待匹配。

#include<stdio.h>
#include<stack>
using namespace std;
stack <int> S;
char str[110];
char ans[110];
int main(){
    while(scanf("%s", str) != EOF){
        int i;
        for (i=0;str[i] != 0;i++){
            if (str[i] == '('){
                S.push(i);
                ans[i] = ' ';
            }

            else if (str[i] == ')'){
                if (S.empty())
                    ans[i] = '?';
                else{
                    S.pop();
                    ans[i] = ' ';
                }
            }
            else
                ans[i] = ' ';
        }
        while(!S.empty()){
            ans[S.top()] = '$';
            S.pop();
        }
        ans[i] = 0;
        puts(str);
        puts(ans);
    }
    return 0;
}
  • 例3.2 简单计算器：读入一个只包含 +，-，*，/ 的非负整数计算表达式，计算该表达式的值。

设置两个堆栈，一个用来保存运算符，一个用来保存数字，在表达式的首尾添加标记运算符，该运算符优先级最低。

从左到右依次遍历字符串，若遍历到运算符则将其与运算符栈栈顶元素进行比较，若运算符栈栈顶运算符优先级小于该运算符或者此时运算符栈为空，将该运算符栈压入堆栈，遍历下一个元素。

若运算符栈栈顶元素优先级大于该元素，则弹出该栈顶运算符，再从数字栈中依次弹出两个栈顶数字，完成运算后再将结果压入数字栈，重复比较此时栈顶运算符与当前遍历到的运算符的优先级，然后重复上述步骤。

若遍历到数字，直接压入数字栈。

若运算符堆栈中仅存有两个运算符且栈顶元素为标记运算符，那么表达式运算结束，此时数字栈中唯一的数字即为表达式的值。

#include<stack>
#include<stdio.h>
using namespace std;
char str[220];
int mat[][5] = {
    1, 0, 0, 0, 0,
    1, 0, 0, 0, 0,
    1, 0, 0, 0, 0,
    1, 1, 1, 0, 0,
    1, 1, 1, 0, 0,
};

stack <int> op;
stack <double> in;

void getOp(bool &retOp, int &retNum, int &i){
    // 获得表达式下一个元素，若 retOp 为 true, 则 retNum 为其编号，若 retOp 为 false, 则 retNum 为数值
    if (i==0 && op.empty() == true){
        retOp = true;
        retNum = 0;
        return;
    }
    if (str[i] == 0){
        retOp = true;
        retNum = 0;
        return;
    }
    if (str[i] >= '0' && str[i] <= '9'){
        retOp = false;
        // retNum = str[i] - '0';
    }
    else{
        retOp = true;
        if (str[i] == '+'){
            retNum = 1;
        }
        else if (str[i] == '-'){
            retNum = 2;
        }
        else if (str[i] == '*'){
            retNum = 3;
        }
        else if (str[i] == '/'){
            retNum = 4;
        }
        i += 2;
        return;
    }
    retNum = 0;
    for (;str[i] != ' ' && str[i] != 0;i++){
        retNum *= 10;
        retNum += str[i] - '0';
    }
    if (str[i] == ' ')
        i++;
    return;
}

int  main(){
    while (gets(str)){  // 输入字符串， 当其位于文件尾时，gets 返回 0
        if (str[0] == '0' && str[1] == 0 )
            break;
        bool retOp;
        int retNum;
        int idx = 0;
        // 清空栈
        while (!op.empty())
            op.pop();
        while (!in.empty())
            in.pop();

        while (true){
            getOp(retOp, retNum, idx);
            if (retOp == false){
                in.push((double) retNum);
            }
            else{
                double tmp;
                if (op.empty() == true || mat[retNum][op.top()] == 1){
                    op.push(retNum);
                }
                else{
                    while (mat[retNum][op.top()] == 0){
                        int ret = op.top();
                        op.pop();
                        double b = in.top();
                        in.pop();
                        double a = in.top();
                        in.pop();
                        if (ret == 1)
                            tmp = a + b;
                        if (ret == 2)
                            tmp = a - b;
                        if (ret == 3)
                            tmp = a * b;
                        if (ret == 4)
                            tmp = a / b;
                        in.push(tmp);
                    }
                    op.push(retNum);
                }
            }
            if (op.size() == 2 && op.top() == 0)
                break;

        }
        printf("%.2f\n", in.top());
    } 
    return 0;

}

哈夫曼树

哈夫曼树求法：将所有结点放入集合 K，若集合 K 中剩余结点大于2个，则取出其中权值最小的两个结点，构造他们同时为某个新结点的左右子节点，设定它的权值为其两个儿子结点的权值和，并将其放入集合 K，若集合K中仅剩余一个结点，该结点就是哈夫曼树的根结点。

我们可以使用优先队列——小顶堆：priority_queue<int, vector, greater> Q，需要在前面包含 的头文件

  • 例3.3 哈夫曼树
#include <queue>
#include <stdio.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > Q;
int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        while (Q.empty() == false)
            Q.pop();
        for (int i=1;i<=n;i++){
            int x;
            scanf("%d", &x);
            Q.push(x);
        }
        int ans = 0;
        while (Q.size() > 1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans += a+b;
            Q.push(a+b);
            // printf("%d\n", ans);
        }
        printf("%d\n", ans);
    }
    return 0;
}

二叉树

用递归方式编写二叉树遍历，二叉树结点用以下结构体表示：

struct Node{
    Node *lchild;    //指向左儿子结点的指针
    Node *rchild;
}

中序遍历：

void inOrder(Node *Tree){
    if (Tree->lchild!=NULL)
        inOrder(Tree->lchild);
    /*
    *
    对当前结点的操作*/
    if (Tree->rchild!=NULL)
        inOrder(Tree-rchild);
    return;
}
  • 例3.4 二叉树遍历：给定前序遍历和中序遍历，求后序遍历
#include<stdio.h>
#include<string.h>
struct Node{
    Node *lchild;
    Node *rchild;
    char c;
}Tree[50];

int loc;
// 申请一个节点空间，返回指向其的指针
Node *creat(){
    Tree[loc].lchild = Tree[loc].rchild = NULL;
    return &Tree[loc++];
}
char str1[30], str2[30];

void postOrder(Node *T){
    // 后序遍历
    if(T->lchild != NULL){
        postOrder(T->lchild);
    }
    if(T->rchild != NULL){
        postOrder(T->rchild);
    }
    printf("%c", T->c);
}


Node *build(int s1, int e1, int s2, int e2){
    Node *ret = creat();
    ret->c = str1[s1];    //前序遍历中第一个字符
    int rootIdx;
    for (int i=s2;i<=e2;i++){ //查找根节点字符在中序遍历中的位置
        if(str2[i] == str1[s1]){
            rootIdx = i;
            break;
        }
    }
    if(rootIdx != s2){ // 如果左子树不为空
        ret->lchild = build(s1+1, s1+(rootIdx-s2), s2, rootIdx-1);
    }
    if(rootIdx != e2){ // 如果右子树不为空
        ret->rchild  = build(s1+(rootIdx-s2)+1, e1, rootIdx+1, e2);
    }
    return ret;
}

int main(){
    while(scanf("%s", str1) != EOF){
        scanf("%s", str2);
        loc = 0;
        int L1 = strlen(str1);
        int L2 = strlen(str2);
        Node *T = build(0, L1-1, 0, L2-1);
        postOrder(T);
        printf("\n");
    }
    return 0;
}

二叉排序树

二叉排序树满足，对于树上任意一个结点，其上的数值必大于等于其左子树上任意结点数值，必小于右子树上任意结点数值。

对二叉排序树作中序遍历，结果一定是一个递增序列。

  • 例3.5 二叉排序树：
#include<stdio.h>
#include<string.h>

struct Node{
    Node *lchild;
    Node *rchild;
    int c;
}Tree[100];

int loc;
Node *creat(){
    Tree[loc].lchild = Tree[loc].rchild = NULL;
    return &Tree[loc++];
}

void postOrder(Node *T){
    // 后序遍历
    if (T->lchild != NULL)
        postOrder(T->lchild);
    if (T->rchild != NULL)
        postOrder(T->rchild);
    printf("%d ", T->c);
}

void inOrder(Node *T){
    // 中序遍历
    if (T->lchild != NULL)
        inOrder(T->lchild);
    printf("%d ", T->c);
    if (T->rchild != NULL)
        inOrder(T->rchild);
}

void preOrder(Node *T){
    // 前序遍历
    printf("%d ", T->c);
    if (T->lchild != NULL)
        preOrder(T->lchild);
    if (T->rchild != NULL)
        preOrder(T->rchild);
}

Node *insert(Node *T, int x){
    // 插入数字
    if (T == NULL){
        T = creat();   //必须
        T->c = x;
        return T;
    }
    else if (x < T->c)
        T->lchild = insert(T->lchild, x);
    else if (x > T->c)
        T->rchild = insert(T->rchild, x);
    return T;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        loc = 0;
        Node *T = NULL;
        for (int i=0; i<n;i++){
            int x;
            scanf("%d", &x);
            T = insert(T, x);
        }
        preOrder(T);
        printf("\n");
        inOrder(T);
        printf("\n");
        postOrder(T);
        printf("\n");
    }
    return 0;
}

判断两棵树是否相同，只需要进行包括中序遍历在内的两种遍历，若两种遍历都相同，则两颗树相同。

  • 例3.6 二叉搜索树
#include<stdio.h>
#include<string.h>
struct Node{
    Node *lchild;
    Node *rchild;
    int c;
}Tree[100];

int loc;
Node *creat(){
    Tree[loc].lchild = Tree[loc].rchild = NULL;
    return &Tree[loc++];
}

char str1[25], str2[25];        //保存二叉排序树的遍历结果
int size1, size2;
char *str;        // 当前正在保存字符串
int *size;        //当前正在保存字符串中字符个数

void postOrder(Node *T){
    if (T->lchild != NULL){
        postOrder(T->lchild);
    }
    if (T->rchild != NULL)
        postOrder(T->rchild);
    str[(*size)++] = T->c + '0';
}

void inOrder(Node *T){
    if (T->lchild != NULL){
        inOrder(T->lchild);
    }
    str[(*size)++] = T->c + '0';
    if (T->rchild != NULL){
        inOrder(T->rchild);
    } 
}

Node *insert(Node *T, int x){
    // 插入数字
    if (T==NULL){
        T = creat();
        T->c = x;
        return T;
    }
    else if (x < T->c){
        T->lchild = insert(T->lchild, x);
    }
    else if (x > T->c){
        T->rchild = insert(T->rchild, x);
    }
    return T;
}

int main(){
    int n;
    char tmp[12];
    while (scanf("%d", &n) != EOF && n != 0){
        loc = 0;
        Node *T = NULL;
        scanf("%s", tmp);
        for (int i=0;tmp[i] != 0;i++){
            T = insert(T, tmp[i] - '0');
        }
        size1 = 0;
        str = str1;        //str 中放的是str1地址
        size = &size1;
        postOrder(T);
        inOrder(T);
        str1[size1] = 0;

        while(n-- != 0){
            scanf("%s", tmp);
            Node *T2 = NULL;
            for (int i=0;tmp[i] != 0;i++){
                T2 = insert(T2, tmp[i] - '0');
            }
            size2 = 0;
            str = str2;
            size = &size2;
            postOrder(T2);
            inOrder(T2);
            str[size2] = 0;
            puts(strcmp(str1, str2) == 0 ?"Yes":"No");
        }
    }
    return 0;
}
文章作者: lovelyfrog
文章链接: http://lovelyfrog.github.io/2018/07/15/wangdaojishi2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 lovelyfrog !
王道机试
 上一篇
机试-数学问题 机试-数学问题
数位拆解 例4.1 特殊乘法 #include<stdio.h> int main(){ int a,b; while(scanf("%d%d", &a, &b) != EOF){
2018-07-16 算法
王道机试
下一篇 
机试-经典入门 机试-经典入门
##排序 c++ 快速排序库函数，头文件需包含 algorithm，并使用标准命名空间(sort 被定义在其中)，我们也可以定义新的排序规则： #include<stdio.h> #include<algorithm> us
2018-07-13 算法
王道机试
  目录