因特網域名解析子系統(tǒng)
因特網域名解析子系統(tǒng) No.1 `一. 問題分析:1. 以樹中的孩子—兄弟鏈表形式存儲internet 域名.2. 保存樹的信息:用文件方式, 先根遍歷.3. 查
因特網域名解析子系統(tǒng) 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 , 有
(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()
{
定義類型, 初始化;
打開創(chuàng)建的文件;
主菜單;
選項;
輸出結果;
}
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;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 沒找到‖);
}