數(shù)據(jù)結(jié)構(gòu)課程實驗報告題 目：姓 名：學 院：班 級：學 號： 互聯(lián)網(wǎng)域名查詢 信息科學與工程學院 ,實驗三樹和圖應用類實驗一、 問題定義及i 需求分析1. 問題描述互

數(shù)據(jù)結(jié)構(gòu)課程實驗報告

題 目：姓 名：

學 院：班 級：

學 號： 互聯(lián)網(wǎng)域名查詢 信息科學與工程學院

實驗三樹和圖應用類實驗

一、 問題定義及i 需求分析

1. 問題描述

互聯(lián)網(wǎng)域名系統(tǒng)是一個典型的樹形層次結(jié)構(gòu)。從根節(jié)點往下的第一層是頂層域，如cn 、com 等，最底層（第四層）是葉子結(jié)點，如www 等。因此，域名搜索可以看成是樹的遍歷問題。

2. 實驗要求

設計搜索互聯(lián)網(wǎng)域名的程序。

（1）采用樹的孩子兄弟鏈表等存儲結(jié)構(gòu)。

（2）創(chuàng)建樹形結(jié)構(gòu)。

（3）通過深度優(yōu)先遍歷搜索。

（4）通過層次優(yōu)先遍歷搜索。

3. 數(shù)據(jù)輸入的形式

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

4. 數(shù)據(jù)輸出的形式

輸出對應的ip 地址或者出錯時輸出“找不到服務器或發(fā)生DNS 錯誤”

二、概要設計

（1）為了實現(xiàn)上述程序的功能，應該以孩子兄弟鏈表存儲樹，所以需要樹的抽象數(shù)據(jù)類型。

（2）存入磁盤文件時還需要另一種文件的抽象數(shù)據(jù)類型。

（3）所有的域名和IP 都是以串的形式存的，所以還需要串的抽象數(shù)據(jù)類型。

（4）當用戶輸入站點的域名時，需要將域名分段存儲，在搜索時從最根部依次提出來與樹的節(jié)點域比較，由于用戶輸入是從最小級到最根級，彈出時與輸入順序相反，比如輸入“www.163.com ”，其中：www 是第三級，163是第二級，com 是第一級，所以再與樹節(jié)點比較時，首先比較com ，然后比較163，最后才比較www 。根據(jù)這種“后進先出”的關系，需要棧作為輔助工具，所以需要棧的抽象數(shù)據(jù)類型。

具體內(nèi)容：

1）樹的抽象數(shù)據(jù)類型

ADT Tree {

數(shù)據(jù)對象D ：站點域名的集合。

數(shù)據(jù)關系R ：{H}

（1）D 中存在惟一稱為根的數(shù)據(jù)元素root ，它在關系{H}下沒有前

驅(qū)。

（2）D-{root}之后可劃分為D 1, D 2, ?, Dn （n >0）對任意的劃分都兩

兩不相交。對任意的（i 1≤i ≤n ），惟一的存在數(shù)據(jù)元素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 )

1

有H j H k =Φ，并且對任意的i （1≤i ≤n ）, H j 是Di 上的二元關系，（Di ，{Hi }）是一顆符合本定義的樹，成為根root 的子樹。

基本操作P ：

CreateChild （&T）

初始條件：樹根T 已經(jīng)存在。

操作結(jié)果：根據(jù)用戶輸入的域名建立此域名的樹鏈，并以T 為

樹根如用戶輸入www.cau.edu.cn ，則在建立起以T 為

根，cn 為T 的第一個孩子，www 為葉子的樹鏈，所

有的節(jié)點都鏈在孩子域。

InitialTree （&T）

操作結(jié)果：通過用戶輸入的數(shù)據(jù)，構(gòu)造域名樹。其實是將建好的

域名樹鏈有序地插到樹中相應的位置。

Insert （&T）

初始條件：樹T 已經(jīng)存在。

操作結(jié)果：插入新的域名及IP 。

CreateTree （&T, *fp）

初始條件：包含樹的信息文件已經(jīng)存在，fp 為指向文件的指

針。

操作結(jié)果：通過從文件中讀取數(shù)據(jù)，構(gòu)造域名樹。

DeleteTree （&T）

初始條件：T 已經(jīng)存在。

操作結(jié)果：銷毀樹，釋放空間。

} ADT Tree

2）文件的抽象數(shù)據(jù)類型

ADT File {

數(shù)據(jù)對象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝

數(shù)據(jù)關系：R =｛〈a i -1, a i 〉│a i -1, a i ∈D , i ＝1,2, ?, n ｝

基本操作：│

Save （&T）

初始條件：樹T 存在。

操作結(jié)果：先序遍歷樹，給葉子節(jié)點數(shù)據(jù)域賦IP 值，同時把相

關信息存入文件。

} ADT File

3）串的抽象數(shù)據(jù)類型

ADT String {

數(shù)據(jù)對象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝

數(shù)據(jù)關系：R =｛〈a i -1, a i 〉│a i -1, a i ∈D , i ＝1,2, ?, n ｝

基本操作：

CopyChar （&s, *a）

初始條件：a 是字符串常量。

操作結(jié)果：生成一個其值等于a 的串s 。

CopyStr （&s, a）

2

初始條件：a 是一個串。

操作結(jié)果：生成一個值等于a 的串s 。

CompareStr （a, b）

初始條件：a 和b 是兩個串。

操作結(jié)果：若a>b返回值>0;若a=b,返回值=0;若a

DeleteString （&s）

初始條件：串s 存在。

操作結(jié)果：銷毀串。

} ADT String

4）棧的抽象數(shù)據(jù)類型

ADT Stack {

數(shù)據(jù)對象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝

數(shù)據(jù)關系：R =｛〈a i -1, a i 〉│a i -1, a i ∈D , i ＝1,2, ?, n ｝約定a 1為棧底，a n 為

棧頂

基本操作：

InitialStack （&s）

操作結(jié)果：構(gòu)造一個空棧。

GetTop （s ，&e）

初始條件：棧s 已經(jīng)存在且非空。

操作結(jié)果：用e 返回棧s 的棧頂元素。

Push （&s, e）

初始條件：棧s 已經(jīng)存在且非空。

操作結(jié)果：插入元素e 為新的棧頂元素。

Pop （&s, &e）

初始條件：棧s 已經(jīng)存在且非空。

操作結(jié)果：刪除棧s 的棧頂元素，并用e 返回其值。

DeleteStack （&s）

初始條件：s 已經(jīng)存在。

操作結(jié)果：銷毀棧，釋放空間。

} ADT Stack

5）本程序5個模塊

本程序有5個模塊：主程序模塊，樹模塊（實現(xiàn)樹抽象數(shù)據(jù)類型），文件模塊（實現(xiàn)文件抽象數(shù)據(jù)類型），串模塊（實現(xiàn)串抽象數(shù)據(jù)類型），棧模塊（實現(xiàn)棧抽象數(shù)據(jù)類型）

3

三、詳細設計

typedef unsigned char String[30]; // 存放域名和IP 的串結(jié)構(gòu)

typedef struct TreeNode { // 樹的節(jié)點

ElemType data,IP; // 數(shù)據(jù)域（用來放域名）和IP 域（用來放IP ）

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

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

}TreeNode,*Tree;

typedef struct FileNode { // 存入文件的節(jié)點

ElemType data,IP; // 數(shù)據(jù)域（用來放域名）和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（）; // 輸入域名

4

// 用戶輸入的域名存在棧節(jié)點 // 數(shù)據(jù)域（用來存放域名被 '.' // 指針域，指向域名下一部分

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; // 返回棧頂?shù)闹羔?/p>

} // 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）; // 比較域名和樹的數(shù)據(jù)域

if （t>0） Search （T->nextsibling,webside,p）;

// 若域名比樹節(jié)點值大則遞歸搜索

樹節(jié)點兄弟

else if（t==0）{

Pop （webside,s ）; p=T; // 若域名和樹節(jié)點相同則

域名鏈式棧節(jié)點出棧

Search （T->firstchild,webside,p）; // 繼續(xù)搜索樹節(jié)點的孩子，

即下一層

} // end else

} // end if

} // Search

（2）關于樹的操作

void CreateChild（Tree &T,Stack &webside）{

// 用戶輸入一個網(wǎng)址域名，域名已經(jīng)被輸入到棧中，為域名建立相應的域名樹鏈

if （webside->next!=NULL）{

t=new TreeNode; // 新開一個節(jié)點

Pop （webside,s ）; // 從棧中取出域名第一部分

CopyStr （t->data,s）; // 把第一部分賦值給樹節(jié)點的數(shù)據(jù)域

t->firstchild=t->nextsibling=NULL; // 把樹節(jié)點的孩子和兄弟鏈域暫置空

t->IP[0]='0'; // 把樹節(jié)點的IP 域置0

T->firstchild=t; // 讓根節(jié)點的孩子域指向新建的樹節(jié)點

CreateChild （t,webside ）; // 再以此樹節(jié)點為根建立

5

新的樹節(jié)點，

// 直到把域名全部賦值到樹節(jié)點中

去

if （t->firstchild==NULL）{

cout<<"請輸入域名IP"<

戶輸入IP

cin>>t->IP;

} // end if

} // end if

} // CreateChild

void Insert（Tree &T）{

// 將域名樹鏈插入到樹T 中

do{

cout<<"請輸入站點域名:"<

webside=CreateWeb（）; // 為用戶輸入的域名建立鏈表棧

Search （T,webside,p ）; // 在樹中查找與域名節(jié)點相同的節(jié)點，

// 每一部分查找相匹配的樹節(jié)點，返回

指向

// 最后一個與域名節(jié)點相同的樹節(jié)點的

指針

if （p->firstchild==NULL）{

if （p->IP[0]!='0'） // 若發(fā)現(xiàn)輸入了重復的域名則給出提示

cout<<"你輸入了重復的域名"<

else CreateChild（p,webside ）; // 若這個樹節(jié)點沒有孩子，則直接把新的

// 域名建立成新的樹，并讓這個樹節(jié)點孩

// 子域指向次新開的域名樹。

// 即將域名節(jié)點作為此樹節(jié)點的第一個孩

子

} // end if

else {

if （webside->next==NULL） // 若發(fā)現(xiàn)輸入了錯誤的域名，則給出相應

// 的提示

cout<<"你輸入了錯誤的域名!"<

else{

GetTop （webside,s ）; // 若這個樹節(jié)點有孩子，則在他的孩子的

// 兄弟中找到新開域名樹應該插入的位置，

將其插入

6

// 若是葉子節(jié)點則要求用

t=p->firstchild;

a=CompareStr（t->data,s）; // 比較域名與已經(jīng)存在的

兄弟節(jié)點

if （a>0）{

CreateChild （p,webside ）; // 若域名比兄弟節(jié)點小，則

前插

p->firstchild->nextsibling=t;

} // end if

else{

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

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

t=t->nextsibling; // 若域名比兄弟節(jié)點大，則后插

q=new TreeNode;

Pop （webside,s ）;

CopyStr （q->data,s）;

q->firstchild=NULL;

q->IP[0]='0'; // 給新開節(jié)點賦值

q->nextsibling=t->nextsibling;

// 新開節(jié)點的兄弟指針指向插入處節(jié)//

點的兄弟

t->nextsibling=q; // 插入處的節(jié)點的兄弟指針指

向新開節(jié)點

CreateChild （q,webside ）; // 把整個域名樹鏈插入

} // end else

} // end else

} // end else

DeleteStack （webside ）;

cout<<"是否要繼續(xù)輸入新域名? （y/n）"<

ch=getchar（）; // 獲得用戶輸入的字符

getchar （）; // 此為用戶輸入的回車

}while（ch=='y'）;

} // Insert

void InitialTree（Tree &T）{

// 第一次由用戶輸入網(wǎng)站域名和IP ，建立節(jié)點有序的樹

T=new TreeNode; // 新開一個樹節(jié)點

CopyChar （T->data,"root"）; // 建立樹的根節(jié)點

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

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

Insert （T ）; // 把新的域名樹鏈插入樹中

} // InitialTree

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

// 文件已經(jīng)存在，從文件中讀出數(shù)據(jù)，用遞歸算法先序遍歷構(gòu)建樹的孩子，兄弟二叉鏈表結(jié)構(gòu)

7

if （!feof （fp ））{

T=new TreeNode; // 新建樹節(jié)點

f=new FileNode; // 新建文件節(jié)點用于讀取磁盤文件中的數(shù)據(jù)

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

cout<<"無法打開文件!"<

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

CopyStr （T->IP,f->IP）; // 將文件節(jié)點的IP 的值賦給樹節(jié)點IP

if （f->ltag）

CreateTree （T->firstchild,fp）; // 若樹節(jié)點有孩子則遞歸建立其孩子

else T->firstchild=NULL; // 若無孩子則孩子鏈域置為空

if （f->rtag）

CreateTree （T->nextsibling,fp）; // 若樹節(jié)點有兄弟則遞歸建立其兄弟

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

// 銷毀樹的左子樹 // 銷毀樹的右子樹 // 銷毀樹的根節(jié)點

8

（3）串的操作

voidCopyStr （String &a,String b）{

// 將串b 的值賦給串a(chǎn)

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

賦給a

a[i]='0';

} // CopyStr

voidCopyChar （String &a,char* b）{

// 將字符串b 的值賦給串a(chǎn)

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

a[i]='0';

} // CopyStr

// 將b 數(shù)組中的值一個一個

int CompareStr（String a,String b）{

// 串a(chǎn) 和b 從第一個字符開始比較，直到出現(xiàn)第一個不相同的字符為止

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 的值賦給新節(jié)點數(shù)據(jù)域 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;

9

// 新建一個棧頭節(jié)點 // 頭節(jié)點指向空