数据结构实习四报告

实习题目：利用树型结构的搜索算法模拟因特网域名的查询 学院：计算机与通信工程学院 姓名： 班级： 通信1103 学号： 指导教师： 黄旗明 一、［问题描述］ 在Internet的域名系统中，以树型结构实现域名的搜索。即输入某站点的域名，在域名系统的树型结构中进行搜索，直至域名全部匹配成功或匹配失败；若成功则给出该站点的IP地址166.111.9.2。 二、[测试数据] 可以取常用到的著名站点的域名和IP 地址为例构建域名结构的树，一般应有３０个左右的站点域名。当输入www.tsinghua.edu.cn时，输出为“166.111.9.2”；而输入www.tsinghuo.edu.cn时，输出应为“找不到服务器或发生DNS错误”。 三、［实现提示］ 树的存储结构采用孩子－兄弟链表。 二叉链表的树结构是一种动态结构，除第一次生成的过程需要人工输入数据外，以后每次进行搜索查询大，应首先从文件中保存是数据自动生成树结构。为解决二叉链表与文件之间的转换，可以通过先序遍历的办法保存和恢复二叉链表。例如一个二叉链表的文件保存形式如下：
四、［问题讨论］ 实际的使用中，树结构的使用机会比二叉树还要多，一般情况下都采用孩子－兄弟链表作树的存储结构，此时也可将树视作二叉树，并将对树进行的操作转换成对二叉树的相应操作。 五、［实际设计及具体代码］ 1、创建题头文件binTree #include using namespace std; class treeNode//结点类 { public: treeNode():data(NULL),left(NULL),right(NULL) { } treeNode(char* dat):data(dat),left(NULL),right(NULL) { } char* data;//数据格式 www或.taobao 或者 0.0.0.0 treeNode* left; treeNode* right; }; class binTree//IP二叉树，孩子兄弟表示法，函数bool返回时TRUE凡是成功，否则失败 { public://外部函数接口 binTree():initalFlag(false) { } bool Initialize();//从IP数据库读取数据，并形成IP二叉树，IP数据在倒数第二结点的左孩子里面 char* searchIP(string website);//查找IP，参数为网站名称，例如：www.taobao.com void edit(string IP,string websiteWithoutIP);//查找是否存在该网站，否则不进行编辑 bool addNew(string input);//先验证输入是否正确，然后添加新网站和其IP到二叉树和数据库 void destory() { destoryNodes(root); } ~binTree() { } bool initalFlag; private://内部封装函数和成员 void addNewWebsite(string website);//添加新数据到二叉树，参数为带IP的网址名称，例如：www.cau.edu.cn/0.0.0.0 bool writeToFile(string websiteWithIP);//将带IP地址的网址名称写入文件尾部 bool editIP(string IP,char*& dataPointer,string websiteWithoutIP);//编辑存在网站的IP数据，参数分别是IP,指向IP的指针，和该网站的名称 treeNode* insertNode(treeNode*& head,const char* data);//向HEAD所指向指针的孩子区添加内容为data的结点，如果存在则不添加 void spiltWebsite(string& website,string* IPaddress,string* domain);//将带有IP网站数据分成IP数据，和各个小结点例如：www.taobao.com/0.0.0.0分成0.0.0.0到IPADDRESS和www，.taobao，.com到domain string 数组 treeNode* searchParts(const char* part,treeNode* level,char*& lastPointer);//查找PART所指向的数据，（.com），level为该数据所在的层级，lastpointer当涉及孩子结点的ip数据时，才赋值，一般为null bool checkStringFormat(string toBeChecked,bool whetherHasIP,bool IPpart);//检查string数据是否符合IP格式或网站名称或带IP的网站名称 void destoryNodes(treeNode*& current);//删除二叉树所有结点以及数据 treeNode* root;//根结点，不附加内容。左结点指向IP二叉树 }; bool binTree::Initialize() { root=new treeNode; root->data=new char[11]; strcpy(root->data,"SystemHead"); fstream manipulate; string website; char buffer[100]; manipulate.open("IPDB.txt",ios::in); if (manipulate.is_open()) { while (!manipulate.eof()) { manipulate.getline(buffer,100,'
'); website=buffer; addNewWebsite(website); } manipulate.close(); initalFlag=true; return true; } else { cout<<"Fail to load data to read."<" writeFile.close(); return true; } else { writeFile.close(); cout<<"Can't open the file to write."<=0;--i) { const char* temp=domain[i].c_str(); current=insertNode(current,temp); } char* content=new char[IPaddress.length()+1]; for ( i=0;i<=IPaddress.length();++i) { content[i]=IPaddress[i]; } current->left=new treeNode(content); } treeNode* binTree::insertNode(treeNode*& head,const char* data) { treeNode* child=head; if (child->left!=NULL)//左孩子为空表示head下面没有数据 { child=child->left;//如果存在，则查找head的所有孩子 if (!strcmp(child->data,data))//比较字符串数据，匹配成功返回0,所以!0=1 { return child; } while (child->right!=NULL && strcmp(child->right->data,data))//不匹配继续查找 { child=child->right; } if (child->right == NULL)//查找失败，则新建 { child->right=new treeNode; child->right->data=new char[strlen(data)+1]; strcpy(child->right->data,data); return child->right; } else { return child->right; } } else { child->left=new treeNode; child->left->data=new char[strlen(data)+1]; strcpy(child->left->data,data); return child->left; } } void binTree::spiltWebsite(string& website,string* IPaddress,string* domain) { int position=website.find_first_of('/'); string ip; if (position!=-1)//防止多余的空格导致错误 { ip=website.substr(position+1,website.length()-position);//IPADDRESS website.erase(position,ip.length()+1);//删除IP地址部分 if (IPaddress!=NULL) { //IP地址 *I