數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告題 目： 互聯(lián)網(wǎng)域名查詢 姓 名： 學(xué) 院：信息科學(xué)與工程學(xué)院 班 級(jí)： 學(xué) 號(hào)： 26實(shí)驗(yàn)三 樹(shù)和圖應(yīng)用類實(shí)驗(yàn)一、 問(wèn)題定義及i需求分析1.問(wèn)題描述互聯(lián)網(wǎng)域名系統(tǒng)是一個(gè)典型的樹(shù)形層次結(jié)構(gòu)。從根節(jié)點(diǎn)往下的第一層是頂層域，如cn、com等，最底層（第四層）是葉子結(jié)點(diǎn)，如www等。因此，域名搜索可以看成是樹(shù)的遍歷問(wèn)題。2. 實(shí)驗(yàn)要求設(shè)計(jì)搜索互聯(lián)網(wǎng)域名的程序。（1）采用樹(shù)的孩子兄弟鏈表等存儲(chǔ)結(jié)構(gòu)。（2）創(chuàng)建樹(shù)形結(jié)構(gòu)。（3）通過(guò)深度優(yōu)先遍歷搜索。（4）通過(guò)層次優(yōu)先遍歷搜索。3.數(shù)據(jù)輸入的形式輸入域名地址。如：4.數(shù)據(jù)輸出的形式輸出對(duì)應(yīng)的ip地址或者出錯(cuò)時(shí)輸出“找不到服務(wù)器或發(fā)生DN

2、S錯(cuò)誤”二、概要設(shè)計(jì)（1）為了實(shí)現(xiàn)上述程序的功能，應(yīng)該以孩子兄弟鏈表存儲(chǔ)樹(shù)，所以需要樹(shù)的抽象數(shù)據(jù)類型。（2）存入磁盤(pán)文件時(shí)還需要另一種文件的抽象數(shù)據(jù)類型。（3）所有的域名和IP都是以串的形式存的，所以還需要串的抽象數(shù)據(jù)類型。（4）當(dāng)用戶輸入站點(diǎn)的域名時(shí)，需要將域名分段存儲(chǔ)，在搜索時(shí)從最根部依次提出來(lái)與樹(shù)的節(jié)點(diǎn)域比較，由于用戶輸入是從最小級(jí)到最根級(jí)，彈出時(shí)與輸入順序相反，比如輸入“”，其中：www是第三級(jí)，163是第二級(jí)，com是第一級(jí)，所以再與樹(shù)節(jié)點(diǎn)比較時(shí)，首先比較com，然后比較163，最后才比較www。根據(jù)這種“后進(jìn)先出”的關(guān)系，需要棧作為輔助工具，所以需要棧的抽象數(shù)據(jù)類型。具體內(nèi)容：1）

3、樹(shù)的抽象數(shù)據(jù)類型ADT Tree 數(shù)據(jù)對(duì)象D：站點(diǎn)域名的集合。數(shù)據(jù)關(guān)系R：H（1）D中存在惟一稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒(méi)有前驅(qū)。（2）D-root之后可劃分為D1,D2,Dn（n>0）對(duì)任意的劃分都兩兩不相交。對(duì)任意的i（1in），惟一的存在數(shù)據(jù)元素，有；（3）對(duì)應(yīng)于D-root的劃分，H-root ，Xi（i=1,2,n）有惟一的一個(gè)劃分H1,H2,Hn （n>0），對(duì)任意的(ij,kn)有，并且對(duì)任意的i（1in）, 是Di上的二元關(guān)系，（Di，Hi）是一顆符合本定義的樹(shù)，成為根root的子樹(shù)?；静僮鱌：CreateChild（&T）初始條件：樹(shù)根T已經(jīng)

4、存在。操作結(jié)果：根據(jù)用戶輸入的域名建立此域名的樹(shù)鏈，并以T為樹(shù)根如用戶輸入，則在建立起以T為根，cn為T(mén)的第一個(gè)孩子，www為葉子的樹(shù)鏈，所有的節(jié)點(diǎn)都鏈在孩子域。InitialTree（&T）操作結(jié)果：通過(guò)用戶輸入的數(shù)據(jù)，構(gòu)造域名樹(shù)。其實(shí)是將建好的域名樹(shù)鏈有序地插到樹(shù)中相應(yīng)的位置。Insert（&T）初始條件：樹(shù)T已經(jīng)存在。操作結(jié)果：插入新的域名及IP。CreateTree（&T, *fp）初始條件：包含樹(shù)的信息文件已經(jīng)存在，fp 為指向文件的指針。操作結(jié)果：通過(guò)從文件中讀取數(shù)據(jù)，構(gòu)造域名樹(shù)。DeleteTree（&T）初始條件：T已經(jīng)存在。操作結(jié)果：銷毀樹(shù)，釋

5、放空間。 ADT Tree2）文件的抽象數(shù)據(jù)類型ADT File 數(shù)據(jù)對(duì)象：D =aiaiElemSet, i1,2,n, n0數(shù)據(jù)關(guān)系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：Save（&T）初始條件：樹(shù)T存在。操作結(jié)果：先序遍歷樹(shù)，給葉子節(jié)點(diǎn)數(shù)據(jù)域賦IP值，同時(shí)把相關(guān)信息存入文件。 ADT File3）串的抽象數(shù)據(jù)類型ADT String 數(shù)據(jù)對(duì)象：D =aiaiElemSet, i1,2,n, n0數(shù)據(jù)關(guān)系：R =ai-1,aiai-1,aiD, i1,2,n基本操作：CopyChar（&s, *a）初始條件：a是字符串常量。操作結(jié)果：生成一個(gè)其值等

6、于a的串s。CopyStr（&s, a）初始條件：a是一個(gè)串。操作結(jié)果：生成一個(gè)值等于a的串s。CompareStr（a, b）初始條件：a和b是兩個(gè)串。操作結(jié)果：若a>b返回值>0;若a=b,返回值=0;若a<b，返回值<0。DeleteString（&s）初始條件：串s存在。操作結(jié)果：銷毀串。 ADT String4）棧的抽象數(shù)據(jù)類型ADT Stack 數(shù)據(jù)對(duì)象：D =aiaiElemSet, i1,2,n, n0數(shù)據(jù)關(guān)系：R =ai-1,aiai-1,aiD, i1,2,n約定為棧底，為棧頂基本操作：InitialStack（&s）操作結(jié)果

7、：構(gòu)造一個(gè)空棧。GetTop（s，&e）初始條件：棧s已經(jīng)存在且非空。操作結(jié)果：用e返回棧s的棧頂元素。Push（&s, e）初始條件：棧s已經(jīng)存在且非空。操作結(jié)果：插入元素e為新的棧頂元素。Pop（&s, &e）初始條件：棧s已經(jīng)存在且非空。操作結(jié)果：刪除棧s的棧頂元素，并用e返回其值。DeleteStack（&s）初始條件：s已經(jīng)存在。操作結(jié)果：銷毀棧，釋放空間。 ADT Stack5）本程序5個(gè)模塊本程序有5個(gè)模塊：主程序模塊，樹(shù)模塊（實(shí)現(xiàn)樹(shù)抽象數(shù)據(jù)類型），文件模塊（實(shí)現(xiàn)文件抽象數(shù)據(jù)類型），串模塊（實(shí)現(xiàn)串抽象數(shù)據(jù)類型），棧模塊（實(shí)現(xiàn)棧抽象數(shù)據(jù)類型）

8、三、詳細(xì)設(shè)計(jì)typedef unsigned char String30;/ 存放域名和IP的串結(jié)構(gòu)typedef struct TreeNode / 樹(shù)的節(jié)點(diǎn)ElemType data,IP;/ 數(shù)據(jù)域（用來(lái)放域名）和IP域（用來(lái)放IP）struct TreeNode *firstchild,*nextsibling;/ 指向孩子和兄弟的指針/ 兄弟表示同一層，孩子表示下一層 TreeNode,*Tree;typedef struct FileNode / 存入文件的節(jié)點(diǎn)ElemType data,IP;/ 數(shù)據(jù)域（用來(lái)放域名）和IP域（用來(lái)放IP）int ltag,rtag;/ 左右標(biāo)志域

9、：0表示無(wú)孩子，1表示有孩子 FileNode;typedef struct SNode / 用戶輸入的域名存在棧節(jié)點(diǎn)SElemType data;/ 數(shù)據(jù)域（用來(lái)存放域名被 '.' 分開(kāi)的一部分struct SNode *next;/ 指針域，指向域名下一部分 SNode,*Stack;（1）基本操作Stack CreateWeb（） / 用戶輸入域名時(shí)按 '.' 將域名分開(kāi)分別放入鏈?zhǔn)綏Ｖ? 最后將 "root" 入棧，為查找做準(zhǔn)備，返回棧頂指針CopyChar（root,"root"）;/ 把 "root&

10、quot; 的值賦給串rootInitialStack（webside）;/ 初始化鏈?zhǔn)綏o a =getchar（）;/ 輸入域名for （int i=0;a!='.'&&a!='n'i+）si=a; a=getchar（）;/ 得到兩個(gè) '.' 間的域名，將其值放入一個(gè)串中si='0'Push（webside,s）;/ 將串的值入棧 while（a!='n'）;Push（webside,root）;/ 將root入棧return webside;/ 返回棧頂?shù)闹羔?/ CreateWebvoi

11、d Search（Tree T,Stack &webside,Tree &p）/ 用遞歸算法通過(guò)域名查找相應(yīng)的IP，返回相同層的指針/ 若存在則輸出IP，若不存在則輸出相應(yīng)的出錯(cuò)信息if （T&&webside->next!=NULL）GetTop（webside,s）;/ 取得域名棧頂元素int t=CompareStr（s,T->data）;/ 比較域名和樹(shù)的數(shù)據(jù)域if （t>0） Search（T->nextsibling,webside,p）;/ 若域名比樹(shù)節(jié)點(diǎn)值大則遞歸搜索樹(shù)節(jié)點(diǎn)兄弟else if（t=0）Pop（webside

12、,s）; p=T;/ 若域名和樹(shù)節(jié)點(diǎn)相同則域名鏈?zhǔn)綏９?jié)點(diǎn)出棧Search（T->firstchild,webside,p）;/ 繼續(xù)搜索樹(shù)節(jié)點(diǎn)的孩子，即下一層 / end else / end if / Search（2）關(guān)于樹(shù)的操作void CreateChild（Tree &T,Stack &webside） / 用戶輸入一個(gè)網(wǎng)址域名，域名已經(jīng)被輸入到棧中，為域名建立相應(yīng)的域名樹(shù)鏈if（webside->next!=NULL）t=new TreeNode;/ 新開(kāi)一個(gè)節(jié)點(diǎn)Pop（webside,s）;/ 從棧中取出域名第一部分CopyStr（t->data

13、,s）;/ 把第一部分賦值給樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域t->firstchild=t->nextsibling=NULL;/ 把樹(shù)節(jié)點(diǎn)的孩子和兄弟鏈域暫置空t->IP0='0'/ 把樹(shù)節(jié)點(diǎn)的IP域置0T->firstchild=t;/ 讓根節(jié)點(diǎn)的孩子域指向新建的樹(shù)節(jié)點(diǎn)CreateChild（t,webside）;/ 再以此樹(shù)節(jié)點(diǎn)為根建立新的樹(shù)節(jié)點(diǎn)，/ 直到把域名全部賦值到樹(shù)節(jié)點(diǎn)中去if（t->firstchild=NULL）cout<<"請(qǐng)輸入域名IP"<<endl;/ 若是葉子節(jié)點(diǎn)則要求用戶輸入IPcin>&

14、gt;t->IP; / end if / end if / CreateChildvoid Insert（Tree &T）/ 將域名樹(shù)鏈插入到樹(shù)T中do cout<<"請(qǐng)輸入站點(diǎn)域名:"<<endl;webside=CreateWeb（）;/ 為用戶輸入的域名建立鏈表?xiàng)earch（T,webside,p）;/ 在樹(shù)中查找與域名節(jié)點(diǎn)相同的節(jié)點(diǎn)，/ 每一部分查找相匹配的樹(shù)節(jié)點(diǎn)，返回指向/ 最后一個(gè)與域名節(jié)點(diǎn)相同的樹(shù)節(jié)點(diǎn)的指針if（p->firstchild=NULL）if（p->IP0!='0'）/ 若發(fā)現(xiàn)輸入

15、了重復(fù)的域名則給出提示cout<<"你輸入了重復(fù)的域名"<<endl;else CreateChild（p,webside）;/ 若這個(gè)樹(shù)節(jié)點(diǎn)沒(méi)有孩子，則直接把新的/ 域名建立成新的樹(shù)，并讓這個(gè)樹(shù)節(jié)點(diǎn)孩/ 子域指向次新開(kāi)的域名樹(shù)。/ 即將域名節(jié)點(diǎn)作為此樹(shù)節(jié)點(diǎn)的第一個(gè)孩子 / end ifelse if（webside->next=NULL）/ 若發(fā)現(xiàn)輸入了錯(cuò)誤的域名，則給出相應(yīng)/ 的提示cout<<"你輸入了錯(cuò)誤的域名!"<<endl;else GetTop（webside,s）;/ 若這個(gè)樹(shù)節(jié)點(diǎn)有孩

16、子，則在他的孩子的/ 兄弟中找到新開(kāi)域名樹(shù)應(yīng)該插入的位置，將其插入t=p->firstchild;a=CompareStr（t->data,s）;/ 比較域名與已經(jīng)存在的兄弟節(jié)點(diǎn)if（a>0）CreateChild（p,webside）;/ 若域名比兄弟節(jié)點(diǎn)小，則前插p->firstchild->nextsibling=t; / end ifelse while（t->nextsibling!=NULL&&（a=CompareStr（t->nextsibling->data,s）<0）t=t->nextsibling;

17、/ 若域名比兄弟節(jié)點(diǎn)大，則后插q=new TreeNode;Pop（webside,s）;CopyStr（q->data,s）;q->firstchild=NULL;q->IP0='0'/ 給新開(kāi)節(jié)點(diǎn)賦值q->nextsibling=t->nextsibling;/ 新開(kāi)節(jié)點(diǎn)的兄弟指針指向插入處節(jié)/ 點(diǎn)的兄弟t->nextsibling=q;/ 插入處的節(jié)點(diǎn)的兄弟指針指向新開(kāi)節(jié)點(diǎn)CreateChild（q,webside）;/ 把整個(gè)域名樹(shù)鏈插入 / end else / end else / end elseDeleteStack（webs

18、ide）;cout<<"是否要繼續(xù)輸入新域名?（y/n）"<<endl;ch=getchar（）;/ 獲得用戶輸入的字符getchar（）;/ 此為用戶輸入的回車 while（ch='y'）; / Insertvoid InitialTree（Tree &T）/ 第一次由用戶輸入網(wǎng)站域名和IP，建立節(jié)點(diǎn)有序的樹(shù)T=new TreeNode;/ 新開(kāi)一個(gè)樹(shù)節(jié)點(diǎn)CopyChar（T->data,"root"）;/ 建立樹(shù)的根節(jié)點(diǎn)T->firstchild=T->nextsibling=NULL

19、;T->IP0='0'Insert（T）;/ 把新的域名樹(shù)鏈插入樹(shù)中 / InitialTreevoid CreateTree（Tree &T,FILE *fp）/ 文件已經(jīng)存在，從文件中讀出數(shù)據(jù)，用遞歸算法先序遍歷構(gòu)建樹(shù)的孩子，兄弟二叉鏈表結(jié)構(gòu)if（!feof（fp）T=new TreeNode;/ 新建樹(shù)節(jié)點(diǎn)f=new FileNode;/ 新建文件節(jié)點(diǎn)用于讀取磁盤(pán)文件中的數(shù)據(jù)if（fread（f,sizeof（struct FileNode）,1,fp）!=1）cout<<"無(wú)法打開(kāi)文件!"<<endl;CopyS

20、tr（T->data,f->data）;CopyStr（T->IP,f->IP）;/ 將文件節(jié)點(diǎn)的IP的值賦給樹(shù)節(jié)點(diǎn)IPif（f->ltag）CreateTree（T->firstchild,fp）;/ 若樹(shù)節(jié)點(diǎn)有孩子則遞歸建立其孩子else T->firstchild=NULL;/ 若無(wú)孩子則孩子鏈域置為空if（f->rtag）CreateTree（T->nextsibling,fp）;/ 若樹(shù)節(jié)點(diǎn)有兄弟則遞歸建立其兄弟else T->nextsibling=NULL;/ 若無(wú)兄弟則兄弟鏈域置為空delete f; / end if

21、 / CreateTreevoid DeleteTree（Tree &T）/ 用遞歸算法銷毀樹(shù)，釋放空間if（T）DeleteTree（T->firstchild）;/ 銷毀樹(shù)的左子樹(shù)DeleteTree（T->nextsibling）;/ 銷毀樹(shù)的右子樹(shù)delete T;/ 銷毀樹(shù)的根節(jié)點(diǎn) / end if / DeleteTree（3）串的操作void CopyStr（String &a,String b）/ 將串b的值賦給串a(chǎn)for（int i=0;bi!='0'i+） ai=bi;/ 將b數(shù)組中的值一個(gè)一個(gè)賦給aai='0'

22、/ CopyStrvoid CopyChar（String &a,char* b）/ 將字符串b的值賦給串a(chǎn)for（int i=0;*b!='0'b+,i+） ai=*b;ai='0' / CopyStrint CompareStr（String a,String b） / 串a(chǎn)和b從第一個(gè)字符開(kāi)始比較，直到出現(xiàn)第一個(gè)不相同的字符為止for（int i=0;ai!='0'&&bi!='0'i+）/ 如果a>b,return >0;if（ai!=bi） return ai-bi;/ 如果a<

23、b,return <0;if（ai!='0'） return 1;/ 如果a=b,return =0;else if（bi!='0'） return -1;else return 0; / CompareStr（4）棧的基本操作void InitialStack（Stack &s）/ 初始化空棧s=new SNode;/ 新建一個(gè)棧頭節(jié)點(diǎn)s->next=NULL;/ 頭節(jié)點(diǎn)指向空 / InitialStackvoid Push（Stack &s,SElemType e）/ 將元素e插入鏈?zhǔn)綏Ｖ?，成為新的棧頂元素p=new SNode;

24、/ 為新的棧頂元素分配空間CopyStr（p->data,e）;/ 將e的值賦給新節(jié)點(diǎn)數(shù)據(jù)域p->next=s->next;/ 插入新的棧頂元素s->next=p;/ 修改棧頂指針 / Pushvoid Pop（Stack &s,SElemType &e） / 若棧為空則給出相應(yīng)的信息，若不空則刪除棧頂元素并將其值賦給e if（!s->next） cout<<"空棧!"<<endl;/ ?？?，給出信息CopyStr（e,s->next->data）;/ 取出棧頂元素的值賦給ep=s->n

25、ext;/ 刪除棧頂元素s->next=p->next; delete p;/ 釋放空間 / Popvoid GetTop（Stack& s,SElemType &e） / 將棧頂元素的值賦給e，但不刪除棧頂元素if（!s->next）cout<<"空棧!"<<endl;else CopyStr（e,s->next->data）; / GetTopvoid DeleteStack（Stack &s）/ 將棧的鏈表節(jié)點(diǎn)一個(gè)一個(gè)刪掉while（s->next!=NULL）p=s->next

26、;s->next=p->next ;delete p; / end whiledelete s; / DeleteStack（5）文件的操作void Save（Tree T,FILE *fp） / 用遞歸算法先序遍歷樹(shù)，為每一個(gè)節(jié)點(diǎn)建立一個(gè)對(duì)應(yīng)的文件節(jié)點(diǎn)。/ 文件節(jié)點(diǎn)的數(shù)據(jù)域存儲(chǔ)和樹(shù)節(jié)點(diǎn)相同的數(shù)據(jù)，/ 文件節(jié)點(diǎn)的左右標(biāo)志域分別表示樹(shù)節(jié)點(diǎn)是否有孩子或兄弟if（T）f=new FileNode;/ 建立新的文件節(jié)點(diǎn)CopyStr（f->data,T->data）;/ 將樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域賦給文件節(jié)點(diǎn)數(shù)據(jù)域f->ltag=（T->firstchild=NULL?0:1

27、）;/ 給文件節(jié)點(diǎn)左標(biāo)志賦值：0表示無(wú)孩子節(jié)點(diǎn)f->rtag=（T->nextsibling=NULL?0:1）;/ 給文件節(jié)點(diǎn)右標(biāo)志賦值：0表示無(wú)兄弟節(jié)點(diǎn)CopyStr（f->IP,T->IP）; if（fwrite（f,sizeof（struct FileNode）,1,fp）!=1）cout<<"無(wú)法打開(kāi)文件!"<<endl;/ 將文件節(jié)點(diǎn)的值寫(xiě)入磁盤(pán)delete f; Save（T->firstchild,fp）;/ 將左孩子樹(shù)保存入文件Save（T->nextsibling,fp）;/將右兄弟子樹(shù)保存文件

28、 / end if / Save（6）主函數(shù)Main（）a=getchar（）;/ 用戶輸入選擇switch（a）case '1': / 1表示輸入域名和IP建立樹(shù)if（!（fp=fopen（"Internet","wb"） cout<<"無(wú)法打開(kāi)文件!"<<endl;/ 打開(kāi)文件InitialTree（T）;/ 初始化建立樹(shù)Save（T,fp）;/ 將樹(shù)以文件形式保存fclose（fp）;DeleteTree（T）;/ 刪除樹(shù)break;case '2':/ 2表示將用戶輸入的

29、新域名和IP插入已有樹(shù)中if（fp=fopen（"Internet","rb"）=NULL） cout<<"無(wú)法打開(kāi)文件!"<<endl;/ 打開(kāi)文件并讀取CreateTree（T,fp）;/ 從文件讀取數(shù)據(jù)建立樹(shù)fclose（fp）;/ 關(guān)閉文件if（!（fp=fopen（"Internet","wb"） cout<<"無(wú)法打開(kāi)文件!"<<endl;/ 打開(kāi)文件并寫(xiě)入Insert（T）;/ 將新的域名IP插入Save（T,fp

30、）;/ 將新的樹(shù)保存到文件中fclose（fp）;/ 關(guān)閉文件break;case '3':/ 3表示查詢用戶輸入的域名相應(yīng)得IPif（fp=fopen（"Internet","rb"）=NULL） cout<<"無(wú)法打開(kāi)文件!"<<endl;/ 打開(kāi)并讀取文件CreateTree（T,fp）;/ 根據(jù)文件建立樹(shù)fclose（fp）;/ 關(guān)閉文件do cout<<"輸入你想搜索的域名（請(qǐng)注意大小寫(xiě)）:"<<endl;webside=CreateWeb（

31、）;/ 建立域名樹(shù)鏈Search（T,webside,p）;/ 查找域名if（p->firstchild=NULL&&webside->next=NULL） cout<<p->IP<<endl;else cout<<"無(wú)法找到服務(wù)器或DNS錯(cuò)誤!"<<endl;cout<<"是否繼續(xù)查詢? y/n"<<endl;a=getchar（）;getchar（）; while（a='y'）;if（a='n'） control=

32、0;DeleteTree（T）;break;case '4': default:/ 4表示退出,其他的也退出control=0;break; / end switch / main四、調(diào)試分析1）基本操作算法的時(shí)間復(fù)雜度通過(guò)用戶輸入域名建立域名鏈表的函數(shù)CreateWeb是將域名按 '.' 分開(kāi)入棧，時(shí)間復(fù)雜度為O(m），m是域名分的m個(gè)串。通過(guò)域名查詢IP的函數(shù)Search是一個(gè)遞歸函數(shù)，通過(guò)和每個(gè)節(jié)點(diǎn)比較來(lái)搜索，由于樹(shù)的同一層節(jié)點(diǎn)是升序排列的，所以一旦比較到域名比樹(shù)節(jié)點(diǎn)小就退遞歸，因此可以節(jié)省時(shí)間，一般的時(shí)間復(fù)雜度為O(h），h為樹(shù)高。但最壞時(shí)要把每個(gè)樹(shù)節(jié)點(diǎn)

33、都遍歷一遍。（2）樹(shù)的操作算法的時(shí)間復(fù)雜度構(gòu)造域名樹(shù)鏈的算法CreateChild由用戶輸入網(wǎng)站域名，建立每個(gè)域名的樹(shù)鏈?zhǔn)且粋€(gè)遞歸函數(shù)，通過(guò)先序遍歷樹(shù)的時(shí)間復(fù)雜度為O(n），n為域名長(zhǎng)，比如域名的域名長(zhǎng)是3。構(gòu)造樹(shù)的算法InitialTree把域名樹(shù)鏈插入樹(shù)中的相應(yīng)位置，主要操作是插入算法Insert：若域名節(jié)點(diǎn)比樹(shù)中要插入的那一層節(jié)點(diǎn)都小則時(shí)間復(fù)雜度為O(1），比如與比較之后應(yīng)該插在edu為根的樹(shù)下，cau比pku小則完成前插操作。若域名節(jié)點(diǎn)最大則時(shí)間復(fù)雜度是O(n），n是兄弟鏈的長(zhǎng)度。從文件中讀取數(shù)據(jù)并且建立樹(shù)的算法CreateTree是一個(gè)遞歸函數(shù)，主要操作是通過(guò)先序遍歷樹(shù)讀取文件建立樹(shù)

34、的節(jié)點(diǎn)；算法DeleteTree是一個(gè)遞歸刪除樹(shù)的節(jié)點(diǎn)的函數(shù)，這兩個(gè)算法的時(shí)間復(fù)雜度均為O(h），h為樹(shù)高。（3）串的操作算法的時(shí)間復(fù)雜度串賦值算法CopyStr和CopyChar的時(shí)間復(fù)雜度都是O(k），k是串或字符串長(zhǎng)。（4）棧的操作算法的時(shí)間復(fù)雜度初始化棧的算法InitialStack，入棧算法Push，取棧頂元素值的算法GetTop，出棧算法Pop的時(shí)間復(fù)雜度均為O(1）。刪除算法DeleteStack的主要功能是將棧鏈表的節(jié)點(diǎn)一個(gè)一個(gè)刪除，時(shí)間復(fù)雜度為O(n），n為鏈表的長(zhǎng)度。（5）文件操作算法的時(shí)間復(fù)雜度建立文件的算法Save是一個(gè)遞歸函數(shù)，通過(guò)先序遍歷樹(shù)存入文件，主要操作是建立文

35、件節(jié)點(diǎn)并存儲(chǔ)，時(shí)間復(fù)雜度為O(h），h為樹(shù)高。（6）算法的空間復(fù)雜度由于InitialTree、Save、CreateTree、Search、DeleteTree都是遞歸函數(shù)，所以都要設(shè)棧。因此空間復(fù)雜度是O(h），h是樹(shù)高。五、使用說(shuō)明第一次程序運(yùn)行后，用戶根據(jù)提示輸入站點(diǎn)域名和IP，用“回車鍵”作為間隔，程序?qū)⒔?shù)節(jié)點(diǎn)，并存入文件。若是用戶輸入了重復(fù)的IP，或是用戶輸入了不合法的域名，程序會(huì)給出相應(yīng)的提示：（1）用戶可以選擇插入新的域名IP，或是查詢。（2）用戶根據(jù)提示來(lái)輸入要查詢的站點(diǎn)域名，若此站點(diǎn)在樹(shù)中存在程序?qū)⑤敵鯥P，若沒(méi)有則輸出相應(yīng)的出錯(cuò)信息。 六、測(cè)試結(jié)果（1）建立樹(shù)輸入 域

36、 名IP域 名IP5568924038553S（提示出錯(cuò)）04903002591731216311210

37、.32.0.93704319733401（2）搜索 輸入：輸出：9輸入：輸出：無(wú)法找到服務(wù)器或DNS錯(cuò)誤！七、附錄（1）define.h#include <stdio.h>#include <iostream>#define MAXSIZE 400#define ElemType String#define SElemType Stringusing namespace std;/*

38、-typedef-*/typedef unsigned char String30;/ 存放域名和IP的串結(jié)構(gòu)typedef struct TreeNode / 樹(shù)的節(jié)點(diǎn) ElemType data,IP;/ 數(shù)據(jù)域（用來(lái)放域名）和IP域（用來(lái)放IP） struct TreeNode *firstchild,*nextsibling;/ 指向孩子和兄弟的指針/ 兄弟表示同一層，孩子表示下一層 TreeNode,*Tree;typedef struct FileNode / 存入文件的節(jié)點(diǎn) ElemType data,IP;/ 數(shù)據(jù)域（用來(lái)放域名）和IP域（用來(lái)放IP） int ltag,rta

39、g;/ 左右標(biāo)志域：0表示無(wú)孩子，1表示有孩子 FileNode;typedef struct SNode / 用戶輸入的域名存在棧節(jié)點(diǎn) SElemType data;/ 數(shù)據(jù)域，用來(lái)存放域名被'.'分開(kāi)的一部分 struct SNode *next;/ 指針域，指向域名下一部分 SNode,*Stack;/*-Tree-*/void InitialTree(Tree&);/ 第一次構(gòu)建樹(shù)void CreateTree(Tree&,FILE*);/ 從文件中讀取數(shù)據(jù)建立樹(shù)void CreateChild(Tree &T,Stack &websid

40、e);void DeleteTree(Tree&);/*-String-*/int CompareStr(String,String);/ 比較兩個(gè)串的大小void CopyStr(String&,String);/ 將一個(gè)串的值賦給另一個(gè)void CopyChar(String&,char*);/ 將以個(gè)字符串的值賦給一個(gè)串void DeleteString(String&);/*-Stack-*/void InitialStack(Stack&);/ 初始化棧void Push(Stack&,SElemType);/ 入棧操作void Pop

41、(Stack&,SElemType&);/ 出棧操作void GetTop(Stack&,SElemType&);/ 取棧頭節(jié)點(diǎn)的值void DeleteStack(Stack&);/*-FileNode-*/void Save(Tree,FILE*);/ 先序遍歷樹(shù)并存儲(chǔ)文件Stack CreateWeb();/ 創(chuàng)建用戶輸入域名的鏈表void Search(Tree,Stack&,Tree&);/ 搜索域名的IPvoid Insert(Tree&);/*end of define.h*/(2)function.h#includ

42、e <stdio.h>#include <iostream>#include "define.h"using namespace std;/*-String-*/void CopyStr(String &a,String b) int i;/ 將串b的值賦給串a(chǎn) for( i=0; bi!='0' i+) ai=bi; ai='0'void CopyChar(String &a, const char* b) int i;/ 將字符串b的值賦給串a(chǎn) for( i=0; *b!='0' b

43、+,i+) ai=*b; ai='0'int CompareStr(String a,String b) int i;/ 比較串a(chǎn),b for( i=0; ai!='0'&&bi!='0' i+)/ 如果a>b,return >0; if(ai!=bi)return ai-bi;/ 如果a<b,return <0; if(ai!='0') return 1;/ 如果a=b,return =0; else if(bi!='0')return -1; else return 0;

44、void DeleteString(String s)/ 銷毀串 delete s;/*-Tree-*/void CreateChild(Tree &T,Stack &webside)/ 用戶輸入一個(gè)網(wǎng)址域名，域名已經(jīng)別輸入到棧中，為域名建立相應(yīng)的域名樹(shù) String s; if(webside->next!=NULL) Tree t=new TreeNode;/ 新開(kāi)一個(gè)節(jié)點(diǎn) Pop(webside,s);/ 從棧中取出域名第一部分 CopyStr(t->data,s);/ 把第一部分賦值給樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域 t->firstchild=t->nextsi

45、bling=NULL;/ 把樹(shù)節(jié)點(diǎn)的孩子和兄弟鏈域暫置空 t->IP0='0'/ 把樹(shù)節(jié)點(diǎn)的IP域置0 T->firstchild=t;/ 讓根節(jié)點(diǎn)的孩子域指向新建的樹(shù)節(jié)點(diǎn) CreateChild(t,webside);/ 以此樹(shù)節(jié)點(diǎn)為根建立新的樹(shù)節(jié)點(diǎn)，/ 直到把域名全部賦值到樹(shù)節(jié)點(diǎn)中去 if(t->firstchild=NULL) cout<<"請(qǐng)輸入域名IP"<<endl;/ 若是葉子節(jié)點(diǎn)則要求用戶輸入IP cin>>t->IP; void Insert(Tree &T) Stack w

46、ebside; Tree t,q,p=NULL; String s; char ch;/int control=1; do cout<<"請(qǐng)輸入站點(diǎn)域名:"<<endl; webside=CreateWeb();/ 為用戶輸入的域名建立鏈表?xiàng)?Search(T,webside,p);/ 在樹(shù)中查找與域名節(jié)點(diǎn)相同的節(jié)點(diǎn)，/ 每一部分查找相匹配的樹(shù)節(jié)點(diǎn)，返回指向/ 最后一個(gè)與域名節(jié)點(diǎn)相同的樹(shù)節(jié)點(diǎn)的指針 if(p->firstchild=NULL) if(p->IP0!='0'&&webside->next

47、=NULL) cout<<"你輸入了重復(fù)的域名"<<endl; else CreateChild(p,webside); / 如果這個(gè)樹(shù)節(jié)點(diǎn)沒(méi)有孩子，則直接把新的域名建立成新樹(shù)，并讓這個(gè)樹(shù)節(jié)點(diǎn)的孩子域/ 指向次新開(kāi)的域名樹(shù)，即將域名節(jié)點(diǎn)作為此樹(shù)節(jié)點(diǎn)的第一個(gè)孩子 else if(webside->next=NULL) cout<<"你輸入了錯(cuò)誤的域名!"<<endl; else GetTop(webside,s);/ 如果這個(gè)樹(shù)節(jié)點(diǎn)有孩子，則在他的孩子的兄弟中/ 找到新開(kāi)域名樹(shù)應(yīng)該插入的位置，將其插入

48、t=p->firstchild; int a=CompareStr(t->data,s);/ 比較域名與已經(jīng)存在的兄弟節(jié)點(diǎn) if(a>0) CreateChild(p,webside);/ 若域名比兄弟節(jié)點(diǎn)小，則前插 p->firstchild->nextsibling=t; else while(t->nextsibling!=NULL&&(a=CompareStr(t->nextsibling->data,s)<0) t=t->nextsibling;/ 若域名比兄弟節(jié)點(diǎn)大，則后插 q=new TreeNode;

49、Pop(webside,s); CopyStr(q->data,s); q->firstchild=NULL; q->IP0='0' q->nextsibling=t->nextsibling; t->nextsibling=q; CreateChild(q,webside); DeleteStack(webside); cout<<"是否要繼續(xù)輸入新域名?（y/n）"<<endl; ch=getchar(); getchar(); while(ch='y');void InitialTree(Tree &T)/ 第一次由用戶輸入網(wǎng)站域名和IP，建立節(jié)點(diǎn)有序的樹(shù) T=new TreeNode;/ 新開(kāi)一個(gè)樹(shù)節(jié)點(diǎn) CopyChar(T->data,"root");/ 建立樹(shù)的根節(jié)點(diǎn) T->firstchild=T->nextsibling=NULL; T->IP0='0' Insert(T);/