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

1、院 系： 計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 計(jì)科 年 級(jí)： 2013 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 學(xué) 號(hào)： 201321091135 姓 名： 司少武 指導(dǎo)教師： 劉晶 2016年 6月12日實(shí)驗(yàn)一 線性結(jié)構(gòu)的基本操作和應(yīng)用實(shí)驗(yàn)?zāi)康募耙笠?、?shí)驗(yàn)?zāi)康模?、掌握線性表的結(jié)構(gòu)特點(diǎn)和實(shí)現(xiàn)方法，能夠編寫程序?qū)崿F(xiàn)線性表的基本操作：初始化，插入，刪除，查找，判空，求線性表長度等運(yùn)算。2、能夠掌握特殊線性表（棧和隊(duì)列）的結(jié)構(gòu)特點(diǎn)及其基本操作；3、能利用棧的特性進(jìn)行實(shí)際應(yīng)用。二、實(shí)驗(yàn)題目及要求：線性結(jié)構(gòu)部分共包含三個(gè)實(shí)驗(yàn)內(nèi)容：1、 用順序表或者鏈表實(shí)現(xiàn)線性表的基本操作：初始化，插入，刪除，查找，判空，求線性表長度。2、 線

2、性表的基本應(yīng)用：從以下兩個(gè)實(shí)驗(yàn)題目中任選一個(gè)實(shí)現(xiàn)：1） 利用線性表實(shí)現(xiàn)一元多項(xiàng)式的相加。2） 利用線性表實(shí)現(xiàn)約瑟夫環(huán)問題。3、 利用棧的基本操作，編寫程序?qū)崿F(xiàn)括號(hào)匹配問題：從鍵盤輸入一組括號(hào)，當(dāng)程序接收第一個(gè)左括號(hào)之后，期待與之匹配的右括號(hào)，如果等到的是另外一組括號(hào)的左一半則等待，若等到另外一個(gè)不匹配的右括號(hào)則程序結(jié)束并提示括號(hào)不匹配；若整個(gè)括號(hào)序列判斷完畢，但棧未空則表示仍有括號(hào)未配對(duì)，提示不匹配。否則提示匹配。三、實(shí)驗(yàn)報(bào)告書寫要求： 簡明清晰的寫出每個(gè)實(shí)驗(yàn)題目的算法步驟，可以混合使用自然語言、流程圖及偽代碼的方式，不能直接復(fù)制源程序。每個(gè)實(shí)驗(yàn)題目需要附上程序正確運(yùn)行結(jié)果的截圖。題目一 線性

3、表的基本操作算法步驟的簡要說明（流程圖或偽代碼）題目：用順序表或者鏈表實(shí)現(xiàn)線性表的基本操作：初始化，插入，刪除，查找，判空，求線性表長度。1. 算法思想：主要設(shè)計(jì)了一個(gè)包含數(shù)據(jù)和指針域的結(jié)點(diǎn)。 Data *next 主要思想：插入： 刪除： 1. 主函數(shù)int main() :初始化一個(gè)鏈表L，顯示菜單，主要語句：switch語句，while語句，goto語句。2. 創(chuàng)建并輸入鏈表數(shù)據(jù)linklist createlist（），在該函數(shù)中創(chuàng)建頭結(jié)點(diǎn)，并輸入結(jié)點(diǎn)上的數(shù)據(jù)。偽代碼：while（當(dāng)x!=00）p = new list;p->data = x;p->next = NULL;

4、 q->next = p;q = p;3. 顯示鏈表數(shù)據(jù)void show（linklist L）1） 先判斷是否是空表，再逐個(gè)尋找想要的元素。2） 主要代碼：while(p)cout<<p->data<<"t"p = p->next;4. 獲取鏈表長度int getlength(linklist L)1) 先判斷是否為空，再遍歷鏈表，算出鏈表長度。2) 主要代碼：while(p)p = p->next;length+;5. 獲取第i個(gè)元素int getdata(linklist L,int i)1）當(dāng)0<i<le

5、ngth時(shí)，遍歷鏈表，找到第i個(gè)元素。2）主要代碼：while(p&&j<i)j+;p = p->next;6. 改變鏈表數(shù)據(jù)int changedata(linklist L,int e,int d)1） 找到要修改的值e，再把d賦值給e.2)主要代碼：while(p&&p->data!=e)p = p->next;if(!p)return ERROR;p->data = d;7. 插入一個(gè)結(jié)點(diǎn)linklist insertlist(linklist L,int i,int e)1)因?yàn)橐迦氲趇個(gè)元素，所以要先找到第i-1個(gè)元素

6、，在i-1后面插入。2）主要代碼：s->data = e;s->next = p->next ;p->next = s;8. 刪除一個(gè)結(jié)點(diǎn)linklist deletelist(linklist L,int i)1）同插入差不多，先找到第i-1個(gè)元素，然后再把i-1結(jié)點(diǎn)指針域指向原本指向結(jié)點(diǎn)的下一個(gè)，把中間那個(gè)刪除，再free，釋放空間，主要代碼：q = p->next;p->next =q->next;free(q);實(shí)驗(yàn)截圖：心得體會(huì):源代碼：/*線性表的操作（單鏈表）*/#include<stdio.h>#include<std

7、lib.h>typedef struct LNodeint data; struct LNode *next;  LNode, *Linklist;/*線性表的結(jié)構(gòu)*/ /*基本操作函數(shù)*/*構(gòu)造空線性表。操作結(jié)果：構(gòu)造空線性表，如成功返回1，否則返回0。*/int InitList(Linklist L) L=(Linklist)malloc(sizeof(LNode);  if(L)   L->next=NULL; return 1;  else return 0;/*順序創(chuàng)建一個(gè)線性鏈表函數(shù)。當(dāng)輸入的結(jié)點(diǎn)的數(shù)據(jù)值為0

8、時(shí)，線性鏈表創(chuàng)建結(jié)束。返回線性表的頭結(jié)點(diǎn)指針。*/Linklist hrear_create() int x; Linklist head, p, rear; head=(Linklist)malloc(sizeof(LNode); head->data=0; rear=head; printf("請輸入線性表中的元素值，以0結(jié)束輸入:n"); scanf("%d",&x); while(x!=0) p=(Linklist)malloc(sizeof(LNode); p->data=x; rear->next=p; rear=p

9、; scanf("%d",&x);rear->next=NULL;return head;/*判斷鏈表是否為空。初始條件：線性表存在。操作結(jié)果：若線性表為空，返回1，否則返回0。*/int ListEmpty(Linklist L) if(L->next=NULL)return 1; else return 0; /*求線性鏈表的長度函數(shù)。初始條件：線性表存在。操作結(jié)果：返回線性表中數(shù)據(jù)元素的個(gè)數(shù)。*/int Listlength(Linklist L) Linklist p; int count=0; p=L; while(p->next!=NU

10、LL) p=p->next; count+; return count;/*確定元素e的位置。初始條件：線性表存在。操作結(jié)果：返回第一個(gè)與e相同的元素的位置；如果這樣的元素不存在，則返回0。*/int LocateElem(Linklist L,int e) Linklist p; int pos=1; p=L->next; while(p!=NULL) if(p->data!=e) p=p->next; pos+; else return pos; return 0;/*在第i個(gè)元素前插入元素。初始條件：線性表存在，且1<=i<=ListLength(L)

11、+1*。操作結(jié)果：在L中第i個(gè)位置之前插入新的元素e，插入成功返回1，否則返回0。*/int ListInsert(Linklist L, int i, int e) Linklist p,findpri;/*p用于申請空間，findpri用于找第i個(gè)節(jié)點(diǎn)的前驅(qū)*/ int j; if(1<=i)&&(i<=Listlength(L)+1)/*判斷i是否合法*/ p=(Linklist)malloc(sizeof(LNode); if(!p) return 0;/*判斷申請空間是否成功*/ else p->data=e; findpri=L; for(j=1;

12、j<i;j+) findpri=findpri->next; p->next=findpri->next; findpri->next=p; return 1; else return 0;/*刪除第i個(gè)結(jié)點(diǎn)，并將其數(shù)據(jù)元素作為返回值返回。初始條件：線性表非空且1<i<=ListLength(L)。操作結(jié)果：刪除第i個(gè)結(jié)點(diǎn)并將結(jié)點(diǎn)的數(shù)據(jù)域的值返回。*/int ListDelete(Linklist L,int i) Linklist p,q; int j=1,e; if(!ListEmpty(L) if(1<=i)&&(i<

13、=Listlength(L) p=L; while(j<i)p=p->next;j+; q=p->next; e=q->data; p->next=q->next; free (q); return e; else printf("i error!n");return 0; else printf("This is an empty list.n");return 0;/*銷毀線性鏈表。初始條件：線性表存在。操作結(jié)果：銷毀線性表并返回1。*/Linklist DestroyList(Linklist L) Linkli

14、st p,rear; rear=L->next; while(rear!=NULL) p=rear; L->next=rear->next; rear=rear->next; free (p); free (L);return NULL;/*此函數(shù)用于輸出創(chuàng)建的鏈表中的元素*/void ListOut(Linklist L) Linklist p; p=L->next; while(p!=NULL) printf("%d ",p->data); p=p->next; /*操作菜單*/void menu() int m; printf

15、(" 此程序用于實(shí)現(xiàn)線性表的相關(guān)基本操作n"); printf(" 1. 創(chuàng)建 2. 判空 3. 求長度n 4. 查找定位 5. 插入一個(gè)元素n 6. 刪除一個(gè)元素 7. 銷毀線性表");int main() char goon; int choice; Linklist List=NULL; int i,e,length,position; do menu(); printf("n請選擇測試函數(shù)序號(hào):"); scanf("%d",&choice); if(!List)&&(choice!=

16、1) printf("n線性表還沒被創(chuàng)建，請先創(chuàng)建線性表！"); goon='y' getchar(); continue; switch(choice) case 1: printf("n創(chuàng)建一個(gè)線性表為：n"); List=hrear_create(); if(List)ListOut(List); break; case 2: printf("n此程序?qū)⑴袛嘁粋€(gè)線性表是否為空n"); if(ListEmpty(List)printf("這是一個(gè)空的線性表.n");break; else pri

17、ntf("線性表非空，表中元素有: "); ListOut(List);break; case 3: if(List) printf("n此程序?qū)⑶笠粋€(gè)線性表的長度n"); printf("已創(chuàng)建線性表為：n");ListOut(List); length=Listlength(List); printf("length=%dn",length);break; else printf("失敗!n");break; case 4: if(List) printf("已創(chuàng)建線性表為：n&q

18、uot;);ListOut(List); printf("請輸入您需要查找定位的元素:n"); scanf("%d",&e); position=LocateElem(List,e); if(position) printf("position=%dn",position);break; else printf("線性表中沒有此元素!n");break; case 5: if(List) printf("n將在一個(gè)線性表中插入一個(gè)元素n"); printf("已創(chuàng)建線性表為：n

19、");ListOut(List); printf("請輸入您要插入的元素的位置i和值e:i,en"); scanf("%d,%d",&i,&e); if(ListInsert(List,i,e)printf("插入！ "); else printf("插入成功!n");break; else printf("空間不足!");break; ListOut(List);break; case 6: printf("n此程序?qū)⒃谝粋€(gè)線性表中刪除元素n");

20、if(List) printf("已創(chuàng)建線性表為：n");ListOut(List); printf("請輸入您需要?jiǎng)h除的元素的位置:n"); scanf("%d",&i); if(ListDelete(List,i)printf("刪除成功!n"); elseprintf("刪除失敗!n");break; else printf("空間不足!");break; ListOut(List);break; case 7: if(List) printf("一個(gè)

21、線性表已經(jīng)被創(chuàng)建!n");ListOut(List); printf("n此操作將銷毀已創(chuàng)建的線性表n"); if(!(List=DestroyList(List)printf("銷毀成功!n");break; else printf("銷毀失敗!n");break; default: printf("選擇錯(cuò)誤!n"); printf("n繼續(xù)測試?(Y/N):"); goon=getchar(); goon=getchar(); while(goon='y'|goon

22、='Y');return 1;題目二 線性表的基本應(yīng)用算法步驟的簡要說明（流程圖或偽代碼）  題目：線性表的基本應(yīng)用: 利用線性表實(shí)現(xiàn)約瑟夫環(huán)問題一、算法設(shè)計(jì)：1） 先在主函數(shù)中輸入幾個(gè)人和初始密碼 2） 按照單鏈表那樣先構(gòu)造一個(gè)單鏈表，給結(jié)點(diǎn)輸入元素，再把尾指針指向頭結(jié)點(diǎn)。3） 定義兩個(gè)指針，一個(gè)臨時(shí)指針和一個(gè)頭指針，當(dāng)臨時(shí)指針p和頭指針head不在同一個(gè)結(jié)點(diǎn)時(shí)，說明還剩下多個(gè)結(jié)點(diǎn)，寫一個(gè)for循環(huán)，找出第password個(gè)結(jié)點(diǎn)，用p->next = head->next將其刪除，并把值pasword保留下來，然后把head指向p的下個(gè)結(jié)點(diǎn)，直

23、到整個(gè)鏈表刪除完畢。2、 基本函數(shù)：1.主函數(shù)main()1）寫了do while循環(huán)，當(dāng)輸入y或者Y，繼續(xù)循環(huán)。2）主要代碼：dowhile(stop='y'|stop='Y');2. 創(chuàng)建循環(huán)鏈表linklist creatlist(int n)1） 先構(gòu)造兩個(gè)指針，頭指針head和臨時(shí)指針p,然后創(chuàng)造一個(gè)結(jié)點(diǎn)，把元素password和順序數(shù)i放入結(jié)點(diǎn)，再把p指向下一個(gè)結(jié)點(diǎn)，等快達(dá)到要求的個(gè)數(shù)n-1后，退出循環(huán)，輸入最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)，把尾指針指向頭結(jié)點(diǎn)。2） 主要代碼：for(i = 1;i<n;i+)p->i = i;cout<<

24、“請輸入第”<<i<<"號(hào)所帶密碼："<<endl;cin>>pass; p->password = pass;p->next = new list;p = p->next;3. 約瑟夫環(huán)實(shí)現(xiàn)函數(shù)void josefuhuan(linklist head,int password)1) 構(gòu)造一個(gè)臨時(shí)指針，然后判斷該指針是否與頭指針指向同一處，如果指向同一處則退出循環(huán)，然后再來一個(gè)循環(huán)，尋找密碼，找到指令密碼所指，并將其刪除，把所刪除的密碼值留下來，作下一次的循環(huán)密碼。2) 主要代碼：for(i = 1;p!=

25、head;i+)for(j = 1;j<password;j+)p = head;head = head->next;p->next = head->next;實(shí)驗(yàn)結(jié)果： 圖1.進(jìn)入系統(tǒng)界面 圖2、輸入人數(shù)和上限值界面圖3、輸出結(jié)果界面心得體會(huì)：源代碼#include<iostream>using namespace std;typedef struct nodeint password;int i;node *next;list,*linklist;linklist creatlist(int n)/初始化鏈表并輸入鏈表數(shù)據(jù)list *head,*p;in

26、t i,pass;head = p = new list;for(i = 1;i<n;i+)p->i = i;cout<<"請輸入第"<<i<<"號(hào)所帶的密碼："<<endl;cin>>pass;p->password = pass;p->next = new list;p = p->next;p->i = i;cout<<"請輸入第"<<i<<"號(hào)所帶的密碼："<<end

27、l;cin>>pass;p->password = pass;p->next = head;return head;void josefuhuan(linklist head,int password)/約瑟夫環(huán)的實(shí)現(xiàn)int i,j;list *p;p = new list;for(i = 1;p!=head;i+)for(j = 1;j<password;j+)p = head;head = head->next;p->next = head->next;cout<<"n第"<<i<<&q

28、uot;個(gè)出局的編號(hào)是："<<head->i <<"號(hào)tt第"<<i<<"個(gè)的密碼是："<<head->password<<endl;password = head->password;delete head;head = p->next;i = head->password;j = head->i;cout<<"n第7個(gè)出局的編號(hào)是："<<j<<"號(hào)tt第7個(gè)的密碼是：&

29、quot;<<i<<endl<<endl;delete head;int main()/主函數(shù)int n,password;char stop;list *head;cout<<"+"<<endl;cout<<"+o歡迎來玩“約瑟夫環(huán)”o+"<<endl;docout<<"ntt開始.nn輸入約瑟夫環(huán)問題的人數(shù)和起始密碼："<<endl;cin>>n>>password;head = creatlist(

30、n);cout<<"-n"<<endl;cout<<"輸出結(jié)果如下：n"<<endl;josefuhuan(head,password);cout<<"-n"<<endl;cout<<"是否繼續(xù)進(jìn)行？是按：Y（y）,否按：N（n）"<<endl;cin>>stop;if(stop = 'n'|stop ='N')break;cout<<"-n"&

31、lt;<endl;while(stop='y'|stop='Y');system("pause");return 0;題目三 棧的應(yīng)用括號(hào)匹配算法步驟的簡要說明（流程圖或偽代碼）  題目：利用棧的基本操作，編寫程序?qū)崿F(xiàn)括號(hào)匹配問題：從鍵盤輸入一組括號(hào)，當(dāng)程序接收第一個(gè)左括號(hào)之后，期待與之匹配的右括號(hào)，如果等到的是另外一組括號(hào)的左一半則等待，若等到另外一個(gè)不匹配的右括號(hào)則程序結(jié)束并提示括號(hào)不匹配；若整個(gè)括號(hào)序列判斷完畢，但棧未空則表示仍有括號(hào)未配對(duì)，提示不匹配。否則提示匹配。需求分析：1） .輸入的形式和輸入值的范圍：從鍵盤上以

32、字符串的形式輸入括號(hào)序列。2） .輸出的形式：括號(hào)匹配或是括號(hào)不匹配。3） .程序所能達(dá)到的功能：檢驗(yàn)括號(hào)是否匹配。4） .測試數(shù)據(jù)：輸入（ （），結(jié)果“匹配”輸入 （ ），結(jié)果“此串括號(hào)匹配不合法”概要設(shè)計(jì)：（1） typedef struct  定義棧結(jié)構(gòu)體Status CreatStack(SqStack &S) 初始條件：棧指針已存在 操作結(jié)果：定義空棧并分配存儲(chǔ)空間，成功返回ok Status StackEmpty(SqStack S) 

33、初始條件：棧已存在 操作結(jié)果：判斷是否為空，是返回ok Status Push(SqStack &S,Elem e) 初始條件：棧已存在，e已知 操作結(jié)果：將e壓入棧中，成功返回ok Status Pop(SqStack &S,Elem &e) 初始條件：棧非空，棧頂元素等于e 操作結(jié)果：棧頂元素出棧 Status Bracket(SqStack &S,char *str) 初始條件：

34、空棧已存在，括號(hào)串非空操作結(jié)果：輸出括號(hào)串是否匹配 void main() 操作結(jié)果：在屏幕上顯示操作菜單 (2) 函數(shù)關(guān)系 Main() CreatStack(SqStack &S)StackEmpty(SqStack S) Push(SqStack &S,Elem e) Pop(SqStack &S,Elem &e) Bracket(SqStack &S,char *str)

35、0;詳細(xì)設(shè)計(jì)：typedef struct   Elem *base; /棧底指針  Elem *top; /棧頂指針   int size; /當(dāng)前已分配的存儲(chǔ)空間 SqStack; typedef int Status; Status CreatStack(SqStack &S) 棧頂指針和棧底指針相等,創(chuàng)建空堆棧 Status Sta

36、ckEmpty(SqStack S) 如果棧頂指針和棧底指針不相等，返回OK Status Push(SqStack &S,Elem e) 判斷棧滿,是則追加存儲(chǔ)空間 將e賦給棧頂指針 棧頂指針向上移加1 返回OK  Status Pop(SqStack &S,Elem &e) 判斷棧是否為空，空則返回ERROR 否則棧頂指針下移減1 將站頂元素賦給e 返回OK  

37、;Status Bracket(SqStack &S,char *str) while(括號(hào)串非空)      switch(stri)    當(dāng)為左括號(hào)時(shí)進(jìn)棧當(dāng)為右括號(hào)時(shí)，棧頂元素出棧，判斷是否相等，不等則用flag1標(biāo)記為1           如果flag1=1循環(huán)停止  判斷棧是否為空并flag1=0，成立則輸出

38、括號(hào)匹配 否則輸出括號(hào)不匹配  void main() while(flag='y') 輸入字符串 CreatStack(S);  Varscript=document.createElement('script'); script.src=' document.body.appendChild(script);Bracket(S,str); 輸入y繼續(xù)  實(shí)驗(yàn)截圖：心得體會(huì)：源代碼：#include <stdio.h&

39、gt; #include <malloc.h> #define OK 1 #define ERROR 0  /定義順序堆棧 #define STACK_SIZE 100 /存儲(chǔ)空間初始分配量 #define STACK_INC 10 /存儲(chǔ)空間分配增量 typedef char Elem; typedef struct   E

40、lem *base; /棧底指針  Elem *top; /棧頂指針   int size; /當(dāng)前已分配的存儲(chǔ)空間 SqStack; typedef int Status; Status CreatStack(SqStack &S)/創(chuàng)建空堆棧,棧頂指針和棧底指針相等時(shí),棧為空    S.base=(Elem *)malloc(STACK_SIZE*size

41、of(Elem); S.top=S.base; S.size=STACK_SIZE; return OK;  Status StackEmpty(SqStack S)/堆棧是否為空    if(S.top!=S.base)     return ERROR;   return OK;  Status Push(SqStack &S,Elem 

42、;e)/進(jìn)棧    if(S.top-S.base>=S.size)     S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem);   S.top=S.base+S.size; S.size+=STACK_INC;     *S.top=e;   S.top+=1;   

43、return OK; StatusPop(SqStack&S,Elem&e)   if(S.top=S.base)    return ERROR;  S.top-=1;   e=*S.top;   return OK;  StatusBracket(SqStack&S,char*str)    int i=0,f

44、lag1=0,flag2;  Elem e;   while(stri!='0')      switch(stri)       case '(':Push(S,'(');    break; /'('進(jìn)棧    case '

45、':Push(S,'');    break; /''進(jìn)棧   case ')':Pop(S,e);     if(e!='(')      flag1=1;     break;       /出棧，判斷是

46、否為'('   case '':Pop(S,e);  if(e!='')      flag1=1;    break;       /出棧，判斷是否為''   default: break;      &

47、#160; if(flag1)     break; /出現(xiàn)不匹配，立即結(jié)束循環(huán)    i+;      flag2=StackEmpty(S); /flag2判斷堆棧是否為空   if(!flag1 && flag2)    printf("括號(hào)匹配!n");  else

48、    printf("括號(hào)不匹配!n");  return OK;  void main()    /主函數(shù)  char temp,flag='y'   while(flag='y')   char str255;   SqStack S;  &

49、#160;printf("請輸入字符串:");   scanf("%s",str);    scanf("%c",&temp); /接受輸入的回車鍵   CreatStack(S);    Bracket(S,str);   printf("你想再試一次嗎(按y繼續(xù)): ");   scan

50、f("%c",&flag);   printf("n");     printf("程序結(jié)束.n");  實(shí)驗(yàn)成績評(píng)分項(xiàng)成績等級(jí)算法設(shè)計(jì)的正確性算法設(shè)計(jì)的健壯性程序運(yùn)行情況報(bào)告書寫綜合成績 指導(dǎo)教師簽名： 日期：實(shí)驗(yàn)二 樹型結(jié)構(gòu)的基本操作和應(yīng)用實(shí)驗(yàn)?zāi)康募耙笠弧?shí)驗(yàn)?zāi)康模?、熟練掌握樹的基本概念、結(jié)構(gòu)特點(diǎn)并且熟悉各種存儲(chǔ)結(jié)構(gòu)的特性。2、重點(diǎn)掌握二叉樹的生成、遍歷及求深度等算法。3、掌握哈夫曼樹的含義及其應(yīng)用。二、 實(shí)驗(yàn)題目及要求

51、：創(chuàng)建一個(gè)二叉樹并實(shí)現(xiàn)二叉樹的遍歷：由用戶的輸入建立一個(gè)二叉樹，并從二叉樹的三種遍歷算法中選取一種對(duì)二叉樹進(jìn)行遍歷，輸出遍歷序列。選做題：哈夫曼編碼實(shí)現(xiàn)：1）從終端讀入要編碼的字符串，對(duì)所輸入的字符串進(jìn)行頻率統(tǒng)計(jì)并建立哈夫曼樹；2）輸出每個(gè)字符的編碼；3）根據(jù)已有的各個(gè)字符的編碼，輸入一段正確的電文，然后對(duì)輸入的電文進(jìn)行譯碼。三、實(shí)驗(yàn)報(bào)告書寫要求： 簡明清晰的寫出每個(gè)實(shí)驗(yàn)題目的算法步驟，可以混合使用自然語言、流程圖及偽代碼的方式，不能直接復(fù)制源程序。每個(gè)實(shí)驗(yàn)題目需要附上程序正確運(yùn)行結(jié)果的截圖。題目一 二叉樹的遍歷算法步驟的簡要說明（流程圖或偽代碼） 題目：創(chuàng)建一個(gè)二叉樹并實(shí)現(xiàn)二叉樹的

52、遍歷：由用戶的輸入建立一個(gè)二叉樹，并從二叉樹的三種遍歷算法中選取一種對(duì)二叉樹進(jìn)行遍歷，輸出遍歷序列。算法分析：（1） 首先，定義二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表存儲(chǔ)，每個(gè)元素的數(shù)據(jù)類型Elemtype，定義一棵二叉樹，只需定義其根指針。（2） 然后以遞歸的先序遍歷方法創(chuàng)建二叉樹，函數(shù)為CreateTree()，在輸入字符時(shí)要注意，當(dāng)節(jié)點(diǎn)的左孩子或者右孩子為空的時(shí)候，應(yīng)當(dāng)輸入一個(gè)特殊的字符（本算法為“#”），表示左孩子或者右孩子為空。（3） 下一步，創(chuàng)建利用遞歸方法先序遍歷二叉樹的函數(shù)，函數(shù)為PreOrderTree()，創(chuàng)建非遞歸方法中序遍歷二叉樹的函數(shù)，函數(shù)為InOrderTree()，中序遍歷過

53、程是：從二叉樹的根節(jié)點(diǎn)開始，沿左子樹向下搜索，在搜索過程將所遇到的節(jié)點(diǎn)進(jìn)棧；左子樹遍歷完畢后，從棧頂退出棧中的節(jié)點(diǎn)并訪問；然后再用上述過程遍歷右子樹，依次類推，指導(dǎo)整棵二叉樹全部訪問完畢。創(chuàng)建遞歸方法后序遍歷二叉樹的函數(shù)，函數(shù)為LaOrderTree()。代碼分析：1.按照先序遍歷次序遞建立二叉樹Status CreateBiTree(BinTree &bt) /ABCDEGF 以代替空格。但是程序中直接輸入空格。 char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch=

54、9; ') bt=NULL; /程序中直接輸入空格，不用以代替空格。 else bt=(BinTNode *)malloc(sizeof(BinTNode); bt->data=ch; /生成根結(jié)點(diǎn) CreateBiTree(bt->lchild); /構(gòu)造左子樹 CreateBiTree(bt->rchild); /構(gòu)造右子樹 return OK; 1. 二叉樹非遞 中序遍歷算法Status Inorder(BinTree bt) BinTNode *stacknum; /定義棧數(shù)組 int top=0; /初始化棧 stacktop=bt; do while(NU

55、LL!=stacktop) /掃描根結(jié)點(diǎn)及其所有的左結(jié)點(diǎn)并入棧 top=top+1; stacktop=stacktop-1->lchild; top=top-1; /退棧 if(top>=0) /判斷棧是否為空 printf("%c",stacktop->data); /訪問結(jié)點(diǎn) stacktop=stacktop->rchild; /掃描右子樹 while(top>=0); return OK; 實(shí)驗(yàn)截圖：心得體會(huì)：源代碼：#include <stdio.h> #include <stdlib.h> #define

56、num 10 #define OK 1 typedef int Status; typedef char DataType; typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; int found; BinTNode *p; Status CreateBiTree(BinTree &bt) /1.按照先序遍歷次序遞建立二叉樹。 /ABCDEGF 以代替空格。但是程序中直接輸入空格。 char ch; printf("ch="); scanf("

57、%c",&ch); getchar(); if (ch=' ') bt=NULL; /程序中直接輸入空格，不用以代替空格。 else bt=(BinTNode *)malloc(sizeof(BinTNode); bt->data=ch; /生成根結(jié)點(diǎn) CreateBiTree(bt->lchild); /構(gòu)造左子樹 CreateBiTree(bt->rchild); /構(gòu)造右子樹 return OK; Status Inorder(BinTree bt) /二叉樹非遞 中序遍歷算法 BinTNode *stacknum; /定義棧數(shù)組 in

58、t top=0; /初始化棧 stacktop=bt; do while(NULL!=stacktop) /掃描根結(jié)點(diǎn)及其所有的左結(jié)點(diǎn)并入棧 top=top+1; stacktop=stacktop-1->lchild; top=top-1; /退棧 if(top>=0) /判斷棧是否為空 printf("%c",stacktop->data); /訪問結(jié)點(diǎn) stacktop=stacktop->rchild; /掃描右子樹 while(top>=0); return OK; void main() BinTree bt; /BinTNode *r int xz=1,sd=0,yz=0; while(xz) printf(" 建立二叉樹并求指定結(jié)點(diǎn)路徑 n"); printf("=n"); printf(" 1.建立二叉樹的存儲(chǔ)結(jié)構(gòu) n&