數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告題 目：姓 名：學(xué) 院：班 級(jí)：學(xué) 號(hào)： 互聯(lián)網(wǎng)域名查詢 信息科學(xué)與工程學(xué)院 ,實(shí)驗(yàn)三樹和圖應(yīng)用類實(shí)驗(yàn)一、 問(wèn)題定義及i 需求分析1. 問(wèn)題描述互
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告
題 目：姓 名：
學(xué) 院：班 級(jí)：
學(xué) 號(hào)： 互聯(lián)網(wǎng)域名查詢 信息科學(xué)與工程學(xué)院
,實(shí)驗(yàn)三樹和圖應(yīng)用類實(shí)驗(yàn)
一、 問(wèn)題定義及i 需求分析
1. 問(wèn)題描述
互聯(lián)網(wǎng)域名系統(tǒng)是一個(gè)典型的樹形層次結(jié)構(gòu)。從根節(jié)點(diǎn)往下的第一層是頂層域，如cn 、com 等，最底層（第四層）是葉子結(jié)點(diǎn)，如www 等。因此，域名搜索可以看成是樹的遍歷問(wèn)題。
2. 實(shí)驗(yàn)要求
設(shè)計(jì)搜索互聯(lián)網(wǎng)域名的程序。
（1）采用樹的孩子兄弟鏈表等存儲(chǔ)結(jié)構(gòu)。
（2）創(chuàng)建樹形結(jié)構(gòu)。
（3）通過(guò)深度優(yōu)先遍歷搜索。
（4）通過(guò)層次優(yōu)先遍歷搜索。
3. 數(shù)據(jù)輸入的形式
輸入域名地址。如：www.sohu.com
4. 數(shù)據(jù)輸出的形式
輸出對(duì)應(yīng)的ip 地址或者出錯(cuò)時(shí)輸出“找不到服務(wù)器或發(fā)生DNS 錯(cuò)誤”
二、概要設(shè)計(jì)
（1）為了實(shí)現(xiàn)上述程序的功能，應(yīng)該以孩子兄弟鏈表存儲(chǔ)樹，所以需要樹的抽象數(shù)據(jù)類型。
（2）存入磁盤文件時(shí)還需要另一種文件的抽象數(shù)據(jù)類型。
（3）所有的域名和IP 都是以串的形式存的，所以還需要串的抽象數(shù)據(jù)類型。
（4）當(dāng)用戶輸入站點(diǎn)的域名時(shí)，需要將域名分段存儲(chǔ)，在搜索時(shí)從最根部依次提出來(lái)與樹的節(jié)點(diǎn)域比較，由于用戶輸入是從最小級(jí)到最根級(jí)，彈出時(shí)與輸入順序相反，比如輸入“www.163.com ”，其中：www 是第三級(jí)，163是第二級(jí)，com 是第一級(jí)，所以再與樹節(jié)點(diǎn)比較時(shí)，首先比較com ，然后比較163，最后才比較www 。根據(jù)這種“后進(jìn)先出”的關(guān)系，需要棧作為輔助工具，所以需要棧的抽象數(shù)據(jù)類型。
具體內(nèi)容：
1）樹的抽象數(shù)據(jù)類型
ADT Tree {
數(shù)據(jù)對(duì)象D ：站點(diǎn)域名的集合。
數(shù)據(jù)關(guān)系R ：{H}
（1）D 中存在惟一稱為根的數(shù)據(jù)元素root ，它在關(guān)系{H}下沒(méi)有前
驅(qū)。
（2）D-{root}之后可劃分為D 1, D 2, ?, Dn （n >0）對(duì)任意的劃分都兩
兩不相交。對(duì)任意的（i 1≤i ≤n ），惟一的存在數(shù)據(jù)元素Xi ∈Di ，
有?root , Xi ?∈H ；
（3）對(duì)應(yīng)于D-{root}的劃分，H-{〈root ，Xi 〉}（i=1,2,?, n ）有惟
一的一個(gè)劃分H 1, H 2, ?, Hn （n >0），對(duì)任意的j ≠k (i≤j , k ≤n )
1
,有H j H k =Φ，并且對(duì)任意的i （1≤i ≤n ）, H j 是Di 上的二元關(guān)系，（Di ，{Hi }）是一顆符合本定義的樹，成為根root 的子樹。
基本操作P ：
CreateChild （&T）
初始條件：樹根T 已經(jīng)存在。
操作結(jié)果：根據(jù)用戶輸入的域名建立此域名的樹鏈，并以T 為
樹根如用戶輸入www.cau.edu.cn ，則在建立起以T 為
根，cn 為T 的第一個(gè)孩子，www 為葉子的樹鏈，所
有的節(jié)點(diǎn)都鏈在孩子域。
InitialTree （&T）
操作結(jié)果：通過(guò)用戶輸入的數(shù)據(jù)，構(gòu)造域名樹。其實(shí)是將建好的
域名樹鏈有序地插到樹中相應(yīng)的位置。
Insert （&T）
初始條件：樹T 已經(jīng)存在。
操作結(jié)果：插入新的域名及IP 。
CreateTree （&T, *fp）
初始條件：包含樹的信息文件已經(jīng)存在，fp 為指向文件的指
針。
操作結(jié)果：通過(guò)從文件中讀取數(shù)據(jù)，構(gòu)造域名樹。
DeleteTree （&T）
初始條件：T 已經(jīng)存在。
操作結(jié)果：銷毀樹，釋放空間。
} ADT Tree
2）文件的抽象數(shù)據(jù)類型
ADT File {
數(shù)據(jù)對(duì)象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝
數(shù)據(jù)關(guān)系：R =｛〈a i -1, a i 〉│a i -1, a i ∈D , i ＝1,2, ?, n ｝
基本操作：│
Save （&T）
初始條件：樹T 存在。
操作結(jié)果：先序遍歷樹，給葉子節(jié)點(diǎn)數(shù)據(jù)域賦IP 值，同時(shí)把相
關(guān)信息存入文件。
} ADT File
3）串的抽象數(shù)據(jù)類型
ADT String {
數(shù)據(jù)對(duì)象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝
數(shù)據(jù)關(guān)系：R =｛〈a i -1, a i 〉│a i -1, a i ∈D , i ＝1,2, ?, n ｝
基本操作：
CopyChar （&s, *a）
初始條件：a 是字符串常量。
操作結(jié)果：生成一個(gè)其值等于a 的串s 。
CopyStr （&s, a）
2
,初始條件：a 是一個(gè)串。
操作結(jié)果：生成一個(gè)值等于a 的串s 。
CompareStr （a, b）
初始條件：a 和b 是兩個(gè)串。
操作結(jié)果：若a>b返回值>0;若a=b,返回值=0;若a
DeleteString （&s）
初始條件：串s 存在。
操作結(jié)果：銷毀串。
} ADT String
4）棧的抽象數(shù)據(jù)類型
ADT Stack {
數(shù)據(jù)對(duì)象：D =｛a i │a i ∈ElemSet, i ＝1,2, ?, n , n ≥0｝
數(shù)據(jù)關(guān)系：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)造一個(gè)空棧。
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個(gè)模塊
本程序有5個(gè)模塊：主程序模塊，樹模塊（實(shí)現(xiàn)樹抽象數(shù)據(jù)類型），文件模塊（實(shí)現(xiàn)文件抽象數(shù)據(jù)類型），串模塊（實(shí)現(xiàn)串抽象數(shù)據(jù)類型），棧模塊（實(shí)現(xiàn)棧抽象數(shù)據(jù)類型）
3
,三、詳細(xì)設(shè)計(jì)
typedef unsigned char String[30]; // 存放域名和IP 的串結(jié)構(gòu)
typedef struct TreeNode { // 樹的節(jié)點(diǎn)
ElemType data,IP; // 數(shù)據(jù)域（用來(lái)放域名）和IP 域（用來(lái)放IP ）
struct TreeNode *firstchild,*nextsibling; // 指向孩子和兄弟的指針
// 兄弟表示同一層，孩子表示下一層
}TreeNode,*Tree;
typedef struct FileNode { // 存入文件的節(jié)點(diǎn)
ElemType data,IP; // 數(shù)據(jù)域（用來(lái)放域名）和IP 域（用來(lái)放IP ）
int ltag,rtag; // 左右標(biāo)志域：0表示無(wú)孩子，1表示有孩子
}FileNode;
typedef struct SNode {
SElemType data;
分開的一部分
struct SNode *next;
}SNode,*Stack;
（1）基本操作
Stack CreateWeb（）{
// 用戶輸入域名時(shí)按 '.' 將域名分開分別放入鏈?zhǔn)綏Ｖ?/p>
// 最后將 "root" 入棧，為查找做準(zhǔn)備，返回棧頂指針
CopyChar （root,"root" ）; // 把 "root" 的值賦給串root InitialStack （webside ）; // 初始化鏈?zhǔn)綏?/p>
do{
a =getchar（）; // 輸入域名
4
// 用戶輸入的域名存在棧節(jié)點(diǎn) // 數(shù)據(jù)域（用來(lái)存放域名被 '.' // 指針域，指向域名下一部分
,for （int i=0;a!='.'&&a!='n';i ）{
s[i]=a; a=getchar（）; // 得到兩個(gè) '.' 間的域名，將其值放
入一個(gè)串中
}
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）{
// 用遞歸算法通過(guò)域名查找相應(yīng)的IP ，返回相同層的指針
// 若存在則輸出IP ，若不存在則輸出相應(yīng)的出錯(cuò)信息
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é)點(diǎn)值大則遞歸搜索
樹節(jié)點(diǎn)兄弟
else if（t==0）{
Pop （webside,s ）; p=T; // 若域名和樹節(jié)點(diǎn)相同則
域名鏈?zhǔn)綏９?jié)點(diǎn)出棧
Search （T->firstchild,webside,p）; // 繼續(xù)搜索樹節(jié)點(diǎn)的孩子，
即下一層
} // end else
} // end if
} // Search
（2）關(guān)于樹的操作
void CreateChild（Tree &T,Stack &webside）{
// 用戶輸入一個(gè)網(wǎng)址域名，域名已經(jīng)被輸入到棧中，為域名建立相應(yīng)的域名樹鏈
if （webside->next!=NULL）{
t=new TreeNode; // 新開一個(gè)節(jié)點(diǎn)
Pop （webside,s ）; // 從棧中取出域名第一部分
CopyStr （t->data,s）; // 把第一部分賦值給樹節(jié)點(diǎn)的數(shù)據(jù)域
t->firstchild=t->nextsibling=NULL; // 把樹節(jié)點(diǎn)的孩子和兄弟鏈域暫置空
t->IP[0]='0'; // 把樹節(jié)點(diǎn)的IP 域置0
T->firstchild=t; // 讓根節(jié)點(diǎn)的孩子域指向新建的樹節(jié)點(diǎn)
CreateChild （t,webside ）; // 再以此樹節(jié)點(diǎn)為根建立
5
,新的樹節(jié)點(diǎn)，
// 直到把域名全部賦值到樹節(jié)點(diǎn)中
去
if （t->firstchild==NULL）{
cout<<"請(qǐng)輸入域名IP"< 戶輸入IP cin>>t->IP; } // end if } // end if } // CreateChild void Insert（Tree &T）{ // 將域名樹鏈插入到樹T 中 do{ cout<<"請(qǐng)輸入站點(diǎn)域名:"< webside=CreateWeb（）; // 為用戶輸入的域名建立鏈表?xiàng)?/p> Search （T,webside,p ）; // 在樹中查找與域名節(jié)點(diǎn)相同的節(jié)點(diǎn)， // 每一部分查找相匹配的樹節(jié)點(diǎn)，返回 指向 // 最后一個(gè)與域名節(jié)點(diǎn)相同的樹節(jié)點(diǎn)的 指針 if （p->firstchild==NULL）{ if （p->IP[0]!='0'） // 若發(fā)現(xiàn)輸入了重復(fù)的域名則給出提示 cout<<"你輸入了重復(fù)的域名"< else CreateChild（p,webside ）; // 若這個(gè)樹節(jié)點(diǎn)沒(méi)有孩子，則直接把新的 // 域名建立成新的樹，并讓這個(gè)樹節(jié)點(diǎn)孩 // 子域指向次新開的域名樹。 // 即將域名節(jié)點(diǎn)作為此樹節(jié)點(diǎn)的第一個(gè)孩 子 } // end if else { if （webside->next==NULL） // 若發(fā)現(xiàn)輸入了錯(cuò)誤的域名，則給出相應(yīng) // 的提示 cout<<"你輸入了錯(cuò)誤的域名!"< else{ GetTop （webside,s ）; // 若這個(gè)樹節(jié)點(diǎn)有孩子，則在他的孩子的 // 兄弟中找到新開域名樹應(yīng)該插入的位置， 將其插入 6 // 若是葉子節(jié)點(diǎn)則要求用 t=p->firstchild; a=CompareStr（t->data,s）; // 比較域名與已經(jīng)存在的 兄弟節(jié)點(diǎn) if （a>0）{ CreateChild （p,webside ）; // 若域名比兄弟節(jié)點(diǎn)小，則 前插 p->firstchild->nextsibling=t; } // end if else{ while （t->nextsibling!=NULL&&（a=CompareStr （t->nextsibling->data,s））<0） t=t->nextsibling; // 若域名比兄弟節(jié)點(diǎn)大，則后插 q=new TreeNode; Pop （webside,s ）; CopyStr （q->data,s）; q->firstchild=NULL; q->IP[0]='0'; // 給新開節(jié)點(diǎn)賦值 q->nextsibling=t->nextsibling; // 新開節(jié)點(diǎn)的兄弟指針指向插入處節(jié)// 點(diǎn)的兄弟 t->nextsibling=q; // 插入處的節(jié)點(diǎn)的兄弟指針指 向新開節(jié)點(diǎn) CreateChild （q,webside ）; // 把整個(gè)域名樹鏈插入 } // 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é)點(diǎn)有序的樹 T=new TreeNode; // 新開一個(gè)樹節(jié)點(diǎn) CopyChar （T->data,"root"）; // 建立樹的根節(jié)點(diǎn) 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é)點(diǎn) f=new FileNode; // 新建文件節(jié)點(diǎn)用于讀取磁盤文件中的數(shù)據(jù) if （（fread （f,sizeof （struct FileNode）,1,fp ））!=1） cout<<"無(wú)法打開文件!"< CopyStr （T->data,f->data）; CopyStr （T->IP,f->IP）; // 將文件節(jié)點(diǎn)的IP 的值賦給樹節(jié)點(diǎn)IP if （f->ltag） CreateTree （T->firstchild,fp）; // 若樹節(jié)點(diǎn)有孩子則遞歸建立其孩子 else T->firstchild=NULL; // 若無(wú)孩子則孩子鏈域置為空 if （f->rtag） CreateTree （T->nextsibling,fp）; // 若樹節(jié)點(diǎn)有兄弟則遞歸建立其兄弟 else T->nextsibling=NULL; // 若無(wú)兄弟則兄弟鏈域置為空 delete f; } // end if } // CreateTree void DeleteTree（Tree &T）{ // 用遞歸算法銷毀樹，釋放空間 if （T ） { DeleteTree （T->firstchild）; DeleteTree （T->nextsibling）; delete T; } // end if } // DeleteTree // 銷毀樹的左子樹 // 銷毀樹的右子樹 // 銷毀樹的根節(jié)點(diǎn) 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ù)組中的值一個(gè)一個(gè) int CompareStr（String a,String b）{ // 串a(chǎn) 和b 從第一個(gè)字符開始比較，直到出現(xiàn)第一個(gè)不相同的字符為止 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 插入鏈?zhǔn)綏Ｖ?，成為新的棧頂元?/p> p=new SNode; // 為新的棧頂元素分配空間 CopyStr （p->data,e）; // 將e 的值賦給新節(jié)點(diǎn)數(shù)據(jù)域 p->next=s->next; // 插入新的棧頂元素 s->next=p; // 修改棧頂指針 } // Push voidPop （Stack &s,SElemType &e）{ // 若棧為空則給出相應(yīng)的信息，若不空則刪除棧頂元素并將其值賦給e if （!s->next） cout<<"空棧!"< CopyStr （e,s->next->data）; // 取出棧頂元素的值賦給e p=s->next; // 刪除棧頂元素 s->next=p->next; 9 // 新建一個(gè)棧頭節(jié)點(diǎn) // 頭節(jié)點(diǎn)指向空