003、数据结构与算法课程设计

本课程完成了三项任务：拦截导弹、一元稀疏多项式计算器和手机斗地主游戏。内容依据课程报告、实验报告和计划表整理，属于算法与完整程序组织的入门实践。

返回项目实践 · 课程资料（提取码：3ezu）

1、课程概览

项目	内容
学习阶段	大二下学期
主要语言	C++
核心训练	动态规划、链表、规则建模、复杂度分析
资料依据	课程设计报告、实验报告、计划表和源码压缩包

编号	任务	数据结构或算法	完成情况
A02	拦截导弹	子序列、动态规划、贪心对比	已完成
B03	一元稀疏多项式计算器	带头结点链表、多项式加减	已完成
C59	手机斗地主游戏	扑克牌建模、牌型判断、状态管理	已完成

2、A02 拦截导弹

任务围绕导弹高度序列，求解可拦截序列问题。报告中比较了三种方案：

方案	思路	报告中的复杂度
方案一	直接枚举和比较子序列	O(n^3)
方案二	动态规划记录阶段最优结果	O(n^2)
方案三	贪心方式维护当前可行序列	O(n^2)

这一部分不只给出结果，还通过随机输入和较大数据量测试比较不同方案的运行时间。课程代码中同时保留了动态规划版本和贪心版本，能看出当时已经开始比较“能做出来”和“做得更合适”的区别。

3、B03 一元稀疏多项式计算器

多项式使用带头结点的链表存储，每个结点保存系数、指数和后继指针。程序完成：

• 多项式输入与规范化输出。
• 按指数顺序组织项。
• 同类项合并。
• 两个稀疏多项式的加法和减法。

这项任务的关键不是公式，而是链表遍历、结点插入、同类项合并和零系数项处理。源码里保留了带头结点链表版本，也保留了后来用 list<polyNode> 封装的版本。

4、C59 手机斗地主游戏

课程报告将斗地主拆成牌、玩家、牌局状态和规则判断几个部分，主要完成：

• 扑克牌生成、洗牌、发牌和排序。
• 单张、对子、顺子等牌型的合法性判断。
• 当前出牌与上一手牌的比较。
• 玩家与机器人回合切换。
• 胜负条件和基本交互流程。

与前两题相比，这一任务第一次明显涉及“系统状态”和“规则之间的关系”。即使界面较简单，它也比单个算法题更接近完整程序。

5、关键代码记录

5.1 拦截导弹

动态规划版本用 f 记录最长不上升子序列长度，用 g 记录最长上升子序列长度：前者对应一套系统最多拦截多少枚导弹，后者对应最少需要多少套拦截系统。

for (int i = 1; i <= n; i++) {
    cin >> v[i];
    f[i] = g[i] = 1;

    for (int j = 1; j < i; j++) {
        if (v[i] <= v[j]) {
            f[i] = max(f[i], f[j] + 1);
        }
        if (v[i] > v[j]) {
            g[i] = max(g[i], g[j] + 1);
        }
    }

    maxn = max(maxn, f[i]);
    minn = max(minn, g[i]);
}

课程源码还写了贪心版本：每来一枚导弹，就放进当前能够拦截它且拦截高度最低的系统；如果没有合适系统，就新增一套系统。

for (int i = 2; i <= n; i++) {
    p = 0;
    for (int j = 1; j <= k; j++) {
        if (b[j] >= t[i]) {
            if (p == 0 || b[p] > b[j]) {
                p = j;
            }
        }
    }

    if (p == 0) {
        k++;
        b[k] = t[i];
        c[k] = 1;
    } else {
        b[p] = t[i];
        c[p]++;
    }
}

5.2 一元稀疏多项式

Poly::Add 的思路是两个有序多项式同时向后走：指数小的项先插入，指数相同则合并系数，系数为 0 的项直接删除。

void Poly::Add(Poly another)
{
    list<polyNode>::iterator iter_this = l.begin();
    list<polyNode>::iterator iter_another = another.l.begin();

    while (iter_this != l.end() && iter_another != another.l.end()) {
        if ((*iter_another).expn < (*iter_this).expn) {
            polyNode temp((*iter_another).coef, (*iter_another).expn);
            iter_this = l.insert(iter_this, temp);
            iter_this++;
            another.l.pop_front();
            iter_another = another.l.begin();
        } else if ((*iter_another).expn > (*iter_this).expn) {
            iter_this++;
        } else {
            (*iter_this).coef += (*iter_another).coef;
            iter_another++;
            if ((*iter_this).coef == 0) {
                iter_this = l.erase(iter_this);
            }
        }
    }

    while (iter_another != another.l.end()) {
        l.push_back(*iter_another);
        iter_another++;
    }
}

5.3 手机斗地主

斗地主部分把“牌”“牌型”“玩家”“牌局”拆成类。牌型判断先统计每种点数的数量，再根据数量、连续性和附带牌判断单牌、对子、顺子、炸弹、飞机等类型。

void CardGroup::calType()
{
    unsigned long n = cards.size();
    if (n == 0) {
        type.init("不出", 14, 0, 0, 0);
        return;
    }
    if (n == 2 && cards[0]->value == 15 && cards[1]->value == 14) {
        type.init("王炸", 0, 0, 0, 0);
        return;
    }

    int cntFlag[VALUECOUNT] = {0};
    for (int i = 0; i < n; i++) {
        cntFlag[cards[i]->value]++;
    }

    int maxCnt = 0;
    for (int i = 0; i < VALUECOUNT; i++) {
        maxCnt = max(maxCnt, cntFlag[i]);
    }

    if (n == 4 && maxCnt == 4) {
        type.init("炸dan", 1, 4, 0, 0);
        return;
    }
    if (n >= 5 && maxCnt == 1 &&
        cards[0]->value == cards[n - 1]->value + n - 1) {
        type.init("顺子", 9, 1, 1, 0);
        return;
    }
}

这段源码还有一个值得修正的小点：原程序里“炸弹”字符串写成了 炸dan，属于编码或输入习惯留下的小痕迹。正文说明里按正常中文理解，代码记录保留原始写法。

6、完整代码整理

下面三份代码都可以单独复制运行，用来复盘题目核心逻辑。课程原始工程以网盘中的源码压缩包为准，这里整理成更适合阅读和二次学习的版本。

6.1 A02 拦截导弹

题目要求：

1. 输入导弹数量 n 和 n 个导弹高度。
2. 第一行输出一套系统最多能拦截多少枚导弹。
3. 第二行输出拦截全部导弹最少需要多少套系统。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }

    vector<int> down(n, 1);
    vector<int> up(n, 1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (height[i] <= height[j]) {
                down[i] = max(down[i], down[j] + 1);
            }
            if (height[i] > height[j]) {
                up[i] = max(up[i], up[j] + 1);
            }
        }
    }

    int maxIntercept = 0;
    int minSystemCount = 0;
    for (int i = 0; i < n; i++) {
        maxIntercept = max(maxIntercept, down[i]);
        minSystemCount = max(minSystemCount, up[i]);
    }

    cout << maxIntercept << endl;
    cout << minSystemCount << endl;

    return 0;
}

示例：

8
389 207 155 300 299 170 158 65

输出：

6
2

6.2 B03 一元稀疏多项式计算器

题目要求：

1. 输入两个多项式，每一项由系数和指数组成。
2. 输出多项式 A、B、A+B 和 A-B。
3. 自动合并同类项，并删除系数为 0 的项。

#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <string>
using namespace std;

struct Term {
    double coefficient;
    int exponent;
};

class Polynomial {
private:
    list<Term> terms;

    static bool sameZero(double value) {
        return fabs(value) < 1e-9;
    }

public:
    void addTerm(double coefficient, int exponent) {
        if (sameZero(coefficient)) {
            return;
        }
        terms.push_back({coefficient, exponent});
    }

    void normalize() {
        terms.sort([](const Term& a, const Term& b) {
            return a.exponent > b.exponent;
        });

        for (auto it = terms.begin(); it != terms.end();) {
            auto nextIt = next(it);
            while (nextIt != terms.end() && nextIt->exponent == it->exponent) {
                it->coefficient += nextIt->coefficient;
                nextIt = terms.erase(nextIt);
            }

            if (sameZero(it->coefficient)) {
                it = terms.erase(it);
            } else {
                ++it;
            }
        }
    }

    Polynomial add(const Polynomial& other) const {
        Polynomial result = *this;
        for (const Term& term : other.terms) {
            result.addTerm(term.coefficient, term.exponent);
        }
        result.normalize();
        return result;
    }

    Polynomial subtract(const Polynomial& other) const {
        Polynomial result = *this;
        for (const Term& term : other.terms) {
            result.addTerm(-term.coefficient, term.exponent);
        }
        result.normalize();
        return result;
    }

    void print(const string& name) const {
        cout << name << " = ";

        if (terms.empty()) {
            cout << "0" << endl;
            return;
        }

        bool first = true;
        for (const Term& term : terms) {
            double coefficient = term.coefficient;

            if (!first) {
                cout << (coefficient >= 0 ? " + " : " - ");
            } else if (coefficient < 0) {
                cout << "-";
            }

            double absCoefficient = fabs(coefficient);
            cout << fixed << setprecision(2) << absCoefficient;

            if (term.exponent != 0) {
                cout << "x";
                if (term.exponent != 1) {
                    cout << "^" << term.exponent;
                }
            }

            first = false;
        }

        cout << endl;
    }
};

Polynomial readPolynomial() {
    int count;
    cin >> count;

    Polynomial polynomial;
    for (int i = 0; i < count; i++) {
        double coefficient;
        int exponent;
        cin >> coefficient >> exponent;
        polynomial.addTerm(coefficient, exponent);
    }

    polynomial.normalize();
    return polynomial;
}

int main() {
    Polynomial a = readPolynomial();
    Polynomial b = readPolynomial();

    Polynomial sum = a.add(b);
    Polynomial difference = a.subtract(b);

    a.print("A");
    b.print("B");
    sum.print("A+B");
    difference.print("A-B");

    return 0;
}

示例输入：

3
3 4
-2 2
5 0
3
1 3
2 2
-5 0

示例输出：

A = 3.00x^4 - 2.00x^2 + 5.00
B = 1.00x^3 + 2.00x^2 - 5.00
A+B = 3.00x^4 + 1.00x^3
A-B = 3.00x^4 - 1.00x^3 - 4.00x^2 + 10.00

6.3 C59 手机斗地主游戏

题目要求：

1. 生成一副 54 张牌并洗牌。
2. 给三名玩家发牌，保留 3 张底牌。
3. 能识别常见牌型：单牌、对子、三张、顺子、炸弹、王炸。
4. 输入上一手牌和当前手牌，判断当前手牌能否压过上一手牌。

#include <algorithm>
#include <ctime>
#include <iostream>
#include <map>
#include <random>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

enum class Kind {
    Invalid,
    Pass,
    Single,
    Pair,
    Triple,
    Straight,
    Bomb,
    Rocket
};

struct Card {
    int rank;
    string name;
};

struct HandInfo {
    Kind kind = Kind::Invalid;
    int mainRank = 0;
    int length = 0;
};

string kindName(Kind kind) {
    switch (kind) {
        case Kind::Pass: return "不出";
        case Kind::Single: return "单牌";
        case Kind::Pair: return "对子";
        case Kind::Triple: return "三张";
        case Kind::Straight: return "顺子";
        case Kind::Bomb: return "炸弹";
        case Kind::Rocket: return "王炸";
        default: return "无效牌型";
    }
}

vector<Card> buildDeck() {
    vector<Card> deck;
    vector<pair<int, string>> ranks = {
        {3, "3"}, {4, "4"}, {5, "5"}, {6, "6"}, {7, "7"},
        {8, "8"}, {9, "9"}, {10, "10"}, {11, "J"}, {12, "Q"},
        {13, "K"}, {14, "A"}, {15, "2"}
    };

    for (const auto& [rank, name] : ranks) {
        for (int i = 0; i < 4; i++) {
            deck.push_back({rank, name});
        }
    }

    deck.push_back({16, "SJ"});
    deck.push_back({17, "BJ"});
    return deck;
}

int nameToRank(const string& name) {
    static map<string, int> rankMap = {
        {"3", 3}, {"4", 4}, {"5", 5}, {"6", 6}, {"7", 7},
        {"8", 8}, {"9", 9}, {"10", 10}, {"J", 11}, {"Q", 12},
        {"K", 13}, {"A", 14}, {"2", 15}, {"SJ", 16}, {"BJ", 17}
    };

    auto it = rankMap.find(name);
    if (it == rankMap.end()) {
        return -1;
    }
    return it->second;
}

string rankToName(int rank) {
    static map<int, string> nameMap = {
        {3, "3"}, {4, "4"}, {5, "5"}, {6, "6"}, {7, "7"},
        {8, "8"}, {9, "9"}, {10, "10"}, {11, "J"}, {12, "Q"},
        {13, "K"}, {14, "A"}, {15, "2"}, {16, "SJ"}, {17, "BJ"}
    };
    return nameMap[rank];
}

vector<int> parseRanks(const string& line) {
    vector<int> ranks;
    string token;
    stringstream stream(line);

    while (stream >> token) {
        if (token == "N" || token == "n") {
            ranks.clear();
            return ranks;
        }

        int rank = nameToRank(token);
        if (rank == -1) {
            return {-1};
        }
        ranks.push_back(rank);
    }

    sort(ranks.begin(), ranks.end());
    return ranks;
}

HandInfo judge(vector<int> ranks) {
    if (ranks.empty()) {
        return {Kind::Pass, 0, 0};
    }
    if (ranks.size() == 1 && ranks[0] == -1) {
        return {Kind::Invalid, 0, 0};
    }

    sort(ranks.begin(), ranks.end());
    int n = static_cast<int>(ranks.size());

    if (n == 1) {
        return {Kind::Single, ranks[0], n};
    }

    if (n == 2 && ranks[0] == 16 && ranks[1] == 17) {
        return {Kind::Rocket, 17, n};
    }

    bool same = all_of(ranks.begin(), ranks.end(), [&](int rank) {
        return rank == ranks[0];
    });

    if (n == 2 && same) {
        return {Kind::Pair, ranks[0], n};
    }
    if (n == 3 && same) {
        return {Kind::Triple, ranks[0], n};
    }
    if (n == 4 && same) {
        return {Kind::Bomb, ranks[0], n};
    }

    bool straight = n >= 5 && ranks.back() < 15;
    for (int i = 1; i < n && straight; i++) {
        if (ranks[i] != ranks[i - 1] + 1) {
            straight = false;
        }
    }
    if (straight) {
        return {Kind::Straight, ranks.back(), n};
    }

    return {Kind::Invalid, 0, n};
}

bool canBeat(const HandInfo& current, const HandInfo& previous) {
    if (current.kind == Kind::Invalid || current.kind == Kind::Pass) {
        return false;
    }
    if (previous.kind == Kind::Invalid) {
        return false;
    }
    if (previous.kind == Kind::Pass) {
        return true;
    }
    if (current.kind == Kind::Rocket) {
        return previous.kind != Kind::Rocket;
    }
    if (previous.kind == Kind::Rocket) {
        return false;
    }
    if (current.kind == Kind::Bomb && previous.kind != Kind::Bomb) {
        return true;
    }
    if (current.kind != previous.kind || current.length != previous.length) {
        return false;
    }
    return current.mainRank > previous.mainRank;
}

void printCards(const vector<Card>& cards) {
    for (const Card& card : cards) {
        cout << card.name << " ";
    }
    cout << endl;
}

int main() {
    vector<Card> deck = buildDeck();
    mt19937 randomEngine(static_cast<unsigned int>(time(nullptr)));
    shuffle(deck.begin(), deck.end(), randomEngine);

    vector<Card> players[3];
    vector<Card> bottomCards;

    for (int i = 0; i < 51; i++) {
        players[i % 3].push_back(deck[i]);
    }
    for (int i = 51; i < 54; i++) {
        bottomCards.push_back(deck[i]);
    }

    for (int i = 0; i < 3; i++) {
        sort(players[i].begin(), players[i].end(), [](const Card& a, const Card& b) {
            return a.rank < b.rank;
        });
        cout << "Player " << i + 1 << ": ";
        printCards(players[i]);
    }

    cout << "Bottom cards: ";
    printCards(bottomCards);

    cout << "\n输入牌面时用空格分隔，例如：3 4 5 6 7，王用 SJ BJ，不出用 N。" << endl;

    string previousLine;
    string currentLine;
    cout << "上一手牌：";
    getline(cin >> ws, previousLine);
    cout << "当前手牌：";
    getline(cin, currentLine);

    HandInfo previous = judge(parseRanks(previousLine));
    HandInfo current = judge(parseRanks(currentLine));

    cout << "上一手牌型：" << kindName(previous.kind) << endl;
    cout << "当前牌型：" << kindName(current.kind) << endl;

    if (canBeat(current, previous)) {
        cout << "当前手牌可以压过上一手。" << endl;
    } else {
        cout << "当前手牌不能压过上一手。" << endl;
    }

    return 0;
}

示例：

上一手牌：7 8 9 10 J
当前手牌：8 9 10 J Q

输出：

上一手牌型：顺子
当前牌型：顺子
当前手牌可以压过上一手。

7、课程外延

同期实践周报告还整理了机器学习基础、阿尔茨海默病预测、模型后门和数据投毒等主题。这部分不是三项课程设计的核心实现，但体现了当时已经开始关注计算机视觉与安全方向。

8、个人复盘

1. 同一道题可以有多种正确方案，复杂度和测试数据决定方案是否真正可用。
2. 链表题的难点常在边界和内存管理，而不是主体循环。
3. 游戏规则需要先建模再编码，否则判断逻辑很快会互相缠绕。
4. 原报告已经具备算法说明和测试意识；现在回看，最值得继续优化的是单元测试、模块边界和更清晰的命名。