Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.
由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构。
用数组分别表示存储数据元素（顶点）的信息和数据元素之间的关系（边或者弧）的信息
#define INFINITY INT_MAX //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef enum {DG,DN,UDG,UDM} GraphKind; //{有向图，有向网，无向图，无向网}
typedef struct ArcCell
{
VRType adj; //VRType是顶点关系类型，对无权图，用0/1
//表示相邻与否，对带权图则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
sypedef struct
{
VertexTypd vex[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}MGraph;
若考虑无向图的邻接矩阵的对称性，则可采用压缩存储的方式只存入矩阵的下三角（或上三角）元素。
用邻接矩阵构造图：
Status CreateGraph( MGraph &G ) {
// 采用数组(邻接矩阵)表示法，构造图G。
scanf(&G.kind); // 自定义输入函数，读入一个随机值
switch (G.kind) {
case DG: return CreateDG(G); // 构造有向图G
case DN: return CreateDN(G); // 构造有向网G
case UDG: return CreateUDG(G); // 构造无向图G
case UDN: return CreateUDN(G); // 构造无向网G，算法7.2
default : return ERROR;
}
} // CreateGraph
Status CreateUDN(MGraph &G) {
// 采用数组（邻接矩阵）表示法，构造无向网G。
int i,j,k,w;
VertexType v1,v2;
printf("G.vexnum :" ); scanf("%d",&G.vexnum);
printf("G.arcnum :"); scanf("%d",&G.arcnum);
getchar(); /*** 加上此句getchar()!!! ***/
// scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo);
for (i=0; i的权值
// if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息
G.arcs[j][i].adj = G.arcs[i][j].adj; // 置的对称弧
}
return OK;
} // CreateUDN
邻接矩阵使用方便，操作简单，但是容易浪费存储空间，如果不是稠密图，动态存储将是更好的选择。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接矩阵
int G[100][100];
int add1 (int i,int j,int w)
{
G[i][j] = w;
return 0;
}
int main()
{
int i,n;
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add1 (a,b,w);
//无向图加上
add1 (b,a,w);
}
return 0;
}
邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧。）每个结点由3个域组成，其中邻接点域指示与顶点vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息，如权值等。
每个链表上附设一个表头结点。在表头结点中，除了设有链域只想链表中第一个结点之外，还设有存储顶点vi的名或其他有关信息的数据域。
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode，AdjList[MAX_VERTEX_NUM];
sypedef struct
{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
int kind; //图的种类标志
}ALGraph;
若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏(e << (n(n-1))/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间。
邻接表可以根据邻接的是入点还是出点分为邻接表和逆邻接表，两者各有各的优势，如果经常访问下一个结点，统计出度，邻接表将有优势；如果经常访问上一个结点，统计入度，逆邻接表将有优势。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接表
struct dot
{
int d;
int w;
struct dot *next;
};
struct hed
{
int v;
struct dot *next;
}head[100];
int add2(int i,int j,int w)
{
struct dot * p;
struct dot * t = new dot;
t->d = j;
t->w = w;
t->next = NULL;
if (head[i].next == NULL)
{
head[i].next = t;
return 0;
}
p = head[i].next;
while (p->next != NULL)
p = p->next;
p->next = t;
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add2 (a,b,w);
//无向图加上
add2 (b,a,w);
}
return 0;
}
建立邻接表的时间复杂度为O（n+e）。
十字链表是有向图的另一种存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。
存储表示：
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcBox
{
int tailvex,headvex; //该弧的尾和头顶点的位置
struct ArcBox *hlink,*tlink; //分别为弧头相同和弧尾相同的弧的链域
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VexNode
{
VertexType data; //顶点信息
ArcNode *firstin，*firstout; //指向第一条依附该顶点的弧的指针
}VexNode;
sypedef struct
{
VexNode xlist[MAX_VERTEX_NUM]; //表头向量
int vexnum,arcnum; //图的当前顶点数和弧数
}OLGraph;
用十字链表建图：
Status CreateDG(OLGraph &G) {
// 采用十字链表存储表示，构造有向图G（G.kind=DG）。
//scanf(&G.vexnum, &G.arcnum, &IncInfo);
int i,j,k;
char v1,v2;
int IncInfo=0;
struct ArcBox *p;
scanfInit(); // 输入初始化
scanf(&G.vexnum, &G.arcnum, &IncInfo); // 自定义输入函数
for (i=0; itailvex=i;
p->headvex=j;
p->hlink=G.xlist[j].firstin;
p->tlink=G.xlist[j].firstout;
G.xlist[j].firstin = G.xlist[i].firstout = p;
// 完成在入弧和出弧链头的插入
//if (IncInfo) Input(*p->info); // 输入弧含有相关信息，此略!!!
}
return OK;
} // CreateDG
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//十字链表
struct dot
{
int d;
int w;
struct dot *next;
};
struct hed
{
int v;
struct dot *to;
struct dot *next;
}head[100];
int add3(int i,int j,int w)
{
struct dot * p;
struct dot * t = new dot;
t->d = j;
t->w = w;
t->next = NULL;
//正邻接表构建
if (head[i].next == NULL)
{
head[i].next = t;
}else
{
p = head[i].next;
while (p->next != NULL)
p = p->next;
p->next = t;
}
//逆邻接表打十字
if (head[i].to == NULL)
{
head[i].to = t;
return 0;
}else
{
p = head[i].to;
while (p->next != NULL)
p = p->next;
p->next = t;
}
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add3 (a,b,w);
}
return 0;
}
十字链表中和了邻接表和逆邻接表的优势。
邻接多重表示无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是在邻接表中每一条边（vi,vj）有两个结点，分别周四第i个和第j个链表中，这些给某些图的操作带来了不便。如对已被搜索过的边作标记或删除一条边等。如果一个结点能表示一条边的两个点的数据结构比较适宜。
因此，邻接多重表诞生了。他的核心就是用一个结点代表了一条边。
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef emnu{unvisited,visited} VisitIf
;
typedef struct EBox
{
VisitIf mark; //访问标记
int ivex,jvex; //该边依附的两个顶点的位置
struct EBox *ilink,*jlink; //分别为指向依附这两个顶点的下一条边
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VexBox
{
VertexType data; //顶点信息
EBox *firstedge; //指向第一条依附该顶点的弧的指针
}VexBox;
sypedef struct
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,arcnum; //无向图的当前顶点数和弧数
}AMLGraph;
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接多重表（无向图）
struct dot
{
int i,j;
int w;
struct dot *inext;
struct dot *jnext;
};
struct hed
{
int v;
struct dot *next;
}head[100];
int add4(int i,int j,int w)
{
struct dot *t = new dot;
struct dot *p = NULL,*tp = NULL;
t->i = i;
t->j = j;
t->w = w;
t->inext = NULL;
t->jnext = NULL;
if (head[i].next == NULL)
{
head[i].next = t;
}else
{
p = head[i].next;
while (p != NULL)
{
tp = p;
if (p->i == i)
p = p->inext;
else
p = p->jnext;
}
if (tp->i == i)
tp->inext = t;
else
tp->jnext = t;
}
if (head[j].next == NULL)
{
head[j].next = t;
}else
{
p = head[j].next;
while (p != NULL)
{
tp = p;
if (p->i == j)
p = p->inext;
else
p = p->jnext;
}
if (tp->i == j)
tp->inext = t;
else
tp->jnext = t;
}
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add4 (a,b,w);
}
return 0;
}
第十四章讲的是C++中的代码重用，代码重用是C++的主要目标之一，因此，通过多种继承、模板来实现。
公有继承是is-a关系，也就是说is a type of，可认为是并列关系。但两个类之间不光有并列关系，还是包含关系：has-a关系。那么就又有了包含，私有继承，保护继承。
包含很简单，就是在类的声明中添加一个类的对象作为数据成员。
私有继承基类的公有成员和保护成员都将成为派生类的私有成员。这将意味着基类方法将不会成为派生对象的公有接口的一部分，但可以在派生类的成员函数中使用它。
通过初始化列表直接调用基类析构函数初始化基类对象，而对于访问基类对象则可以使用强制转换。当然，访问基类对象是在他的可见作用域，派生类的内部实现的。
保护继承，基类的公有成员和保护成员都将成为派生类的保护成员。和私有继承一样，基类的接口在派生类中也是可用的，但在继承层次结构之外是不可用的。当派生类派生出另一个类时，私有继承和保护继承之间的主要区别便呈现出来了。使用私有继承时，第三代类将不能使用基类的接口，这是因为基类的公有方法在派生类中将变为私有方法；使用保护继承时，基类的公有方法在第二代中将变成裱糊的，因此第三代派生类可以使用他们。
对于保护的方法，可以使用using来在public重新定义对外访问权限，定义方法比如：
using std::valarray::min;
来开放min函数的对外权限。
多重继承可以让一个类从多个基类继承。
如果多个基类有共同祖先，那么新继承的类中可能有多个相同部分（共同祖先），当然，他们并存而且可以分别访问（通过，对基类的作用域解析运算符），但是大多数情况是不需要的，因此，可以在继承的时候添加virtual，使用虚基类，那么，对于多个虚基类的共同祖先，只会产生一个。
如果是虚基类，在构造函数就不应该用初始化列表调用基类，而应该调用基类的祖先。在虚基类中，这是必须的，但是非虚基类，这是非法的。
因为多重继承经常产生二义性的问题，因此，善用作用域解析运算符。
C++的类模板为生成通用的类声明提供了一种更好的方法。模板提供参数化类型，既能够将类型名作为参数传递给接收方来建立类或函数。
使用方法，在类的声明和函数的定义（如果是类外定义的话）前加上：
template
类模板可以做基类，可以用作组件类，可以做其他模板的类型参数，可以递归嵌套使用。
和函数模板一样，可以隐式实例化，显式实例化，显式具体化。甚至可以部分具体化（只支出几个而不是全部参数）。
类模板可以作为类的成员或者模板类的成员但在template语句是注意嵌套关系。
模板包含类型参数和非类型参数。模板还可以包含本身就是模板的参数，这种参数是模板新增的特性，用于实现STL。
模板类声明也可以有友元，模板的友元分3类：
之前的别名都是通过typedef实现，C++11允许使用using，比如：
using LL = long long;
和typedef相比，不仅可读性更强，而且对于模板的重命名更方便，比如：
template
using arrtype = std::array;
所有的这些机制的目的都是为了让程序员能够重用经过测试的代码，而不用手工复制他们，这样可以简化编程工作，提高程序可靠性！
面向对象编程的主要目的之一是提供可重用的代码，C++类提供了更高层次的重用性，比如类继承。类有三种继承方式，公用，私有，保护。这一章只讲公有继承。
使用公有派生，基类的公有成员将成为派生类的公有成员，基类的私有部分也将成为派生类的一部分，但只能通过基类的公有和保护方法访问。
构造函数必须给新成员和继承的成员提供数据，但是派生类不能直接访问基类的私有成员，而必须通过基类方法进行访问，换句话说，要构造派生类，需要调用基类的构造函数。
释放对象的顺序与创建对象的顺序相反，即首先执行派生类的析构函数，然后自动调用基类的析构函数。
基类指针可以指向派生类对象，但相反却不可以。基类指针指向派生类对象是向上强制转换，而派生类指针指向基类对象是向下强制转换。如果是强制转换的话倒也可以编译，但是是有风险的。因为基类的方法派生类都有，但派生类的方法，基类不一定有。这是C++的一个保护手段。
也正是因为基类的指针和引用可以指向派生类，导致了，原来为基类准备的函数，派生类也可以调用。很符合代码的重用性。
如果派生类想改变基类中已经存在的类方法，那么只需要再重新定义一个就好，但是这样出现了一个问题，因为基类指针是可以指向派生类的，那么如果指针或引用调用类方法的时候，默认是基类的类方法，尽管两个方法的实现不同，毕竟是基类指针，哪怕指向的是派生类函数。
为了解决这个问题，可以再基类的方法的声明前加上virtual，表示是虚方法，那么，当指针和引用调用方法的时候会判断到底是基类方法还是派生类方法。
如果重新定义基类方法时却需要调用基类方法肿么办？为了防止陷入递归死循环，应该使用作用域解析符。
还要注意，只要派生类重新定义了类方法，基类中的所有类方法都不能用了，包括基类中的函数重载。
因为基类可能使用动态内存，派生类也可能使用，因此，最好在基类中使用虚析构函数，保证派生类释放时正确。不是采用基类析构函数释放的。
protected和private的区别只有在基类派生的类中 才会表现出来。派生类的成员可以直接访问基类的保护成员，但不能直接访问基类的私有成员。因此，对于外部世界来书，保护成员的行为与私有成员相似；但对于派生类来说，保护成员的行为与公有成员相似。
最好对数据成员私有而不是保护，部分方法可以保护。
如果两个或多个类有共同点，而又有不同点，那么便可以声明一个只含有共同点的抽象基类，然后其他各个类都作为这个基类的派生，只添加不同点。
要声明抽象基类，需要让它包含纯虚函数，所谓纯虚函数，就是虚函数的声明后面加上个=0.
纯虚函数可以没有定义，但也可以有定义，他的定义只用在派生类没有定义的情况。纯虚函数用来定义派生类的通用接口。
抽象基类不被允许声明对象，只是作为一个基类使用，只要包含纯虚函数便被认为是抽象基类。
我也不知道为什么把强制转换单独拿出来总结，感觉挺重要的，或者说挺容易错的。
因为基类和派生类的关系很微妙，派生类在一定程度上讲，对基类的方法挺兼容，但是对象友元函数，运算符重载等一些特殊情况，很容易照成二义性甚至是因为类型判断失误导致递归性的死循环，因此善用强制转换，尤其是在基类和派生类类型模糊的时候。多想想，多写点，累不死。^^
动态内存如此灵活，在类中也十分常用。
如果在构造函数的时候使用new，那么无论是构造，赋值，复制，析构都需要注意
如果在类中有个static静态成员变量，便可以在类外用作用域解析运算符直接赋值，但是要指出变量类型，如：
int A::num = 0;
如果静态成员是const或者枚举，则可以在类声明初始化。
在复制，赋值过程中，可能会用到临时变量，如果在类中存在动态内存，那么给一个对象赋值时，是一个临时变量给这个对象赋值，过程：
很明显，这样形成了一个野指针。而这个复制过程被成为浅赋值。也就是由编译器默认复制构造函数实现的。但是，对于使用动态内存的类来说，这样明显是有问题了。因此，要使用深度复制。
深度复制就是使用复制构造函数和重载赋值运算符。
静态类成员函数
可以将成员函数声明为静态的（函数声明包含关键字static）
指针和对象之间的使用，和指针和结构体等的使用方式相同。善待指针！
为了防止隐式转换可以使用explicit关键字。
应该是一个星期前，韩祥波老师把我叫讲台上做一个关于初始化列表的题，不过到现在我才知道什么是初始化列表= =。
其实就是C++为const常量初始化的一种方式，只能用在构造函数上。
如果Queue类中有个叫qsize的常量，常量除了初始化是不允许被赋值的，那么就使用初始化列表进行初始化：
Queue (int qs):qsize(qs)
{
...
}
其他变量也可以用初始化列表进行初始化。其初始化的顺序和类声明中的顺序相同，和初始化列表的顺序无关。
C++11给diao，他可以在类声明中，直接初始化，甚至就是直接默认参数。
就像之前说的，就是在总结的时候浪费时间，那么我节约总结的时间来保证进度，那么代价就是总结不详细。但是有弊也有利，我现在很明确每一篇总结的重点，难点。因为写的都是重点难点。
类就像服务器给客户开了一个玩笑，然后想尽千方百计的圆这个谎。
运算符重载就是C++中多态的另一种表现，目的是让类使用起来更自然。
使用方法，类内重载：
返回值 operator运算符(参数);
比如,对于类A：
A operator + (int n);
使用就可以
A tmp;
int n;
tmp = tmp + n;
但是n+tmp是错误的，因为类内重载说白了还是成员函数，运算符左面就是第一个参数，也就是对象本身，运算符右面就是重载运算符函数的参数。如果需要反过来，可以用类外重载（非成员函数重载），也就是通过友元函数。
以下10种运算符不允许重载（不允许重载的运算符）：
. ：成员运算符
?: ：条件运算符
siezof：:sizeof运算符
:: ：作用域解析运算符
.* ：成员指针运算符
typeid：一个RTTI运算符
const_cast：强制转换运算符
dynamic_cast：强制转换运算符
teinterpret_cast：强制转换运算符
static_cast：强制转换运算符
友元有3种：友元函数，友元类，友元成员函数。
通过函数称为类的友元，可以赋予该函数与类的成员函数相同的访问权限，这里主要写友元函数。
为了解决上文的问题，其实大部分运算符都可以类外重载。以此来交换传参的顺序。
友元就是在成员函数最前面加个friend。
这样，这个函数就不是成员函数，就不能用成员运算符调用
虽然不是成员函数，但是他却又类作用域。
因为不是成员函数，所以编写函数定义的时候不需要加作用域限定符，不要再定义的时候加friend。
{
os
当然，这个重载要作为A的友元才能方法A的私有成员数据。当然，如果A类有返回要打印的数据的函数，重载不一定必须是友元。换句话说，只要能打印出数据，是不是友元无所谓，我们重载operator TypdName();
注意：
比如：
operator double();
使用起来也比较奇葩，比如对于类A：
A tmp = 1.2;
double tt = double(tmp);
这就是为什么说更像数据类型重载而不是强制转换了。
但是还要注意的是：没有返回类型不是没有return，要不然，强制转换之后，到底赋值赋的什么呢？还是靠return控制的，只是在声明和定义中不写罢了。
当然，转换函数有了，显式隐式转换都无所谓了，因为都可以实现。
最后一点，一定要注意好转换中的二义性，比如，定义了int和double转换函数，却给一个long赋值，会怎么样呢？
如果只有一个转换函数，那么语法没有错误，int或double对long都是合法的，但如果都存在，则编译器无法判断使用哪个重载，便报错，对于这种情况，要么就再定义一个long 的转换函数，要么直接使用强制转换。
如果转换函数和友元函数联合起来，效果是惊人的。一个可以控制类型的转换，一个可以进行运算等操作。
但是，过多的转换函数却很容易导致二义性，所以说，玩火谨防尿床。
但还是分析一下：
如果依赖隐式转换完成运算，程序更简短，定义的函数更少，出错几率也就小但是每次转换的时候都将调用转换构造函数，这增加时间和内存开销。反之，利用重载运算符，程序员需要完成的工作更多，但程序运行速度较快。
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.