因特網(wǎng)域名解析子系統(tǒng) No.1 `一. 問(wèn)題分析:1. 以樹(shù)中的孩子—兄弟鏈表形式存儲(chǔ)internet 域名.2. 保存樹(shù)的信息:用文件方式, 先根遍歷.3. 查

因特網(wǎng)域名解析子系統(tǒng) No.1 `一. 問(wèn)題分析:

1. 以樹(shù)中的孩子—兄弟鏈表形式存儲(chǔ)internet 域名.

2. 保存樹(shù)的信息:用文件方式, 先根遍歷.

3. 查詢:將所給域名在樹(shù)上匹配, 之后轉(zhuǎn)換成IP 地址.

4. 匹配是要拆分所給的字符串, 儲(chǔ)存到鏈表或棧中.

5. 若要申請(qǐng)一個(gè)新域名, 則插到樹(shù)上的相應(yīng)位置上, 并儲(chǔ)存其IP 地址.

6. 測(cè)試數(shù)據(jù).(附后)

二. 總體設(shè)計(jì):

1. 抽象數(shù)據(jù)類型樹(shù)的定義如下:

ADT Tree{

數(shù)據(jù)對(duì)象D: D是具有相同特性的數(shù)據(jù)元素的集合.

數(shù)據(jù)關(guān)系R: 若D 為空集, 則稱為空樹(shù).

若D 僅含一個(gè)數(shù)據(jù)元素, 則R 為空集, 否則R={H}.

H 是如下二元關(guān)系:

(1) 在D 中存在唯一的稱為根的數(shù)據(jù)元素root, 它在關(guān)系H 下無(wú)前驅(qū);

(2) 若D –{root}≠Φ, 則存在D-{root}的一個(gè)劃分D 1, D 2, …D m (m>0),對(duì)任意j

≠k(1≦j,k ≧m), 有D j ∩D k =Φ, 且對(duì)任意的i (1≦i ≦m), 唯一存在數(shù)據(jù)元

素x i ∈D i , 有∈H;

(3) 對(duì)應(yīng)于D ―{root}的劃分.H ―{,…,}有唯一的一個(gè)

劃分H 1, H 2, …H m (m>0),對(duì)任意j ≠k(1≦j,k ≦m) 有 Hj ∩H k =φ, 且對(duì)

任意(1≦i ≦m),H i 是D i 上的二元關(guān)系,(Di, {Hi })是一棵符合本定義的樹(shù),

稱為根root 的子樹(shù).

基本操作P:

InitTree(&T);

操作結(jié)果: 構(gòu)造空樹(shù)T.

CreateTree(&T,definition);

初始條件: definition給出樹(shù)T 的定義.

操作結(jié)果: 按definition 構(gòu)造樹(shù)T.

InsertChild(&T,&p,ic);

初始條件: 樹(shù)T 存在,p 指向T 中某個(gè)結(jié)點(diǎn),1≦i ≦p 所指結(jié)點(diǎn)的度 1,非空 樹(shù)c 與T 不相交.

操作結(jié)果: 插入c 為T 中p 指結(jié)點(diǎn)的第I 棵子樹(shù).

TraverseTree(&T,Visit());

初始條件: 樹(shù)T 存在,Visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù).

操作結(jié)果: 按某種次序?qū) 的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次. 一旦visit()失敗, 則操作失敗.

DisplayTree(&T,level);

初始條件: 樹(shù)T 存在,level 代表結(jié)點(diǎn)的層數(shù).

操作結(jié)果: 按某種次序?qū) 進(jìn)行遍歷, 每次遇到一個(gè)結(jié)點(diǎn)就把它

打出來(lái), 利用 level記錄結(jié)點(diǎn)層數(shù), 依據(jù)level 的多少打印空 格.

No.2

SearchTree(&T,KEY());

初始條件: 樹(shù)T 存在, 利用線性表KEY()存儲(chǔ)想找的域名, 與樹(shù)上的結(jié)點(diǎn)匹配. 操作結(jié)果: 如果線性表中的域名與樹(shù)中的結(jié)點(diǎn)一一對(duì)應(yīng), 則返回域名的IP 地 址值.

若沒(méi)找到, 則返回‖沒(méi)找到‖.

若線性表中的域名少于樹(shù)中相應(yīng)子樹(shù)的結(jié)點(diǎn)數(shù)(即沒(méi)到葉子結(jié)點(diǎn)), 則把子樹(shù)中所有 結(jié)點(diǎn)的IP 地址值打出來(lái).

ApplyTree(&T,KEY());

初始條件: 樹(shù)T 存在, 若想申請(qǐng)一個(gè)樹(shù)上沒(méi)有的結(jié)點(diǎn), 則先查找, 把它插

到相應(yīng)結(jié)點(diǎn)的firstchild 或nextsibling 上去.

操作結(jié)果: 若線性表中結(jié)點(diǎn)在樹(shù)中完全匹配, 則返回‖域名已存在‖.

若找不到, 則申請(qǐng)一個(gè)新結(jié)點(diǎn)插入到結(jié)點(diǎn)的firstchild 或

nextsibling處.

}ADT Tree

2. 主程序:

void main()

{

定義類型, 初始化;

打開(kāi)創(chuàng)建的文件;

主菜單;

選項(xiàng);

輸出結(jié)果;

}

3. 本程序的模塊如下:

每個(gè)詳細(xì)的域名對(duì)應(yīng)一個(gè)固定的IP 地址

_________________↓__________________________________________ ↓ ↓ ↓

生成一棵用孩子―兄弟鏈表 在樹(shù)上遍歷查詢所需要 保存信息

做成的樹(shù), 把結(jié)點(diǎn)信息存入到 的域名,(用按層遍歷的 當(dāng)用戶退出時(shí), 出現(xiàn)

文件中, 每次用文件調(diào)用. 方法) ―是否保存‖的字樣

(Create) (Search) 根據(jù)需求不保存或

∣ 保存到文件中.

｜ (Save)

_____________________________↓______________________________

↓ ↓ ↓ ↓

用戶輸入一域名, 把輸入的域名用鏈表存儲(chǔ), 顯示整棵樹(shù) 申請(qǐng)一個(gè)域名:

按輸入的‖. ‖把域名 將單個(gè)字符串與樹(shù)上的結(jié)點(diǎn) 先進(jìn)行匹配, 當(dāng)完全匹配時(shí) 拆分成為一個(gè)個(gè)單 匹配. 若找到了, 則返回‖找 返回‖已存在‖. 當(dāng)不匹配時(shí) 個(gè)字符串 到‖及其IP 地址. 若沒(méi)找到, 就在不匹配處后生成其兄 就返回‖沒(méi)找到‖. 弟結(jié)點(diǎn), 把信息放入.

No.3

三. 詳細(xì)設(shè)計(jì):

1. 樹(shù)的結(jié)點(diǎn)和葉子的類型:

#define NULL 0 ∥樹(shù)中指針指向空

#define maxsize 20 ∥結(jié)點(diǎn)的URL 數(shù)值的最大值 typedef struct tree{ ∥樹(shù)中結(jié)點(diǎn)的信息

int level; ∥結(jié)點(diǎn)在樹(shù)中的層數(shù)

char url[maxsize]; ∥結(jié)點(diǎn)中放的域名

char IP[18]; ∥葉子結(jié)點(diǎn)的IP 地址

struct tree *firstchild; ∥結(jié)點(diǎn)的頭孩子指針

struct tree *nextsibling; ∥結(jié)點(diǎn)的兄弟指針

char tag; ∥

}CSTREE; ∥樹(shù)結(jié)點(diǎn)的類型

typedef struct keynode{ ∥線性表結(jié)點(diǎn), 用于字符串的拆分 char keynode[maxsize]; ∥線性表結(jié)點(diǎn)的域名

struct keynode *nextkey; ∥線性表結(jié)點(diǎn)中指向下一個(gè)結(jié)點(diǎn)的指針 }KEY; ∥線性表結(jié)點(diǎn)的類型

樹(shù)的基本操作:

void InitTree(CSTREE &T);

∥初始化樹(shù)的二叉鏈表(孩子―兄弟), 表示一個(gè)空樹(shù), 從文件讀入結(jié)點(diǎn)信息. Status display_URL(CSTREE &T);

∥遍歷整棵樹(shù), 顯示樹(shù)的形狀.

Status client_URL();

∥用戶建入域名, 用此函數(shù)進(jìn)行字符串的拆分, 用頭插法生成線性表.

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

∥利用線性表儲(chǔ)存一個(gè)要找的域名, 利用strcmp 函數(shù)對(duì)線性表中結(jié)點(diǎn)和樹(shù)中 ∥結(jié)點(diǎn)進(jìn)行匹配. 若找到, 則返回‖找到‖并顯示域名的IP 地址;

∥若沒(méi)找到, 則返回‖URL 沒(méi)找到‖.

∥若線性表中域名樹(shù)少于樹(shù)中相應(yīng)子樹(shù)的結(jié)點(diǎn)數(shù)(即沒(méi)到葉子結(jié)點(diǎn))

∥則顯示處所有相應(yīng)子樹(shù)的IP 地址值.

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

∥申請(qǐng)一個(gè)域名

∥先用search 函數(shù)找, 如果找到這個(gè)要申請(qǐng)的域名就返回‖此域名已存在‖, ∥若域名不存在, 而輸入的IP 地址已存在則返回‖IP 地址已存在‖.

∥若所申請(qǐng)的域名和IP 地址不存在, 則利用client 將字符串分解,

∥再插入到相應(yīng)位置, 將其保存.

部分操作的偽碼如下:

void Display_CSTREE(File *fp){ ∥讀入U(xiǎn)RL 的值

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){ ∥顯示樹(shù)的形狀

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){ ∥在樹(shù)中查找用戶輸入的域名, ∥找到就返回其IP 地址,

∥沒(méi)找到就返回‖沒(méi)找到‖. if (root){

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

head=head->nextkey;

if(head為空){

if(root->firstchild為空)

printf(root->ip);

else

leave_ip(root); ∥此函數(shù)為:

∥找葉子結(jié)點(diǎn)的IP 值 }

else

seach(head,root->nextsibling);

}

else

if(head)

printf(―URL 沒(méi)找到‖);

}