《中文版教材主要数据结构.ppt》由会员分享，可在线阅读，更多相关《中文版教材主要数据结构.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性表的顺序存储结构线性表的顺序存储结构typedef struct SqList;/俗称 顺序表顺序表#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)Typedef struct LNode ElemType data;/数据域 struct Lnode *next;/指针域 LNode,*LinkList;线性表的链
2、式存储结构线性表的链式存储结构LinkList L；/L 为单链表的头指针为单链表的头指针#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;二叉树的顺序存储表示二叉树的顺序存储表示例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326ABCDEFG AB C E D F Groot AB C E D F G 树的二叉链表树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法哈哈
3、 夫夫 曼曼 树树 与与 哈哈 夫夫 曼曼 编编 码码 最优树的定义最优树的定义 如何构造最优树如何构造最优树 前缀编码前缀编码 最优树的定义最优树的定义树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。树的带权路径长度树的带权路径长度定义为：树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)。在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径带权路径长度取最小值长度取最小值的树，称为“最优树最优树”。例如：例如：27 9 75492WPL(T
4、)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54 根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；如何构造最优树如何构造最优树(1)(赫夫曼算法)以二叉树为例：在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；(2)从F中删去这两棵树，同时加入 刚生成的新树；重复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)9例
5、如:已知权值 W=5,6,2,9,7 5627527697671395276713952795271667132900001111000110110111 指的是，任何一个字符的编码都任何一个字符的编码都不是同一字符集中另一个字符的编码不是同一字符集中另一个字符的编码的前缀的前缀。前缀编码前缀编码 利用赫夫曼树可以构造一种不等长利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的的二进制编码，并且构造所得的赫夫赫夫曼编码曼编码是一种是一种最优前缀编码最优前缀编码，即使所，即使所传传电文的总长度最短电文的总长度最短。Aij=0 (i,j)VR1 (i,j)VR图的数组(邻接矩阵)存储表示B
6、ACDFE定义定义:矩阵的元素为矩阵的元素为有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECFtypedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType /顶点信息 vexsMAX_VERTEX_NUM;AdjMatrix arcs;/弧的信息 in
7、t vexnum,arcnum;/顶点数，边数 GraphKind kind;/图的种类标志 MGraph;图的结构定义（邻接矩阵）图的结构定义（邻接矩阵）0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE图的邻接表存储表示图的邻接表存储表示1 4230 120 1 2 3 4 A B C D E有向图的邻接表有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。typedef st
8、ruct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;data firstarc顶点的结点结构顶点的结点结构typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;图的结构定义（邻接表）图的结构定义（邻接表）