北海网站网站建设,湖南网站网络推广哪家奿,wordpress4.8.3中文,合肥网站建设pqiw文章目录 对称矩阵构造与析构下标访问的实现输入输出删除行列插入行列 无向图数据结构构造与析构图的顶点数特殊顶点的操作查找顶点第i个顶点的第1个邻接顶点第i个顶点的下一个邻接顶点 插入顶点删除顶点输入与输出 采用形式化的定义#xff0c;图 G G G由两个集合 V V V和 E … 文章目录 对称矩阵构造与析构下标访问的实现输入输出删除行列插入行列 无向图数据结构构造与析构图的顶点数特殊顶点的操作查找顶点第i个顶点的第1个邻接顶点第i个顶点的下一个邻接顶点 插入顶点删除顶点输入与输出 采用形式化的定义图 G G G由两个集合 V V V和 E E E组成记为 G ( V , E ) G(V,E) G(V,E)其中 V V V是顶点的有限集合记为 V ( G ) V(G) V(G) E E E是连接 V V V中两个不同顶点(顶点对)的边的有限集合记为 E ( G ) E(G) E(G)。如果在图 G G G中若 i , j ∈ E ( G ) i,j\in E(G) i,j∈E(G)必有 j , i ∈ E ( G ) j,i\in E(G) j,i∈E(G)即 E ( G ) E(G) E(G)是对称的则用 ( i , j ) (i,j) (i,j)代替这两个顶点对表示顶点 i i i与顶点 j j j的一条无向边则称 G G G为无向图。
图的存储结构除了要存储图中各个顶点本身的信息以外同时还要存储顶点与顶点之间的所有关系(边的信息)。常用的图的存储结构有邻接矩阵和邻接表。由于图的结构是未知的出于节省存储空间的考虑采用邻接矩阵作为物理存储结构。
对称矩阵
由于考虑的是特殊的图——无向图其邻接矩阵是一个对角线全为0的对称矩阵。因此真正起作用的部分只有对角线上方的元素若直接使用二维数组处理邻接矩阵将造成巨大的空间浪费。因此有必要专门写一个“对称矩阵”类。
构造与析构
由于C语言只提供了数组这种底层结构并没有“上三角形”结构因此从第一行开始逐个元素存入数组即可。1此外为了后续程序的方便补写了一个对角元素的静态数据成员并赋值为0。2
template typename T
class sy_mat
{ // 为了方便存取数据补全对角线元素但声明为静态数据成员static T diag; // 对角线元素的值默认为0T *a;unsigned n;sy_mat(T *p, unsigned m) : a(p), n(m) {}public:sy_mat() : a(nullptr), n(0) {}~sy_mat(){if (a)delete[] a;}sy_mat(const sy_mat x){if (x.a){T *p(x.a);*(a new T[n x.n]) *p;while (--n)*a *p;a - n x.n;}else{n 0;a nullptr;}}sy_mat(unsigned k) : n(k), a(new T[k * (k - 1) / 2]){if (n 1)a nullptr;}sy_mat operator(const sy_mat x){if (a)delete[] a;if (!x.a){a nullptr;n x.n;return *this;}T *p(x.a);*(a new T[n x.n]) *p;while (--n)*a *p;a - n x.n;return *this;}
};
template typename T
T sy_matT::diag 0;下标访问的实现
由于人为地将上三角强制存入了一维数组因此需要给出计算给定行列返回元素值的函数。设 a i j a_{ij} aij为第 i i i行第 j j j列元素到第一个实际上存储的元素(即 a 12 a_{12} a12)的距离。当 i j ij ij时 a i j ∑ k n − i 1 n − 1 k j − i − 1 n ( i − 1 ) − i ( i 1 ) 2 j − 1 a_{ij}\sum\limits_{kn-i1}^{n-1}kj-i-1n(i-1)-\dfrac{i(i1)}2j-1 aijkn−i1∑n−1kj−i−1n(i−1)−2i(i1)j−1当 i j ij ij时返回diag即可当 i j ij ij时利用矩阵的对称性 a i j a j i n ( j − 1 ) − j ( j 1 ) 2 i − 1 a_{ij}a_{ji}n(j-1)-\dfrac{j(j1)}2i-1 aijajin(j−1)−2j(j1)i−1。由于此函数将会很常用因此重载了函数调用运算符()方便后续的操作。
inline const T operator()(unsigned i, unsigned j) const
{ // 以上三角形式存储节省存储空间if (i j)return diag;if (i j)return a[n * (j - 1) - j * (j 1) / 2 i - 1];return a[n * (i - 1) - i * (i 1) / 2 j - 1];
}
inline T operator()(unsigned i, unsigned j)
{if (i j)return diag;if (i j)return a[n * (j - 1) - j * (j 1) / 2 i - 1];return a[n * (i - 1) - i * (i 1) / 2 j - 1];
}输入
从存储结构很容易发现同一行的元素在物理存储结构上是相邻的因此在用户输入矩阵的时候只需要将上三角的数据用指针循环存储到数组中即可。此外还特例化了unsigned char类型的输入。3程序如下
template typename T
std::istream operator(std::istream c, sy_matT x)
{std::cout 请输入矩阵阶数:\n;c x.n;if (x.a)delete[] x.a;if (x.n 1){x.a nullptr;return c;}std::cout 请输入矩阵: std::endl;T *p(x.a new T[x.n * (x.n - 1)]), tem;for (unsigned i(1); i x.n; i)for (unsigned j(1); j x.n; j)if (i j)c *p;elsec tem;for (unsigned i(0); i x.n; i)c tem;return c;
}
std::istream operator(std::istream c, sy_matunsigned char x)
{std::cout 请输入矩阵阶数:\n;c x.n;if (x.a)delete[] x.a;if (x.n 1){x.a nullptr;return c;}std::cout 请输入矩阵: std::endl;unsigned char *p(x.a new unsigned char[x.n * (x.n - 1)]);unsigned short tem;for (unsigned i(1); i x.n; i)for (unsigned j(1); j x.n; j){c tem;if (i j)*p tem;}for (unsigned i(0); i x.n; i)c tem;return c;
}输出
由于物理存储结构与矩阵的逻辑结构上有较大差距因此利用下标元素访问的方式套用两层循环来实现输出。程序如下
template typename T
std::ostream operator(std::ostream c, const sy_matT x)
{if (!x.n){c \t[空] std::endl;return c;}if (x.n 1){c 0 std::endl;return c;}for (unsigned i(1); i x.n; i){for (unsigned j(1); j x.n; j)c x(i, j) \t;c std::endl;}return c;
}
std::ostream operator(std::ostream c, const sy_matunsigned char x)
{if (!x.n){c \t[空] std::endl;return c;}if (x.n 1){c 0 std::endl;return c;}for (unsigned i(1); i x.n; i){for (unsigned j(1); j x.n; j)c short(x(i, j)) \t;c std::endl;}return c;
}删除行列
对于一个数学结构来说矩阵删除行列的操作是必要的。4但是为了保持矩阵的对称性删除一行的同时也需要删除一列。因此删除后的数组大小为 ( n − 1 ) ( n − 2 ) 2 \dfrac{(n-1)(n-2)}2 2(n−1)(n−2)依次赋值即可。程序如下
sy_mat del(unsigned k) // 删除第k行及第k列
{if (!k || k n || !n)return *this;if (n 1){--n;return *this;}if (n 2){delete[] a;--n;a nullptr;return *this;}T *p(new T[(n - 2) * (n - 1) / 2]), *q(p);for (unsigned i(1); i n; i)for (unsigned j(1); j n; j)if (i j i ! k j ! k)*q this-operator()(i, j);a p;--n;return *this;
}插入行列
对应地有删除行列就有插入行列。5插入后的数组大小为 n ( n 1 ) 2 \dfrac{n(n1)}2 2n(n1)依次赋值即可。程序如下
sy_mat add(unsigned k, T *b nullptr)
{ // 将b数组插入到第k1行列if (k n)k n;if (n 1)return *this;T *p(a), *q(a new T[n * (n - 1) / 2]), *t(p);if (b){for (unsigned i(1); i n; i)for (unsigned j(1); j n; j)if (i j)if (i k || j k)*q *b;else*q *p;}elsefor (unsigned i(1); i n; i)for (unsigned j(1); j n; j)if (i j)if (i k || j k)*q 0;else*q *p;if (n ! 2)delete[] t;return *this;
}无向图数据结构
构造与析构
由图的定义可知图 G ( V , E ) G(V,E) G(V,E)。其中 V V V是顶点的有限集合记为 V ( G ) V(G) V(G)用一个长度为n的数组存储 E E E是连接 V V V中两个不同顶点(顶点对)的边的有限集合记为 E ( G ) E(G) E(G)用邻接矩阵存储。由于领接矩阵类包含了n为了避免空间浪费不再单独设置长度变量来存储顶点数。程序如下
#include sy_mat.h
template typename T, typename U unsigned char
class graph
{T *node; // 顶点sy_matU W; // 邻接矩阵
public:graph() : node(nullptr) {}~graph(){if (node)delete[] node;}graph(const graph x) : W(x.W){if (W.n){T *p(x.node);*(node new T[W.n]) *p;while (--W.n)*node *p;node - W.n x.W.n;}elsenode nullptr;}graph operator(const graph x){W x.W;if (node)delete[] node;if (!x.node){node nullptr;return *this;}T *p(x.node);*(node new T[W.n]) *p;while (--W.n)*node *p;node - W.n x.W.n;return *this;}inline T operator[](unsigned i) { return node[--i]; }inline const T operator[](unsigned i) const { return node[--i]; }inline U operator()(unsigned i, unsigned j){if (i j)return sy_matU::diag;if (i j)return W.a[W.n * (j - 1) - j * (j 1) / 2 i - 1];return W.a[W.n * (i - 1) - i * (i 1) / 2 j - 1];}inline const U operator()(unsigned i, unsigned j) const{if (i j)return sy_matU::diag;if (i j)return W.a[W.n * (j - 1) - j * (j 1) / 2 i - 1];return W.a[W.n * (i - 1) - i * (i 1) / 2 j - 1];}
};图的顶点数
直接返回领接矩阵的阶数即可。程序如下
inline unsigned size() const { return W.n; }特殊顶点的操作
查找顶点
给定一个元素值查找顶点所在位置下标同线性表。程序如下
unsigned locateVex(T x) const
{T *p(node);unsigned k(1);if (*p x)return k;while (k W.n)if (*p x)return k;return 0;
}第i个顶点的第1个邻接顶点
unsigned firstAdjVex(unsigned i) const
{for (unsigned j(1); j W.n; j)if (W(i, j))return j;return 0;
}第i个顶点的下一个邻接顶点
unsigned nextAdjVex(unsigned i) const
{for (unsigned j(i 1); j W.n; j)if (W(i, j))return j;return 0;
}插入顶点
graph insertnode(unsigned k, T value, U *w nullptr)
{unsigned n((W.add(k, w)).n);T *p(node), *q(node new T[n]), *t(p);if (k n)k n;n - k;while (--k)*q *p;*q value;while (n--)*q *p;delete[] t;return *this;
}删除顶点
graph deletenode(unsigned k)
{unsigned n(W.n);if (!k || k n || !n)return *this;W.del(k);if (!n){delete[] node;return *this;}T *p(node), *q(node new T[n]), *t(p);n - k;while (--k)*q *p;while (--n)*q *p;delete[] t;return *this;
}输入与输出
直接让用户输入顶点集和领接矩阵。但是由于领接矩阵元素类型有可能为unsigned char因此利用C语言中的concepts和type_traits来判断类型。6
#include concepts
#include type_traits
template typename T, typename U
std::istream operator(std::istream c, graphT, U x)
{std::cout 请输入顶点数:\n;c x.W.n;std::cout 请输入顶点:\n;if (x.node)delete[] x.node;T *p(x.node new T[x.W.n]);for (unsigned i(0); i x.W.n; i)c *p;std::cout 请输入邻接矩阵:\n;if (x.W.a)delete[] x.W.a;if (x.W.n 1){x.W.a nullptr;return c;}U *q(x.W.a new U[x.W.n * (x.W.n - 1)]);if (std::is_same_vU, unsigned char){unsigned short tem;for (unsigned i(1); i x.W.n; i)for (unsigned j(1); j x.W.n; j){c tem;if (i j)*q tem;}for (unsigned i(0); i x.W.n; i)c tem;}else{U tem;for (unsigned i(1); i x.W.n; i)for (unsigned j(1); j x.W.n; j)if (i j)c *q;elsec tem;for (unsigned i(0); i x.W.n; i)c tem;}return c;
}
template typename T, typename U
std::ostream operator(std::ostream c, const graphT, U x)
{if (!x.W.n){c \t[空] std::endl;return c;}if (x.W.n 1){c 顶点:\n *x.node std::endl;return c;}c 顶点:\n;unsigned m(x.W.n);T *p(x.node);doc *p \t;while (--m);c \n邻接矩阵:\n x.W;return c;
}此时数组的大小为 ∑ i 1 n − 1 i ( n − 1 ) n 2 \sum\limits_{i1}^{n-1}i\dfrac{(n-1)n}2 i1∑n−1i2(n−1)n。 ↩︎ 也可以是当前数据类型中可能的最大值代表无穷。 ↩︎ 防止其直接进行字符输入。 ↩︎ 对应到图中就是删除其中一个顶点。 ↩︎ 对应到图中就是插入一个顶点。 ↩︎ 这是由于C语言不支持函数模板偏特化因此不能直接重写函数如下templatetypename Tstd::istream operator(std::istream c, graphT, unsigned char x)。 ↩︎
