数据结构实习四报告.doc

实习题目：利用树型结构的搜索算法模拟因特网域名的查询学院：计算机与通信工程学院 姓名： 班级： 通信1103 学号： 指导教师： 黄旗明 一、问题描述在Internet的域名系统中，以树型结构实现域名的搜索。即输入某站点的域名，在域名系统的树型结构中进行搜索，直至域名全部匹配成功或匹配失败；若成功则给出该站点的IP地址。二、测试数据可以取常用到的著名站点的域名和IP 地址为例构建域名结构的树，一般应有个左右的站点域名。当输入时，输出为“”；而输入时，输出应为“找不到服务器或发生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 或者 treeNode* left; treeNode* right;class binTree/IP二叉树，孩子兄弟表示法，函数bool返回时TRUE凡是成功，否则失败public:/外部函数接口 binTree():initalFlag(false) bool Initialize();/从IP数据库读取数据，并形成IP二叉树，IP数据在倒数第二结点的左孩子里面 char* searchIP(string website);/查找IP，参数为网站名称，例如： void edit(string IP,string websiteWithoutIP);/查找是否存在该网站，否则不进行编辑 bool addNew(string input);/先验证输入是否正确，然后添加新网站和其IP到二叉树和数据库 void destory() destoryNodes(root); binTree() bool initalFlag;private:/内部封装函数和成员 void addNewWebsite(string website);/添加新数据到二叉树，参数为带IP的网址名称，例如：/ 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数据，和各个小结点例如：/分成到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 char11; strcpy(root-data,SystemHead); fstream manipulate; string website; char buffer100; manipulate.open(IPDB.txt,ios:in); if (manipulate.is_open() while (!manipulate.eof() manipulate.getline(buffer,100,n); website=buffer; addNewWebsite(website); manipulate.close(); initalFlag=true; return true; else coutFail to load data to read.endl; manipulate.close(); initalFlag=false; return false; bool binTree:addNew(string input) if (checkStringFormat(input,true,NULL) addNewWebsite(input); return writeToFile(input); else coutFail to addinputendl; return false; bool binTree:writeToFile(string websiteWithIP) fstream writeFile(IPDB.txt,ios:out|ios:app); if (writeFile.is_open() const char* toBeSaved=websiteWithIP.c_str(); writeFile.write(toBeSaved,strlen(toBeSaved)*sizeof(char); writeFileendl;/不要忘记n writeFile.close(); return true; else writeFile.close(); coutCant open the file to write.endl; return false; char* binTree:searchIP(string website) string domain4; const char* parts4; spiltWebsite(website,NULL,domain); for (int i=0;i4;+i) partsi=domaini.c_str(); int count=strlen(parts3)?4:3; bool flag; char* lastPointer=null; treeNode* temp=root; while (count-) temp=searchParts(partscount,temp,lastPointer); if (temp=NULL) return NULL; return lastPointer;void binTree:edit(string IP,string websiteWithoutIP) char * data=NULL; data=searchIP(websiteWithoutIP); if (data!=NULL & editIP(IP,data,websiteWithoutIP) return; cout无该网站，无法编辑或者格式错误=0;-i) const char* temp=domaini.c_str(); current=insertNode(current,temp); char* content=new charIPaddress.length()+1; for ( i=0;ileft=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 charstrlen(data)+1; strcpy(child-right-data,data); return child-right; else return child-right; else child-left=new treeNode; child-left-data=new charstrlen(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地址 *IPaddress=ip; /下面还是分组website int count=0; int j=0;/i means begin and j means the end unsigned int i=j; while (1) for (;ileft; if (current=NULL) return NULL; while (strcmp(current-data,part) & current-right!=NULL ) current=current-right; if (!strcmp(current-data,part) if (lastPointer!=NULL) for (int i=0;idata);+i) if (current-datai=.) return current; lastPointer=current-left-data; return current; return NULL;bool binTree:checkStringFormat(string toBeChecked,bool whetherHasIP,bool IPpart) if (!whetherHasIP) if (toBeChecked0=.|toBeCheckedtoBeChecked.length()-1=.) return false; for (int i=1;ileft!=NULL) destoryNodes(current-left); if (current-right!=NULL) destoryNodes(current-right); if (current-data!=NULL) delete current-data; delete current;bool binTree:editIP(string IP,char*& dataPointer,string websiteWithoutIP) if (checkStringFormat(IP,false,true) delete dataPointer;/编辑就是先把原来的先删除了再创建新的 dataPointer=new charIP.length()+1; strcpy(dataPointer,IP.c_str(); string fullWebsite=websiteWithoutIP+/+IP; writeToFile(fullWebsite); return true; else return false; 2、编写主函数代码#include #include #include #include binTree.husing namespace std;int main() binTree domainTree; const char str=1.IP二叉树初始化 2.查找IP 3.添加新数据 4.编辑IP 5.销毁二叉树 6.退出程序 ; string websiteWithoutIP,websiteWithIP,newIP; char whetherDestory; bool result; char* output; while (true) coutstroption; switch (option) case 1: if (!domainTree.initalFlag) result=domainTree.Initialize(); if (result=false) cout找不到服务器或者DNS错误endl; else cout找不到服务器或者DNS错误endl; break; case 2: if (domainTree.initalFlag) cout请输入网址，例如: websiteWithoutIP; output=domainTree.searchIP(websiteWithoutIP); if (output!=NULL) coutoutputendl; else cout找不到服务器或者DNS错误endl; else cout找不到服务器或者DNS错误endl; break; case 3: if (domainTree.initalFlag) cout请输入网址和IP,例如: /websiteWithIP; result=domainTree.addNew(websiteWithI