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

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

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

問(wèn)題描述

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

基本要求

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

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

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

實(shí)現(xiàn)提示

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

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

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

二叉樹 文件保存形式

問(wèn)題討論

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

3