本站使用了 Pjax 等基于 JavaScript 的开发技术,但您的浏览器已禁用 JavaScript,请开启 JavaScript 以保证网站正常显示!

写一个图类


layout: post
title: 写一个图类
tags:

  • Traffic-Network-Model

categories: 日记
abbrlink: e75e

date: 2017-10-15 08:28:27

说到交通网路的模拟化表示,那就不得不用到数据结构中的图。想必这应该是最方便形象的表示方法了把。

图的概念

    图是由顶点集合及顶点之间关系的集合组成的一种数据结构,Graph = (V,E)。其中顶点集合V = { x | x ∈ 某个数据对象集}是个有穷非空集合。E = {< x , y > | x , y ∈ V && Path( x , y )}

        </span></span></p><p><span style="font-size:12pt;"><span style="font-family:等线;">,即边集。</span><span style="font-family:宋体;">
        </span></span></p><h3>我所知的图的存储结构 

邻接矩阵表示

邻接矩阵的表示,首先将所有的顶点信息组成一个表。然后利用一个矩阵来表示各顶点之间的相邻关系,称之为邻接矩阵。

邻接表表示

在第i行的单链表中,各节点(或称边节点)分别存放与同一个顶点Vi关联的各条边。各个节点配有其标识(及对应的顶点)和权值(若为有权图)以及指向另一个边节点的指针。

*邻接多重表表示

邻接多重表的表示,主要一处理图的边为主(为什么会有这个需求?在什么情况会用到?),要求每条边处理一次的实际应用中特别有用(比如?)。它的主要思想是把多重表结构引入到图的邻接表中,就有点像把边作为研究的基本单位,用一个多重表节点来表示一条边。

*十字链表表示

此为百度词条:十字链表(Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图,可以达到高效的存取效果。同时,代码的可读性也会得到提升。

    </span></p><p style="margin-left:51pt;"><img src="http://thinkmoonmagic.files.wordpress.com/2017/09/091617_1416_1.jpg" alt="" /><span style="font-family:宋体;font-size:12pt;">
    </span></p><h3>我该选什么存储结构 

    首先,交通道路网络是双向的,所以我们可以将其视为无向图; 其次在一座城市的交通网络下,道路E 与路口 n的关系是 E << n^2,而且道路是会出现两点之间多条路的情况(即多重图)所以我舍弃第一种方法; 后面两种表示方式其实我也是一知半解,我有种感觉,如果在交通道路的分层模型下,可能第三种方式要更具优势,但是目前还想不了那么远。所以我暂时选用第二种方式,用邻接表表示。

我的实现代码

Graph_lnk.h // V1.0.1

  1. #  pragma once

                            </span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;"># include < iostream > <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">using namespace std;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:#006699;"><span style="font-family:Consolas;font-size:9pt;"><strong>const</strong><span style="color:black;"> <span style="color:#006699;"><strong>int</strong><span style="color:black;"> DefaultMaxVertices = 500; <span style="color:#008200;">//</span></span></span></span></span><span style="color:#006699;"><span style="font-family:微软雅黑;font-size:9pt;">最大顶点数</span><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">  <span style="color:#5c5c5c;">
                                </span></span>
                        </span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">auto memory_error = [](<span style="color:#006699;"><strong>const</strong><span style="color:black;"> <span style="color:#006699;"><strong>char</strong><span style="color:black;"> * <span style="color:#006699;"><strong>function</strong><span style="color:black;">, string aim) {  <span style="color:#5c5c5c;">
                                                </span></span></span></span></span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    cerr << <span style="color:#006699;"><strong>function</strong><span style="color:black;"> << <span style="color:blue;">"</span></span></span></span><span style="color:black;"><span style="font-family:微软雅黑;font-size:9pt;">申请</span><span style="color:blue;"><span style="font-size:9pt;"><span style="font-family:Consolas;">"<span style="color:black;"> << aim.c_str() << <span style="color:blue;">"</span></span></span><span style="font-family:微软雅黑;">内存分配错误</span><span style="font-family:Consolas;">"<span style="color:black;"> << endl;  <span style="color:#5c5c5c;">
                                        </span></span></span></span>
                        </span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    exit(1);  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">}; <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-family:微软雅黑;font-size:9pt;">内存申请错误的提示</span><span style="color:#008200;"><span style="font-size:9pt;"><span style="font-family:Consolas;">lamba</span><span style="font-family:微软雅黑;">表达式</span></span><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">  <span style="color:#5c5c5c;">
                                    </span></span>
                            </span></span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">struct Edge {  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>int</strong><span style="color:black;"> dest; <span style="color:#008200;">//</span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">标记关系节点</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>double</strong><span style="color:black;"> weight; <span style="color:#008200;">//</span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">权值</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Edge * link; <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">指向边的指针</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Edge(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> num, <span style="color:#006699;"><strong>double</strong><span style="color:black;"> weight): dest(num), weight(weight), link(nullptr) {}  <span style="color:#5c5c5c;">
                                        </span></span></span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">struct Vertex {  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    string data; <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-family:微软雅黑;font-size:9pt;">道路口的信息,暂时用</span><span style="color:#008200;"><span style="font-family:Consolas;font-size:9pt;">string<span style="color:black;">  <span style="color:#5c5c5c;">
                                    </span></span></span>
                        </span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Edge * adj; <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">指向边的指针</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Vertex(string data = <span style="color:blue;">"</span></span><span style="color:black;"><span style="font-family:微软雅黑;font-size:9pt;">点</span><span style="color:blue;"><span style="font-family:Consolas;font-size:9pt;">"<span style="color:black;">): data(data), adj(nullptr) {}  <span style="color:#5c5c5c;">
                                    </span></span></span>
                        </span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:#006699;"><span style="font-family:Consolas;font-size:9pt;"><strong>class</strong><span style="color:black;"> Graph_lnk {  <span style="color:#5c5c5c;">
                            </span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    friend ostream & operator << (ostream & <span style="color:#006699;"><strong>in</strong><span style="color:black;"> , Graph_lnk & G); <span style="color:#008200;">//</span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">运算符重载,图的输出</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>public</strong><span style="color:black;">: Graph_lnk(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> sv = DefaultMaxVertices);  <span style="color:#5c5c5c;">
                                        </span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    ~Graph_lnk();  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>int</strong><span style="color:black;"> NumberOfVertices() {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>return</strong><span style="color:black;"> numVertices;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">返回当前顶点数</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>int</strong><span style="color:black;"> NumberOfEdges() {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>return</strong><span style="color:black;"> numEdges;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">返回当前边数</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Vertex getVertex(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> v) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>return</strong><span style="color:black;"> NodeTable[v];  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">返回该节点</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    string getValue(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> v) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>return</strong><span style="color:black;"> NodeTable - > data;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">返回道路信息</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    bool insertEdge(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> v1, <span style="color:#006699;"><strong>int</strong><span style="color:black;"> v2, <span style="color:#006699;"><strong>double</strong><span style="color:black;"> weight); <span style="color:#008200;">//</span></span></span></span></span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">插入一条边</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    bool insertVertex(string data); <span style="color:#008200;">//</span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">插入一个路口</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>protected</strong><span style="color:black;">: <span style="color:#006699;"><strong>int</strong><span style="color:black;"> numVertices; <span style="color:#008200;">//</span></span></span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">当前顶点数</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>int</strong><span style="color:black;"> numEdges; <span style="color:#008200;">//</span></span></span></span><span style="color:black;"><span style="font-size:9pt;"><span style="font-family:微软雅黑;">当前边数</span><span style="font-family:Consolas;">  <span style="color:#5c5c5c;">
                                </span></span></span>
                    </span></span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>private</strong><span style="color:black;">: Vertex * NodeTable;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">ostream & operator << (ostream & out, Graph_lnk & G) {  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    out << <span style="color:blue;">"--------------------------------------------"<span style="color:black;"> << endl;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    out << <span style="color:blue;">"</span></span><span style="color:black;"><span style="font-family:微软雅黑;font-size:9pt;">当前顶点数</span><span style="color:blue;"><span style="font-size:9pt;"><span style="font-family:Consolas;">"<span style="color:black;"> << G.NumberOfVertices() << <span style="color:blue;">",</span></span></span><span style="font-family:微软雅黑;">边数</span><span style="font-family:Consolas;">"<span style="color:black;"> << G.NumberOfEdges() << endl;  <span style="color:#5c5c5c;">
                                        </span></span></span></span>
                        </span></span></span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    Edge * p = nullptr;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>for</strong><span style="color:black;"> (<span style="color:#006699;"><strong>int</strong><span style="color:black;"> i = 0; i < G.NumberOfVertices(); i++) {  <span style="color:#5c5c5c;">
                                        </span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        Vertex v = G.getVertex(i);  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        out << v.data.c_str() << <span style="color:blue;">" "<span style="color:black;">;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        p = v.adj;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        <span style="color:#006699;"><strong>while</strong><span style="color:black;"> (p != nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            out << <span style="color:blue;">"->{"<span style="color:black;"> << p - > dest << <span style="color:blue;">":"<span style="color:black;"> << p - > weight << <span style="color:blue;">"}"<span style="color:black;">;  <span style="color:#5c5c5c;">
                                                </span></span></span></span></span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            p = p - > link;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        out << endl;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    out << <span style="color:blue;">"--------------------------------------------"<span style="color:black;"> << endl;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>return</strong><span style="color:black;"> out;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">Graph_lnk::Graph_lnk(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> sv) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    numVertices = sv;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    numEdges = 0;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    NodeTable = <span style="color:#006699;"><strong>new</strong><span style="color:black;"> Vertex[DefaultMaxVertices];  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>if</strong><span style="color:black;"> (NodeTable == nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        memory_error(__func__, <span style="color:blue;">"NodeTable"<span style="color:black;">);  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>for</strong><span style="color:black;"> (<span style="color:#006699;"><strong>int</strong><span style="color:black;"> i = 0; i < sv; i++) NodeTable[i].adj = nullptr;  <span style="color:#5c5c5c;">
                                        </span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">bool Graph_lnk::insertEdge(<span style="color:#006699;"><strong>int</strong><span style="color:black;"> v1, <span style="color:#006699;"><strong>int</strong><span style="color:black;"> v2, <span style="color:#006699;"><strong>double</strong><span style="color:black;"> weight) {  <span style="color:#5c5c5c;">
                                                </span></span></span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>if</strong><span style="color:black;"> (v1 >= 0 && v1 < numVertices && v2 >= 0 && v2 < numVertices && v1 != v2) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        Edge * q = nullptr, * p = nullptr;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        <span style="color:#006699;"><strong>if</strong><span style="color:black;"> (NodeTable[v1].adj != nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            p = NodeTable[v1].adj;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            q = p - > link;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>while</strong><span style="color:black;"> (q != nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">                p = q;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">                q = p - > link;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            q = <span style="color:#006699;"><strong>new</strong><span style="color:black;"> Edge(v2, weight);  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            p - > link = q;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#006699;"><strong>else</strong><span style="color:black;"> {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            NodeTable[v1].adj = <span style="color:#006699;"><strong>new</strong><span style="color:black;"> Edge(v2, weight);  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        <span style="color:#006699;"><strong>if</strong><span style="color:black;"> (NodeTable[v2].adj != nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            p = NodeTable[v2].adj;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            q = p - > link;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            <span style="color:#006699;"><strong>while</strong><span style="color:black;"> (q != nullptr) {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">                p = q;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">                q = p - > link;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            q = <span style="color:#006699;"><strong>new</strong><span style="color:black;"> Edge(v1, weight);  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            p - > link = q;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        } <span style="color:#006699;"><strong>else</strong><span style="color:black;"> {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">            NodeTable[v2].adj = <span style="color:#006699;"><strong>new</strong><span style="color:black;"> Edge(v1, weight);  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        numEdges++;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>return</strong><span style="color:black;"> 0;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">}  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">bool Graph_lnk::insertVertex(string data) {  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>if</strong><span style="color:black;"> (numVertices == DefaultMaxVertices) <span style="color:#006699;"><strong>return</strong><span style="color:black;"> <span style="color:#006699;"><strong>false</strong><span style="color:black;">;  <span style="color:#5c5c5c;">
                                                </span></span></span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>else</strong><span style="color:black;"> {  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        NodeTable[numVertices].data = data;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        NodeTable[numVertices].adj = nullptr;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">        numVertices++;  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    }  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>return</strong><span style="color:black;"> <span style="color:#006699;"><strong>true</strong><span style="color:black;">;  <span style="color:#5c5c5c;">
                                        </span></span></span></span></span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">}  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li><li><div style="background:white;">    

     

  2. Graph_lnk::~Graph_lnk() {  

                        </span></span>
                </span></div></li><li><div style="background:#f8f8f8;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">    <span style="color:#006699;"><strong>delete</strong><span style="color:black;">[] NodeTable;  <span style="color:#5c5c5c;">
                                </span></span></span></span>
                </span></div></li><li><div style="background:white;"><span style="color:black;"><span style="font-family:Consolas;font-size:9pt;">};  <span style="color:#5c5c5c;">
                        </span></span>
                </span></div></li></ol><h3>分析与理由 

    在交通道路网络图的构建中,一定需要的两个函数insertEdge();和insertVertex(); 我使用两个主要的数据结构,Edge(表示边),Vertex(表示点)。用它们的集合来表示整个图,这样做可以有效的利用空间?(但是还是申请了VerTex(500))

     
     

    缺陷与不足

    1. 不管你构建含多少个点的图,都需要申请固定的空间,只有当点小于而且越接近于500时空间利用率才最高。
    2. 插入边时,需要在两个点做增加,但是好像对于实际情况这样做并没有好处?
    3. 。。。。

       
       

    问题与思考

    1. 作为交通网络图,是否还需要拓展一些别的功能?
    2. 在储存的过程中,是否用bit矩阵来存储数据?
    3. 能不能在插入的过程中只新增一个点上的边?
    4. 或者直接以边为基本研究单位,来构建图类?

    心得与感悟

    • 本来以为写一个图类,会是一件比较容易的事,没想到却也花了这么久,是考虑的太多?还是基础不牢?
    • 刚开始想用模板类来表示,这样在后期数据类型拓展时比较方便,没想到却是发现一堆错误,还解决不了,最后要重新来过。
    • 基础还是要牢固才可以,现在写的东西自己都感觉境界不够,没有别人那种精妙绝伦的感觉。
    • 平常有时间多沉下心来学习,切记好高骛远,绕了一圈最后发现自己什么都不行
    • 。。。。。

    ———— 本文结束 感谢阅读 ————

推广

 继续浏览关于 的文章

 本文最后更新于:2019/10/28 17:27:51,可能因经年累月而与现状有所差异

 引用转载请注明:指尖魔法屋 > 学习笔记 > 写一个图类