因特網(wǎng)域名解析子系統(tǒng)
因特網(wǎng)域名解析子系統(tǒng) No.1 `一. 問題分析:1. 以樹中的孩子—兄弟鏈表形式存儲(chǔ)internet 域名.2. 保存樹的信息:用文件方式, 先根遍歷.3. 查
因特網(wǎng)域名解析子系統(tǒng) No.1 `一. 問題分析:
1. 以樹中的孩子—兄弟鏈表形式存儲(chǔ)internet 域名.
2. 保存樹的信息:用文件方式, 先根遍歷.
3. 查詢:將所給域名在樹上匹配, 之后轉(zhuǎn)換成IP 地址.
4. 匹配是要拆分所給的字符串, 儲(chǔ)存到鏈表或棧中.
5. 若要申請一個(gè)新域名, 則插到樹上的相應(yīng)位置上, 并儲(chǔ)存其IP 地址.
6. 測試數(shù)據(jù).(附后)
二. 總體設(shè)計(jì):
1. 抽象數(shù)據(jù)類型樹的定義如下:
ADT Tree{
數(shù)據(jù)對象D: D是具有相同特性的數(shù)據(jù)元素的集合.
數(shù)據(jù)關(guān)系R: 若D 為空集, 則稱為空樹.
若D 僅含一個(gè)數(shù)據(jù)元素, 則R 為空集, 否則R={H}.
H 是如下二元關(guān)系:
(1) 在D 中存在唯一的稱為根的數(shù)據(jù)元素root, 它在關(guān)系H 下無前驅(qū);
(2) 若D –{root}≠Φ, 則存在D-{root}的一個(gè)劃分D 1, D 2, …D m (m>0),對任意j
≠k(1≦j,k ≧m), 有D j ∩D k =Φ, 且對任意的i (1≦i ≦m), 唯一存在數(shù)據(jù)元
素x i ∈D i , 有
(3) 對應(yīng)于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 上的二元關(guān)系,(Di, {Hi })是一棵符合本定義的樹,
稱為根root 的子樹.
基本操作P:
InitTree(&T);
操作結(jié)果: 構(gòu)造空樹T.
CreateTree(&T,definition);
初始條件: definition給出樹T 的定義.
操作結(jié)果: 按definition 構(gòu)造樹T.
InsertChild(&T,&p,ic);
初始條件: 樹T 存在,p 指向T 中某個(gè)結(jié)點(diǎn),1≦i ≦p 所指結(jié)點(diǎn)的度 1,非空 樹c 與T 不相交.
操作結(jié)果: 插入c 為T 中p 指結(jié)點(diǎn)的第I 棵子樹.
TraverseTree(&T,Visit());
初始條件: 樹T 存在,Visit 是對結(jié)點(diǎn)操作的應(yīng)用函數(shù).
操作結(jié)果: 按某種次序?qū) 的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次. 一旦visit()失敗, 則操作失敗.
DisplayTree(&T,level);
初始條件: 樹T 存在,level 代表結(jié)點(diǎn)的層數(shù).
操作結(jié)果: 按某種次序?qū) 進(jìn)行遍歷, 每次遇到一個(gè)結(jié)點(diǎn)就把它
打出來, 利用 level記錄結(jié)點(diǎn)層數(shù), 依據(jù)level 的多少打印空 格.
,No.2
SearchTree(&T,KEY());
初始條件: 樹T 存在, 利用線性表KEY()存儲(chǔ)想找的域名, 與樹上的結(jié)點(diǎn)匹配. 操作結(jié)果: 如果線性表中的域名與樹中的結(jié)點(diǎn)一一對應(yīng), 則返回域名的IP 地 址值.
若沒找到, 則返回‖沒找到‖.
若線性表中的域名少于樹中相應(yīng)子樹的結(jié)點(diǎn)數(shù)(即沒到葉子結(jié)點(diǎn)), 則把子樹中所有 結(jié)點(diǎn)的IP 地址值打出來.
ApplyTree(&T,KEY());
初始條件: 樹T 存在, 若想申請一個(gè)樹上沒有的結(jié)點(diǎn), 則先查找, 把它插
到相應(yīng)結(jié)點(diǎn)的firstchild 或nextsibling 上去.
操作結(jié)果: 若線性表中結(jié)點(diǎn)在樹中完全匹配, 則返回‖域名已存在‖.
若找不到, 則申請一個(gè)新結(jié)點(diǎn)插入到結(jié)點(diǎn)的firstchild 或
nextsibling處.
}ADT Tree
2. 主程序:
void main()
{
定義類型, 初始化;
打開創(chuàng)建的文件;
主菜單;
選項(xiàng);
輸出結(jié)果;
}
3. 本程序的模塊如下:
每個(gè)詳細(xì)的域名對應(yīng)一個(gè)固定的IP 地址
_________________↓__________________________________________ ↓ ↓ ↓
生成一棵用孩子―兄弟鏈表 在樹上遍歷查詢所需要 保存信息
做成的樹, 把結(jié)點(diǎn)信息存入到 的域名,(用按層遍歷的 當(dāng)用戶退出時(shí), 出現(xiàn)
文件中, 每次用文件調(diào)用. 方法) ―是否保存‖的字樣
(Create) (Search) 根據(jù)需求不保存或
∣ 保存到文件中.
｜ (Save)
_____________________________↓______________________________
↓ ↓ ↓ ↓
用戶輸入一域名, 把輸入的域名用鏈表存儲(chǔ), 顯示整棵樹 申請一個(gè)域名:
按輸入的‖. ‖把域名 將單個(gè)字符串與樹上的結(jié)點(diǎn) 先進(jìn)行匹配, 當(dāng)完全匹配時(shí) 拆分成為一個(gè)個(gè)單 匹配. 若找到了, 則返回‖找 返回‖已存在‖. 當(dāng)不匹配時(shí) 個(gè)字符串 到‖及其IP 地址. 若沒找到, 就在不匹配處后生成其兄 就返回‖沒找到‖. 弟結(jié)點(diǎn), 把信息放入.
,No.3
三. 詳細(xì)設(shè)計(jì):
1. 樹的結(jié)點(diǎn)和葉子的類型:
#define NULL 0 ∥樹中指針指向空
#define maxsize 20 ∥結(jié)點(diǎn)的URL 數(shù)值的最大值 typedef struct tree{ ∥樹中結(jié)點(diǎn)的信息
int level; ∥結(jié)點(diǎn)在樹中的層數(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; ∥樹結(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)的類型
樹的基本操作:
void InitTree(CSTREE &T);
∥初始化樹的二叉鏈表(孩子―兄弟), 表示一個(gè)空樹, 從文件讀入結(jié)點(diǎn)信息. Status display_URL(CSTREE &T);
∥遍歷整棵樹, 顯示樹的形狀.
Status client_URL();
∥用戶建入域名, 用此函數(shù)進(jìn)行字符串的拆分, 用頭插法生成線性表.
Status search(CSTREE &T,KEY &head);
∥利用線性表儲(chǔ)存一個(gè)要找的域名, 利用strcmp 函數(shù)對線性表中結(jié)點(diǎn)和樹中 ∥結(jié)點(diǎn)進(jìn)行匹配. 若找到, 則返回‖找到‖并顯示域名的IP 地址;
∥若沒找到, 則返回‖URL 沒找到‖.
∥若線性表中域名樹少于樹中相應(yīng)子樹的結(jié)點(diǎn)數(shù)(即沒到葉子結(jié)點(diǎn))
∥則顯示處所有相應(yīng)子樹的IP 地址值.
Status apply(CSTREE &T,KEY &head);
∥申請一個(gè)域名
∥先用search 函數(shù)找, 如果找到這個(gè)要申請的域名就返回‖此域名已存在‖, ∥若域名不存在, 而輸入的IP 地址已存在則返回‖IP 地址已存在‖.
∥若所申請的域名和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){ ∥顯示樹的形狀
if(root){
for(i=0;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); ∥此函數(shù)為:
∥找葉子結(jié)點(diǎn)的IP 值 }
else
seach(head,root->nextsibling);
}
else
if(head)
printf(―URL 沒找到‖);
}