数据结构实验报告.docx

数据结构课程实验报告
题目: 互联网域名查询
姓名:
学院:信息科学与工程学院
班级:
学号:
实验三树和图应用类实验
问题定义及i需求分析

互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域,等,最底层(第四层)是叶子结点,如www等。因此,域名搜索可以看成是树的遍历问题。
2. 实验要求
设计搜索互联网域名的程序。
(1)采用树的孩子兄弟链表等存储结构。
(2)创建树形结构。
(3)通过深度优先遍历搜索。
(4)通过层次优先遍历搜索。

输入域名地址。如:

输出对应的ip地址或者出错时输出“找不到服务器或发生DNS错误”
二、概要设计
(1)为了实现上述程序的功能,应该以孩子兄弟链表存储树,所以需要树的抽象数据类型。
(2)存入磁盘文件时还需要另一种文件的抽象数据类型。
(3)所有的域名和IP都是以串的形式存的,所以还需要串的抽象数据类型。
(4)当用户输入站点的域名时,需要将域名分段存储,在搜索时从最根部依次提出来与树的节点域比较,由于用户输入是从最小级到最根级,弹出时与输入顺序相反,比如输入“”,其中:,com是第一级,所以再与树节点比较时,,然后比较163,最后才比较出”的关系,需要栈作为辅助工具,所以需要栈的抽象数据类型。
具体内容:
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)
初始条件:树根T已经存在。
操作结果:根据用户输入的域名建立此域名的树链,并以T为树根如用户输入,为T的第一个孩子,在孩子域。
InitialTree(&T)
操作结果:通过用户输入的数据,构造域名树。其实是将建好的域名树链有序地插到树中相应的位置。
Insert(&T)
初始条件:树T已经存在。
操作结果:插入新的域名及IP。
CreateTree(&T, *fp)
初始条件:包含树的信息文件已经存在,fp 为指向文件的指针。
操作结果:通过从文件中读取数据,构造域名树。
DeleteTree(&T)
初始条件:T已经存在。
操作结果:销毁树,释放空间。
} ADT Tree
2)文件的抽象数据类型
ADT File {
数据对象: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值,同时把相关信息存入文件。
} ADT File
3)串的抽象数据类型
ADT String {
数据对象: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)
初始条件:a是一个串。
操作结果:生成一个值等于a的串s。
CompareStr(a, b)
初始条件:a和b是两个串。
操作结果:若a>b返回值>0;若a=b,返回值=0;若a<b,返回值<0。
DeleteString(&s)
初始条件:串s存在。
操作结果:销毁串。
} ADT String
4)栈的抽象数据类型
ADT Stack {
数据对象:D ={ai│ai∈ElemSet, i=1,2,…,n, n≥0}
数据关系:R ={〈ai-1,ai〉│ai-1,ai∈D, i=1,2,…,n}约定为栈底,为栈顶
基本操作:
InitialStack(&s)
操作结果:构造一个空栈。
GetTop(s,&e)
初始条件:栈s已经存在且非空。
操作结果:用e返回栈s的栈顶元素。
Push(&s, e)
初始条件:栈s已经存在且非空。