数据结构实验报告

数据结构课程实验报告题目：互联网域名查询姓名：学院：信息科学与工程学院班级：学号：1实验三树和图应用类实验一、问题定义及i需求分析1.问题描述互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如等。因此，域名搜索可以看成是树的遍历问题。2.实验要求设计搜索互联网域名的程序。（1）采用树的孩子兄弟链表等存储结构。（2）创建树形结构。（3）通过深度优先遍历搜索。（4）通过层次优先遍历搜索。3.数据输入的形式输入域名地址。如：地址或者出错时输出“找不到服务器或发生DNS错误”二、概要设计（1）为了实现上述程序的功能，应该以孩子兄弟链表存储树，所以需要树的抽象数据类型。（2）存入磁盘文件时还需要另一种文件的抽象数据类型。（3）所有的域名和IP都是以串的形式存的，所以还需要串的抽象数据类型。（4）当用户输入站点的域名时，需要将域名分段存储，在搜索时从最根部依次提出来与树的节点域比较，由于用户输入是从最小级到最根级，弹出时与输入顺序相反，比如输入“”，其中：是第三级，163是第二级，com是第一级，所以再与树节点比较时，首先比较com，然后比较163，最后才比较。根据这种“后进先出”的关系，需要栈作为辅助工具，所以需要栈的抽象数据类型。具体内容：1）树的抽象数据类型ADTTree{数据对象D：站点域名的集合。数据关系R：{H}（1）D中存在惟一称为根的数据元素root，它在关系{H}下没有前驱。（2）D-{root}之后可划分为D1,D2,…,Dn（n0）对任意的划分都两两不相交。对任意的i（1≤i≤n），惟一的存在数据元素DiXi，有HXi,root；（3）对应于D-{root}的划分，H-{〈root，Xi〉}（i=1,2,…,n）有惟一的一个划分H1,H2,…,Hn（n0），对任意的kj(i≤j,k≤n)2有kjHH，并且对任意的i（1≤i≤n）,jH是Di上的二元关系，（Di，{Hi}）是一颗符合本定义的树，成为根root的子树。基本操作P：CreateChild（&T）初始条件：树根T已经存在。操作结果：根据用户输入的域名建立此域名的树链，并以T为树根如用户输入，则在建立起以T为根，cn为T的第一个孩子，为叶子的树链，所有的节点都链在孩子域。InitialTree（&T）操作结果：通过用户输入的数据，构造域名树。其实是将建好的域名树链有序地插到树中相应的位置。Insert（&T）初始条件：树T已经存在。操作结果：插入新的域名及IP。CreateTree（&T,*fp）初始条件：包含树的信息文件已经存在，fp为指向文件的指针。操作结果：通过从文件中读取数据，构造域名树。DeleteTree（&T）初始条件：T已经存在。操作结果：销毁树，释放空间。}ADTTree2）文件的抽象数据类型ADTFile{数据对象：D=｛ai│ai∈ElemSet,i＝1,2,…,n,n≥0｝数据关系：R=｛〈ai-1,ai〉│ai-1,ai∈D,i＝1,2,…,n｝基本操作：│Save（&T）初始条件：树T存在。操作结果：先序遍历树，给叶子节点数据域赋IP值，同时把相关信息存入文件。}ADTFile3）串的抽象数据类型ADTString{数据对象：D=｛ai│ai∈ElemSet,i＝1,2,…,n,n≥0｝数据关系：R=｛〈ai-1,ai〉│ai-1,ai∈D,i＝1,2,…,n｝基本操作：CopyChar（&s,*a）初始条件：a是字符串常量。操作结果：生成一个其值等于a的串s。CopyStr（&s,a）3初始条件：a是一个串。操作结果：生成一个值等于a的串s。CompareStr（a,b）初始条件：a和b是两个串。操作结果：若ab返回值0;若a=b,返回值=0;若ab，返回值0。DeleteString（&s）初始条件：串s存在。操作结果：销毁串。}ADTString4）栈的抽象数据类型ADTStack{数据对象：D=｛ai│ai∈ElemSet,i＝1,2,…,n,n≥0｝数据关系：R=｛〈ai-1,ai〉│ai-1,ai∈D,i＝1,2,…,n｝约定1a为栈底，na为栈顶基本操作：InitialStack（&s）操作结果：构造一个空栈。GetTop（s，&e）初始条件：栈s已经存在且非空。操作结果：用e返回栈s的栈顶元素。Push（&s,e）初始条件：栈s已经存在且非空。操作结果：插入元素e为新的栈顶元素。Pop（&s,&e）初始条件：栈s已经存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。DeleteStack（&s）初始条件：s已经存在。操作结果：销毁栈，释放空间。}ADTStack5）本程序5个模块本程序有5个模块：主程序模块，树模块（实现树抽象数据类型），文件模块（实现文件抽象数据类型），串模块（实现串抽象数据类型），栈模块（实现栈抽象数据类型）4主函数模块数模块栈模块文件模块串模块三、详细设计typedefunsignedcharString[30];//存放域名和IP的串结构typedefstructTreeNode{//树的节点ElemTypedata,IP;//数据域（用来放域名）和IP域（用来放IP）structTreeNode*firstchild,*nextsibling;//指向孩子和兄弟的指针//兄弟表示同一层，孩子表示下一层}TreeNode,*Tree;typedefstructFileNode{//存入文件的节点ElemTypedata,IP;//数据域（用来放域名）和IP域（用来放IP）intltag,rtag;//左右标志域：0表示无孩子，1表示有孩子}FileNode;typedefstructSNode{//用户输入的域名存在栈节点SElemTypedata;//数据域（用来存放域名被'.'分开的一部分structSNode*next;//指针域，指向域名下一部分}SNode,*Stack;（1）基本操作StackCreateWeb（）{//用户输入域名时按'.'将域名分开分别放入链式栈中//最后将root入栈，为查找做准备，返回栈顶指针CopyChar（root,root）;//把root的值赋给串rootInitialStack（webside）;//初始化链式栈do{a=getchar（）;//输入域名5for（inti=0;a!='.'&&a!='\n';i++）{s[i]=a;a=getchar（）;//得到两个'.'间的域名，将其值放入一个串中}s[i]='\0';Push（webside,s）;//将串的值入栈}while（a!='\n'）;Push（webside,root）;//将root入栈returnwebside;//返回栈顶的指针}//CreateWebvoidSearch（TreeT,Stack&webside,Tree&p）{//用递归算法通过域名查找相应的IP，返回相同层的指针//若存在则输出IP，若不存在则输出相应的出错信息if（T&&webside-next!=NULL）{GetTop（webside,s）;//取得域名栈顶元素intt=CompareStr（s,T-data）;//比较域名和树的数据域if（t0）Search（T-nextsibling,webside,p）;//若域名比树节点值大则递归搜索树节点兄弟elseif（t==0）{Pop（webside,s）;p=T;//若域名和树节点相同则域名链式栈节点出栈Search（T-firstchild,webside,p）;//继续搜索树节点的孩子，即下一层}//endelse}//endif}//Search（2）关于树的操作voidCreateChild（Tree&T,Stack&webside）{//用户输入一个网址域名，域名已经被输入到栈中，为域名建立相应的域名树链if（webside-next!=NULL）{t=newTreeNode;//新开一个节点Pop（webside,s）;//从栈中取出域名第一部分CopyStr（t-data,s）;//把第一部分赋值给树节点的数据域t-firstchild=t-nextsibling=NULL;//把树节点的孩子和兄弟链域暂置空t-IP[0]='\0';//把树节点的IP域置0T-firstchild=t;//让根节点的孩子域指向新建的树节点CreateChild（t,webside）;//再以此树节点为根建立6新的树节点，//直到把域名全部赋值到树节点中去if（t-firstchild==NULL）{cout请输入域名IPendl;//若是叶子节点则要求用户输入IPcint-IP;}//endif}//endif}//CreateChildvoidInsert（Tree&T）{//将域名树链插入到树T中do{cout请输入站点域名:endl;webside=CreateWeb（）;//为用户输入的域名建立链表栈Search（T,webside,p）;//在树中查找与域名节点相同的节点，//每一部分查找相匹配的树节点，返回指向//最后一个与域名节点相同的树节点的指针if（p-firstchild==NULL）{if（p-IP[0]!='\0'）//若发现输入了重复的域名则给出提示cout你输入了重复的域名endl;elseCreateChild（p,webside）;//若这个树节点没有孩子，则直接把新的//域名建立成新的树，并让这个树节点孩//子域指向次新开的域名树。//即将域名节点作为此树节点的第一个孩子}//endifelse{if（webside-next==NULL）//若发现输入了错误的域名，则给出相应//的提示cout你输入了错误的域名!endl;else{GetTop（webside,s）;//若这个树节点有孩子，则在他的孩子的//兄弟中找到新开域名树应该插入的位置，将其插入7t=p-firstchild;a=CompareStr（t-data,s）;//比较域名与已经存在的兄弟节点if（a0）{CreateChild（p,webside）;//若域名比兄弟节点小，则前插p-firstchild-nextsibling=t;}//endifelse{while（t-nextsibling!=NULL&&（a=CompareStr（t-nextsibling-data,s））0）t=t-nextsibling;//若域名比兄弟节点大，则后插q=newTreeNode;Pop（webside,s）;CopyStr（q-data,s）;q-firstchild=NULL;q-IP[0]='\0';//给新开节点赋值q-nextsibling=t-nextsibling;//新开节点的兄弟指针指向插入处节//点的兄弟t-nextsibling=q;//插入处的节点的兄弟指针指向新开节点CreateChild（q,webside）;//把整个域名树链插入}//endelse}//endelse}//endelseDeleteStack（webside）;cout是否要继续输入新域名?（y/n）endl;ch=getchar（）;//获得用户输入的字符getchar（）;//此为用户输入的回车}while（ch=='y'）;}//InsertvoidInitialTree（Tree&T）{//第一次由用户输入网站域名和IP，建立节点有序的树T=newTreeNode;//新开一个树节点CopyChar（T-data,root）;//建立树的根节点T-firstchild=T-nextsibli