树和图这样的数据结构，有什么用？用在什么地方呢？
[问题点数：40分，结帖人LICHUNLI1022]
本版专家分：0
结帖率 96.79%
CSDN今日推荐
本版专家分：0
2012年4月 多媒体/设计/Flash/Silverlight 开发大版内专家分月排行榜第一
本版专家分：0
2005年7月 荣获微软MVP称号2007年7月 荣获微软MVP称号2006年7月 荣获微软MVP称号
2010年6月 专题开发/技术/项目大版内专家分月排行榜第二
2010年4月 专题开发/技术/项目大版内专家分月排行榜第三
本版专家分：0
本版专家分：0
本版专家分：0
匿名用户不能发表回复！|
其他相关推荐
写在前面：当浏览者访问一个网页时，浏览者的浏览器会向网页所在服务器发出请求。当浏览器接收并显示网页前，此网页所在的服务器会返回一个包含HTTP状态码的信息头用以响应浏览器的请求。本文主要是：关于$http状态码是什么，有什么用，在哪里查看状态码分别代表什么意思的分享，这里面内容也是非常多的，所以在此科普一下，做波分享。这里面有关键词版本和详细介绍每个错误的版本。http状态码有什么用？http状态码
先根遍历：树非空，先访问根节点，在按照从左到右的顺序遍历根节点的每一颗子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
后根遍历：树非空，则按照从左到右的顺序遍历根节点的每一颗子树，之后在访问根节点。其访问顺序和这棵树对应的二叉树的中序遍历顺序相同。
二叉树：先序遍历，后序遍历，中序遍历
广度优先遍历：类似于树的层次遍历，从数组中
前面文章中介绍了线性结构和表结构，但是这些数据结构一般不适合于描述具有分支结构的数据。在这种数据之间可能有祖先—后代，上级—下级、整体—部分等分支的关系。下文介绍的树形结构则是以分支关系定义的层次结构，是一类重要的非线性数据结构，在计算机领域有着广泛应用。例如，在文件系统和数据库系统中，树是组织信息的重要形式之一；在编译系统中，树用来表示源程序的语法结构；在算法设计与分析中，树还是刻画程序动态性质的工具。
树的基本概念
为了完整的建立有关树的基本概念，以下给出两种树的定义，即自由树和有根树
按位与运算符&&&是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。
例如：9&5可写算式如下：
(9的二进制补码)
(5的二进制补码)
(1的二进制补码)
In order to change we must be sick and tired of being sick and tired.
Name：WIllam
Time：、名词解释：
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶
其实我们要知道大数据的实质特性：针对增量中海量的结构化，非结构化，半结构数据，在这种情况下，如何快速反复计算挖掘出高效益的市场数据？
带着这个问题渗透到业务中去分析，就知道hadoop需要应用到什么业务场景了！！！如果关系型数据库都能应付的工作还需要hadoop吗？
1.银行的信用卡业务，当你正在刷卡完一笔消费的那一瞬间，假如在你当天消费基础上再消费满某个额度，你就可以免费
面向过程就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。 面向对象是把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在整个解决问题的步骤中的行为。
php程序编写分总分两种方式，分别为面向过程和面向对象，用两者比较你会更容易理解些以下数据库操作为例：面向过程：$conn = mysql_connect('
程序 = 算法 + 数据结构
数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。
常见数据结构
集合：set，multiset
线性结构：数组、链表、队列
数据结构体系图与存储结构实现，包括 线性表，栈，队列，树，图等等....
1.线性表的顺序存储结构
//线性表顺序存储结构的构建
#define MaxSize 100
typedef int DataT
typedef struct
DataType list[MaxSize];
//初始化顺序表L
void ListIni
图、码、文 介绍 优先队列之堆
优先队列；最大树；最大堆、最小堆的插入、删除、初始化；
堆的用途：堆排序；haffman编码；haffman tree 解决优化问题5.3K266 条评论分享收藏感谢收起赞同 3.7K43 条评论分享收藏感谢收起7927 条评论分享收藏感谢收起赞同 193 条评论分享收藏感谢收起博客访问： 1527741
博文数量： 249
博客积分： 1305
博客等级： 军士长
技术积分： 4693
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
欢迎关注微信公众号：菜鸟的机器学习
分类： C/C++ 15:31:17
一、图的存储结构
1.1 邻接矩阵
& & 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
& & 设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
& & 看一个实例，下图左就是一个无向图。
& & 从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij&= aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
& & 从这个矩阵中，很容易知道图中的信息。
& & （1）要判断任意两顶点是否有边无边就很容易了；
& & （2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；
& & （3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；
& & 而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。
& & 若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
& & 这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。
& & 那么邻接矩阵是如何实现图的创建的呢？代码如下。
typedef char VertexT
&&&&&&&&//顶点类型应由用户定义
typedef int EdgeT
&&&&&&&&//边上的权值类型应由用户定义
#define MAXVEX 100
//最大顶点数，应由用户定义
#define INFINITY 65535
&&&&&&&&//用65535来代表无穷大
#define DEBUG
typedef struct
VertexType vexs[MAXVEX]; &&&&&&&&//顶点表
arc[MAXVEX][MAXVEX]; &&&&&&&&//邻接矩阵，可看作边
int numVertexes, numE
//图中当前的顶点数和边数
int locates(Graph *g, char ch)
int i = 0;
for(i = 0; i numV i++)
if(g->vexs[i] == ch)
if(i >= g->numVertexes)
return -1;
//建立一个无向网图的邻接矩阵表示
void CreateGraph(Graph *g)
int i, j, k,
printf("输入顶点数和边数:\n");
scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
#ifdef DEBUG
printf("%d %d\n", g->numVertexes, g->numEdges);
for(i = 0; i numV i++)
g->vexs[i] = getchar();
while(g->vexs[i] == '\n')
g->vexs[i] = getchar();
#ifdef DEBUG
for(i = 0; i numV i++)
printf("%c ", g->vexs[i]);
printf("\n");
for(i = 0; i numE i++)
for(j = 0; j numE j++)
g->arc[i][j] = INFINITY; //邻接矩阵初始化
for(k = 0; k numE k++)
printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
p = getchar();
while(p == '\n')
p = getchar();
q = getchar();
while(q == '\n')
q = getchar();
scanf("%d", &w);
int m = -1;
int n = -1;
m = locates(g, p);
n = locates(g, q);
if(n == -1 || m == -1)
fprintf(stderr, "there is no this vertex.\n");
//getchar();
g->arc[m][n] =
g->arc[n][m] = g->arc[m][n]; //因为是无向图，矩阵对称
void printGraph(Graph g)
for(i = 0; i < g.numV i++)
for(j = 0; j < g.numV j++)
printf("%d
", g.arc[i][j]);
printf("\n");
int main(int argc, char **argv)
//邻接矩阵创建图
CreateGraph(&g);
printGraph(g);
&& & 从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2&+ e)，其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。
1.2 邻接表
& & 邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。
& & 邻接表的处理方法是这样的：
& & （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
& & （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
& & 例如，下图就是一个无向图的邻接表的结构。
& & 从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
& & 对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。
& & 对于邻接表结构，图的建立代码如下。
/* 邻接表表示的图结构 */
#define DEBUG
#define MAXVEX 1000
//最大顶点数
typedef char VertexT
//顶点类型应由用户定义
typedef int EdgeT
//边上的权值类型应由用户定义
typedef struct EdgeNode
//边表结点
//邻接点域，存储该顶点对应的下标
//用于存储权值，对于非网图可以不需要
struct EdgeNode *
//链域，指向下一个邻接点
typedef struct VertexNode
//顶点表结构
//顶点域，存储顶点信息
EdgeNode *
//边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct
AdjList adjL
int numVertexes, numE //图中当前顶点数和边数
int Locate(GraphList *g, char ch)
for(i = 0; i adjList[i].data)
if(i >= MAXVEX)
fprintf(stderr,"there is no vertex.\n");
return -1;
//建立图的邻接表结构
void CreateGraph(GraphList *g)
EdgeNode *e;
EdgeNode *f;
printf("输入顶点数和边数:\n");
scanf("%d,%d", &g->numVertexes, &g->numEdges);
#ifdef DEBUG
printf("%d,%d\n", g->numVertexes, g->numEdges);
for(i = 0; i numV i++)
printf("请输入顶点%d:\n", i);
g->adjList[i].data = getchar();
//输入顶点信息
g->adjList[i].firstedge = NULL;
//将边表置为空表
while(g->adjList[i].data == '\n')
g->adjList[i].data = getchar();
//建立边表
for(k = 0; k numE k++)
printf("输入边(vi,vj)上的顶点序号:\n");
p = getchar();
while(p == '\n')
p = getchar();
q = getchar();
while(q == '\n')
q = getchar();
m = Locate(g, p);
n = Locate(g, q);
if(m == -1 || n == -1)
#ifdef DEBUG
printf("p = %c\n", p);
printf("q = %c\n", q);
printf("m = %d\n", m);
printf("n = %d\n", n);
//向内存申请空间，生成边表结点
e = (EdgeNode *)malloc(sizeof(EdgeNode));
if(e == NULL)
fprintf(stderr, "malloc() error.\n");
//邻接序号为j
e->adjvex =
//将e指针指向当前顶点指向的结构
e->next = g->adjList[m].
//将当前顶点的指针指向e
g->adjList[m].firstedge =
f = (EdgeNode *)malloc(sizeof(EdgeNode));
if(f == NULL)
fprintf(stderr, "malloc() error.\n");
f->adjvex =
f->next = g->adjList[n].
g->adjList[n].firstedge =
void printGraph(GraphList *g)
int i = 0;
#ifdef DEBUG
printf("printGraph() start.\n");
while(g->adjList[i].firstedge != NULL && i adjList[i].data);
EdgeNode *e = NULL;
e = g->adjList[i].
while(e != NULL)
printf("%d
", e->adjvex);
printf("\n");
int main(int argc, char **argv)
CreateGraph(&g);
printGraph(&g);
&& & 对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。
& & 本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。
1.3 十字链表
& & 对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。
& & 重新定义顶点表结点结构，如下所示。
& & 其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。
& & 重新定义边表结构，如下所示。
& & 其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。
& & 比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。
& & 重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。
& & 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。
& & 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。
& & 这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。
二、图的遍历
& & 图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。
& & 对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。
2.1 深度优先遍历
& & 深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。
& & 它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
& & 我们用邻接矩阵的方式，则代码如下所示。
#define MAXVEX
//最大顶点数
typedef int B &&&&&&&&//Boolean 是布尔类型，其值是TRUE 或FALSE
Boolean visited[MAXVEX];&&&&&&&&//访问标志数组
#define TRUE 1
#define FALSE 0
//邻接矩阵的深度优先递归算法
void DFS(Graph g, int i)
visited[i] = TRUE;
printf("%c ", g.vexs[i]);
&&&&&&&&&&&&&&&&//打印顶点，也可以其他操作
for(j = 0; j < g.numV j++)
if(g.arc[i][j] == 1 && !visited[j])
DFS(g, j);
//对为访问的邻接顶点递归调用
//邻接矩阵的深度遍历操作
void DFSTraverse(Graph g)
for(i = 0; i < g.numV i++)
visited[i] = FALSE;
//初始化所有顶点状态都是未访问过状态
for(i = 0; i < g.numV i++)
if(!visited[i])
//对未访问的顶点调用DFS，若是连通图，只会执行一次
& & 如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。
//邻接表的深度递归算法
void DFS(GraphList g, int i)
EdgeNode *p;
visited[i] = TRUE;
printf("%c ", g->adjList[i].data); //打印顶点，也可以其他操作
p = g->adjList[i].
if(!visited[p->adjvex])
DFS(g, p->adjvex);
//对访问的邻接顶点递归调用
//邻接表的深度遍历操作
void DFSTraverse(GraphList g)
for(i = 0; i < g.numV i++)
visited[i] = FALSE;
for(i = 0; i < g.numV i++)
if(!visited[i])
DFS(g, i);
&& & 对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
2.2 广度优先遍历
& & 广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。
& & 邻接矩阵做存储结构时，广度优先搜索的代码如下。
//邻接矩阵的广度遍历算法
void BFSTraverse(Graph g)
for(i = 0; i < g.numV i++)
visited[i] = FALSE;
InitQueue(&q);
for(i = 0; i < g.numV i++)//对每个顶点做循环
if(!visited[i])
//若是未访问过
visited[i] = TRUE;
printf("%c ", g.vexs[i]); //打印结点，也可以其他操作
EnQueue(&q, i);
//将此结点入队列
while(!QueueEmpty(q))
//将队中元素出队列，赋值给
DeQueue(&q, &m);
for(j = 0; j < g.numV j++)
//判断其他顶点若与当前顶点存在边且未访问过
if(g.arc[m][j] == 1 && !visited[j])
visited[j] = TRUE;
printf("%c ", g.vexs[j]);
EnQueue(&q, j);
&&&&对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下。
//邻接表的广度遍历算法
void BFSTraverse(GraphList g)
EdgeNode *p;
for(i = 0; i < g.numV i++)
visited[i] = FALSE;
InitQueue(&q);
for(i = 0; i adjvex])
visited[p->adjvex] = TRUE;
printf("%c ", g.adjList[p->adjvex].data);
EnQueue(&q, p->adjvex);
& & &&对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。
&&&&& & 参考：《大话数据结构》
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & 梦醒潇湘love
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & & & & & & & & & & & & &&& &15:30
阅读(97060) | 评论(3) | 转发(23) |
给主人留下些什么吧！~~
邻接表结构实现的创建图&void&CreateGraph(GraphList&*g)，你是随意写的每个顶点加两个边数，和图片里的内容不一致，对吧？
：没必要这么拘泥于book，数组的不足在于浪费空间，链表的不足在于cache的命中不行，可以综合数组和链表的有点，用变长数组来矩阵做邻接
说的对&&应该学会变通&&&感谢 |
没必要这么拘泥于book，数组的不足在于浪费空间，链表的不足在于cache的命中不行，可以综合数组和链表的有点，用变长数组来矩阵做邻接
请登录后评论。