77范文网 - 专业文章范例文档资料分享平台

数据结构知识点总结(详细无题目)综述(3)

来源:网络收集 时间:2019-04-22 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

赫夫曼编码(前缀码)

向左分支为0,向右分支为1,从根到叶子的路径构成叶子的前缀编码。

五、 图

1.

完全图:有1\\2 n(n-1)条变得无向图

有向完全图:具有n(n-1)条弧的有向图。 权:与图的边或弧相关的数。

顶点v的度:和v相关联的边的数目。 入度:以顶点v为头的弧的数目 出度:以顶点v为尾的弧的数目

回路或环:第一个顶点和最后一个顶点相同的路径。 简单路径:序列中顶点不重复出现的路径。 2. 图的存储结构

·邻接矩阵:

A 0 1 1 0 0 B 0 0 1 1 0 C 0 0 0 1 0 D 1 0 0 0 0 E 1 0 0 1 0 ·邻接表:

typedef struct ArcNode { // 弧结点 int adjvex;

struct ArcNode *nextarc; } ArcNode;

typedef struct VexNode { // 顶点结点 VertexType

ArcNode *firstarc; } VexNode;

const int MAX_VERTEX = 最大顶点个数; typedef struct Graph { // 图 VexNode

int vexnum, arcnum; } Graph;

边(弧)多则需要存储空间多。

// 邻接点

// 下一个邻接点

data; // 顶点信息 // 第一个邻接点

vexs[MAX_VERTEX]; // 顶点向量 // 顶点和弧的个数

·十字链表: 十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中,对应于有向图中每一条弧有一个结点,对应于每个顶点有一个结点。 ·邻接多重表 3. 图的遍历

1) 深度优先(DFS)搜索

访问方式:从图中某顶点v出发: a)访问顶点v;

b)从v的未被访问的邻接点出发,继续对图进行深度优先遍历,若从某点出发所有邻接点都已访问过,退回前一个点继续上述过程,若退回开始点,结束。

2) 广度(宽度,BFS)优先搜索

a)访问顶点v ;

b)访问同v相邻的所有未被访问的邻接点w1,w2, …wk; c)依次从这些邻接点出发,访问它们的所有未被访问的邻接点; 依此类推,直到图中所有访问过的顶点的邻接点都被访问; 4. 生成树和最小生成树

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分,将遍历经过的边同图的顶点构成一个子图,该子图称为生成树。因此有DFS生成树和BFS生成树。 1) 最小生成树

·Kruskal算法

一句话,“不构成环的情况下,每次选取最小边”。

5 B 3 1 A 3 E 3 C 5 B 3 1 A 3 E 3 C ·普里姆算法

2 6 7 D (d) B 2 6 7 D (a) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (e) B 2 6 7 D (b) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (f) 2 6 7 D (c)

0 1 2 3 4 A B C D E 1 2 3 0 0 /\\ /\\ 2 /\\ 3 /\\ 3 /\\

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构知识点总结(详细无题目)综述(3)在线全文阅读。

数据结构知识点总结(详细无题目)综述(3).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/616823.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: