数据结构实验报告

环境：CLion

Cpp1过于没用不传了

#include <iostream>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

string infixToPostfix(const string &infix) {
    stack<char> s;
    string postfix;

    for (char ch : infix) {
        if (isdigit(ch)) {
            postfix += ch;
        } else if (ch == '(') {
            s.push(ch);
        } else if (ch == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();  // pop '('
        } else {
            while (!s.empty() && precedence(s.top()) >= precedence(ch)) {
                postfix += s.top();
                s.pop();
            }
            s.push(ch);
        }
    }

    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }

    return postfix;
}

int evaluatePostfix(const string &postfix) {
    stack<int> s;

    for (char ch : postfix) {
        if (isdigit(ch)) {
            s.push(ch - '0');
        } else {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();

            switch (ch) {
                case '+': s.push(a + b); break;
                case '-': s.push(a - b); break;
                case '*': s.push(a * b); break;
                case '/': s.push(a / b); break;
            }
        }
    }

    return s.top();
}

int main() {
    string infix;
    cout << "Enter infix expression: ";
    getline(cin, infix);

    string postfix = infixToPostfix(infix);
    cout << "Postfix expression: " << postfix << endl;

    int result = evaluatePostfix(postfix);
    cout << "Result: " << result << endl;

    return 0;
}

实验3

#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <sstream>

using namespace std;

struct TreeNode {
    string name;
    int count;
    vector<TreeNode*> children;
};

map<string, TreeNode*> nodesMap;

TreeNode* getNode(string name) {
    if(nodesMap.find(name) == nodesMap.end()) {
        nodesMap[name] = new TreeNode{name, 0};
    }
    return nodesMap[name];
}

void buildTree(string filename) {
    ifstream infile(filename);
    if (!infile.is_open()) {
        cerr << "Could not open file: " << filename << endl;
        exit(EXIT_FAILURE);
    }
    string line;
    while(getline(infile, line)) {
        stringstream ss(line);
        string parentName, childName;
        int count;
        ss >> parentName >> count >> childName;
        TreeNode* parentNode = getNode(parentName);
        TreeNode* childNode = getNode(childName);
        parentNode->children.push_back(childNode);
        parentNode->count += count;
    }
    infile.close();
}

void queryTree(string filename) {
    ifstream infile(filename);
    if (!infile.is_open()) {
        cerr << "Could not open file: " << filename << endl;
        exit(EXIT_FAILURE);
    }
    string line;
    while(getline(infile, line)) {
        stringstream ss(line);
        string operation, target;
        ss >> operation;
        if(operation == "whatis") {
            ss >> target;
            TreeNode* node = getNode(target);
            cout << "Part " << target << " subparts are:" << endl;
            for(auto& child : node->children) {
                cout << "      " << child->count << " " << child->name << endl;
            }
        } else if(operation == "howmany") {
            string child;
            ss >> child >> target;
            // Additional logic to calculate count based on child and target
            // You may need to implement a function to recursively count the specified child nodes
        }
    }
    infile.close();
}


int main() {
    buildTree("D:\\Learn\\CPP2\\definitions.txt");
    queryTree("D:\\Learn\\CPP2\\queries.txt");
    return 0;
}

实验四

#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <set>
#include <limits>

using namespace std;

// 城市结构
struct City {
    string name;
    unordered_map<string, pair<int, int>> neighbors; // 与该城市相邻的其他城市 -> {费用, 距离}
};

// 图类
class Graph {
public:
    // 向图中添加城市
    void addCity(const string& cityName) {
        if (cities.find(cityName) == cities.end()) {
            cities[cityName] = City{cityName, unordered_map<string, pair<int, int>>()};
        }
    }

    // 向图中添加路线
    void addRoute(const string& city1, const string& city2, int cost, int distance) {
        cities[city1].neighbors[city2] = {cost, distance};
        cities[city2].neighbors[city1] = {cost, distance};
    }

    // 使用Dijkstra算法找到两个城市之间的最低费用路径
    pair<int, string> shortestPath(const string& start, const string& end) {
        unordered_map<string, int> dist;      // 距离映射
        unordered_map<string, string> prev;   // 前一个城市映射
        set<pair<int, string>> queue;         // 用于排序的队列

        for (auto& pair : cities) {
            if (pair.first == start) {
                dist[pair.first] = 0;
            } else {
                dist[pair.first] = numeric_limits<int>::max();
            }
            queue.insert({dist[pair.first], pair.first});
        }

        while (!queue.empty()) {
            string current = queue.begin()->second;
            queue.erase(queue.begin());

            for (auto& neighbor : cities[current].neighbors) {
                int alt = dist[current] + neighbor.second.first; // 以费用为优先级
                if (alt < dist[neighbor.first]) {
                    queue.erase({dist[neighbor.first], neighbor.first});
                    dist[neighbor.first] = alt;
                    prev[neighbor.first] = current;
                    queue.insert({dist[neighbor.first], neighbor.first});
                }
            }
        }

        // 构建路径
        string city = end;
        string path = end;
        while (prev.find(city) != prev.end()) {
            path = prev[city] + " -> " + path;
            city = prev[city];
        }

        return {dist[end], path};
    }

private:
    unordered_map<string, City> cities; // 城市映射
};

int main() {
    Graph graph;

    // 从文件中读取城市数据
    ifstream infile("D:\\Learn\\CPP2\\services.txt");
    string city1, city2;
    int cost, distance;

    while (infile >> city1 >> city2 >> cost >> distance) {
        graph.addCity(city1);
        graph.addCity(city2);
        graph.addRoute(city1, city2, cost, distance);
    }
    infile.close();

    // 输入起始城市和目标城市
    string start, end;
    cout << "Enter a start and destination city: ";
    cin >> start >> end;

    // 查找最短路径并打印
    auto result = graph.shortestPath(start, end);
    cout << "The cheapest route from " << start << " to " << end << " costs " << result.first << " euros." << endl;
    cout << "Route: " << result.second << endl;

    return 0;
}