酷米网(kmw.com),专注高端域名快速交易!

  1. 当前位置: 
  2. 首页 > 
  3. 域名资讯  > 因特网域名解析子系统
服务器时间:2018-01-23 20:02:49 (CST +08:00)

因特网域名解析子系统

2017-12-17 17:23:47     浏览量: 7

因特网域名解析子系统 No.1 `一. 问题分析:

1. 以树中的孩子—兄弟链表形式存储internet 域名.

2. 保存树的信息:用文件方式, 先根遍历.

3. 查询:将所给域名在树上匹配, 之后转换成IP 地址.

4. 匹配是要拆分所给的字符串, 储存到链表或栈中.

5. 若要申请一个新域名, 则插到树上的相应位置上, 并储存其IP 地址.

6. 测试数据.(附后)

二. 总体设计:

1. 抽象数据类型树的定义如下:

ADT Tree{

数据对象D: D是具有相同特性的数据元素的集合.

数据关系R: 若D 为空集, 则称为空树.

若D 仅含一个数据元素, 则R 为空集, 否则R={H}.

H 是如下二元关系:

(1) 在D 中存在唯一的称为根的数据元素root, 它在关系H 下无前驱;

(2) 若D –{root}≠Φ, 则存在D-{root}的一个划分D 1, D 2, …D m (m>0),对任意j

≠k(1≦j,k ≧m), 有D j ∩D k =Φ, 且对任意的i (1≦i ≦m), 唯一存在数据元

素x i ∈D i , 有∈H;

(3) 对应于D ―{root}的划分.H ―{,…,}有唯一的一个

划分H 1, H 2, …H m (m>0),对任意j ≠k(1≦j,k ≦m) 有 Hj ∩H k =φ, 且对

任意(1≦i ≦m),H i 是D i 上的二元关系,(Di, {Hi })是一棵符合本定义的树,

称为根root 的子树.

基本操作P:

InitTree(&T);

操作结果: 构造空树T.

CreateTree(&T,definition);

初始条件: definition给出树T 的定义.

操作结果: 按definition 构造树T.

InsertChild(&T,&p,ic);

初始条件: 树T 存在,p 指向T 中某个结点,1≦i ≦p 所指结点的度 1,非空 树c 与T 不相交.

操作结果: 插入c 为T 中p 指结点的第I 棵子树.

TraverseTree(&T,Visit());

初始条件: 树T 存在,Visit 是对结点操作的应用函数.

操作结果: 按某种次序对T 的每个结点调用函数visit()一次且至多一次. 一旦visit()失败, 则操作失败.

DisplayTree(&T,level);

初始条件: 树T 存在,level 代表结点的层数.

操作结果: 按某种次序对T 进行遍历, 每次遇到一个结点就把它

打出来, 利用 level记录结点层数, 依据level 的多少打印空 格.

,

No.2

SearchTree(&T,KEY());

初始条件: 树T 存在, 利用线性表KEY()存储想找的域名, 与树上的结点匹配. 操作结果: 如果线性表中的域名与树中的结点一一对应, 则返回域名的IP 地 址值.

若没找到, 则返回‖没找到‖.

若线性表中的域名少于树中相应子树的结点数(即没到叶子结点), 则把子树中所有 结点的IP 地址值打出来.

ApplyTree(&T,KEY());

初始条件: 树T 存在, 若想申请一个树上没有的结点, 则先查找, 把它插

到相应结点的firstchild 或nextsibling 上去.

操作结果: 若线性表中结点在树中完全匹配, 则返回‖域名已存在‖.

若找不到, 则申请一个新结点插入到结点的firstchild 或

nextsibling处.

}ADT Tree

2. 主程序:

void main()

{

定义类型, 初始化;

打开创建的文件;

主菜单;

选项;

输出结果;

}

3. 本程序的模块如下:

每个详细的域名对应一个固定的IP 地址

_________________↓__________________________________________ ↓ ↓ ↓

生成一棵用孩子―兄弟链表 在树上遍历查询所需要 保存信息

做成的树, 把结点信息存入到 的域名,(用按层遍历的 当用户退出时, 出现

文件中, 每次用文件调用. 方法) ―是否保存‖的字样

(Create) (Search) 根据需求不保存或

∣ 保存到文件中.

| (Save)

_____________________________↓______________________________

↓ ↓ ↓ ↓

用户输入一域名, 把输入的域名用链表存储, 显示整棵树 申请一个域名:

按输入的‖. ‖把域名 将单个字符串与树上的结点 先进行匹配, 当完全匹配时 拆分成为一个个单 匹配. 若找到了, 则返回‖找 返回‖已存在‖. 当不匹配时 个字符串 到‖及其IP 地址. 若没找到, 就在不匹配处后生成其兄 就返回‖没找到‖. 弟结点, 把信息放入.

,

No.3

三. 详细设计:

1. 树的结点和叶子的类型:

#define NULL 0 ∥树中指针指向空

#define maxsize 20 ∥结点的URL 数值的最大值 typedef struct tree{ ∥树中结点的信息

int level; ∥结点在树中的层数

char url[maxsize]; ∥结点中放的域名

char IP[18]; ∥叶子结点的IP 地址

struct tree *firstchild; ∥结点的头孩子指针

struct tree *nextsibling; ∥结点的兄弟指针

char tag; ∥

}CSTREE; ∥树结点的类型

typedef struct keynode{ ∥线性表结点, 用于字符串的拆分 char keynode[maxsize]; ∥线性表结点的域名

struct keynode *nextkey; ∥线性表结点中指向下一个结点的指针 }KEY; ∥线性表结点的类型

树的基本操作:

void InitTree(CSTREE &T);

∥初始化树的二叉链表(孩子―兄弟), 表示一个空树, 从文件读入结点信息. Status display_URL(CSTREE &T);

∥遍历整棵树, 显示树的形状.

Status client_URL();

∥用户建入域名, 用此函数进行字符串的拆分, 用头插法生成线性表.

Status search(CSTREE &T,KEY &head);

∥利用线性表储存一个要找的域名, 利用strcmp 函数对线性表中结点和树中 ∥结点进行匹配. 若找到, 则返回‖找到‖并显示域名的IP 地址;

∥若没找到, 则返回‖URL 没找到‖.

∥若线性表中域名树少于树中相应子树的结点数(即没到叶子结点)

∥则显示处所有相应子树的IP 地址值.

Status apply(CSTREE &T,KEY &head);

∥申请一个域名

∥先用search 函数找, 如果找到这个要申请的域名就返回‖此域名已存在‖, ∥若域名不存在, 而输入的IP 地址已存在则返回‖IP 地址已存在‖.

∥若所申请的域名和IP 地址不存在, 则利用client 将字符串分解,

∥再插入到相应位置, 将其保存.

部分操作的伪码如下:

void Display_CSTREE(File *fp){ ∥读入URL 的值

static int level=0;

fgets(root->url,20,fp);

if(root->url==0)

,

root=NULL;

No.4

else{

root->firstchild=load(fp);

root->nextsibling=load(fp);

}

}

void display (CSTREE *root){ ∥显示树的形状

if(root){

for(i=0;ilevel;i )

printf(―t‖);

printf(root->url);

display (root->firstchild);

display (root->nextsibling);

}

}

KEY *client(){ ∥用户输入域名, 拆分字符串, 用头 ∥插法生成线性表.

head=(KEY*)malloc(sizeof(KEY));

head->nextkey=NULL;

i=0;

while((ch=getchar())!=’n’){

if(ch==’. ’){

head->key[i]=’n’;

head->key[i 1]=NULL;

s=(KEY*)malloc(sizeof(KEY));

s->nextkey=head;

head=s;

i=0;

}

else{head->key[i]=ch;

i ;

}

}

head->key[i]=’n’;

head->key[i 1]=NULL;

return head;

}

,

No.5

void search (KEY *head,CSTREE *root){ ∥在树中查找用户输入的域名, ∥找到就返回其IP 地址,

∥没找到就返回‖没找到‖. if (root){

if(head->key==root->url)){

head=head->nextkey;

if(head为空){

if(root->firstchild为空)

printf(root->ip);

else

leave_ip(root); ∥此函数为:

∥找叶子结点的IP 值 }

else

seach(head,root->nextsibling);

}

else

if(head)

printf(―URL 没找到‖);

}