22232程序设计实践·数据结构

2023-03-16

笔记

字数统计: 9.5k | 阅读时长≈ 42 分钟

这是本系列的第三篇文章，旨在记录程序设计实践中数据结构部分的感想。

DA-1 IP转换

题目信息

题目描述：

在进行基于协议的网络通讯时，用长度为32的信号表示地址。为了便于使用，通常会将32位信号转换为4个长度为8的信号。

例如: 01111111000000000000000000000001会被转化为 127.0.0.1

现在给出一系列地址的二进制表示，需要转化为它的对应十进制便于阅读的表示方式，即形式。

输入

第一行包含一个整数表示样例个数

对于每个样例，输入一个长度为的二进制串表示地址。

输出

对于每个样例，输出一行字符串表示便于阅读的地址。

样例输入

1
01111111000000000000000000000001

样例输出

127.0.0.1

数据范围

正常范围

题目分析

地址的二进制转换，每一个8位二进制数就对应一个十进制数。

二进制转换处理方式：

初始时，设定转换后的数字为；每读入一个数字，前面已经转换过得数字乘以后再加上，直至读入完成后输出。

为什么这么转换？

举个例子，比如说，我们现在有一个二进制数，他可以拆成.

模拟一下：

$读入（）：$

内核不言而喻，每读一位，都会相当于在之前的二进制数后面添个零（），再加上这一位。

数据处理的问题解决了，但是，数据的传入又是一个问题。鉴于转换的性质，数字只能一个一个的读入。借助string类字符串处理后强制类型转换是一个选择，但是如果想纯纯的借助char类输入的话，就需要面对一个问题：getchar()函数的一个潜在的缺陷。

C++的键盘数据输入是标准数据输入模式。对于标准输入，C++程序从键盘读取了一连串的数据之后，当我们按动回车（注意：只有回车能完成此操作）时，数据流会进入缓冲区储存。同时，按动的回车符，同时占用一个字节的空间。比如123456这个字符串，输入后敲一下回车键（将这个字符串送入了缓冲区中，此时缓冲区中的字节个数是7（123456) ，而不是6。

cin读取数据是从缓冲区中获取数据，缓冲区为空时，cin的成员函数会阻塞等待数据的到来，一旦缓冲区中有数据，就触发cin的成员函数去读取数据。当cin>>从缓冲区中读取数据时，若缓冲区中第一个字符是空格、tab或换行这些分隔符时，cin>>会将其忽略并清除，继续读取下一个字符（连续读入字符，比如说，可以读入23这一个整体而不是分成两个），若缓冲区为空，则继续等待。但是如果读取成功后再遇到分隔符（即输入数据后敲个回车或者空格），字符后面的分隔符是残留在缓冲区的，cin>>不做处理。

翻译过来就是：

cin>>a会被空格，回车符，制表符打断。免疫空格输入、回车换行符输入、制表符输入。
cin>>a末尾发现的空格、回车换行符、制表符，仍然在缓冲区里面好好地躺着，依然可以被不免疫它们的数据流读入函数截获。

而getchar()是stdio.h中的库函数，它的作用是从stdin流中读入一个字符，也就是说，如果stdin有数据的话不用输入它就可以直接读取了。他们是共用缓冲区的，并且getchar()不免疫空格和回车，空格会读入ASCII 32，回车会读入ASCII 10。

*那就会出现一个问题：cin后想用getchar读入数据时，getchar却拿走了缓冲区的回车符。

我们需要把这些讨厌的换行符给它嘎了。

怎么拿掉？

模拟一下输入流：

2\n
01111111000000000000000000000001\n
11111111111111111111111111111111\n

我们第一步输入的2使用的是cin;cin丢下了一个换行符。接下来每一组输入的数据，前面都会有一个上一组数据丢下的换行符。所以在每一次开始之前，都需要先把回车符丢掉，也就是说在while循环里，第一步先ch=getchar()甩掉回车符。

但是这样完成后，最后一个换行符又剩下了。

其实这个残留无所谓，程序已经结束了。如果不想这么留着，就在return 0前再来一个getchar()拿掉他。

代码

#include <bits/stdc++.h>
using namespace std;
stack<int> rd;
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        char ch = getchar();//使用getchar()的缺点：注意回车符吸收

        int num, a[4];
        for (int i = 1; i <= 4; i++)
        {
            int n = 0;
            for (int j = 1; j <= 8; j++)
            {
                num = getchar() - '0';
                n <<= 1;
                n += num;
            }
            a[i - 1] = n;
        }
        cout << a[0] << "." << a[1] << "." << a[2] << "." << a[3] << endl;
    }
    char chs = getchar();
    system("pause");
    return 0;
}

DA-2 进制转换

题目信息

题目描述：

输入一个十进制数，将它转换成进制数输出。

输入

输入数据包含多个测试实例，每个测试实例包含两个整数和.

输出

为每个测试实例输出转换后的数，每个输出占一行。如果大于，则对应的数字规则参考进制（比如，用表示，等等）。

样例输入

7 2
23 12
-4 3

样例输出

111
1B
-11

数据范围

为位整数,。

题目分析

十进制转换其它进制采用短除法实现，逐次短除余数相加，通过栈的调用实现倒序的输出。需要注意，没有10这个数字！

代码

#include <bits/stdc++.h>
using namespace std;
string num[20] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E"};
void exchange(int a, int n)
{
    if(a<0){a=-a;cout<<"-";}
    stack<int> s;
    while (a != 0)
    {
        s.push(a % n);
        a /= n;
    }
    while (!s.empty())
    {
        cout << num[s.top()];
        s.pop();
    }
}
int main()
{
    int a, n;
    while (cin >> a >> n)
    {
        exchange(a,n);
        cout<<endl;
    }
    system("pause");
    return 0;
}

DA-3/DA-EX-3 简单计算器

题目信息

题目描述：

DA-3:

读入一个只包含的非负整数计算表达式，计算该表达式的值。

DA-EX-3:

突袭模式：运算符包括小括号

输入

测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入

DA-3:

1 + 2
4 + 2 * 5 - 7 / 11
0

DA-EX-3:

1 + 2
4 + 2 * 5 - 7 / 11
9+(3-1)*3+10/2
0

样例输出

3.00
13.36
20.00

数据范围

正常范围

题目分析

多项表达式的计算分为两步，一是后缀表达式的构建，二是后缀表达式的计算。

一.后缀表达式的构建

后缀表达式的构建是通过队列来实现的，因为最后表达式计算的时候要从队列的头开始取元素计算。

对普通的中序表达式（正常算式）构建的时候，有以下三条准则：

从左往右遍历中序表达式。
如果下一个进入队列的是数字，就直接进入队列。
如果下一个进入的是算作符，若该运算符为右括号（不高于上一个进入运算符缓冲栈的运算符等级的运算符），则将运算符缓冲栈内的运算符依次出栈并入队列，直至左括号出栈（栈顶运算符等级高于此运算符）。若是左括号，则左括号不入队列。

举个例子：

$入队列$

$当前表达式为$

$：入缓冲栈（目前栈空，栈空就进栈）$

$：入栈$

$目前缓冲栈里从上到下：$

$：入队列$

$当前表达式为$

$入栈$

$目前栈里从上到下：$

$入队列$

$当前表达式为$

$右括号，输出栈顶元素直至左括号并清除左括号，入队列。$

$当前表达式为$

$当前栈从上到下$

$优先级高于直接入栈$

$入队列$

$当前表达式$

$当前栈从上到下$

$运算符等级不高于和运算符出栈并入队列$

$当前表达式$

$当前缓冲区：$

$入队列$

$当前表达式$

$进缓冲栈$

$入队列$

$当前表达式$

$当前栈从上到下$

$由于已经没有符号和数字了$

$栈内依次出栈并写入表达式$

$最后得出$

二.后缀表达式的运算

表达式的计算相较构建简单了不少，每碰到一个运算符就把运算符前面已经进运算栈的两个数字出栈运算，并将结果重新塞回运算栈，直至遍历结束，输出运算栈结果内容。

接着上面的例子：

$后缀表达式：$

$依次进运算栈$

$当前运算栈内元素为$

$发现、出栈运算，进栈。$

$当前栈内元素$

$入栈$

$当前栈内元素$

$发现、出栈运算，进栈。$

$当前栈内元素$

$发现、出栈运算，进栈$

$当前栈内元素$

$、进栈$

$当前栈内元素$

$进栈，，出栈运算，进栈$

$当前栈内元素$

$进栈，，出栈运算，进栈$

$输出$

代码1:（手动类）

算法逻辑解决了，下面的问题就是如何用代码实现。

先手动实现了栈的类

//S3-3class.h
#include<bits/stdc++.h>
using namespace std;
class stacker
{
    private:
    int topn=0;
    int maxcapacity;
    string *s=NULL;
    public:
    stacker();\\空构造函数
    stacker(const int &n);\\生成一个大小为n的栈
    ~stacker();\\析构函数
    bool empty();\\判栈空
    bool full();\\判栈满
    void push(string a);\\栈插入元素
    void pop();\\栈弹出元素
    int size();\\栈现存元素个数
    string top();\\返回栈顶元素
    string* output();\\返回整体栈内元素
};

//S3-3class.cpp
#include<bits/stdc++.h>
#include"S3-3class.h"
using namespace std;
stacker::stacker(const int &n)
{
    maxcapacity=n;
    s=new string[n];
    topn=0;
}
stacker::~stacker(){}
int stacker::size()
{
    return topn;
}
bool stacker::empty()
{
    return topn==0;
}
bool stacker::full()
{
    return topn==maxcapacity;
}
void stacker::push(string a)
{
    if(!full())
    s[topn++]=a;
}
void stacker::pop()
{
    if(!empty())
    topn--;
}
string stacker::top()
{
    return s[topn-1];
}
string* stacker::output()
{
    string *s=new string[topn+1];
    for(int i=topn-1;i>=0;i--)
    {
        s[i]=top();
        pop();
    }
    return s;
}

下面就是大头：生成函数和运算函数。

先分析生成函数逻辑。一开始我想着是将所有的运算符都归一个等级大小比较，设定加和减为1，乘和除为2，压栈符号#为-1，左右括号为0.但是这时会有比较准则3的时候同级运算符弹出的问题（即左括号被弹到了表达式里面）；后来又想上调左括号等级为3，但是这时左括号比加减乘除等级高，加减乘除将被弹出。所以如果是括号，只能采取SpecialJudge来处理。

int exchange(string s)
{
    if (s == "(")
        return 0;
    else if (s == "*" || s == "/")
        return 2;
    else if (s == "+" || s == "-")
        return 1;
    else if (s == ")")
        return 0;
    else if (s == "#")
        return -1;
    return 10;//没有意义的返回无穷大
}
int check(string a, string b) // 新入栈符号，上一栈符号
{
    if (exchange(a) == 0)//右括号SpecialJudge
        return 2;
    else if (exchange(a) > exchange(b))
        return 1;//新入栈权限高于上一个
    return 0;//不高于上一个
}
void operate(const string s, stacker &num, stacker &op)
{
    if (s == "#") // 读到井号表示算式结束，运算符栈净空
    {
        while (!op.empty())
        {
            num.push(op.top());
            op.pop();
        }
        num.pop(); // 把#去了
    }
    else if (s == "(")//左括号SpecialJudge，直接入栈
    {
        op.push(s);
        return;
    }
    else//其他符号判定
    {
        if (check(s, op.top()) == 2)//右括号SpecialJudge
        {
            while (op.top() != "(")
            {
                num.push(op.top());//出栈入队
                op.pop();
            }
            op.pop();//左括号清除
            return;
        }
        else if (check(s, op.top()) == 1)//权限高，入栈
        {
            op.push(s);
            return;
        }
        else
        {
            while (check(s, op.top()) == 0)//权限不高，持续出栈直至权限高后入栈
            {
                num.push(op.top());
                op.pop();
            }
            op.push(s);//新符号入栈，切记
            return;
        }
    }
}

再讨论运算逻辑，但在这之前有一个问题，我们所有的数字全部是靠string类存储的，这对运算尤其是小数运算产生了极大的影响。我们需要对string类转换为数字类。

怎么转换？

i/ostringstream类提供了标准的转换运算符，支持将int型和不多于8位（建议的最高精度）的浮点数与string类互换。这个方法在较早的老式g++编译器版本中依旧可以正常运行，相较于后来衍生的函数有更高的兼容性

string转成数字（double为例）

string s="123.45678";
istringstream ss(s);
double num;
ss>>num;//都是ss在前
cout<<num<<endl;

数字转换为string

double num=123.45678;
ostringstream ss;
ss<<num;//都是ss在前
string s=ss.str();
cout<<s<<endl;

实现计算：

double calc(string *num, int n)
{
    stacker as(n);
    for (int i = 0; i < n; i++)
    {
        if (num[i] != "+" && num[i] != "-" && num[i] != "*" && num[i] != "/")
            as.push(num[i]);
        else
        {
            string a = as.top();
            as.pop();
            string b = as.top();
            as.pop();
            istringstream ss(a); // string转int
            istringstream sn(b);
            double num1, num2;
            ss >> num1;
            sn >> num2;
            double ans = 0.0;
            if (num[i] == "+")
                ans = 1.0 * (num2 + num1);
            else if (num[i] == "-")
                ans = 1.0 * (num2 - num1);
            else if (num[i] == "*")
                ans = 1.0 * num2 * num1;
            else if (num[i] == "/")
                ans = 1.0 * num2 / num1;
            string p;
            ostringstream sf; // int转string
            sf << ans;
            p = sf.str();
            as.push(p);
        }
    }
    string numfinal = as.top();
    istringstream sg(numfinal);
    double ansfinal;
    sg >> ansfinal;
    return ansfinal;
}

针对输入的空格问题，通过find函数扫描清除。

补充：string::find()函数和string::find_first_of()的区别在于，find_first_of()在母串上从指定位置开始查找，如果遇到的字符与目标串中任意字符相同，则查找成功，返回该字符的位置（交集非空即有返回值）;find()则是在母串上从指定位置开始，查找字符或字符串。当查找字符串时，要保证目标串为母串的子串（完成子串）。查找成功则返回字符串子串的第一个字符的位置。

void trim(string &s)
{
    int index = 0;
    if (!s.empty())
    {
        while ((index = s.find(' ', index)) != string::npos)
        {
            s.erase(index, 1);
        }
    }
}

完整主函数文件：

#include"S3-3class.cpp"
int exchange(string s)
{
    if (s == "(")
        return 0;
    else if (s == "*" || s == "/")
        return 2;
    else if (s == "+" || s == "-")
        return 1;
    else if (s == ")")
        return 0;
    else if (s == "#")
        return -1;
    return 10;
}
int check(string a, string b) // 新入栈符号，上一栈符号
{
    if (exchange(a) == 0)
        return 2;
    else if (exchange(a) > exchange(b))
        return 1;
    return 0;
}
void operate(const string s, stacker &num, stacker &op)
{
    if (s == "#") // 读到井号表示算式结束，运算符栈净空
    {
        while (!op.empty())
        {
            num.push(op.top());
            op.pop();
        }
        num.pop(); // 把#去了
    }
    else if (s == "(")
    {
        op.push(s);
        return;
    }
    else
    {
        if (check(s, op.top()) == 2)
        {
            while (op.top() != "(")
            {
                num.push(op.top());
                op.pop();
            }
            op.pop();
            return;
        }
        else if (check(s, op.top()) == 1)
        {
            op.push(s);
            return;
        }
        else
        {
            while (check(s, op.top()) == 0)
            {
                num.push(op.top());
                op.pop();
            }
            op.push(s);
            return;
        }
    }
}
double calc(string *num, int n)
{
    stacker as(n);
    for (int i = 0; i < n; i++)
    {
        if (num[i] != "+" && num[i] != "-" && num[i] != "*" && num[i] != "/")
            as.push(num[i]);
        else
        {
            string a = as.top();
            as.pop();
            string b = as.top();
            as.pop();
            istringstream ss(a); // string转int
            istringstream sn(b);
            double num1, num2;
            ss >> num1;
            sn >> num2;
            double ans = 0.0;
            if (num[i] == "+")
                ans = 1.0 * (num2 + num1);
            else if (num[i] == "-")
                ans = 1.0 * (num2 - num1);
            else if (num[i] == "*")
                ans = 1.0 * num2 * num1;
            else if (num[i] == "/")
                ans = 1.0 * num2 / num1;
            string p;
            ostringstream sf; // int转string
            sf << ans;
            p = sf.str();
            as.push(p);
        }
    }
    string numfinal = as.top();
    istringstream sg(numfinal);
    double ansfinal;
    sg >> ansfinal;
    return ansfinal;
}
void trim(string &s)
{
    int index = 0;
    if (!s.empty())
    {
        while ((index = s.find(' ', index)) != string::npos)
        {
            s.erase(index, 1);
        }
    }
}

int main()
{
    string s;
    while (getline(cin, s) && s != "0")
    {

        trim(s);
        s += "#";
        int slength = s.length();
        stacker num(slength);
        stacker op(slength);
        op.push("#");
        // cout<<op.top()<<endl;
        string ns;
        for (int i = 0; i < slength; i++)
        {

            if (s[i] >= '0' && s[i] <= '9')
            {
                ns += s[i];
            }
            else
            {
                if (ns != "")
                    num.push(ns);
                ns = "";
                string opr = "";
                opr += s[i];
                operate(opr, num, op);
            }
        }
        int n = num.size();
        string *snew = new string[n + 1];
        snew = num.output();
        cout << fixed << setprecision(2) << calc(snew, n) << endl;
    }
    system("pause");
    return 0;
}

代码2：STL重置

借助STL进行了完成的优化，删除了大部分无用代码。

#include <bits/stdc++.h>
using namespace std;
queue<string> num;
stack<string> op;
string exchange(char a)
{
    string s;
    s.push_back(a);
    return s;
}
void del(string &s)
{
    int point = 0;
    while ((point = s.find(" ", point)) != string::npos)
        s.erase(point, 1);
    return;
}
int judge(string s)
{
    if (s == "(")
        return 0;
    else if (s == "+" || s == "-")
        return 1;
    else if (s == "*" || s == "/")
        return 2;
    else if (s == ")")
        return 0;
    else if (s == "#")
        return -1;
    return 10;
}
void suffix_build(string s, queue<string> &num, stack<string> &op)
{
    s += "#";
    op.push("#");
    int length = s.length();
    string n = "";
    for (int i = 0; i < length; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            n += s[i];
            continue;
        }
        if (n != "")
            num.push(n);
        n = "";
        switch (judge(exchange(s[i])))
        {
        case -1:
            while (!op.empty())
            {
                if (op.top() != "#")
                    num.push(op.top());
                op.pop();
            }
            break;
        case 0:
            if (s[i] == '(')
            {
                op.push(exchange(s[i]));
                break;
            }
            else
            {
                while (op.top() != "(")
                {
                    num.push(op.top());
                    op.pop();
                }
                op.pop();
                break;
            }
            break;
        default:
            while (judge(exchange(s[i])) <= judge(op.top()))
            {
                num.push(op.top());
                op.pop();
            }
            op.push(exchange(s[i]));
            break;
        }
    }
    return;
}
double suffix_calc(queue<string> num)
{
    stack<double> calcs;
    while (!num.empty())
    {
        while (num.front() != "+" && num.front() != "-" && num.front() != "*" && num.front() != "/")
        {
            istringstream ss(num.front());
            double q;
            ss >> q;
            calcs.push(q);
            num.pop();
        }
        double num1 = calcs.top();
        calcs.pop();
        double num2 = calcs.top();
        calcs.pop();
        switch (judge(num.front()))
        {
        case 1:
            if (num.front() == "+")
            {
                calcs.push(1.0 * (num1 + num2));
                num.pop();
            }
            else
            {
                calcs.push(1.0 * (-num1 + num2));
                num.pop();
            }
            break;
        case 2:
            if (num.front() == "*")
            {
                calcs.push(1.0 * (num1 * num2));
                num.pop();
            }
            else
            {
                calcs.push(1.0 * num2 / num1);
                num.pop();
            }
        }
    }
    return calcs.top();
}
int main()
{
    string s;
    while (getline(cin, s) && s != "0")
    {
        del(s);
        suffix_build(s, num, op);
        cout << fixed << setprecision(2) << suffix_calc(num) << endl;
    }
    system("pause");
    return 0;
}

DA-TR-4 栈和队列

题目信息

题目描述：

$队列和栈是两种重要的数据结构，它们具有和操作。是将数字加入到队列或栈中，则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。$

$队列是先进先出的：把队列看成横向的一个通道，则是将放到队列的最右边，而则是从队列的最左边取出一个数。$

$栈是后进先出的：把栈也看成横向的一个通道，则是将放到栈的最右边，而也是从栈的最右边取出一个数。$

$假设队列和栈当前从左至右都含有和两个数，则执行和操作示例图如下：$

          push 5          pop

队列 1 2  ------->  1 2 5 ------>  2 5

          push 5          pop

栈   1 2  ------->  1 2 5 ------>  1 2

$现在，假设队列和栈都是空的。给定一系列和操作之后，输出队列和栈中存的数字。若队列或栈已经空了，仍然接收到操作，则输出。$

输入

$第一行为，表示有组测试输入，。$ $每组第一行为，表示下列有行或操作。（）$ $接下来行，每行是或者，其中是一个整数。$ $（输入保证同时在队列或栈中的数不会超过个）$

输出

$对每组测试数据输出两行，正常情况下，第一行是队列中从左到右存的数字，第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到，则输出。输出应该共行。$

样例输入

2
4
push 1
push 3
pop
push 5
1
pop

样例输出

3 5
1 5
error
error

数据范围

输入已给出

题目分析

~~都是TR训练关卡了就别让我跟写EX突袭一样了呗~~

代码（手动模板类）

#include <bits/stdc++.h>
using namespace std;
template <typename T>
class stackown;//模板类栈
template <typename T>
class queueown;//模板类队列
template <typename T>
class listnode//借助链表：队列单链表，栈双链表
{
    friend class stackown<T>;//友元类
    friend class queueown<T>;
private:
    T pos;
    listnode *before=NULL;
    listnode *next = NULL;
public:
    listnode(){};
    ~listnode(){};
};
template <typename T>
class queueown
{
private:
    listnode<T> *first;
    listnode<T> *last;
    listnode<T> *cnt;
public:
    queueown();//构造函数
    ~queueown();//析构函数
    bool empty();//判空
    void push(const T &a);//队列从尾插入
    void pop();//队列从头弹出。如果为空，输出error
    T front();//返回队首元素。如果为空，返回随机，无意义
    void print();//打印队列元素
};
template<class T>
void queueown<T>::print()
{
    if(empty())return;
    cnt=first->next;
    for(;cnt!=last->next;cnt=cnt->next)
    cout<<cnt->pos<<" ";
    cout<<endl;
    return;
};
template <typename T>
class stackown
{
private:
    listnode<T> *first;
    listnode<T> *last;
public:
    stackown();
    ~stackown();
    bool empty();
    void push(T &a);
    void pop();
    T top();
    void print();
};
template<class T>
void stackown<T>::print()
{
    if(empty())return;
    listnode<T> *p=first->next;
    for(;p!=last->next;p=p->next)
    {
        cout<<p->pos<<" ";
    }
    cout<<endl;
};
template <class T>
stackown<T>::stackown()
{
    last=first=new listnode<T>;
};
template <class T>
stackown<T>::~stackown(){};
template <class T>
bool stackown<T>::empty()
{
    if(first==last)return true;
    return false;
};
template <class T>
void stackown<T>::push(T &a)
{
    last->next=new listnode<T>;
    last->next->before=last;
    last=last->next;
    last->pos=a;
    return;
}
template <class T>
T stackown<T>::top()//返回栈顶元素
{
    return last->pos;
}
template <class T>
void stackown<T>::pop()//删除栈顶元素
{
    if(!empty()){last=last->before;
    delete last->next;
    last->next=NULL;}
    return;
}
template <class T>
queueown<T>::queueown()
{
   last=first=new listnode<T>;//空头标记,此处无元素。
   cnt=new listnode<T>;
};
template <class T>
queueown<T>::~queueown(){};
template <class T>
bool queueown<T>::empty()
{
    if(last==first)return true;
    return false;
};
template <class T>
void queueown<T>::push(const T &a)
{
    last->next=new listnode<T>;
    last=last->next;
    last->pos=a;
    return;
}
template <class T>
T queueown<T>::front()//返回队列的第一个元素
{
    if(!empty())return first->next->pos;
    return first->pos;
}
template <class T>
void queueown<T>::pop()//删除队列的第一个元素，如果队列为空，输出“error”
{
    if(!empty())first->next=first->next->next;
    return;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        queueown<int> q;
        stackown<int> s;
        int sp;
        cin>>sp;
        for(int i=1;i<=sp;i++)
        {
            string su;
            cin>>su;
            if(su=="push")
            {
                int o;
                cin>>o;
                q.push(o);
                s.push(o);
            }
            else if(su=="pop")
            {
                if(!q.empty())q.pop();
                else cout<<"error"<<endl;
                if(!s.empty())s.pop();
                else cout<<"error"<<endl;
            }
        }
        q.print();
        s.print();
    }
    system("pause");
    return 0;
}

DA-5/DA-EX-5 报数

题目信息

题目描述： DA-5: 今天一共位同学参加了期末考试，大家计划在期末考试后在教室玩一个游戏，个同学编号后围成一圈报数，报到的倍数的同学将被移出队伍，然后下一位同学继续现在的报数。当剩余人数少于时结束游戏。

请你输出剩余同学的原始编号。

DA-EX-5:

突袭模式：数据增强

输入

第一行包含一个整数，表示样例个数。对于每个样例，包含一个单独的整数表示同学的编号。

输出

对于每个样例，在一行输出剩余同学的编号，使用空格分隔。

样例输入

2
5
8

样例输出

1 2 3 4 5
1 2 3 4 5 8

1 2 3 4 5
1 2 3 4 5 8
3 5 6 8 9 10

数据范围

题目分析

和士兵列队训练问题是同一个板子，但是挂为突袭关卡的原因在于单循环链表的头指针问题。

采用单循环链表进行删除操作的时候，非Node1的节点删除不会影响最后的单循环链遍历，但是一旦出现了如图所示的Node1的删除，鉴于启动子First指针依旧是指向Node1的，所以当该单链表展开的时候，第一段依旧是带有Node1的，这是不符合要求的。推广之，对于任意的位于First后面的指针节点涉及删除时，都需要添加一步针对于启动子First的First->next的修改以彻底删除该节点：

Node1删除前

Node1删除与启动子修改

template<class T>void LinkList<T>::targetdelete()
{
    LinkNode<T> *p=first;
    for(int i=1;size>=7;i++)
    {
        p=p->next;
        if(i%7==6)
        {
            LinkNode<int> *d=p->next;
            if(p->next==first->next)first->next=d->next;
            p->next=d->next;
            delete d;
            size--;
            i=0;
        }
    }
    return;
};

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>class LinkList;
template<typename T>class LinkNode//链节点类
{
    friend class LinkList<T>;
    private:
    T posdata;
    LinkNode<T> *next=NULL;
    public:
    LinkNode(){};
    ~LinkNode(){};
};
template<typename T>class LinkList//单链表类
{
    private:
    LinkNode<T> *first;
    LinkNode<T> *last;
    LinkNode<T> *cnt;
    bool ecir=false;
    int size=0;
    public:
    LinkList();
    ~LinkList();
    /*!
    @brief 单链表的数据嵌入
    @param a
    目标字符
    @return 
    无返回值，在链表的末尾新建一值为a的节点
    */
    void push(const T &a);
    /*!
    @brief 数据成环
    @return 无返回值，last指针的后继指向first的后继
    */
    void circlemade();
    /*!
    @brief 数据删除
    @return 无返回值，返回调整后的链表环
    */
    void targetdelete();
    void print();
};
template<class T>LinkList<T>::LinkList()//构造函数
{
    first=last=new LinkNode<T>;
    cnt=new LinkNode<T>;
};
template<class T>LinkList<T>::~LinkList(){};
template<class T>void LinkList<T>::push(const T &a)
{
    if(!ecir)
    {
        size++;
        last->next=new LinkNode<T>;
        last=last->next;
        last->posdata=a;
    }
    return;
};
template<class T>void LinkList<T>::circlemade()
{
    ecir=true;
    last->next=first->next;
    return;
};
template<class T>void LinkList<T>::targetdelete()
{
    LinkNode<T> *p=first;
    for(int i=1;size>=7;i++)
    {
        p=p->next;
        if(i%7==6)
        {
            LinkNode<int> *d=p->next;
            if(p->next==first->next)first->next=d->next;
            p->next=d->next;
            delete d;
            size--;
            i=0;
        }
    }
    return;
};
template<class T>void LinkList<T>::print()
{
    LinkNode<T> *p=first;
    for(int i=1;i<=size;i++)
    {
        p=p->next;
        cout<<p->posdata<<" ";
    }
    cout<<endl;
    return;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int s;
        cin>>s;
        LinkList<int> line;
        for(int i=1;i<=s;i++)
        {
            line.push(i);
        }
        line.circlemade();
        line.targetdelete();
        line.print();
        line.~LinkList();
    }
    system("pause");
    return 0;
}

DA-6/DA-EX-6 二叉树遍历1

题目信息

题目描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。

例如如下的先序遍历字符串：

$You can't use 'macro parameter character #' in math mode ABC##DE#G##F###$

其中“ $You can't use 'macro parameter character #' in math mode #$ ”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

突袭模式：禁止使用递归方式建树

输入

输入包括1行字符串

输出

可能有多组测试数据，对于每组数据，

输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。

每个输出结果占一行。

样例输入

a#b#cdef#####
a##

样例输出

a b f e d c 
a

数据范围

字符串长度;

题目分析

方法一：递归模式做法 相似于二叉树的前序遍历模式，建立递归函数读入字符。二叉树的构成是该根节点+其左子树+其右子树，故建立递归函数表明建立以为前序遍历的二叉树，其结构可以是。

tree *buildtree_first(string &s)
{
    tree *tmp = new tree;
    if (s[0] == '#')
        return NULL;
    tmp->pos = s[0];
    tmp->leftson = buildtree_first(s = s.substr(1, s.length() - 1));
    tmp->rightson = buildtree_first(s = s.substr(1, s.length() - 1));
    return tmp;
}

方法二：突袭模式分析

在不使用递归的话，需要对每一个树节点的访问进行分析。

一个树节点的可能的来访路径有两种。

从上一个节点的左右子树指针来访。
从上一个空节点的父亲指针回退来访或从上一个左右子树节点均已填满的节点的父亲指针回退来访。

一个树节点可能的节点信息有两种： 1. 字符 2. #（空树）

一个树节点可能的去向路径有两种： 1. 它的左儿子或者右儿子节点。 2. 它的父亲节点。

此时需要进行判断：

这个节点是不是已经填上了？如果没填上，填上；如果填上了，不执行2，3。
填的是什么？如果是正常字符，不执行2步；如果填的是空字符#，第3，4，5步跳过。
是否生成左右子树节点？如果左右没有生成，则生成。
访问左子节点回退第1步。
访问右子节点回退第1步。
回退父子节点回退步骤1。

void first_buildtree(tree *s, string read)
{
    tree *p = s;
    int length = read.size();
    for (int i = 0; i < length; i++)
    {
        while (1)//节点回退步骤
        {
            if (p->pos == '0')//1.这个节点是否已经填上了？
            {
                p->pos = read[i];//填上
                while (1)
                {
                    if (p->leftson == NULL)//3.是否生成左子树节点
                    {
                        if (read[i] != '#')//2.填的是什么？
                        {
                            p->leftson = new tree;
                            p->leftson->father = p;
                            p = p->leftson;//4.while循环访问左子节点
                            break;//break第二层while结束判定
                        }
                        else//填空字符
                        {
                            p = p->father;//while循环回退父亲节点
                            break;
                        }
                    }
                    else if (p->rightson == NULL)
                    {

                        if (read[i] != '#')
                        {
                            p->rightson = new tree;
                            p->rightson->father = p;
                            p = p->rightson;
                            break;
                        }
                        else
                        {
                            p = p->father;
                            break;
                        }
                    }
                    else
                        p = p->father;
                }
                break;//打破第一层循环更换字符
            }
            else//如果填上了，直接进入第4,5步
            {
                if(p->leftson==NULL)p->leftson=new tree,p->leftson->father=p,p=p->leftson;
                else if(p->rightson==NULL)p->rightson=new tree,p->rightson->father=p,p=p->rightson;
                else p=p->father;//6.回退父亲节点
            }
        }
    }
}

代码1：递归版

#include <bits/stdc++.h>
using namespace std;
typedef struct tree
{
    char pos;
    tree *leftson = NULL;
    tree *rightson = NULL;
} tree;
tree *buildtree_first(string &s)
{
    tree *tmp = new tree;
    if (s[0] == '#')
        return NULL;
    tmp->pos = s[0];
    tmp->leftson = buildtree_first(s = s.substr(1, s.length() - 1));
    tmp->rightson = buildtree_first(s = s.substr(1, s.length() - 1));
    return tmp;
}
void middlesearch(tree *p)
{
    if (p == NULL)
        return;
    middlesearch(p->leftson);
    if (p->pos != '#')
        cout << p->pos << " ";
    middlesearch(p->rightson);
    return;
}
int main()
{
    string s;
    while (cin >> s)
    {
        middlesearch(buildtree_first(s));
        cout<<endl;
    }
        system("pause");
        return 0;
    
}

代码2：突袭非递归版

#include <bits/stdc++.h>
using namespace std;
typedef struct tree
{
    char pos ='0' ;
    tree *father = NULL;
    tree *leftson = NULL, *rightson = NULL;

} tree;
void first_buildtree(tree *s, string read)
{
    tree *p = s;
    int length = read.size();
    for (int i = 0; i < length; i++)
    {
        while (1)//节点回退步骤
        {
            if (p->pos == '0')//1.这个节点是否已经填上了？
            {
                p->pos = read[i];//填上
                while (1)
                {
                    if (p->leftson == NULL)//3.是否生成左子树节点
                    {
                        if (read[i] != '#')//2.填的是什么？
                        {
                            p->leftson = new tree;
                            p->leftson->father = p;
                            p = p->leftson;//4.while循环访问左子节点
                            break;//break第二层while结束判定
                        }
                        else//填空字符
                        {
                            p = p->father;//while循环回退父亲节点
                            break;
                        }
                    }
                    else if (p->rightson == NULL)
                    {

                        if (read[i] != '#')
                        {
                            p->rightson = new tree;
                            p->rightson->father = p;
                            p = p->rightson;
                            break;
                        }
                        else
                        {
                            p = p->father;
                            break;
                        }
                    }
                    else
                        p = p->father;
                }
                break;//打破第一层循环更换字符
            }
            else//如果填上了，直接进入第4,5步
            {
                if(p->leftson==NULL)p->leftson=new tree,p->leftson->father=p,p=p->leftson;
                else if(p->rightson==NULL)p->rightson=new tree,p->rightson->father=p,p=p->rightson;
                else p=p->father;//6.回退父亲节点
            }
        }
    }
}
void middlesearch(tree *p)
{
    if (p == NULL)
        return;
    middlesearch(p->leftson);
    if (p->pos != '#')
        cout << p->pos << " ";
    middlesearch(p->rightson);
    return;
}
int main()
{
    string s;
    while (cin >> s)
    {
        tree *t = new tree;
        first_buildtree(t, s);
        middlesearch(t);
        cout<<endl;
        delete t;
    }
    system("pause");
    return 0;
}

DA-7/DA-EX-7 复原二叉树

题目信息

题目描述：

给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

突袭模式：禁止建树

输入

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出

对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

数据范围

正常范围

题目分析

方法一：建树遍历输出

一棵树的前序遍历的第一个确定了这个树的根节点；在明确根节点的情况下；中序遍历可以给出这棵树的左右子树的中序遍历（就是节点字符的左右两侧的子串）；根据子串长度又可以解出前序遍历；因而可以建树。

在这之前，先解决一个分割开字符子串的问题。

类的标准分割函数提供了分割类字符串的功能，其返回的是从位置开始的长度为的字符子串。如果不填写，默认为从pos到字符串的最后一位。

对于长度为n的中序遍历串，假定根节点字符位置为:

那么其左子树中序遍历字符串为位置到的字符子串，长度为,即:

其右子树中序遍历字符串为位置到的字符子串，长度为,即:

其左子树前序遍历字符串为位置到的字符子串，长度为,即:

其右子树前序遍历字符串为位置到的字符子串，长度为,即:

tree *buildtree(string s1, string s2)
{
    if (s1 == "" || s2 == "")
        return NULL;
    tree *tem = new tree;
    tem->pos = s1[0];
    int position = s2.find(s1[0], 0);
    tem->leftson = buildtree(s1.substr(1, s2.substr(0, position).size()), s2.substr(0, position));
    //if (tem->leftson != NULL)
        //tem->leftson->father = tem;
    tem->rightson = buildtree(s1.substr(s2.substr(0, position).size() + 1, s2.substr(position + 1, s2.length() - 1 - position).size()/*s1.length() - 1 - s2.substr(0, position).size()*/ ), s2.substr(position + 1, s2.length() - 1 - position));
    //if (tem->rightson != NULL)
        //tem->rightson->father = tem;
    return tem;
}

方法二：突袭模式分析

假定函数会输出以和为前序遍历的树的后序遍历，则其后序遍历为+

void print(string s1,string s2)
{
    if(s1=="\0"||s2=="\0") return;
    int pos=s2.find(s1[0]);
    print (s1.substr(1,pos),s2.substr(0,pos));
    print (s1.substr(pos+1),s2.substr(pos+1));
    cout<<s1[0];
}

代码1：建树

#include <bits/stdc++.h>
using namespace std;
typedef struct tree
{
    char pos = '0';
    //tree *father = NULL;
    tree *leftson = NULL, *rightson = NULL;

} tree;
tree *buildtree(string s1, string s2)
{
    if (s1 == "" || s2 == "")
        return NULL;
    tree *tem = new tree;
    tem->pos = s1[0];
    int position = s2.find(s1[0], 0);
    tem->leftson = buildtree(s1.substr(1, s2.substr(0, position).size()), s2.substr(0, position));
    //if (tem->leftson != NULL)
        //tem->leftson->father = tem;
    tem->rightson = buildtree(s1.substr(s2.substr(0, position).size() + 1, s2.substr(position + 1, s2.length() - 1 - position).size()/*s1.length() - 1 - s2.substr(0, position).size()*/ ), s2.substr(position + 1, s2.length() - 1 - position));
    //if (tem->rightson != NULL)
        //tem->rightson->father = tem;
    return tem;
}
void lastsearch(tree *p)
{
    if (p == NULL)
        return;
    lastsearch(p->leftson);
    lastsearch(p->rightson);
    cout << p->pos;
    return;
}
int main()
{
    string s1, s2;
    while (cin >> s1 >> s2)
    {
        tree *p = buildtree(s1, s2);
        lastsearch(p);
        cout << endl;
    }
    system("pause");
    return 0;
}

代码2：不建树

#include<bits/stdc++.h>
using namespace std;
void print(string s1,string s2)
{
    if(s1=="\0"||s2=="\0") return;
    int i=s2.find(s1[0]);
    print (s1.substr(1,i),s2.substr(0,i));
    print (s1.substr(i+1),s2.substr(s+1));
    cout<<s1[0];
}
int main()
{
    string s1,s2;
    while(cin>>s1&&cin>>s2)
    {
        print(s1,s2);
        cout<<endl;
    }
    system("pause");
    return 0;
}

DA-8 合并果子

题目信息

题目描述：

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有种果子，数目依次为，，。可以先将、堆合并，新堆数目为，耗费体力为。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为，耗费体力为。所以多多总共耗费体力。可以证明为最小的体力耗费值。

输入

第一行是一个整数，表示果子的种类数。第二行包含个整数，用空格分隔，第个整数是第种果子的数目。

输出

这一行只包含一个整数，也就是最小的体力耗费值。

样例输入

10
3 5 1 7 6 4 2 5 4 1

样例输出

数据范围

输入数据保证输出小于。

题目分析

贪心算法（最优树结构），每次移动的都是最小的两堆果子，即可保证结果最小。

采用上篇文章的2.4 选择排序中提及的堆排序(小根堆)维护数据区间，每次弹出两个最小的数字，加和后回堆，堆容量减一。

代码

#include <bits/stdc++.h>
using namespace std;
void swap(int *a, int m, int n)
{
    int arr = a[m];
    a[m] = a[n];
    a[n] = arr;
    return;
}
void buildheap(int *a, int n)
{
    for (int target = n / 2 - 1; target >= 0; target--)
    {
        int parent = target;
        int child = 2 * parent + 1;
        while (child < n)
        {
            if (child + 1 < n && a[child] > a[child + 1])
                child++;
            if (a[child] < a[parent])
            {
                swap(a, child, parent);
                parent = child;
                child = child * 2 + 1;
                continue;
            } // 转移至更改的节点分析该节点以下的数据
            break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    int *a=new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int sum = 0;
    for (int i = n; i >= 3; i--)
    {
        int aus = 0;
        buildheap(a, i);
        aus += a[0];
        swap(a, 0, i - 1);
        buildheap(a, i - 1);
        aus += a[0];
        swap(a, 0, i - 2);
        a[i - 2] = aus;
        sum += aus;
    }
    sum += a[0] + a[1];
    cout << sum << endl;
    system("pause");
    return 0;
}

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！