异质树的实现——代码+实验报告
-
-
-
#include"stdafx.h"
-
#include<iostream.h>
-
#include<string>
-
#include<stdlib.h>
-
#include<stdio.h>
-
classNode
- {
-
protected:chartype;
-
protected:Node*parent;
-
public:Node*children[11];
-
public:intchildNum;
-
public:chardataStr[20];
-
public:Node()
- {
- childNum=0;
- parent=NULL;
-
for(inti=0;i<11;i++)
- children[i]=NULL;
-
- }
-
public:virtualvoidsetData(char*data)=0;
-
public:virtualchar*getData()=0;
-
public:voidsetType(chartype)
- {
-
this->type=type;
- }
-
public:chargetType()
- {
-
returntype;
- }
-
public:voidsetParent(Node*parent)
- {
-
this->parent=parent;
- }
-
public:Node*getParent()
- {
-
returnthis->parent;
- }
-
public:Node*addChild(Node*childNode)
- {
- childNum++;
-
if(childNum>=11)
- {
- childNum--;
-
returnNULL;
- }
- children[childNum]=childNode;
-
childNode->setParent(this);
-
cout<<"结点"<<childNode->getData()<<"插入在children["<<childNum<<"]位置"<<endl;;
-
returnchildNode;
- }
- };
-
classIntNode:publicNode
- {
-
private:intdata;
-
public:IntNode(char*data)
- {
-
this->setType('i');
-
this->setData(data);
-
- }
-
public:voidsetData(char*data)
- {
-
this->data=atoi(data);
- }
-
public:char*getData()
- {
-
itoa(this->data,dataStr,10);
-
returndataStr;
- }
- };
-
classStrNode:publicNode
- {
-
private:char*data;
-
public:StrNode(char*data)
- {
-
this->setType('s');
-
this->setData(data);
- }
-
public:voidsetData(char*data)
- {
-
this->data=data;
- }
-
public:char*getData()
- {
-
returnthis->data;
- }
- };
-
classHelper
- {
-
public:voidnavTree(Node*node)
- {
-
-
if(node->getParent()==NULL)
- {
-
cout<<(*node).getData()<<"";
- }
-
intnum=(*node).childNum;
-
if(num!=0)
- {
-
for(inti=1;i<=num;i++)
- {
- Node*child=(*node).children[i];
-
cout<<(*child).getData()<<"";
- navTree(child);
- }
- }
- }
-
public:voidfindNode(Node*root,chartyChar,char*dataStr,Node*&foundNode)
- {
-
intnum=(*root).childNum;
-
-
if(num!=0)
- {
-
for(inti=1;i<=num;i++)
- {
- Node*child=root->children[i];
-
char*childData=child->getData();
-
-
-
if(tyChar==child->getType()&&strcmpi(childData,dataStr)==0)
- {
-
- foundNode=child;
-
break;
-
return;
- }
-
elsefindNode(child,tyChar,dataStr,foundNode);
-
}
- }
-
elsereturn;
- }
-
private:voidremoveNode(Node*node)
- {
-
intnum=(*node).childNum;
-
cout<<"结点"<<node->getData()<<"有"<<num<<"个孩子"<<endl;
-
if(num!=0)
- {
-
for(inti=1;i<=num;i++)
- {
- Node*child=(*node).children[i];
- removeNode(child);
- }
- }
-
if(num==0)
- {
- Node*parent=node->getParent();
-
cout<<"欲删除结点:"<<node->getData()<<"其父亲结点有孩子"<<parent->childNum<<"个"<<endl;
-
for(inti=1;i<=parent->childNum;i++)
- {
-
cout<<"parent->children["<<i<<"]="<<parent->children[i]->getData()<<endl;
-
-
-
if(strcmpi(parent->children[i]->getData(),node->getData())==0
- &
- parent->children[i]->getType()==node->getType()
- )
- {
-
-
- parent->children[i]=parent->children[i+1];
-
- parent->childNum--;
-
cout<<"已删除结点"<<node->getData()<<",其父亲结点"<<parent->getData()<<"的孩子数="<<parent->childNum<<endl;
-
break;
- }
- }
-
if(parent->childNum==0)
- {
- removeNode(parent);
- }
-
}
- }
-
public:voiddeleteNode(Node*root,chartyChar,char*dataStr)
- {
- Node*foundNode=NULL;
- findNode(root,tyChar,dataStr,foundNode);
-
if(foundNode==NULL)cout<<"查无此结点,无法删除"<<endl;
-
else
- {
-
cout<<"找到结点:"<<foundNode->getData()<<",正在删除..."<<endl;
- removeNode(foundNode);
- }
- }
- };
-
intmain(intargc,char*argv[])
- {
-
-
Node*root=newStrNode("root");
-
Node*inode1=newIntNode("1");
-
Node*inode2=newIntNode("2");
-
Node*snode1_1=newStrNode("1_1");
-
Node*snode1_2=newStrNode("1_2");
-
Node*snode1_1_1=newStrNode("1_1_1");
-
Node*snode1_1_2=newStrNode("1_1_2");
- root->addChild(inode1);
- root->addChild(inode2);
- inode1->addChild(snode1_1);
- inode1->addChild(snode1_2);
- snode1_1->addChild(snode1_1_1);
- snode1_1->addChild(snode1_1_2);
- Helperhelper;
-
-
-
helper.deleteNode(root,'i',"1");
- helper.navTree(root);
- root->addChild(inode1);
- helper.navTree(root);
-
return0;
- }
北航软件学院《一级实践》实验报告<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
学号:GS0821594 姓名:叶现一 第 9 周
内容训练
|
异质树的实现
|
本周开发源代码
|
代码的功能简述
|
实现异质树的查找、插入、删除和遍历
|
开发的收获
|
关于纯虚函数的使用;类的继承的使用;派生类对象的初始化;指针引用;递归函数的使用
|
开发中碰到的主要困难
|
1) 在选择实现方案上:曾经设想用共用体的方式解决树的不同结点存储不同数据类型的数据问题,但该方案其一比较浪费内存,其二要针对不同的结点类型定义不同的插入子结点策略、删除子结点策略等。后期编写比较困难,而且难以维护。
2) 在编写对树结点的查找函数时,找不到有效的办法能使找到的结点地址被成功的返回。最终采用了指针引用的方式将地址返回。
3) 在保存一个结点的子结点策略上:因为一个普通树结点的子结点没有固定的数量,所以理论上应该采用一个链表用于保存一个结点上的子结点,但此方案的前提是已经有一个工作良好的链表类用于使用。由于为此目的单独开发一个链表类相当耗时,所以最终采用了次方案——用一个固定大小的数组用于保存该结点的所有子结点的地址。这种方案固然不是一个很好的方案,因为限定了数组的大小就等于限定了一个结点所能拥有的子结点的数量。还有一个较好的方案则是使用STL中已经定义好的链表类,不仅功能齐备而且性能可靠。但由于未能掌握其基本使用方法该方案最终未能得以实施。
4) 关于删除结点问题:由于采用了定长数组保存每个结点的子结点地址,且在删除一个结点的同时应该将其后代全部删除,但在每删除一个结点的时候都应该将其地址从该结点的父结点中的子结点列表中删除。于是就引出了以下问题——如果假定一个结点的子结点列表(数组)中3个成员变量(子结点地址),分别存储在1位、2位和3位上,现要删除2位上的结点。当将2位上的地址清空后需要将其后的地址依次向前移动一个单元,否则在删除完该结点后立刻进行树的遍历操作时会产生运行时错误。因为根据递归调用,程序并不清楚2位上的地址段中的结点已经被删除。
|
|
开发中未能解决的问题
|
1) 关于上述开发困难中的(2):我认为可以找到更直接更人性化的方法将找到的树结点的地址返回来,而不是用指针引用。因为我们通常习惯用Node* foundNode = findNode(root,typeChar,dataStr);的方式获取到结点的地址,而不是通过Node* foundNode = NULL ;
findNode(root, tyChar,dataStr,foundNode);
的方式获取结点地址。我正在考虑使用指向指针的指针以解决该问题。
2) 关于上述开发困难中的(3)和(4):希望能够采用一个链表来保存一个结点的所有子结点的地址而不是定长数组。这需要借助于STL的链表类,因此该程序有待于在掌握STL的具体使用方法后做进一步的改进。
3) 在删除树结点的过程中不能做到真实的释放树结点的地址空间,即执行语句delete node;因此在本程序中对结点的删除只是假删除——只把结点的子结点地址从该结点的子结点列表中删除掉,而其子结点的空间并没有释放掉,今后还可以重用。这是极不安全的一种实现方案,迫切需要更正!
|
针对本周训练内容自己设计的案例
|
案例的主要功能
|
实现异质树的查找、插入、删除和遍历
|
用到的基本知识
|
纯虚函数的使用;类的继承的使用;派生类对象的初始化;指针引用;递归函数的使用
|
程序注意了哪些规范
|
1) 使用了抽象类与类继承关系,最大限度的提高了代码的重用性。
2) 将结点类的关键成员变量或方法设定为private或者protected类型,仅向用户暴露必要的接口方法间接修改类的成员属性。
|
你进行了哪些测试
|
相同类型和不同类型树结点间的查找、插入、删除和遍历操作;
|
程序进行了哪些有效性检查
|
程序对用户传入的参数,包括结点数据类型和结点数据进行了有效性验证。
|
你是如何保证程序的高效率的
|
在程序中尽可能使用指针运算以代替类对象的传递操作。
|
注意:实验报告和案例源代码须在本次小组讨论会前提交
分享到:
相关推荐
树是二叉排序树,支持异质节点,二叉排序树支持添加、删除、查找节点。详细请查看代码中的注释。为了查看方便,我把所有的代码放在一个文件中。
可以用来分析土壤异质性等有关异质性的处理
基于SPORT5图像的小城市城区绿地系统景观异质性分析——以邹城市为例,王震,张志国,以邹城市建成区为研究对象,以邹城市2006年的SPOT5遥感影像为信息源,通过ERDAS IMAGINE 8.5对图片进行处理后,利用Arcview GIS的...
c++实现的异质树,c++实现的异质树
一个简单的异质树 c++ 实现 需要的请下载吧,很简单的小例子希望对大家有帮助
异质树的实现--C++实现 c++程序,主要也就是学习使用一下多态的概念
北航的三个实验报告(异质树,PV操作和Socket通信),本人亲自编写并测试通过!
关于异质树的实现,C++语言编写,主要用到了面向对象相关知识
#资源达人分享计划#
人工智能AI源代码解析-基于元学习的异质信息网络推荐冷启动方案(代码+数据)
社交内容电商商业模式的同质化和异质化——以小红书和蘑菇街为例
代码、计算过程、原始数据!3W+数据!高管团队异质性数据2008-2020年 1、数据来源:在文件中附带 2、时间跨度:2008-2020 3、区域范围:各上市公司 4、指标说明: 高管团队异质性即高管团队成员在人员背景、认知理念...
社交内容电商商业模式的同质化和异质化——以小红书和蘑菇街为例.pdf
异质树构造c++
/* 题目: ... 异质链表实现:有三个类 student,teacher,staff,再定义一个 链表类,此类用来存放这几个不同类的对象,并将链表类 list 声明为所有这些 类的友元,使它们可以访问它们的私有成员。*/
这部分知识的讲解我已经在博客中记录,近期会发布该博客,可以根据关键字或者标题:详解【异质图注意力网络——HAN (附代码实现)】GAN原理 | ACM数据集、IMDB数据集 介绍 | 再次认识 metapath | 开发集 | dgl-API ...
含可运行及编译程序,采用虚函数、多态、类的调用。 C++学习的基础知识,程序可编译,含全部文件。
很好的异质链表的实现,里面介绍了虚函数的一些知识
Python-基于异质集成的房价预测(含实验报告)
论文实证代码描述性分析相关性分析多元回归分析异质性分析稳健性检验等stata代码