C++程序设计第四章树形结构解读.ppt

* 4.4.2 树与等价问题 C++类MEset定义（续）： //析构函数：释放空间 ~MEset() { delete[] m_nodes; } bool Create( char [], const int ); // 建立集合 void Display(); // 显示当前集合的状态 int LocateElem( const char ); // 查找元素在集合中的位置 int FindRoot( const int ); // 查找元素所处集合的根 void Merge( const int , const int ); // 合并两个集合 void EffMerge( const int , const int ); // 高效合并两个集合 private: int m_len; int m_size; PTnode *m_nodes; }; 4.4.2 树与等价问题 构造函数为存储集合中的数据元素分配了m个（双亲表示法结点结构）存储单元的顺序空间。 4.4.2 树与等价问题 建立n个只含一个元素的等价类的过程（成员函数Create） // 建立n个集合（初始时每一集合只有一个元素） bool MEset::Create( char ch[], int const n) { int i = 0; if( n m_size) return false; while ( i n){ m_nodes[i].data = ch[i]; m_nodes[i].parent = -1; i++; } m_len = n; return true; } 4.4.2 树与等价问题 建立n个等价类实际上是建立了含有n棵子树的森林，如下图所示。 4.4.2 树与等价问题 读入偶对(x, y)如何判定某个元素所在的子集（子树），又如何合并两个互不相交的子集（子树）？ 首先，分别查找元素x和y在数组中的位置（设x和y在数组中的位置分别是i和j） // 查找元素e在集合中的位置 int MEset::LocateElem(const char e) { int i=0; while ( i m_len m_nodes[i].data != e) i++; if (i = m_len) return -1; return i; } 4.4.2 树与等价问题 接着分别查找位序是i和j的数据元素所处子集（子树）的根 // 查找位序是i的元素所处集合的根 int MEset::FindRoot(const int i) { int k; for ( k = i; m_nodes[k].parent = 0; k = m_nodes[k].parent); return k; } 4.4.2 树与等价问题 若元素x和y在集合中所处子集（子树）的根不同（i != j），则合并之。 // 合并根的位置是i和j的两个集合 void MEset::Merge( const int i, const int j) { m_nodes[i].parent = j; } 4.4.2 树与等价问题 如偶对(a,c)中的数据元素a所属子集（子树）为0，数据元素c所属子集（子树）为2，如下图所示，则有：m_nodes[0].parent=2。 4.4.2 树与等价问题 这种方法有可能出现单支树的情形，使得查找某一数据元素所处子集（子树）的根时，有哪些信誉好的足球投注网站长度达到最大如下图所示。 假设n个集合S1,S2,…,Sn, 每个子集只有一个元素Si = { i }，用n棵只有一个根节点的树表示，则在做了n-1次并操作后，最后得到的集合（树）深度平均为log n，最坏时为n。 4.4.2 树与等价问题 为确保集合（树）的深度任何情况下不超出log n，则需对合并方法进行改良 。 //高效合并根的位置是i和j的两个集合 void MEset::EffMerge(const int i,const int j) { if (m_nodes[i].parent m_nodes[j].parent) { m_nodes[j].parent += m_nodes[i].parent; m_no