数据结构实习四报告

实习题目：利用树型结构搜索算法模拟因特网域名查询学院：计算机与通信工程学院姓名：班级：通信1103学号：指导教师：黄旗明一、［问题描述］在Internet域名系统中，以树型结构实现域名搜索。即输入某站点域名，在域名系统树型结构中进行搜索，直至域名全部匹配成功或匹配失败；若成功则给出该站点IP地址。二、[测试数据]能够取惯用到著名站点域名和IP地址为例构建域名结构树，通常应有３０个左右站点域名。当输入.时，输出为“”；而输入.时，输出应为“找不到服务器或发生DNS错误”。三、［实现提醒］树存放结构采取孩子－弟兄链表。二叉链表树结构是一个动态结构，除第一次生成过程需要人工输入数据外，以后每次进行搜索查询大，应首先从文件中保留是数据自动生成树结构。为处理二叉链表与文件之间转换，能够经过先序遍历方法保留和恢复二叉链表。比如一个二叉链表文件保留形式以下：四、［问题讨论］实际使用中，树结构使用机会比二叉树还要多，通常情况下都采取孩子－弟兄链表作树存放结构，此时也可将树视作二叉树，并将对树进行操作转换成对二叉树对应操作。五、［实际设计及详细代码］1、创建题头文件binTree#include<fstream>usingnamespacestd;classtreeNode//结点类{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;};classbinTree//IP二叉树，孩子弟兄表示法，函数bool返回时TRUE凡是成功，不然失败{public://外部函数接口binTree():initalFlag(false){}boolInitialize();//从IP数据库读取数据，并形成IP二叉树，IP数据在倒数第二结点左孩子里面char*searchIP(stringwebsite);//查找IP，参数为网站名称，比如：.comvoidedit(stringIP,stringwebsiteWithoutIP);//查找是否存在该网站，不然不进行编辑booladdNew(stringinput);//先验证输入是否正确，然后添加新网站和其IP到二叉树和数据库voiddestory(){destoryNodes(root);}~binTree(){}boolinitalFlag;private://内部封装函数和组员voidaddNewWebsite(stringwebsite);//添加新数据到二叉树，参数为带IP网址名称，比如：./boolwriteToFile(stringwebsiteWithIP);//将带IP地址网址名称写入文件尾部booleditIP(stringIP,char*&dataPointer,stringwebsiteWithoutIP);//编辑存在网站IP数据，参数分别是IP,指向IP指针，和该网站名称treeNode*insertNode(treeNode*&head,constchar*data);//向HEAD所指向指针孩子区添加内容为data结点，假如存在则不添加voidspiltWebsite(string&website,string*IPaddress,string*domain);//将带有IP网站数据分成IP数据，和各个小结点比如：.com/分成到IPADDRESS和www，.taobao，.com到domainstring数组treeNode*searchParts(constchar*part,treeNode*level,char*&lastPointer);//查找PART所指向数据，（.com），level为该数据所在层级，lastpointer当包括孩子结点ip数据时，才赋值，通常为nullboolcheckStringFormat(stringtoBeChecked,boolwhetherHasIP,boolIPpart);//检验string数据是否符合IP格式或网站名称或带IP网站名称voiddestoryNodes(treeNode*¤t);//删除二叉树全部结点以及数据treeNode*root;//根结点，不附加内容。左结点指向IP二叉树};boolbinTree::Initialize(){root=newtreeNode;root->data=newchar[11];strcpy(root->data,"SystemHead");fstreammanipulate;stringwebsite;charbuffer[100];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;returntrue;}else{cout<<"Failtoloaddatatoread."<<endl;manipulate.close();initalFlag=false;returnfalse;}}boolbinTree::addNew(stringinput){if(checkStringFormat(input,true,NULL)){ addNewWebsite(input); returnwriteToFile(input);}else{cout<<"Failtoadd"<<input<<endl;returnfalse;}}boolbinTree::writeToFile(stringwebsiteWithIP){fstreamwriteFile("IPDB.txt",ios::out|ios::app);if(writeFile.is_open()){constchar*toBeSaved=websiteWithIP.c_str();writeFile.write(toBeSaved,strlen(toBeSaved)*sizeof(char));writeFile<<endl;//不要忘记"\n"writeFile.close();returntrue;}else{writeFile.close();cout<<"Can'topenthefiletowrite."<<endl;returnfalse;}}char*binTree::searchIP(stringwebsite){stringdomain[4];constchar*parts[4];spiltWebsite(website,NULL,domain);for(inti=0;i<4;++i){parts[i]=domain[i].c_str();}intcount=strlen(parts[3])?4:3;boolflag;char*lastPointer="null";treeNode*temp=root;while(count--){temp=searchParts(parts[count],temp,lastPointer);if(temp==NULL){returnNULL;}}returnlastPointer;}voidbinTree::edit(stringIP,stringwebsiteWithoutIP){char*data=NULL;data=searchIP(websiteWithoutIP);if(data!=NULL&&editIP(IP,data,websiteWithoutIP)){return;}cout<<"无该网站，无法编辑或者格式错误"<<endl;}voidbinTree::addNewWebsite(stringwebsite){stringIPaddress;stringdomain[4];spiltWebsite(website,&IPaddress,domain);intcount=domain[3].length()?4:3;//条件运算符treeNode*current=root;for(inti=count-1;i>=0;--i){constchar*temp=domain[i].c_str();current=insertNode(current,temp);}char*content=newchar[IPaddress.length()+1];for(i=0;i<=IPaddress.length();++i){content[i]=IPaddress[i];}current->left=newtreeNode(content);}treeNode*binTree::insertNode(treeNode*&head,constchar*data){treeNode*child=head;if(child->left!=NULL)//左孩子为空表示head下面没有数据{child=child->left;//假如存在，则查找head全部孩子if(!strcmp(child->data,data))//比较字符串数据，匹配成功返回0,所以!0=1{returnchild;}while(child->right!=NULL&&strcmp(child->right->data,data))//不匹配继续查找{child=child->right;}if(child->right==NULL)//查找失败，则新建{child->right=newtreeNode;child->right->data=newchar[strlen(data)+1];strcpy(child->right->data,data);returnchild->right;}else{returnchild->right;}}else{child->left=newtreeNode;child->left->data=newchar[strlen(data)+1];strcpy(child->left->data,data);returnchild->left;}}voidbinTree::spiltWebsite(string&website,string*IPaddress,string*domain){intposition=website.find_first_of('/');stringip;if(position!=-1)//预防多出空格造成错误{ip=website.substr(position+1,website.length()-position);//IPADDRESSwebsite.erase(position,ip.length()+1);//删除IP地址部分if(IPaddress!=NULL){ //IP地址*IPaddress=ip;}}//下面还是分组websiteintcount=0;intj=0;//imeansbeginandjmeanstheendunsignedinti=j;while(1){for(;i<website.length()&&website[i]!='.';++i);domain[count]=website.substr(j,i-j);if(i==website.length())//最终一次赋值完后，return{return;}j=i;++i;//进入下一次循环准备++count;}}treeNode*binTree::searchParts(constchar*part,treeNode*level,char*&lastPointer){treeNode*current=level->left;if(current==NULL){returnNULL;}while(strcmp(current->data,part)&¤t->right!=NULL){current=current->right;}if(!strcmp(current->data,part)){if(lastPointer!=NULL){for(inti=0;i<strlen(current->data);++i){if(current->data[i]=='.'){returncurrent;}}lastPointer=current->left->data;}returncurrent;}returnNULL;}boolbinTree::checkStringFormat(stringtoBeChecked,boolwhetherHasIP,boolIPpart){if(!whetherHasIP){if(toBeChecked[0]=='.'||toBeChecked[toBeChecked.length()-1]=='.'){returnfalse;}for(inti=1;i<toBeChecked.length()-1;++i){boolflag=isalpha(toBeChecked[i])&&!IPpart;if(isdigit(toBeChecked[i])||flag){continue;}elseif(toBeChecked[i]=='.'){if(toBeChecked[i-1]=='.'||toBeChecked[i+1]=='.'){returnfalse;}}else{returnfalse;}}returntrue;}else{intinterval=toBeChecked.find_first_of('/');if(interval!=-1){ intlength2=toBeChecked.length()-interval; returncheckStringFormat(toBeChecked.substr(0,interval),false,false)&& checkStringFormat(toBeChecked.substr(interval+1,length2),false,true);}returnfalse;}}voidbinTree::destoryNodes(treeNode*¤t){if(current->left!=NULL){destoryNodes(current->left);}if(current->right!=NULL){destoryNodes(current->right);}if(current->data!=NULL){delete[]current->data;}deletecurrent;}boolbinTree::editIP(stringIP,char*&dataPointer,stringwebsiteWithoutIP){if(checkStringFormat(IP,false,true)){delete[]dataPointer;//编辑就是先把原来先删除了再创建新dataPointer=newchar[IP.length()+1];strcpy(dataPointer,IP.c_str());stringfullWebsite=websiteWithoutIP+'/'+IP;writeToFile(fullWebsite);returntrue;}else{returnfalse;}}2、编写主函数代码#include<fstream>#include<iostream>#include<string>#include"binTree.h"usingnamespacestd;intmain(){binTreedomainTree;constcharstr[]="1.IP二叉树初始化2.查找IP3.添加新数据4.编辑IP5.销毁二叉树6.退出程序";stringwebsiteWithoutIP,websiteWithIP,newIP;charwhetherDestory;boolresult;char*output;while(true){cout<<str<<endl;charoption;cin>>option; 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<<"请输入网址，比如:."<<endl; cin>>websiteWithoutIP; output=domainTree.searchIP(websiteWithoutIP);if(output!=NULL){cout<<output<<endl;}else{cout<<"找不到服务器或者DNS错误"<<endl;}}else{cout<<"找不到服务器或者DNS错误"<<endl;} break; case'3':if(domainTree.initalFlag){ cout<<"请输入网址和IP,比如:./"<<endl; cin>>websiteWithIP; result=domainTree.addNew(websiteWithIP);if(result==fals