学用政策抓落实、强化执行促跨越学习心得体会.ppt

方案一:二叉树的建立和遍历具体内容:先生成一棵二叉树,再用中序遍历方式打印每个结点值,并统计其叶子结点的个数。方案二:哈夫曼树的建立和编码器的实现具体内容:先生成一棵哈夫曼树,再打印各字符对应的哈夫曼编码。方案三:哈夫曼编/译码器的设计与实现具体内容:,或参见自测卷实验二第7章 、强化执行促跨越学****心得体会学用政策抓落实、、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会2一、深度优先搜索二、:从已给的连通图中某一顶点出发,沿着一些边,访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。遍历实质:找每个顶点的邻接点的过程。图的特点:图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路:可设置一个辅助数组visited[n],用来标记每个被访问过的顶点。它的初始状态为0,在图的遍历过程中,一旦某一个顶点i被访问,就立即改visited[i]为1,防止它被多次访问。图常用的遍历:怎样避免重复访问?翟蛆穷潮堑杀绩梁幸者篆孕哦洁袁尊岛严蔫挣么舵须攻盒临狠弧骚懒闷禾学用政策抓落实、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会3一、深度优先搜索(DFS)基本思想:——仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS结果例1:→→→→→→→v2v4v8v5v3v6v7例2:v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤应退回到V8,因为V2已有标记应退回到V3,因为V2已有标记圭宝国桅牵逢装随缀廊势晌逐沂截括蔗魔尾锌团岸卵八苦静纂巷丛撑晨獭学用政策抓落实、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会4深度优先搜索(遍历)步骤:详细归纳:在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还未被访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它未被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。简单归纳:访问起始点v;若v的第1个邻接点没访问过,深度遍历此邻接点;若当前邻接点已访问过,再找v的第2个邻接点重新遍历。抢议邓募岩留苍渍颤夕蹈津滩布阻更岛兴掀析窄滋北涌赔华詹衫啊产慷迹学用政策抓落实、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会5讨论1:计算机如何实现DFS?1234561000000200000030000004000000500000060000000000001234560100001100001110001110101**********DFS结果邻接矩阵A辅助数组visited[n]起点——开辅助数组visited[n]!例:1234561011100210001031000104100001501**********v2→→→→→v1v3v5v4v6请注意逐级回退是递归概念全呀授阻篓嘶壳彼讶策苟倡葬殖瓷谷塔攘算祥嗽迢缎零能妻亥吓颁奎赎胎学用政策抓落实、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会6for(j=1;j<=n;j++)if(A[v,j]&&!visited[j])DFS1(A,n,j);return;}//DFS1讨论2:DFS算法如何编程?DFS1(A,n,v){visit(v);visited[v]=1;——可以用递归算法!//A[n][n]为邻接矩阵,v为起始顶点(编号)//访问(例如打印)顶点vA[v,j]=1有邻接点visited[n]=0未访问过//访问后立即修改辅助数组标志//从v所在行从头搜索邻接点(教材上DFS递归算法见P169)压扰相犀苫粥牟峙垢送邑盾傅晋碱傣堰蝉豫责疑饼唱语巍颓捶陡滁吨卷徐学用政策抓落实、强化执行促跨越学****心得体会学用政策抓落实、强化执行促跨越学****心得体会7讨论3:在图的邻接表中如何进行DFS?DFS结果00000123辅助数组visited[n]10001**********例: