数据结构实验报告.docx

数据结构课程实验报告题目: 互联网域名查询姓名: 学院: 信息科学与工程学院班级: 学号: 1 实验三树和图应用类实验一、问题定义及 i 需求分析 。从根节点往下的第一层是顶层域, 等,最底层(第四层)是叶子结点,如,域名搜索可以看成是树的遍历问题。 。(1)采用树的孩子兄弟链表等存储结构。(2)创建树形结构。(3)通过深度优先遍历搜索。(4)通过层次优先遍历搜索。 。如: .数据输出的形式输出对应的 ip地址或者出错时输出“找不到服务器或发生 DNS 错误”二、概要设计(1)为了实现上述程序的功能,应该以孩子兄弟链表存储树,所以需要树的抽象数据类型。(2)存入磁盘文件时还需要另一种文件的抽象数据类型。(3)所有的域名和 IP都是以串的形式存的,所以还需要串的抽象数据类型。(4)当用户输入站点的域名时,需要将域名分段存储,在搜索时从最根部依次提出来与树的节点域比较,由于用户输入是从最小级到最根级,弹出时与输入顺序相反,比如输入“ ”,其中: , 163 是第二级, com 是第一级, 所以再与树节点比较时, ,然后比较 163 ,最后才比较 www 。根据这种“后进先出”的关系,需要栈作为辅助工具,所以需要栈的抽象数据类型。具体内容: 1)树的抽象数据类型 ADT Tree {数据对象 D:站点域名的集合。数据关系 R: {H} (1)D中存在惟一称为根的数据元素 root ,它在关系{H} 下没有前驱。(2) D-{root} 之后可划分为 D1,D2,…, Dn (n >0 )对任意的划分都两两不相交。对任意的 i(1≤i≤n),惟一的存在数据元素,有; (3)对应于 D-{root} 的划分, H-{ 〈 root , Xi〉}( i=1,2, …,n)有惟一的一个划分 H1,H2,…, Hn (n >0 ),对任意的(i≤j,k≤n)有, 并且对任意的 i(1≤i≤n),是 Di上的二元关系,( Di,{ Hi}) 是一颗符合本定义的树,成为根 root 的子树。基本操作 P: CreateChild ( &T ) 2 初始条件:树根 T已经存在。操作结果:根据用户输入的域名建立此域名的树链,并以 T为树根如用户输入 ,则在建立起以 T为根, cn为 T的第一个孩子, ,所有的节点都链在孩子域。 InitialTree ( &T ) 操作结果:通过用户输入的数据,构造域名树。其实是将建好的域名树链有序地插到树中相应的位置。 Insert ( &T ) 初始条件:树 T已经存在。操作结果:插入新的域名及 IP。 CreateTree ( &T, *fp ) 初始条件:包含树的信息文件已经存在, fp为指向文件的指针。操作结果:通过从文件中读取数据,构造域名树。 DeleteTree ( &T ) 初始条件: T已经存在。操作结果:销毁树,释放空间。} ADT Tree 2)文件的抽象数据类型 ADT File {数据对象: D={ a i│ a i∈ ElemSet, i= 1,2, …,n,n≥ 0} 数据关系: R={〈 a i -1,a i〉│ a i -1,a i∈ D,i= 1,2, …,n} 基本操作: │ Save ( &T ) 初始条件:树 T存在。操作结果:先序遍历树,给叶子节点数据域赋 IP值,同时把相关信息存入文件。} ADT File 3)串的抽象数据类型 ADT String {数据对象: D={ a i│ a i∈ ElemSet, i= 1,2, …,n,n≥ 0} 数据关系: R={〈 a i -1,a i〉│ a i -1,a i∈ D,i= 1,2, …,n} 基本操作: CopyChar ( &s, *a) 初始条件: a是字符串常量。操作结果:生成一个其值等于 a的串 s。 CopyStr ( &s, a) 初始条件: a是一个串。操作结果:生成一个值等于 a的串 s。 CompareStr ( a,b) 初始条件: a和 b是两个串。操作结果:若 a>b 返回值>0; 若 a=b, 返回值=0; 若 a<b ,返回值<0 。 DeleteString ( &s ) 3 初始条件:串 s存在。操作结果:销毁串。} ADT String 4)栈的抽象数据类型 ADT Stack {数据对象: D={ a i│ a i∈ ElemSet, i= 1,2, …,n,n≥ 0} 数据关系: R={〈 a i -1,a i〉│ a i -1,a i∈ D,i= 1,2, …,n}约定为栈底,为栈顶基本操作: InitialStack ( &s ) 操作结果:构造一个空栈。