實驗四 利用樹型結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢問題描述在第六章樹結(jié)構(gòu)中曾討論Internet 的域名系統(tǒng)，以樹型結(jié)構(gòu)實現(xiàn)域名的搜索。即輸入某站點的域名，在域名系統(tǒng)的樹型結(jié)構(gòu)中進(jìn)行搜索，直至域名全部

實驗四 利用樹型結(jié)構(gòu)的搜索算法模擬

因特網(wǎng)域名的查詢

問題描述

在第六章樹結(jié)構(gòu)中曾討論Internet 的域名系統(tǒng)，以樹型結(jié)構(gòu)實現(xiàn)域名的搜索。即輸入某站點的域名，在域名系統(tǒng)的樹型結(jié)構(gòu)中進(jìn)行搜索，直至域名全部匹配成功或匹配失敗；若成功則給出該站點的IP 地址，否則給出找不到該站點的信息。

基本要求

首先要實現(xiàn)一個反映域名結(jié)構(gòu)的樹，例如中國科學(xué)技術(shù)大學(xué)www.ustc.edu.cn 在該樹從根到葉子的各層結(jié)點就應(yīng)是root、cn、edu、ustc、www。葉子結(jié)點www 另有一個數(shù)據(jù)域，存放中國科學(xué)技術(shù)大學(xué)站點的IP 地址202.38.64.2。

測試數(shù)據(jù)

可以取常用到的著名站點的域名和IP 地址為例構(gòu)建域名結(jié)構(gòu)的樹，一般應(yīng)有20個左右的站點域名。下面提供了一組測試數(shù)據(jù)，當(dāng)輸入“www.ustc.edu.cn ”輸出為“202.38.64.2”；而輸入www.ustcustc.edu.cn 時，輸出應(yīng)為“找不到服務(wù)器或發(fā)生DNS 錯誤”。 www.baidu.com 220.181.27.5

www.google.com 66.249.89.104

www.microsoft.com 207.46.20.60

1

www.whitehouse.gov 64.215.166.127

www.nasa.gov 210.254.57.56

www.lenovo.com.cn 219.239.195.11

www.sina.com.cn 218.30.13.51

www.ustc.edu.cn 202.38.64.2

bbs.ustc.edu.cn 202.38.64.3

www.pku.edu.cn 162.105.129.12

bbs.pku.edu.cn 162.105.204.150

www.tsinghua.edu.cn 166.111.4.100

ftp.tsinghua.edu.cn 166.111.8.229

www.beijing.gov.cn 210.73.64.10

www.shanghai.gov.cn 61.129.65.58

實現(xiàn)提示

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

二叉鏈表的樹結(jié)構(gòu)是一種動態(tài)結(jié)構(gòu)，除第一次生成的過程需要人工輸入數(shù)據(jù)外，以后每次進(jìn)行搜索查詢時，應(yīng)首先從文件中保存的數(shù)據(jù)自動生成樹的結(jié)構(gòu)。為解決二叉鏈表與文件之間的轉(zhuǎn)換，可以通過先序遍歷的辦法保存和恢復(fù)二叉鏈表。例如一個二叉鏈表的文件保存形式如下：

2

數(shù)據(jù)

A

B

D

F

G

C

E H 左標(biāo)記 1 0 1 0 0 1 0 0 右標(biāo)記 RG 1 1 1 0 0 0 1 0

DATA LG

二叉樹 文件保存形式

問題討論

實際的使用中，樹結(jié)構(gòu)的使用機(jī)會筆二叉樹還要多，一般情況下都采用孩子－兄弟鏈表做樹的存儲結(jié)構(gòu)，此時也可將樹視作二叉樹，并將對樹的操作轉(zhuǎn)換成對二叉樹的相應(yīng)操作。

3