Inertnet域名IP搜索程序实现.doc

“Inertnet域名IP搜索”程序规范说明1.问题描述（1）题目要求：利用树的兄弟孩子二叉链表结构表示Internet域名系统得树型结构，实现输入某站点域名，在树中搜索其IP地址，直至域名全部匹配成功，若成功则给出其IP，否则给出找不到的信息。（2）基本要求：由用户输入站点域名的数据，建立起一个反映域名结构的树，例如中国农大的站点：在该树中从根到叶子的各层节点应该是root,cn,edu,cau,www.叶子节点www另有一个数据域，存放中国农大站点的IP:03。（3）测试数据：取常用的著名网站域名和IP建立了域名结构树，有35个站点域名。当输入“”时输出为“9”，而输入为时输出为“找不到服务器或发生DNS错误”。2.需求分析（1）本程序用以求出树内已经存在的站点的IP。（2）程序运行之后会提示用户输入站点的域名。（3）程序一开始要求用户输入站点域名和IP的数据，建立查询树且存入文件。（4）用户输入完之后，程序将输出结果，如果找到全匹配的域名则输出其IP，如果找不到输出相应的出错信息。附加：在此作者为程序添加了一个插入新的域名和IP的功能，这样就可以利用本来已经有的文件内容了。3.概要设计（1）为了实现上述程序的功能，应该以孩子兄弟链表存储树，所以需要树的抽象数据类型。（2）存入磁盘文件时还需要另一种文件的抽象数据类型。（3）所有的域名和IP都是以串的形式存的，所以还需要串的抽象数据类型。（4）当用户输入站点的域名时，需要将域名分段存储，在搜索时从最根部依次提出来与树的节点域比较，由于用户输入是从最小级到最根级，弹出时与输入顺序相反，比如输入“”，其中：www是第三级，163是第二级，com是第一级，所以再与树节点比较时，首先比较com，然后比较163，最后才比较www。根据这种“后进先出”的关系，需要栈作为辅助工具，所以需要栈的抽象数据类型。具体内容：1）树的抽象数据类型ADT Tree 数据对象D：站点域名的集合。数据关系R：H（1）D中存在惟一称为根的数据元素root，它在关系H下没有前驱。（2）D-root之后可划分为D1,D2,Dn（n0）对任意的划分都两两不相交。对任意的i（1in），惟一的存在数据元素，有；（3）对应于D-root的划分，H-root ，Xi（i=1,2,n）有惟一的一个划分H1,H2,Hn （n0），对任意的(ij,kn)有，并且对任意的i（1in）, 是Di上的二元关系，（Di，Hi）是一颗符合本定义的树，成为根root的子树。基本操作P：CreateChild（&T）初始条件：树根T已经存在。操作结果：根据用户输入的域名建立此域名的树链，并以T为树根如用户输入，则在建立起以T为根，cn为T的第一个孩子，www为叶子的树链，所有的节点都链在孩子域。InitialTree（&T）操作结果：通过用户输入的数据，构造域名树。其实是将建好的域名树链有序地插到树中相应的位置。Insert（&T）初始条件：树T已经存在。操作结果：插入新的域名及IP。CreateTree（&T, *fp）初始条件：包含树的信息文件已经存在，fp 为指向文件的指针。操作结果：通过从文件中读取数据，构造域名树。DeleteTree（&T）初始条件：T已经存在。操作结果：销毁树，释放空间。 ADT Tree2）文件的抽象数据类型ADT File 数据对象：D =aiaiElemSet, i1,2,n, n0数据关系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：Save（&T）初始条件：树T存在。操作结果：先序遍历树，给叶子节点数据域赋IP值，同时把相关信息存入文件。 ADT File3）串的抽象数据类型ADT String 数据对象：D =aiaiElemSet, i1,2,n, n0数据关系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：CopyChar（&s, *a）初始条件：a是字符串常量。操作结果：生成一个其值等于a的串s。CopyStr（&s, a）初始条件：a是一个串。操作结果：生成一个值等于a的串s。CompareStr（a, b）初始条件：a和b是两个串。操作结果：若ab返回值0;若a=b,返回值=0;若ab，返回值next!=NULL）GetTop（webside,s）;/ 取得域名栈顶元素int t=CompareStr（s,T-data）;/ 比较域名和树的数据域if （t0） Search（T-nextsibling,webside,p）;/ 若域名比树节点值大则递归搜索树节点兄弟else if（t=0）Pop（webside,s）; p=T;/ 若域名和树节点相同则域名链式栈节点出栈Search（T-firstchild,webside,p）;/ 继续搜索树节点的孩子，即下一层 / end else / end if / Search（2）关于树的操作void CreateChild（Tree &T,Stack &webside） / 用户输入一个网址域名，域名已经被输入到栈中，为域名建立相应的域名树链if（webside-next!=NULL）t=new TreeNode;/ 新开一个节点Pop（webside,s）;/ 从栈中取出域名第一部分CopyStr（t-data,s）;/ 把第一部分赋值给树节点的数据域t-firstchild=t-nextsibling=NULL;/ 把树节点的孩子和兄弟链域暂置空t-IP0=0;/ 把树节点的IP域置0T-firstchild=t;/ 让根节点的孩子域指向新建的树节点CreateChild（t,webside）;/ 再以此树节点为根建立新的树节点，/ 直到把域名全部赋值到树节点中去if（t-firstchild=NULL）cout请输入域名IPt-IP; / end if / end if / CreateChildvoid Insert（Tree &T）/ 将域名树链插入到树T中do cout请输入站点域名:firstchild=NULL）if（p-IP0!=0）/ 若发现输入了重复的域名则给出提示cout你输入了重复的域名next=NULL）/ 若发现输入了错误的域名，则给出相应/ 的提示cout你输入了错误的域名!firstchild;a=CompareStr（t-data,s）;/ 比较域名与已经存在的兄弟节点if（a0）CreateChild（p,webside）;/ 若域名比兄弟节点小，则前插p-firstchild-nextsibling=t; / end ifelse while（t-nextsibling!=NULL&（a=CompareStr（t-nextsibling-data,s）nextsibling;/ 若域名比兄弟节点大，则后插q=new TreeNode;Pop（webside,s）;CopyStr（q-data,s）;q-firstchild=NULL;q-IP0=0;/ 给新开节点赋值q-nextsibling=t-nextsibling;/ 新开节点的兄弟指针指向插入处节/ 点的兄弟t-nextsibling=q;/ 插入处的节点的兄弟指针指向新开节点CreateChild（q,webside）;/ 把整个域名树链插入 / end else / end else / end elseDeleteStack（webside）;cout是否要继续输入新域名?（y/n）data,root）;/ 建立树的根节点T-firstchild=T-nextsibling=NULL;T-IP0=0;Insert（T）;/ 把新的域名树链插入树中 / InitialTreevoid CreateTree（Tree &T,FILE *fp）/ 文件已经存在，从文件中读出数据，用递归算法先序遍历构建树的孩子，兄弟二叉链表结构if（!feof（fp）T=new TreeNode;/ 新建树节点f=new FileNode;/ 新建文件节点用于读取磁盘文件中的数据if（fread（f,sizeof（struct FileNode）,1,fp）!=1）cout无法打开文件!data,f-data）;CopyStr（T-IP,f-IP）;/ 将文件节点的IP的值赋给树节点IPif（f-ltag）CreateTree（T-firstchild,fp）;/ 若树节点有孩子则递归建立其孩子else T-firstchild=NULL;/ 若无孩子则孩子链域置为空if（f-rtag）CreateTree（T-nextsibling,fp）;/ 若树节点有兄弟则递归建立其兄弟else T-nextsibling=NULL;/ 若无兄弟则兄弟链域置为空delete f; / end if / CreateTreevoid DeleteTree（Tree &T）/ 用递归算法销毁树，释放空间if（T）DeleteTree（T-firstchild）;/ 销毁树的左子树DeleteTree（T-nextsibling）;/ 销毁树的右子树delete T;/ 销毁树的根节点 / end if / DeleteTree（3）串的操作void CopyStr（String &a,String b）/ 将串b的值赋给串afor（int i=0;bi!=0;i+） ai=bi;/ 将b数组中的值一个一个赋给aai=0; / CopyStrvoid CopyChar（String &a,char* b）/ 将字符串b的值赋给串afor（int i=0;*b!=0;b+,i+） ai=*b;ai=0; / CopyStrint CompareStr（String a,String b） / 串a和b从第一个字符开始比较，直到出现第一个不相同的字符为止for（int i=0;ai!=0&bi!=0;i+）/ 如果ab,return 0;if（ai!=bi） return ai-bi;/ 如果ab,return next=NULL;/ 头节点指向空 / InitialStackvoid Push（Stack &s,SElemType e）/ 将元素e插入链式栈中，成为新的栈顶元素p=new SNode;/ 为新的栈顶元素分配空间CopyStr（p-data,e）;/ 将e的值赋给新节点数据域p-next=s-next;/ 插入新的栈顶元素s-next=p;/ 修改栈顶指针 / Pushvoid Pop（Stack &s,SElemType &e） / 若栈为空则给出相应的信息，若不空则删除栈顶元素并将其值赋给e if（!s-next） cout空栈!next-data）;/ 取出栈顶元素的值赋给ep=s-next;/ 删除栈顶元素s-next=p-next; delete p;/ 释放空间 / Popvoid GetTop（Stack& s,SElemType &e） / 将栈顶元素的值赋给e，但不删除栈顶元素if（!s-next）cout空栈!next-data）; / GetTopvoid DeleteStack（Stack &s）/ 将栈的链表节点一个一个删掉while（s-next!=NULL）p=s-next;s-next=p-next ;delete p; / end whiledelete s; / DeleteStack（5）文件的操作void Save（Tree T,FILE *fp） / 用递归算法先序遍历树，为每一个节点建立一个对应的文件节点。/ 文件节点的数据域存储和树节点相同的数据，/ 文件节点的左右标志域分别表示树节点是否有孩子或兄弟if（T）f=new FileNode;/ 建立新的文件节点CopyStr（f-data,T-data）;/ 将树节点的数据域赋给文件节点数据域f-ltag=（T-firstchild=NULL?0:1）;/ 给文件节点左标志赋值：0表示无孩子节点f-rtag=（T-nextsibling=NULL?0:1）;/ 给文件节点右标志赋值：0表示无兄弟节点CopyStr（f-IP,T-IP）; if（fwrite（f,sizeof（struct FileNode）,1,fp）!=1）cout无法打开文件!firstchild,fp）;/ 将左孩子树保存入文件Save（T-nextsibling,fp）;/将右兄弟子树保存文件 / end if / Save（6）主函数Main（）a=getchar（）;/ 用户输入选择switch（a）case 1: / 1表示输入域名和IP建立树if（!（fp=fopen（Internet,wb） cout无法打开文件!endl;/ 打开文件InitialTree（T）;/ 初始化建立树Save（T,fp）;/ 将树以文件形式保存fclose（fp）;DeleteTree（T）;/ 删除树break;case 2:/ 2表示将用户输入的新域名和IP插入已有树中if（fp=fopen（Internet,rb）=NULL） cout无法打开文件!endl;/ 打开文件并读取CreateTree（T,fp）;/ 从文件读取数据建立树fclose（fp）;/ 关闭文件if（!（fp=fopen（Internet,wb） cout无法打开文件!endl;/ 打开文件并写入Insert（T）;/ 将新的域名IP插入Save（T,fp）;/ 将新的树保存到文件中fclose（fp）;/ 关闭文件break;case 3:/ 3表示查询用户输入的域名相应得IPif（fp=fopen（Internet,rb）=NULL） cout无法打开文件!endl;/ 打开并读取文件CreateTree（T,fp）;/ 根据文件建立树fclose（fp）;/ 关闭文件do cout输入你想搜索的域名（请注意大小写）:firstchild=NULL&webside-next=NULL） coutIPendl;else cout无法找到服务器或DSN错误!endl;cout是否继续查询? y/nnext!=NULL）Tree t=new TreeNode;/ 新开一个节点Pop（webside,s）;/ 从栈中取出域名第一部分CopyStr（t-data,s）;/ 把第一部分赋值给树节点的数据域t-firstchild=t-nextsibling=NULL;/ 把树节点的孩子和兄弟链域暂置空t-IP0=0;/ 把树节点的IP域置0T-firstchild=t;/ 让根节点的孩子域指向新建的树节点CreateChild（t,webside）;/ 以此树节点为根建立新的树节点，/ 直到把域名全部赋值到树节点中去if（t-firstchild=NULL）cout请输入域名IPt-IP;void Insert（Tree &T）Stack webside;Tree t,q,p=NULL;String s;char ch;int control=1;do cout请输入站点域名:firstchild=NULL）if（p-IP0!=0&webside-next=NULL） cout你输入了重复的域名next=NULL） cout你输入了错误的域名!firstchild;int a=CompareStr（t-data,s）;/ 比较域名与已经存在的兄弟节点if（a0）CreateChild（p,webside）;/ 若域名比兄弟节点小，则前插p-firstchild-nextsibling=t;else while（t-nextsibling!=NULL&（a=CompareStr（t-nextsibling-data,s）nextsibling;/ 若域名比兄弟节点大，则后插q=new TreeNode;Pop（webside,s）;CopyStr（q-data,s）;q-firstchild=NULL;q-IP0=0;q-nextsibling=t-nextsibling;t-nextsibling=q;CreateChild（q,webside）;DeleteStack（webside）;cout是否要继续输入新域名?（y/n）data,root）;/ 建立树的根节点T-firstchild=T-nextsibling=NULL;T-IP0=0; Insert（T）;/ 把新的域名树链插入树中void CreateTree（Tree &T,FILE *fp） / 文件已经存在从文件中读出数据，用递归算法先序遍历构建树的孩子兄弟二叉链表结构FileNode *f;if（!feof（fp）T=new TreeNode;/ 新建树节点f=new FileNode;/ 新建文件节点，用于读取磁盘文件中的数据if（fread（f,sizeof（struct FileNode）,1,fp）!=1）cout无法打开文件!data,f-data）;CopyStr（T-IP,f-IP）;/ 将文件节点的数据域的值赋给树节点数据域if（f-ltag）CreateTree（T-firstchild,fp）;/ 若树节点有孩子，则递归建立其孩子else T-firstchild=NULL;/ 若无孩子，则孩子链域置为空if（f-rtag）CreateTree（T-nextsibling,fp）;/ 若树节点有兄弟，则递归建立其兄弟else T-nextsibling=NULL;/ 若无兄弟，则兄弟链域置为空delete f;void DeleteTree（Tree &T）if（T）DeleteTree（T-firstchild）;/ 销毁树的左子树DeleteTree（T-nextsibling）;/ 销毁树的右子树delete T;/ 销毁树的根节点/*-String-*/void CopyStr（String &a,String b）/ 将串b的值赋给串afor（int i=0;bi!=0;i+） ai=bi;ai=0;void CopyChar（String &a,char* b）/ 将字符串b的值赋给串afor（int i=0;*b!=0;b+,i+） ai=*b;ai=0;int CompareStr（String a,String b）/ 比较串a,bfor（int i=0;ai!=0&bi!=0;i+）/ 如果ab,return 0;if（ai!=bi）return ai-bi;/ 如果ab,return next=NULL;/ 头节点指向空void Push（Stack &s,SElemType e） / 将元素e插入链式栈中,成为新的栈顶元素Stack p=new SNode;/ 为新的栈顶元素分配空间CopyStr（p-data,e）; / 将e的值赋给新节点数据域p-next=s-next; / 插入新的