《最新双向循环链表操作-二叉树和树操作-图的创建及相关操作的实现8PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新双向循环链表操作-二叉树和树操作-图的创建及相关操作的实现8PPT课件.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2所选题目：所选题目：1 1、双向循环链表双向循环链表2、实现哈夫曼算法；实现哈夫曼算法；3、树、树1、双亲表示法建立树，、双亲表示法建立树，2、孩子链表建立树，、孩子链表建立树，3、孩子、孩子-兄弟表示法建立树。兄弟表示法建立树。4、图的相关操作、图的相关操作1、u-v所有简单路径所有简单路径2、最小生成树、最小生成树9双亲表示法建立树双亲表示法建立树1、节点类、节点类4、levelQueueOrder（）（） class PTNode 层次遍历，运用队列。层次遍历，运用队列。 Object data; int parent; 2、 CreativeTree()创建树创建树 ，俩个队列，俩个
2、队列来实现节点与数值的存储来实现节点与数值的存储3、depth（）实现对双亲树的计算深度（）实现对双亲树的计算深度循环计算找到其循环计算找到其parent=-1时时 的值，并返的值，并返回；回；10孩子链表树孩子链表树孩子链表孩子链表：每个节点的孩子节点用单链表存储，：每个节点的孩子节点用单链表存储，再用含再用含n n个元素的结构数组指向每个孩子链表。个元素的结构数组指向每个孩子链表。1、建立节点类、建立节点类class CNode int child; CNode nextChild; 2、创建孩子树：、创建孩子树： 输入数据作为数组，逐个为输入数据作为数组，逐个为 root赋值，把赋值，把
3、#作为作为root=null 的标志。的标志。3、层次遍历：、层次遍历：调用队列调用队列 。11孩子孩子- -兄弟链表建立树兄弟链表建立树1 1、孩子、孩子- -兄弟链表的节点类兄弟链表的节点类 class CSNodeclass CSNodeObject data;Object data;CSNode firstchild;CSNode firstchild;CSNode nextSibling;CSNode nextSibling; 2 2、创建树的结构：、创建树的结构： 先序递归创建孩子兄弟链表二叉树先序递归创建孩子兄弟链表二叉树3 3、递归的遍历实现先根和后根遍历、队列的存取实现树的层
4、次遍历、递归的遍历实现先根和后根遍历、队列的存取实现树的层次遍历4 4、当二叉树孩子，兄弟为空时计算二叉树的叶子节点个数、当二叉树孩子，兄弟为空时计算二叉树的叶子节点个数12图的功能实现操作所有类与函数方法体图的功能实现操作所有类与函数方法体输出所有路径：输出所有路径：class Graph class Graph Graph Graph（）（） 创建有向图；创建有向图；printAllGraphprintAllGraph（）（） 获取俩节点调用获取俩节点调用printAllGraphprintAllGraph（v ,uv ,u）输出所有路径；输出所有路径；printAllGraphprint
5、AllGraph（v ,uv ,u）输出俩顶点所有路径；输出俩顶点所有路径；class Kruskalclass Kruskalinvexnuminvexnum（）（）获取输入数据建立图；获取输入数据建立图；kruskalkruskal（）（）kruskalkruskal算法主体；算法主体；unionunion（）（） 生成最小树合并；生成最小树合并；printprint（）（）输出符合条件的生成最小数节点与权值输出符合条件的生成最小数节点与权值class PRIM class PRIM void Prim(int graph,int start,int n)void Prim(int gra
6、ph,int start,int n)对于有向图矩阵的对于有向图矩阵的PRIM PRIM 算法主体。算法主体。13图的操作：图的操作：u-vu-v之间所有路径之间所有路径其思路：创建有向图，利用图的邻接表结构，从其思路：创建有向图，利用图的邻接表结构，从u u点一支访问到点一支访问到齐邻接点为空时或者邻接点齐邻接点为空时或者邻接点=v=v然后输出所有路径；然后输出所有路径；class GraphNode class GraphNode 图的节点类图的节点类String data;String data;int weight;int weight;GraphNode next;GraphNode
7、 next;boolean visit;boolean visit; class Graph class Graph 主类主类void printAllGraph()void printAllGraph()输出所有节点的路径输出所有节点的路径void printAllGraph(int u, int v)void printAllGraph(int u, int v)输出俩点之间的所有路径输出俩点之间的所有路径14 图的的最小生成树图的的最小生成树PRIMPRIM算法算法 ：利用邻接矩阵来寻找最小边，然后来构建最小生成树：利用邻接矩阵来寻找最小边，然后来构建最小生成树KruskalKruska
8、l算法：利用邻接表，来寻找最小边，并在同时构建最小生成树。算法：利用邻接表，来寻找最小边，并在同时构建最小生成树。第一步，建立图的节点类；第一步，建立图的节点类；第二步，构建有向图；第二步，构建有向图；第三步，算法寻找最小边；第三步，算法寻找最小边；第四步，链接最小边，去掉环。第四步，链接最小边，去掉环。15primprim算法算法算法的核心：算法的核心：选择向集合选择向集合U U中加入顶点时，要选择到中加入顶点时，要选择到U U具有最短边的顶点。具有最短边的顶点。1 1、对任何一个顶点、对任何一个顶点v v，如果它有多个邻接，如果它有多个邻接U U的边，则需要找出最短的的边，则需要找出最短的
9、边作为邻接到边作为邻接到U U的边；的边；2 2、从所有的、从所有的V UV U顶点中，找出具有最短边的顶点，将它加入顶点中，找出具有最短边的顶点，将它加入U U；16KruskalKruskal算法算法考虑问题的出发点考虑问题的出发点: : 为使生成树上为使生成树上边的权值之和达到最小边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。则应使生成树中每一条边的权值尽可能地小。具体做法具体做法: : 先构造一个只含先构造一个只含n n个顶点的子图个顶点的子图SGSG，然后从权值最小的边开，然后从权值最小的边开始，若它的添加不使始，若它的添加不使SGSG中产生回路，则在中产生回路，则在SGSG上加上这条边，上加上这条边，如此重复，直至加上如此重复，直至加上n-1n-1条边为止。条边为止。