数据结构实验报告

2017-03-27

26342

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

数据结构课程实验报告

题目：姓名：

学院：班级：

学号：互联网域名查询信息科学与工程学院

实验三树和图应用类实验

一、问题定义及i 需求分析

1. 问题描述

互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn 、com 等，最底层（第四层）是叶子结点，如www 等。因此，域名搜索可以看成是树的遍历问题。

2. 实验要求

设计搜索互联网域名的程序。

（1）采用树的孩子兄弟链表等存储结构。

（2）创建树形结构。

（3）通过深度优先遍历搜索。

（4）通过层次优先遍历搜索。

3. 数据输入的形式

输入域名地址。如：www.sohu.com

4. 数据输出的形式

输出对应的ip 地址或者出错时输出“找不到服务器或发生DNS 错误”

二、概要设计

（1）为了实现上述程序的功能，应该以孩子兄弟链表存储树，所以需要树的抽象数据类型。

（2）存入磁盘文件时还需要另一种文件的抽象数据类型。

（3）所有的域名和IP 都是以串的形式存的，所以还需要串的抽象数据类型。

（4）当用户输入站点的域名时，需要将域名分段存储，在搜索时从最根部依次提出来与树的节点域比较，由于用户输入是从最小级到最根级，弹出时与输入顺序相反，比如输入“www.163.com ”，其中：www 是第三级，163是第二级，com 是第一级，所以再与树节点比较时，首先比较com ，然后比较163，最后才比较www 。根据这种“后进先出”的关系，需要栈作为辅助工具，所以需要栈的抽象数据类型。

具体内容：

1）树的抽象数据类型

ADT Tree {

数据对象D ：站点域名的集合。

数据关系R ：{H}

（1）D 中存在惟一称为根的数据元素root ，它在关系{H}下没有前

驱。

（2）D-{root}之后可划分为D 1, D 2, „, Dn （n >0）对任意的划分都两

两不相交。对任意的（i 1≤i ≤n ），惟一的存在数据元素Xi ∈Di ，

有〈root , Xi 〉∈H ；

（3）对应于D-{root}的划分，H-{〈root ，Xi 〉}（i=1,2,„, n ）有惟

一的一个划分H 1, H 2, „, Hn （n >0），对任意的j ≠k (i≤j , k ≤n )

有H j H k =Φ，并且对任意的i （1≤i ≤n ）, H j 是Di 上的二元关系，（Di ，{Hi }）是一颗符合本定义的树，成为根root 的子树。

基本操作P ：

CreateChild （&T）

初始条件：树根T 已经存在。

操作结果：根据用户输入的域名建立此域名的树链，并以T 为

树根如用户输入www.cau.edu.cn ，则在建立起以T 为

根，cn 为T 的第一个孩子，www 为叶子的树链，所

有的节点都链在孩子域。

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

DeleteString （&s）

初始条件：串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 ｝约定a 1为栈底，a n 为

栈顶

基本操作：

InitialStack （&s）

操作结果：构造一个空栈。

GetTop （s ，&e）

初始条件：栈s 已经存在且非空。

操作结果：用e 返回栈s 的栈顶元素。

Push （&s, e）

初始条件：栈s 已经存在且非空。

操作结果：插入元素e 为新的栈顶元素。

Pop （&s, &e）

初始条件：栈s 已经存在且非空。

操作结果：删除栈s 的栈顶元素，并用e 返回其值。

DeleteStack （&s）

初始条件：s 已经存在。

操作结果：销毁栈，释放空间。

} ADT Stack

5）本程序5个模块

本程序有5个模块：主程序模块，树模块（实现树抽象数据类型），文件模块（实现文件抽象数据类型），串模块（实现串抽象数据类型），栈模块（实现栈抽象数据类型）

三、详细设计

typedef unsigned char String[30]; // 存放域名和IP 的串结构

typedef struct TreeNode { // 树的节点

ElemType data,IP; // 数据域（用来放域名）和IP 域（用来放IP ）

struct TreeNode *firstchild,*nextsibling; // 指向孩子和兄弟的指针

// 兄弟表示同一层，孩子表示下一层

}TreeNode,*Tree;

typedef struct FileNode { // 存入文件的节点

ElemType data,IP; // 数据域（用来放域名）和IP 域（用来放IP ）

int ltag,rtag; // 左右标志域：0表示无孩子，1表示有孩子

}FileNode;

typedef struct SNode {

SElemType data;

分开的一部分

struct SNode *next;

}SNode,*Stack;

（1）基本操作

Stack CreateWeb（）{

// 用户输入域名时按 '.' 将域名分开分别放入链式栈中

// 最后将 "root" 入栈，为查找做准备，返回栈顶指针

CopyChar （root,"root" ）; // 把 "root" 的值赋给串root InitialStack （webside ）; // 初始化链式栈

do{

a =getchar（）; // 输入域名

// 用户输入的域名存在栈节点 // 数据域（用来存放域名被 '.' // 指针域，指向域名下一部分

for （int i=0;a!='.'&&a!='n';i ）{

s[i]=a; a=getchar（）; // 得到两个 '.' 间的域名，将其值放

入一个串中

}

s[i]='0';

Push （webside,s ）; // 将串的值入栈

}while（a!='n'）;

Push （webside,root ）; // 将root 入栈

return webside; // 返回栈顶的指针

} // CreateWeb

void Search（Tree T,Stack &webside,Tree &p）{

// 用递归算法通过域名查找相应的IP ，返回相同层的指针

// 若存在则输出IP ，若不存在则输出相应的出错信息

if （T&&webside->next!=NULL）{

GetTop （webside,s ）; // 取得域名栈顶元素

int t=CompareStr（s,T->data）; // 比较域名和树的数据域

if （t>0） 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->IP[0]='0'; // 把树节点的IP 域置0

T->firstchild=t; // 让根节点的孩子域指向新建的树节点

CreateChild （t,webside ）; // 再以此树节点为根建立

新的树节点，

// 直到把域名全部赋值到树节点中

去

if （t->firstchild==NULL）{

cout<<"请输入域名IP"<

户输入IP

cin>>t->IP;

} // end if

} // CreateChild

void Insert（Tree &T）{

// 将域名树链插入到树T 中

do{

cout<<"请输入站点域名:"<

webside=CreateWeb（）; // 为用户输入的域名建立链表栈

Search （T,webside,p ）; // 在树中查找与域名节点相同的节点，

// 每一部分查找相匹配的树节点，返回

指向

// 最后一个与域名节点相同的树节点的

指针

if （p->firstchild==NULL）{

if （p->IP[0]!='0'） // 若发现输入了重复的域名则给出提示

cout<<"你输入了重复的域名"<

else CreateChild（p,webside ）; // 若这个树节点没有孩子，则直接把新的

// 域名建立成新的树，并让这个树节点孩

// 子域指向次新开的域名树。

// 即将域名节点作为此树节点的第一个孩

子

} // end if

else {

if （webside->next==NULL） // 若发现输入了错误的域名，则给出相应

// 的提示

cout<<"你输入了错误的域名!"<

else{

GetTop （webside,s ）; // 若这个树节点有孩子，则在他的孩子的

// 兄弟中找到新开域名树应该插入的位置，

将其插入

// 若是叶子节点则要求用

t=p->firstchild;

a=CompareStr（t->data,s）; // 比较域名与已经存在的

兄弟节点

if （a>0）{

CreateChild （p,webside ）; // 若域名比兄弟节点小，则

前插

p->firstchild->nextsibling=t;

} // end if

else{

while （t->nextsibling!=NULL&&（a=CompareStr

（t->nextsibling->data,s））<0）

t=t->nextsibling; // 若域名比兄弟节点大，则后插

q=new TreeNode;

Pop （webside,s ）;

CopyStr （q->data,s）;

q->firstchild=NULL;

q->IP[0]='0'; // 给新开节点赋值

q->nextsibling=t->nextsibling;

// 新开节点的兄弟指针指向插入处节//

点的兄弟

t->nextsibling=q; // 插入处的节点的兄弟指针指

向新开节点

CreateChild （q,webside ）; // 把整个域名树链插入

} // end else

DeleteStack （webside ）;

cout<<"是否要继续输入新域名? （y/n）"<

ch=getchar（）; // 获得用户输入的字符

getchar （）; // 此为用户输入的回车

}while（ch=='y'）;

} // Insert

void InitialTree（Tree &T）{

// 第一次由用户输入网站域名和IP ，建立节点有序的树

T=new TreeNode; // 新开一个树节点

CopyChar （T->data,"root"）; // 建立树的根节点

T->firstchild=T->nextsibling=NULL;

T->IP[0]='0';

Insert （T ）; // 把新的域名树链插入树中

} // InitialTree

void CreateTree（Tree &T,FILE *fp）{

// 文件已经存在，从文件中读出数据，用递归算法先序遍历构建树的孩子，兄弟二叉链表结构

if （!feof （fp ））{

T=new TreeNode; // 新建树节点

f=new FileNode; // 新建文件节点用于读取磁盘文件中的数据

if （（fread （f,sizeof （struct FileNode）,1,fp ））!=1）

cout<<"无法打开文件!"<

CopyStr （T->data,f->data）;

CopyStr （T->IP,f->IP）; // 将文件节点的IP 的值赋给树节点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;

} // end if

} // CreateTree

void DeleteTree（Tree &T）{

// 用递归算法销毁树，释放空间

if （T ） {

DeleteTree （T->firstchild）;

DeleteTree （T->nextsibling）;

delete T;

} // end if

} // DeleteTree

// 销毁树的左子树 // 销毁树的右子树 // 销毁树的根节点

（3）串的操作

voidCopyStr （String &a,String b）{

// 将串b 的值赋给串a

for （int i=0;b[i]!='0';i ）a[i]=b[i];

赋给a

a[i]='0';

} // CopyStr

voidCopyChar （String &a,char* b）{

// 将字符串b 的值赋给串a

for （int i=0;*b!='0';b ,i ）a[i]=*b;

a[i]='0';

} // CopyStr

// 将b 数组中的值一个一个

int CompareStr（String a,String b）{

// 串a 和b 从第一个字符开始比较，直到出现第一个不相同的字符为止

for （int i=0;a[i]!='0'&&b[i]!='0';i ） // 如果a>b,return >0;

if （a[i]!=b[i]） return a[i]-b[i]; // 如果a

if （a[i]!='0'） return 1; // 如果a=b,return =0;

else if（b[i]!='0'）return -1;

else return 0;

} // CompareStr

（4）栈的基本操作

void InitialStack（Stack &s）{

// 初始化空栈

s=new SNode;

s->next=NULL;

} // InitialStack

voidPush （Stack &s,SElemType e）{

// 将元素e 插入链式栈中，成为新的栈顶元素

p=new SNode; // 为新的栈顶元素分配空间 CopyStr （p->data,e）; // 将e 的值赋给新节点数据域 p->next=s->next; // 插入新的栈顶元素

s->next=p; // 修改栈顶指针

} // Push

voidPop （Stack &s,SElemType &e）{

// 若栈为空则给出相应的信息，若不空则删除栈顶元素并将其值赋给e

if （!s->next） cout<<"空栈!"<

CopyStr （e,s->next->data）; // 取出栈顶元素的值赋给e p=s->next; // 删除栈顶元素

s->next=p->next;

// 新建一个栈头节点 // 头节点指向空

相关推荐