酷米网(kmw.com),专注高端域名快速交易!

  1. 当前位置: 
  2. 首页 > 
  3. 域名资讯  > 数据结构实习四报告
服务器时间:2018-04-21 14:13:32 (CST +08:00)

数据结构实习四报告

2017-12-17 17:52:14     浏览量: 47

实习题目:利用树型结构的搜索算法模拟因特网域名的查询

学院:计算机与通信工程学院

姓名:

班级: 通信1103

学号:

指导教师:

,

一、[问题描述]

在Internet 的域名系统中,以树型结构实现域名的搜索。即输入某站点的域名,在域名系统的树型结构中进行搜索,直至域名全部匹配成功或匹配失败;若成功则给出该站点的IP 地址166.111.9.2。

二、[测试数据]

可以取常用到的著名站点的域名和IP 地址为例构建域名结构的树,一般应有30个左右的站点域名。当输入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,'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<<"无该网站,无法编辑或者格式错误"<

}

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 下面没有数据

{

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地址

*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;//进入下一次循环准备

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;idata); 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;//编辑就是先把原来的先删除了再创建新的

dataPointer=new char[IP.length() 1];

strcpy(dataPointer,IP.c_str());

string fullWebsite=websiteWithoutIP '/' IP;

writeToFile(fullWebsite);

return true;

}

else

{

return false;

}

}

2、编写主函数代码

#include

#include

#include

#include "binTree.h"

using 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;