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

實驗四 利用樹型結構的搜索算法模擬

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

問題描述

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

基本要求

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

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

可以取常用到的著名站點的域名和IP 地址為例構建域名結構的樹，一般應有20個左右的站點域名。下面提供了一組測試數(shù)據(jù)，當輸入“www.ustc.edu.cn ”輸出為“202.38.64.2”；而輸入www.ustcustc.edu.cn 時，輸出應為“找不到服務器或發(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)提示

樹的存儲結構采用孩子兄弟鏈表。

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

2

數(shù)據(jù)

A

B

D

F

G

C

E H 左標記 1 0 1 0 0 1 0 0 右標記 RG 1 1 1 0 0 0 1 0

DATA LG

二叉樹 文件保存形式

問題討論

實際的使用中，樹結構的使用機會筆二叉樹還要多，一般情況下都采用孩子－兄弟鏈表做樹的存儲結構，此時也可將樹視作二叉樹，并將對樹的操作轉換成對二叉樹的相應操作。

3