數(shù)據(jù)結構實習四報告
實習題目：利用樹型結構的搜索算法模擬因特網(wǎng)域名的查詢學院：計算機與通信工程學院姓名：班級： 通信1103學號：指導教師： ,一、［問題描述］在Internet 的域名系統(tǒng)
實習題目：利用樹型結構的搜索算法模擬因特網(wǎng)域名的查詢
學院：計算機與通信工程學院
姓名：
班級： 通信1103
學號：
指導教師：
,一、［問題描述］
在Internet 的域名系統(tǒng)中，以樹型結構實現(xiàn)域名的搜索。即輸入某站點的域名，在域名系統(tǒng)的樹型結構中進行搜索，直至域名全部匹配成功或匹配失?。蝗舫晒t給出該站點的IP 地址166.111.9.2。
二、[測試數(shù)據(jù)]
可以取常用到的著名站點的域名和IP 地址為例構建域名結構的樹，一般應有３０個左右的站點域名。當輸入www.tsinghua.edu.cn 時，輸出為“166.111.9.2”；而輸入www.tsinghuo.edu.cn 時，輸出應為“找不到服務器或發(fā)生DNS 錯誤”。
三、［實現(xiàn)提示］
樹的存儲結構采用孩子－兄弟鏈表。
二叉鏈表的樹結構是一種動態(tài)結構，除第一次生成的過程需要人工輸入數(shù)據(jù)外，以后每次進行搜索查詢大，應首先從文件中保存是數(shù)據(jù)自動生成樹結構。為解決二叉鏈表與文件之間的轉換，可以通過先序遍歷的辦法保存和恢復二叉鏈表。例如一個二叉鏈表的文件保存形式如下：
四、［問題討論］
實際的使用中，樹結構的使用機會比二叉樹還要多，一般情況下都采用孩子－兄弟鏈表作樹的存儲結構，此時也可將樹視作二叉樹，并將對樹進行的操作轉換成對二叉樹的相應操作。
五、［實際設計及具體代碼］
1、創(chuàng)建題頭文件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;//數(shù)據(jù)格式 www或.taobao 或者 0.0.0.0
treeNode* left;
treeNode* right;
};
class binTree//IP二叉樹，孩子兄弟表示法，函數(shù)bool 返回時TRUE 凡是成功，否則失敗 {
public://外部函數(shù)接口
binTree():initalFlag(false)
{
}
bool Initialize();//從IP 數(shù)據(jù)庫讀取數(shù)據(jù)，并形成IP 二叉樹，IP 數(shù)據(jù)在倒數(shù)第二結點的左孩子里面
char* searchIP(string website);//查找IP ，參數(shù)為網(wǎng)站名稱，例如：www.taobao.com void edit(string IP,string websiteWithoutIP);//查找是否存在該網(wǎng)站，否則不進行編輯
bool addNew(string input);//先驗證輸入是否正確，然后添加新網(wǎng)站和其IP 到二叉樹和數(shù)據(jù)庫
void destory()
{
destoryNodes(root);
}
~binTree()
{
}
bool initalFlag;
private://內部封裝函數(shù)和成員
void addNewWebsite(string website);//添加新數(shù)據(jù)到二叉樹，參數(shù)為帶IP 的網(wǎng)址名稱，例如：www.cau.edu.cn/0.0.0.0
bool writeToFile(string websiteWithIP);//將帶IP 地址的網(wǎng)址名稱寫入文件尾部 bool editIP(string IP,char*& dataPointer,string websiteWithoutIP);//編輯存在網(wǎng)站的IP 數(shù)據(jù)，參數(shù)分別是IP, 指向IP 的指針，和該網(wǎng)站的名稱
treeNode* insertNode(treeNode*& head,const char* data);//向HEAD 所指向指針的孩子區(qū)添加內容為data 的結點，如果存在則不添加
void spiltWebsite(string& website,string* IPaddress,string* domain);//將帶有IP 網(wǎng)站數(shù)據(jù)分成IP 數(shù)據(jù)，和各個小結點例如：www.taobao.com/0.0.0.0分成0.0.0.0到IPADDRESS 和www ，.taobao ，.com 到domain string 數(shù)組
treeNode* searchParts(const char* part,treeNode* level,char*& lastPointer);//查找PART 所指向的數(shù)據(jù)，（.com ），level 為該數(shù)據(jù)所在的層級，lastpointer 當涉及孩子結點的ip 數(shù)據(jù)時，才賦值，一般為null
bool checkStringFormat(string toBeChecked,bool whetherHasIP,bool IPpart);//檢
,查string 數(shù)據(jù)是否符合IP 格式或網(wǎng)站名稱或帶IP 的網(wǎng)站名稱
void destoryNodes(treeNode*& current);//刪除二叉樹所有結點以及數(shù)據(jù) 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,'n');
website=buffer;
addNewWebsite(website);
}
manipulate.close();
initalFlag=true;
return true;
}
else
{
cout<<"Fail to load data to read."< manipulate.close(); initalFlag=false; return false; } } bool binTree::addNew(string input) { if (checkStringFormat(input,true,NULL)) { addNewWebsite(input); return writeToFile(input); } else { cout<<"Fail to add"< 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)); writeFile< writeFile.close(); return true; } else { writeFile.close(); cout<<"Can't open the file to write."< return false; } } char* binTree::searchIP(string website) { string domain[4]; const char* parts[4]; spiltWebsite(website,NULL,domain); for (int i=0;i<4; i) { parts[i]=domain[i].c_str(); } int count=strlen(parts[3])?4:3; bool flag; char* lastPointer="null"; treeNode* temp=root; while (count--) { } return lastPointer; } void binTree::edit(string IP,string websiteWithoutIP) { char * data=NULL; data=searchIP(websiteWithoutIP); if (data!=NULL && editIP(IP,data,websiteWithoutIP)) { return; } cout<<"無該網(wǎng)站，無法編輯或者格式錯誤"< } void binTree::addNewWebsite(string website) { string IPaddress; string domain[4]; spiltWebsite(website,&IPaddress,domain); int count=domain[3].length()?4:3;//條件運算符 treeNode* current=root; for (int i=count-1;i>=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 下面沒有數(shù)據(jù) { child=child->left;//如果存在，則查找head 的所有孩子 if (!strcmp(child->data,data))//比較字符串數(shù)據(jù)，匹配成功返回0, 所以!0=1 { return child; } while (child->right!=NULL && strcmp(child->right->data,data))//不匹配繼續(xù)查找 { 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地址 *IPaddress=ip; } } //下面還是分組website int count=0; int j=0;//i means begin and j means the end unsigned int i=j; while (1) { for (;i domain[count]=website.substr(j,i-j); if (i==website.length())//最后一次賦值完后，return { return; } j=i; i;//進入下一次循環(huán)準備 count; } } treeNode* binTree::searchParts(const char* part,treeNode* level,char*& lastPointer) { treeNode* current=level->left; 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;i { if (current->data[i]=='.') { return current; } } lastPointer=current->left->data; } return current; } return NULL; } bool binTree::checkStringFormat(string toBeChecked,bool whetherHasIP,bool IPpart) { if (!whetherHasIP) { if (toBeChecked[0]=='.'||toBeChecked[toBeChecked.length()-1]=='.') { return false; } for (int i=1;i { bool flag=isalpha(toBeChecked[i])&&!IPpart; if (isdigit(toBeChecked[i])||flag) { continue; } else if(toBeChecked[i]=='.') { if (toBeChecked[i-1]=='.'||toBeChecked[i 1]=='.') { return false; } } else { return false; } } return true; } else { int interval=toBeChecked.find_first_of('/'); if (interval!=-1) { int length2=toBeChecked.length()-interval; return checkStringFormat(toBeChecked.substr(0,interval),false,false)&& checkStringFormat(toBeChecked.substr(interval 1,length2),false,true); } return false; } } void binTree::destoryNodes(treeNode*& current) { if (current->left!=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;//編輯就是先把原來的先刪除了再創(chuàng)建新的 dataPointer=new char[IP.length() 1]; strcpy(dataPointer,IP.c_str()); string fullWebsite=websiteWithoutIP '/' IP; writeToFile(fullWebsite); return true; } else { return false; } } 2、編寫主函數(shù)代碼 #include #include #include #include "binTree.h" using namespace std; int main() { binTree domainTree; const char str[]="1.IP二叉樹初始化 2.查找IP 3.添加新數(shù)據(jù) 4.編輯IP 5.銷毀二叉樹 6.退出程序 "; string websiteWithoutIP,websiteWithIP,newIP; char whetherDestory; bool result; char* output;