实验四 利用树型结构的搜索算法模拟因特网域名的查询

实验四 利用树型结构的搜索算法模拟因特网域名的查询问题描述在第六章树结构中曾讨论Internet 的域名系统，以树型结构实现域名的搜索。即输入某站点的域名，在域名系统的树型结构中进行搜索，直至域名全部

实验四 利用树型结构的搜索算法模拟

因特网域名的查询

问题描述

在第六章树结构中曾讨论Internet 的域名系统，以树型结构实现域名的搜索。即输入某站点的域名，在域名系统的树型结构中进行搜索，直至域名全部匹配成功或匹配失败；若成功则给出该站点的IP 地址，否则给出找不到该站点的信息。

基本要求

首先要实现一个反映域名结构的树，例如中国科学技术大学www.ustc.edu.cn 在该树从根到叶子的各层结点就应是root、cn、edu、ustc、www。叶子结点www 另有一个数据域，存放中国科学技术大学站点的IP 地址202.38.64.2。

测试数据

可以取常用到的著名站点的域名和IP 地址为例构建域名结构的树，一般应有20个左右的站点域名。下面提供了一组测试数据，当输入“www.ustc.edu.cn ”输出为“202.38.64.2”；而输入www.ustcustc.edu.cn 时，输出应为“找不到服务器或发生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

实现提示

树的存储结构采用孩子兄弟链表。

二叉链表的树结构是一种动态结构，除第一次生成的过程需要人工输入数据外，以后每次进行搜索查询时，应首先从文件中保存的数据自动生成树的结构。为解决二叉链表与文件之间的转换，可以通过先序遍历的办法保存和恢复二叉链表。例如一个二叉链表的文件保存形式如下：

2

数据

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