1、西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法 B 上機(jī)實習(xí)第一次2012-10-7線性鏈表、刪除、輸出第二次2012-10-25求二叉樹路徑第三次2012-11-8排序算法以及檢索、索引第四次2012-12-12圖的鄰接陣表示和 DFS 生成樹輸出人：班級：信息 14學(xué)號：2110502076第一次上機(jī)實驗一、 上機(jī)實驗題目針對線性表、棧、隊列，編程實現(xiàn)選擇順序和鏈?zhǔn)浇Y(jié)構(gòu)下數(shù)據(jù)結(jié)構(gòu)建立、元素、刪除等基本操作，并演示實際例子運行結(jié)果。二、相關(guān)技術(shù)或知識主要依靠類和鏈表實現(xiàn)對對象的處理，并通過對子函數(shù)的調(diào)用實現(xiàn)各子功能，例如性表中和刪除元素，棧的出入棧操作和隊列的進(jìn)隊出隊操作。三、算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計線性表及棧和隊列

2、的實現(xiàn)設(shè)線性表采用帶表頭附加結(jié)點的單鏈表結(jié)構(gòu)，請編寫線性表抽象數(shù)據(jù)類型各基本操作的實現(xiàn)函數(shù)，并存放在頭文件 LinkList.h 中（注：上為不帶表頭附加結(jié)點）。同時建立一個驗證操作實現(xiàn)的主函數(shù)文件 test5.cpp，編譯并調(diào)試程序，直到正確運行。提示： 單向鏈表的structLNode結(jié)構(gòu)可定義如下：/ 定義單鏈表節(jié)點類型存放結(jié)點中的數(shù)據(jù)信息/ 指示下一個結(jié)點地址的指針ElemTypedata; LNode*next;/線性表基本操作可包括如下一些：void InitList (LNode *&H)單鏈表初始化單鏈表 void ClearList(LNode *&H)除單鏈表/初始化單鏈表

3、初始化單鏈表初始化/清除單鏈表清除單鏈表清除單鏈表清LengthList (LNode *H)/求單鏈表長度求單鏈表長度求單鏈表長度求單鏈表長度 bool EmptyList (LNode *H)/判斷單鏈表是否為空表判斷單鏈表是否為空表判斷單鏈表是否為空表判斷單鏈表是否為空表 ElemType GetList (LNode *H,)/取單鏈表第取單鏈表第取單鏈表第取單鏈表第的元素位置上的元素位置上的元素位置上的元素位置上 void TraverseList(LNode *H)/遍歷單鏈表遍歷單鏈表遍歷單鏈表遍歷單鏈表 bool InsertList ( LNode *&H, ElemType

4、 item,) /向單鏈表一個元素向單鏈表一個元素一個元素向單鏈表一個元素向單鏈表 bool Deleist ( LNode *&H, ElemType &item,) /從單鏈表中刪除一個元素從單鏈表中刪除一個元素從單鏈表中刪除一個元素從單鏈表中刪除一個元素 帶表頭附加結(jié)點的單鏈表初始化操作的實現(xiàn)可參考如下：void InitList(LNode *&H) /構(gòu)造一個空的線性鏈表 H，即為鏈表設(shè)置一個頭結(jié)點， /頭結(jié)點的 data 數(shù)據(jù)域不賦任何值，頭結(jié)點的指針域 next則為空四、上機(jī)環(huán)境和使用語言上機(jī)環(huán)境：VC 6.0使用語言： C 和 C+五、源程序和運行結(jié)果順序表的實現(xiàn)：源程序：#i

5、ncludeusing namespaOVERFLOW=-2; ERROR=0; OK=1;j;td;/-順序表的結(jié)構(gòu)-#define MAXSIZE 10/當(dāng)前順序表可能達(dá)到的最大長度 #define LISTINCREMENT 5typedeftypedefElemType;Sus;typedef structElemType *elem;/空間的址length;/當(dāng)前長度,表中有多少個元素listsize;SqList;初始化/Sus InitList_Sq(SqList &L)/構(gòu)造一個空的順序表 LL.elem=new ElemTypeMAXSIZE;/為順序表分配一個大小為 MAX

6、SIZE 的數(shù)組空間if(!L.elem)exit(OVERFLOW);/空間分配失敗L.listsize=MAXSIZE;L.length=0;/空表的長度為 0 return OK;建立/Sus Build_Sq(SqList &L)i,n;cout請輸入要建立的順序表的中元素的個數(shù)：n;if(nMAXSIZE)/如果 n 的值大于當(dāng)前空間L.elem=new ElemTypen+LISTINCREMENT;if(!L.elem)exit(OVERFLOW);L.listsize=n+LISTINCREMENT;cout請輸入這 n 個元素：endl; for(i=0;iL.elemi;

7、L.length=n;return OK;查找/LocateElem_Sq(SqList L,ElemType e)for(i=0;iL.length;i+)if(L.elemi=e)return i+1; return 0;/Sus ListInsert_Sq(SqList &L,i,ElemType e)/在順序表L 中的第 i 個位置之前新的元素 e/i 值的合法范圍是 1=i=L.length+1 if(iL.length+1)return ERROR;/i 值不合法if(L.length=MAXSIZE)return ERROR;/當(dāng)前空間已滿for(j=L.length-1;j=i

8、-1;j-)L.elemj+1=L.elemj;/位置及之后的元素后移L.elemi-1=e;/將新元素 e 放入第 i 個位置+L.length;/表長增 1 return OK;刪除第 i 個元素/Sus ListDelete_Sq(SqList &L,i,ElemType &e)/在順序表L 中刪除第 i 個元素，并用 e 返回其值/i 的值的合法范圍是 1=i=L.length if(iL.length)return ERROR;e=L.elemi-1;/將欲刪除的元素保留在 e 中for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj;-L.length

9、;return OK;刪除值為 e 的結(jié)點/Sus ListDel_Sq(SqList &L,e)j;temp=0;for(i=0;iL.length;i+)if(L.elemi=e)j=i+1;for(k=j;k=L.length-1;j+) L.elemj-1=L.elemj;-L.length;i-;temp=1;if(temp=0)cout沒有該元素endl; return OK;主函數(shù)/main()choice=0;i; SqList L;ElemType e; InitList_Sq(L);cout選項：endl1、創(chuàng)建endl2、查找endl3、刪除endl4、endl5、退出e

10、ndlchoice; switch(choice)case 1:Build_Sq(L); break;case 2:n;coute; n=LocateElem_Sq(L,e);cout該元素的位置：nendl; break;case 3:choice1;cout1、刪除第 i 個元素endl2、刪除元素為 e 的元素endlchoice1; switch(choice1)case 1:couti;ListDelete_Sq();coute被刪除endl; break;case 2:coute; ListDel_Sq(L,e);coute被刪除endl; break;default:break;

11、break;case 4:couti;coute;ListInsert_Sq();break;case 5:return 0; default:break;cout請選擇：;return 0;運行結(jié)果為;鏈表的實現(xiàn)：源程序：#include stdio.h#include #includetypedef struct Nodedata;struct Node*next;node;node*creat_list(num);void pr_list(node*head);node*add_list(node*head, delete_list(node*head, length(node*head

12、); insert_list(node*head, update_list(node*head,n);i);a,e);a,e);void main()t,k,m,f,a,e,s;node *head=NULL;pr pr pr pr pr pr pr prprf(-鏈表操作n);f(-1.創(chuàng)建新鏈表n);f(-2.后續(xù)增加新節(jié)點n);f(-3.刪除節(jié)點n);f(-4.鏈表長度n);f(-5.顯示鏈表n);f(6.新節(jié)點n);f(-7.修改節(jié)點n);f(8.退出n);lable:prf(請選擇:n); t=0;scanf(%d,&t);switch(t)case 1:prf(請輸入新鏈表的長度:

13、n);scanf(%d,&k);head=creat_list(k);prf(OK！新鏈表創(chuàng)建成功！n);break;case 2:prf(請輸入新增加節(jié)點的個數(shù):n);scanf(%d,&m);head=add_list(head,m); if(head=NULL) prf(鏈表為空,請先創(chuàng)建鏈表！n);break;elseprf(OK!新節(jié)點添加成功！n);break;case 3:prf(請輸入要刪除的節(jié)點位置:n);scanf(%d,&f);s=delete_list(head,f); if(s=-1) prf(鏈表為空,請先創(chuàng)建鏈表！n);break;else if(s=0)prf(

14、輸入位置錯誤！n);break;elseif(s=2)/這種情況是把最后一個節(jié)點也刪掉了，所以要head=NULL;頭結(jié)點prf(刪除成功！n);break;elseprf(刪除成功！n);break;case 4:if(length(head)=0) prf(鏈表為空,請先創(chuàng)建鏈表！n);break;elseprf(鏈表長度為:%d n,length(head);break;pr_list(head);break;case 5:case 6:prf(請輸入你要節(jié)點的位置和節(jié)點值:n);scanf(%d%d,&a,&e);if(insert_list(head,a,e)=0) prf(鏈表為空

15、,請先創(chuàng)建鏈表！n);break;elseif(insert_list(head,a,e)=-1) prf(輸入位置錯誤！n);break;else prf(OK!成功！n);break;f(請輸入你要修改節(jié)點的位置和新節(jié)點值:n);case 7:prscanf(%d%d,&a,&e);if(update_list(head,a,e)=0) prf(鏈表為空,請先創(chuàng)建鏈表！n);break;elseif(update_list(head,a,e)=-1) prf(輸入位置錯誤！n);break;else prf(OK!修改成功！n);break;exit(0);case 8:default:p

16、rf(輸入有錯誤！);prf(請繼續(xù)操作! );goto lable;node*creat_list(num)node*head,*p,*q;p=(node*)malloc(sizeof(node);/創(chuàng)建頭結(jié)點p-data=0;p-next=NULL;he;/頭結(jié)點為零,不放數(shù)值while(num0)q=(node*)malloc(sizeof(node);prf(請輸入節(jié)點的值:);scanf(%d,&q-data);next=q;next=NULL; p=q;num-;return head;void pr_list(node*head)node*p;if (head=NULL)prel

17、sep=head;f(鏈表為空,請先創(chuàng)建鏈表！n);p=p-next;prf(鏈表如下:);while(p!=NULL)prf(%dt,p-data); p=p-next;prf(n);node*add_list(node*head,n)node*p,*q;if(head=NULL)return NULL;p=head;while(p-next!=NULL)p=p-next;while(n0)q=(node*)malloc(sizeof(node);prf(請輸入新節(jié)點的值:);scanf(%d,&q-data);next=q;next=NULL; p=q;n-;return head;del

18、ete_list(node*head,i)node*p,*q;a; if(head=NULL) return -1;if(ilength(head)return 0;p=head;a=i-1; while(a0)p=p-next;a-; /p 指向了要刪除的前一個節(jié)點q=p-next;p-next=q-next; free(q);/刪除后如果都沒有了節(jié)點，把頭結(jié)點也if(length(head)=0)free(head);return 2;return 1;length(node*head)node *p;n=0;if(head=NULL) return 0;p=head;while(p-ne

19、xt!=NULL)p=p-next;n+;return n;insert_list(node*head,node*p,*q; if(head=NULL) return 0;else if(alength(head) return -1;else p=head; a=a-1;while(a0)a,e)p=p-next;a-;q=(node*)malloc(sizeof(node); q-data =e;q-next =p-next ; p-next =q;return 1;update_list(node*head,a,e)node*p;if(head=NULL) return 0;else i

20、f(alength(head) return -1;else p=head; while(a0) p=p-next ; a-;p-data=e; return 1;運行結(jié)果為：順序棧的實現(xiàn);源程序：#include #include #defineMAXSIZE 100using namespatd;struct Datapublic:bookNumMAXSIZE;sictop ;Data:top = 0;/順序棧的初始化 Data* SeqStackInit()Data *s = new Data; s-top = -1;return s;/順序棧的判空 SeqStackEmpty(Data

21、* s)if (-1 = s-top)return true;elsereturn false;/順序棧的入棧void SeqStackPush(Data* s,if (MAXSIZE-1) = s-top)x)cout 棧滿！top+;s-bookNums-top = x;cout入棧元素：bookNums-toptop)cout ?？?！bookNums-top;cout 出棧元素：bookNums-toptop-;return x;/順序棧中取出棧頂元素 SeqStackGetTop(Data* s)if (-1 != s-top)return s-bookNums-top;/順序棧的長度

22、 SeqStackLength(Data* s)top1 = s-top; length = 0;while(-1 != top1)length+; top1-;return length;main()Data* s = SeqStackInit();cout 判空操作：SeqStackEmpty(s)endl; cout 入棧操作：endl;SeqStackPush(s,12);SeqStackPush(s,23); SeqStackPush(s,4); SeqStackPush(s,78); SeqStackPush(s,3);cout 棧頂元素：SeqStackGetTop(s)endl

23、; cout 棧的長度：SeqStackLength(s)endl; cout 出棧操作：endl;SeqStackPop(s);cout 判空操作：SeqStackEmpty(s)endl; cout 棧頂元素：SeqStackGetTop(s)endl; return 0;運行結(jié)果為;鏈?zhǔn)綏５膶崿F(xiàn);源程序：/* * * * * * * * * * * * * * * * * * * * * * * * *:鏈?zhǔn)蕉褩?初始化,入棧,出棧,取棧頂元素/*PROGRAM/*CONTENT*/* * * * * * * * * * * * * * * * * * * * * * * * *#inc

24、lude #include #include #include enum BOOLFalse,True; typedef struct Lnodechardata;struct Lnode *next;LNode,*LPo;/定義節(jié)點結(jié)構(gòu)/數(shù)據(jù)域/后向指針void initial(LPo&);/初始化一個堆棧 voidpush_linkstack(LPo&,char);BOOL pop_linkstack(LPo&,char &);/將一個元素入棧/將一個元素出棧void pr_linkstack(LPo); /顯示棧中所有元素 void main()LPols,p;char ch,j;fla

25、g=1; BOOL temp;prf(本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的堆棧操作。n); prf(鏈?zhǔn)蕉褩２粫a(chǎn)生溢出問題。n);prf(可以進(jìn)行入棧，出棧，取棧頂元素等操作。n);/初始化堆棧 Sinitial(ls);while(flag) prf(請選擇:n);prf(1.顯示棧中所有元素n);prf(2.入棧prf(3.出棧prf(4.退出程序 scanf( %c,&j);switch(j)n);n);n);case 1:pr_linkstack(ls);break;case 2:prf(請輸入要入棧的元素(一個字符):); scanf( %c,&ch);/輸入要入棧的字符 push_linksta

26、ck(ls,ch);/入棧pr_linkstack(ls); break;case 3:temp=pop_linkstack(ls,ch);/出棧 if(temp=True)prf(出棧一個元素:%cn,ch);/若棧不空，顯示出棧的元素 pr_linkstack(ls);else prf(堆棧已空!n);/否則堆棧為空 break;default:flag=0;prf(程序結(jié)束，按任意鍵退出!n);getch();void initial(LPo&pi)pi=NULL;/棧頂指針初始化為 NULLvoid push_linkstack(LPo&pi,char ch)/入棧，由于采用鏈?zhǔn)浇Y(jié)構(gòu)，

27、一般不會產(chǎn)生棧滿的情況LPopo;po=(LPo)malloc(sizeof(LNode);/生成一個新節(jié)點/賦值/新節(jié)點的后向指針指向原棧頂節(jié)點/站頂指針指向新節(jié)點po-dh;po-next=pi;pi=po;BOOL pop_linkstack(LPo&pi,char &e)/出棧，成功返回 True，并用 e 返回該元素值，失敗返回 FalseLPopo=pi;po;/棧頂指針指向下一個節(jié)點pi=po-next;if(po=NULL) return False;/棧已空 else e=po-data;return True;void pr_linkstack(LPo/顯示棧中所有元素p)

28、if(p=NULL) prf(堆棧已空!n);/棧為空 elseprf(堆棧所有元素:);while(p!=NULL)prf(%c ,p-data); p=p-next;prf(n);/否則顯示棧中所有元素運行結(jié)果為：順序隊列的實現(xiàn)：源程序：#include #include #include #define QueueSize 10typedefDaype;typedef structDaype dataQueueSize;front,rear;Seueue;void main()Seueue Q;Daype newelem;char ch;void InitQueue(Seueue *Q)

29、;QueueLength(Seueue Q);bool QueueEmpty(Seueue Q);bool QueueFull(Seueue Q);void EnQueue(Seueue *Q, Daype newelem);DaDaype DeQueue(Seueue *Q);ype GetHead(Seueue Q);ueue Q);void PrQueue(Sedo coutendl;*順序隊列功能菜單*endl;coutcout cout cout cout cout cout cout coutch;a：隊列初始化 c: 判空e：入隊列 g：取隊頭元素 i：z：退出b：求隊列長度 d

30、：判滿f：出隊列 h：j:*endl;*endl;*endl;*endl;*endl;*endl;*endl;請輸入你的選擇：;switch (ch)case a:InitQueue(&Q); Pr Queue(Q); break;case b:coutQueueLength(Q)endl;break; case c:if (QueueEmpty(Q)cout隊列為空！endl;elsecout隊列不為空！endl; break;case d:if (QueueFull(Q)cout隊列為滿！endl;elsecout隊列不為滿！endl; break;case e:coutnewelem;i

31、f (QueueFull(Q)cout隊列為滿！endl;elseEnQueue(&Q,newelem); PrQueue(Q);break; case f:if (QueueEmpty(Q)cout隊列為空！endl;elsecoutDeQueue(&Q)endl; PrQueue(Q);break; case g:if (QueueEmpty(Q)cout隊列為空！endl;elsecoutGetHead(Q)front=0;Q-rear=0;QueueLength(Seueue Q)return (Q.rear+QueueSize-Q.front)%QueueSize;bool Queu

32、eEmpty(Seueue Q)if (Q.rear=Q.front)return true;elsereturn false;bool QueueFull(Seueue Q)if (Q.rear+1)%QueueSize=Q.front)return true;elsereturn false;void EnQueue(Seueue *Q, Daype newelem)Q-dataQ-rear=newelem;Q-rear=(Q-rear+1)%QueueSize;Daype DeQueue(Seueue *Q)Q-front=(Q-front+1)%QueueSize;return Q-d

33、ata(Q-front+QueueSize-1)%QueueSize;Daype GetHead(Seueue Q)return Q.dataQ.front;void PrQueue(Sei;ueue Q)cout從隊頭到隊尾數(shù)據(jù)元素依次為： ; for (i=Q.front; i!=Q.rear;i=(i+1)%QueueSize)coutQ.datai;coutendl;運行結(jié)果為：鏈?zhǔn)疥犃械膶崿F(xiàn);源程序：#include using namespatd;constSIZE=50;claodepublic:Node()pre=NULL;next=NULL;value;Node *pre;N

34、ode *next;class PQueuepublic:PQueue();bool empty() const;bool full() const;void pop();void push(p);size() const;Node * top();void display();private:Node *front,*back;count;PQueue:PQueue()front=NULL;back=NULL;count=0;bool PQueue:empty() constif(front=NULL)return true;elsereturn false;void PQueue:pop(

35、)if(empty()cout隊列為空！next;t-pre=NULL;front=t;elsep-pre-next=p-next;p-next-pre = p-pre;count-;void PQueue:push(p)if(empty()Node *newNode1=new Node();newNode1-value=p;front=newNode1;Node *newNode2=new Node();newNode2-pre=front;back=newNode2;front-next=newNode2;count+;elseNode *newNode=new Node();back-v

36、alue=p;newNode-pre=back;back-next=newNode;back=newNode;count+;PQueue: size() constreturn count;Node * PQueue: top()Node *max=front;Node *temp=front;while(temp-next!=NULL)if(temp-valuemax-value)max=temp;temp=temp-next;return max;void PQueue:display()if(empty()cout隊列為空！next!=NULL)if(i+%5=0)coutendl;co

37、utvaluenext;coutendl;void main(void)PQueue q;t;cout選項：1.push;2.pop;3.display;while(1)cout請輸入選項：t;if(t=1)temp;prf(請輸入數(shù)據(jù)：);cintemp;q.push(temp);else if(t=2)q.pop();else if(t=3)q.display();elsecout請重新輸入：endl;運行結(jié)果為;六、上機(jī)總結(jié)通過這次的上機(jī)實驗，更加熟練的掌握了有關(guān)語言的使用，也對書中的知識有了進(jìn)一步透徹的了解。在第一部分的編程中，掌握了用類建立線性表、棧和隊列，學(xué)會了利用類中的子函數(shù)實現(xiàn)

38、在表中的進(jìn)一步熟練了對指針的使用。七、參考資料數(shù)據(jù)結(jié)構(gòu)與算法分析（C+版）（第二版）、刪除、查找等操作，并C+程序設(shè)計（第2版）第二次上機(jī)實驗一、上機(jī)實習(xí)題目編程實現(xiàn)二叉搜索樹的建立、中序遍歷、元素查找等功能，并演示實際例子的運行結(jié)果。編程實現(xiàn)二叉樹的建立（如先序序列作為輸入）、中序遍歷、層序遍歷、元素查找等功能，并演示實際例子的運行結(jié)果。二、相關(guān)知識或技術(shù)先要掌握二叉樹的建立和過程，并通過遞歸函數(shù)實現(xiàn)對其的三種周游，同時運用子函數(shù)求樹的高度、深度和葉子結(jié)點數(shù)。三、算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計在二叉排序樹中進(jìn)行查找的過程和二分查找類似，也是一個逐步縮小查找范圍的過程。若查找成功，則是走了一條從根結(jié)點到待

39、查結(jié)點的路徑；若查找失敗，則是走了一條根結(jié)點到某個葉子結(jié)點的路徑。因此，查找過程中和關(guān)鍵字比較的次數(shù)不超過樹的深度。由于含有 n 個結(jié)點的二叉排序樹不唯一，形態(tài)和深度可能不同。故含有 n 個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。最好的情況是：二叉排序樹和二叉判定樹形態(tài)相同。樹，這時的平均查找長度和順序查找時相同。的情況是： 二叉排序樹為單支情況示例就平均性能而言，二叉排序樹上的查找和二分查找相差不大，并且二叉排序樹上的分方便，無須大量移動結(jié)點。四、上機(jī)環(huán)境和使用語言上機(jī)環(huán)境：VC 6.0使用語言： C 和 C+五、源程序和實驗結(jié)果和刪除結(jié)點十1）源程序：#include using n

40、amespatd;/*/二叉樹結(jié)點類的定義 template struct BTNodeT data;BTNode * Lchild,*Rchild;BTNode(T nodeValue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ):data(nodeValue),Lchild(leftNode),Rchild(rightNode)數(shù)的默認(rèn)構(gòu)造函數(shù);/可選擇參/*/二叉樹的建立 template void createBBTNode* BTNode*ree(BTNode * &root)p = root;k;T nodeVal

41、ue ; cinnodeValue; if(nodeValue=-1)root=NULL;elseroot=new BTNode(); root-data = nodeValue;createBcreateBree(root-Lchild);ree(root-Rchild);/*/二叉樹的先序遍歷 template void preOrder( BTNode * & p)if(p)coutdataLchild);-Rchild);/*/二叉樹的中序遍歷 template void inOrder(BTNode * & p)if(p)inOrd-Lchild);coutdataRchild);/

42、*/二叉樹的后序遍歷 template void levelOrder(BTNode *& p)if(p)levelOrdlevelOrd-Lchild);-Rchild);coutdata ;/*/統(tǒng)計二叉樹中結(jié)點的個數(shù) templatecountNode(BTNode * & p)if(p = NULL) return 0;return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉樹的深度 templatedepth(BTNode *& p)if(p = NULL)return -1;h1 = depth(p-Lchild); h2 =

43、depth(p-Rchild);if(h1h2)return (h1+1); return h2+1;/*/二叉樹的消毀操作 templateBTNode* destroy(BTNode* p)叉樹中的各個結(jié)點if(p)/消毀函數(shù)，用來消毀二returnreturn deletedestroy(p-Lchild);destroy(p-Rchild); p;/*/主函數(shù)的設(shè)計 main ()BTNode * rootNode=NULL;choiced = 0; while(true)system(cls); coutnnn cout樹n;cout樹n;coutn;cout coutchoiced

44、;-主界面-nnn;2、先序遍歷二叉1、創(chuàng)建二叉樹3、中序遍歷二叉樹4、后序遍歷二叉5、統(tǒng)計結(jié)點總數(shù)6、查看樹深度7、消毀二叉樹請選擇操作：;0、退出nn;if(choiced =return 0;0)else if(choiced =system(cls);1)cout請輸入每個結(jié)點，回車確認(rèn)，并以-1 結(jié)束：n;createBree(rootNode );else if(choiced = 2)system(cls);cout先序遍歷二叉樹結(jié)果：n; preOrder(rootNode);coutendl;system(pause);else if(choiced = 3)system(c

45、ls);cout中序遍歷二叉樹結(jié)果：n; inOrder(rootNode);coutendl; system(pause);else if(choiced = 4)system(cls);cout后序遍歷二叉樹結(jié)果：n; levelOrder(rootNode); coutendl;system(pause);else if(choiced = 5)system(cls);count = countNode(rootNode);cout二叉樹中結(jié)點總數(shù)為countendl; system(pause);else if(choiced = 6)system(cls);dep = depth(r

46、ootNode);cout此二叉樹的深度為dependl; system(pause);else if(choiced = 7)system(cls);cout二叉樹已被消毀！n; destroy(rootNode); coutendl; system(pause);elsesystem(cls); coutnnnnnt 錯誤選擇！n;運行結(jié)果為：2）源程序：#include #include #defineN100 using namespatd;typedef struct NodeNode*lChild,*rChild; val;Node,*pNode;void initBiTree(p

47、Node&biTree,iniArr,len); void preOrdNode&biTree);void inOrdNode&biTree); void lastOrdNode&biTree);main()n;aN;/給定數(shù)組，這里假定元素的值都大于 0，0 表示空，大于 0表示存在該節(jié)點pNodebiTree biTree-lChild biTree-rChild=new Node; NULL; NULL;=memset(a,-1, cinn;N);for(i=0;iai; initBiTree(biTree, a,0);preOrder(biTree); inOrder(biTree);

48、 lastOrder(biTree);cin.get(); cin.get();while(1); return 0;void initBiTree(pNode&biTree,if(NULL=biTree)return;iniArr,)biTree-val= if(iniArr2*pNodeiniArr+1 0);temp=new Node;=temp;biTree-lChildelsebiTree-lChild=NULL;if(iniArr2*+2 0)pNodetemp=new Node;biTree-rChild=temp;elsebiTree-rChild=NULL;initBiTre

49、e(biTree-lChild, initBiTree(biTree-rChild,iniArr, iniArr,2*2*+1);+2);voidpreOrdNode&biTree)stackstack_biTree; stack_biTree.push(biTree); cout前序遍歷結(jié)果：n; while(!stack_biTree.empty()pNodetemp=stack_biTree.top();stack_biTree.pop(); if(NULL !=temp)coutvalrChild); stack_biTree.push(temp-lChild);coutendl;vo

50、idinOrdNode&biTree)stackstack_biTree; stack_biTree.push(biTree); coutlChild);temp=stack_biTree.top();stack_biTree.pop();/退棧,去掉 temp 為 NULL 的值if(!stack_biTree.empty()temp=stack_biTree.top();coutvalrChild);coutendl;voidlastOrdNode&biTree)if(biTree=NULL)coutERROR!endl; return;stack pNodetop= pNodechild

51、stack_biTree; NULL;=NULL;stack_biTree.push(biTree);coutlChild=NULL&top-rChild=NULL)coutvallChild=child)運行結(jié)果為：if(top-rChild!=NULL)stack_biTree.push(top-rChild);elsecoutvalrChild=child)coutvallChild!=NULL)stack_biTree.push(top-lChild); top=stack_biTree.top();coutendl;六、上機(jī)總結(jié)通過這次的上機(jī)實驗，更加熟練的掌握了有關(guān)語言的使用，也對

52、書中的知識有了進(jìn)一步透徹的了解。在這次的編程中，學(xué)會了利用二叉樹處理一些實際問題，學(xué)會了二叉樹的三種周游方式，也學(xué)會了利用二叉查找樹對元素進(jìn)行排序、刪除等操作，也學(xué)會了用進(jìn)行最優(yōu)二叉樹的建立。七、參考資料數(shù)據(jù)結(jié)構(gòu)與算法分析（C+版）（第二版）C+程序設(shè)計（第2版）第三次上機(jī)實驗一、 上機(jī)實習(xí)題目在 S排序、快速排序、歸并排序、堆排序等排序算法中選擇算法，編程實現(xiàn)相應(yīng)算法實現(xiàn)過程，并舉例演示算法各趟運行結(jié)果。二、相關(guān)知識或技術(shù)，主要是熟練掌握直接排序、折半排序、s排序、冒泡排序、選擇排序這幾種基礎(chǔ)的排序，進(jìn)一步實現(xiàn)快速排序、歸并排序、堆排序、基數(shù)排序；其中，快排與歸并均是利用分治法的想。三、算法

53、及數(shù)據(jù)結(jié)構(gòu)設(shè)計快速排序算法原理，而堆排則是利用的思快速排序是對冒泡排序的一種改進(jìn)。它的基本是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。堆排序算法原理n 個關(guān)鍵字序列 Kl，K2，Kn 稱為(Heap)，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))：(1) kiK2i 且 kiK2i+1 或(2)KiK2i 且 kiK2i+1(1i n) /ki 相當(dāng)于二叉樹的非葉結(jié)點，K2i 則是左孩子，k2i+1 是右孩子若將此序列所的向量 R1.n

54、看做是一棵完全二叉樹完全二叉樹完結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：全二叉樹完全二叉樹的堆排序利用了大根堆(或小根堆)堆頂?shù)年P(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的（1） 用大根堆排序的基本變得簡單。先將初始文件 R1.n建成一個大根堆,此堆為初始的無序區(qū) 再將關(guān)鍵字最大的R1(即堆頂)和無序區(qū)的最后一個Rn交換，由此得到新的無序區(qū) R1.n-1和有序區(qū) Rn，且滿足 R1.n-1.keysRn.key由于交換后新的根 R1可能堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū) R1.n-1調(diào)整為堆。然 后再次將 R1.n-1中關(guān)鍵字最大的R1和該區(qū)間的最后一個Rn-1交換，由

55、此得到新的無序區(qū) R1.n-2和有序區(qū) Rn- 1.n，且仍滿足關(guān)系 R1.n-2.keysRn-1.n.keys，同樣要將 R1.n-2調(diào)整為堆。直到無序區(qū)只有一個元素為止。四、上機(jī)環(huán)境和使用語言上機(jī)環(huán)境：VC 6.0使用語言： C 和 C+五、源程序和運行結(jié)果快速排序:源程序： /* 調(diào)用 Partition(R，low，high)時，對 Rlow.high做劃分，*/ Partition( i, j)RMAX;#define MAX 255#include while(ij) /* 從區(qū)間兩端交替向中間掃描，直至 i=j 為止 */while(i=pivot) /* pivot 相當(dāng)于在

56、位置 i 上 */j-;/* 從右向左掃描，查找第 1 個關(guān)鍵字小于 pivot.key 的Rj */if(ij) /* 表示找到的 Rj的關(guān)鍵字pivot.key*/Ri+=Rj; /* 相當(dāng)于交換 Ri和 Rj，交換后 i 指針加 1 */while(ij&Ri=pivot) /* pivot 相當(dāng)于在位置 j 上*/i+; /* 從左向右掃描，查找第 1 個關(guān)鍵字大于 pivot.key 的Ri */if(ipivot.key */Rj-=Ri; /* 相當(dāng)于交換 Ri和 Rj，交換后 j 指針減 1 */ /* endwhile */Ri=pivot; /* 基準(zhǔn)已被最后定位*/ret

57、urn i; /* end of partition*/ void Quick_Sort( low, high) /* 對 Rlow.high快速排序 */if(lowhigh)/* 僅當(dāng)區(qū)間長度大于 1 時才須排序 */pivot=Partition(low,high); /* 對 Rlow.high做劃分 */Quick_Sort(low,pivot-1); /* 對左區(qū)間遞歸排序 */Quick_Sort(pivot+1,high); /* 對右區(qū)間遞歸排序 */ /* end of Quick_Sort */ void main() puts(Please input total el

58、ement number of the sequence:);scanf(%d,&n);if(nMAX)prf(n must moren 0 and lessn %d.n,MAX);exit(0); i,n; pivot; /* 劃分后的基準(zhǔn)的位置 */ pivot=Ri; /* 用區(qū)間的第 1 個作為基準(zhǔn) */* 并返回基準(zhǔn)的位置 */運行結(jié)果:堆排序:源程序：/* * * * * * * * * * * * * * * * * * * * * * * */*PROGRAM :堆排序 *puts(n Press any key to quit.);prf(%4d,Ri);Quick_Sort

59、(1,n);puts(nThe sequence after quick_sort is:);for(i=1;i=n;i+)prf(%4d,Ri);puts(Please input the elements one by one:);for(i=1;i=n;i+)scanf(%d,&Ri);puts(The sequence you input is:);for(i=1;i=n;i+)/*CONTENT :堆排序 */* * * * * * * * * * * * * * * * * * * * * * * * #include #include #include #include #inc

60、lude #define MAXSIZE 20 /排序表的最大容量 typedef struct /定義排序表的結(jié)構(gòu)elemwordMAXSIZE; /數(shù)據(jù)元素關(guān)鍵字 length; /表中當(dāng)前元素的個數(shù)SqList;void InitialSqList(SqList&); /初始化排序表 void HeapSort(SqList &); /堆排序void HeapAdjust(SqList &,); /堆調(diào)整 void PrSqList(SqList); /顯示表中的所有元素 void main()SqList L; /表 L char j=y;程序說明/prf(本程序?qū)⒀菔径雅判虻牟僮?。n