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