数据结构与算法-图的存储,邻接矩阵,邻接表,链式前向星

  • 条件:无

  • 题目:无

  • 原理:无

  • 代码:

    /**
    * Author: Moota
    * Copyright: Moota
    * Description: Written by Moota  
     */
    #include <iostream>
    #include <iomanip>
    #include <algorithm>  //sort
    #include <map>
    #include <queue>
    #include <deque>  //双端队列,头可插,尾可插
    #include <string>
    #include <cstring>
    #include <stack>
    #include <cmath>
    #include <fstream>
    #include <ctime>
    #include <climits> //数值的限制范围
    //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
    using namespace std;
    
    class Solver {
        //通用属性
    public:
        Solver() {
            //取消和c输出输入的同步,加快读取
            ios::sync_with_stdio(false);
            cin.tie(nullptr);
            cout.tie(nullptr);
        }
    
        //通用方法
    public:
        void SaveCpp(string name) const {
    
            fstream input;
            fstream output;
    
            input.open("moota.cpp", ios::in);
            const string file = name + ".cpp";
            output.open(file.c_str(), ios::out);
    
            char c = 'O';
            while (!input.eof()) {
                input.get(c);
                output << c;
            }
    
            input.close();
            output.close();
    
        }
    
    protected:
        //待实现方法
        virtual void BeginPlay() {
    
        };
    
        virtual void Playing() {
        };
    
        virtual void EndPlay() {
        };
    public:
        //外观模式
        void Play() {
            BeginPlay();
            Playing();
            EndPlay();
        }
    };
    
    class SpecialSolver : public Solver {
    public:
        typedef long long lld;
        static const lld MAX = static_cast<lld>(1e4);
        static const lld INF = static_cast<lld>(1e18);
        //实例属性
    private:
        //int map[MAX][MAX]; 邻接矩阵
        /*
        struct Node {  邻接表
            int v;
            int w;
            Node* next;
        } * node[MAX];
    
        int n;
        //邻接表添加节点
        void AddNode(int u, int v, int w) {
            if (node[u] == nullptr) {
                node[u] = new Node{-1, 0, nullptr};
            }
            Node* temp = new Node{v, w, nullptr};
            temp->next = node[u]->next;
            node[u]->next = temp;
        }
    
        //邻接表遍历
        void Order() {
            for (int i = 1; i <= n; ++i) {
                Node* temp = node[i]->next;
                while (temp != nullptr) {
                    cout << i << "-" << temp->v << "-" << temp->w << "\n";
                    temp = temp->next;
                }
            }
        }
        */
        //链式前向星,实际就是邻接表的非链表实现
        int n, m;
        /*
         * @last 前一个 (u相同的) node结构体的下标
         * @vertex u->(不同的) v
         * @weight u->v的权值
        */
        struct Node {
            int last, vertex, weight;
        } node[MAX];
    
        //node结构体的下标
        int cnt = 0;
        //保存最后一个(u,v)node结构体的下标
        int head[MAX];
    
        void AddNode(int u, int v, int w) {
            ++cnt;
            //这里的head[u]是上的一个(u,v)node结构体的下标
            node[cnt] = {head[u], v, w};
            head[u] = cnt;
        }
    
        void Order() {
            /*1 4
            1 2 3
            1 4 5
            1 6 7
            1 8 9
            */
            for (int i = 1; i <= n; ++i) {
                for (int u = head[i]; u != 0; u = node[u].last) {
                    cout << i << "-" << node[u].vertex << "\n";
                }
            }
        }
    
        //实例方法
    private:
    protected:
        virtual void BeginPlay() override {
            Solver::BeginPlay();
            cin >> n >> m;
            int u, v, w;
            while (m--) {
                cin >> u >> v >> w;
                AddNode(u, v, w);
            }
            Order();
        };
    
        virtual void Playing() override {
            Solver::Playing();
    
        };
    
        virtual void EndPlay() override {
            Solver::EndPlay();
        };
    };
    
    SpecialSolver specialSolver;
    
    int main() {
        //注意改名字
        //specialSolver.SaveCpp("图的存储");
        specialSolver.Play();
    }
    
    
上一篇:一些递归


下一篇:RT-Thread自学(1)