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

1、金陵科技學(xué)院實(shí)驗(yàn)報(bào)告學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊(cè)課程名稱(chēng)：算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 順序表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 工科樓A205 實(shí)驗(yàn)日期： 2013年10月16日 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)1 順序表一、實(shí)驗(yàn)?zāi)康暮鸵笳莆枕樞虮淼亩ㄎ?、插入、刪除等操作。二、實(shí)驗(yàn)儀器和設(shè)備Turbo C 2.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫(xiě)程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫(xiě)主函數(shù)測(cè)試結(jié)果。（2） 編寫(xiě)順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號(hào)（序號(hào)

2、從0開(kāi)始編號(hào)）；如果不存在，返回1。編寫(xiě)主函數(shù)測(cè)試結(jié)果。（3） 在遞增有序的順序表中插入一個(gè)新結(jié)點(diǎn)x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；從第一個(gè)元素開(kāi)始找到第一個(gè)大于該新結(jié)點(diǎn)值x的元素位置i即為插入位置；然后將從表尾開(kāi)始依次將元素后移一個(gè)位置直至元素i；最后將新結(jié)點(diǎn)x插入到i位置。（4） 刪除順序表中所有等于X的數(shù)據(jù)元素。2、選做題（5） 已知兩個(gè)順序表A和B按元素值遞增有序排列，要求寫(xiě)一算法實(shí)現(xiàn)將A和B歸并成一個(gè)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。程序清單：1、#define maxsize 100typedef struct

3、int datamaxsize; int last;sequenlist;main() int i; sequenlist l=2,5,6,8,2,8,4,3,7; printf("nThe list is:"); for(i=0;i<=l.last;i+) printf("%2d",l.datai);2、#define maxsize 100typedef struct int datamaxsize; int last;sequenlist;main() int x,i,s=-1; sequenlist l=2,5,6,7,9,8,4,3,7;

4、 printf("nThe list is:"); for(i=0;i<=l.last;i+) printf("%2d",l.datai); printf("nPlease input the number :"); scanf("%d",&x); for(i=0;i<=l.last;i+) if(l.datai=x) s=i;break; printf("%d",s);3、#define maxsize 100typedef struct int datamaxsize;

5、int last;sequenlist;main() int i,x,j; sequenlist l=1,3,5,6,7,9,5; printf("nThe list is:"); for(i=0;i<=l.last;i+) printf("%2d",l.datai); printf("nInput the insert number:"); scanf("%d",&x); for(i=1;i<=l.last;i+) if(l.datai-1>x) break; for(j=l.last;

6、j>=i-1;j-) l.dataj+1=l.dataj; l.datai-1=x; l.last+; printf("the list after insertion is:n"); for(j=0;j<=l.last;j+) printf("%3d",l.dataj);4、#define maxsize 100typedef struct int datamaxsize; int last;sequenlist;main() int i,j,x=0,k=0; sequenlist L=1,3,5,7,2,4,6,8,2,9,9; prin

7、tf("n The list is:"); for(i=0;i<=L.last;i+) printf("%3d",L.datai); printf("nPlease input a number x:"); scanf("%d",&x); for(i=1;i<=L.last+1;i+) if(L.datai-1=x) for(j=i;j<=L.last+1;j+) L.dataj-1=L.dataj; L.last-; i-; k=1; if(k=1) printf("The l

8、ist after deletion is:n"); for(j=0;j<=L.last;j+) printf("%3d",L.dataj); else printf("Not found!n");四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1、輸出結(jié)果：The list is： 2 5 6 8 2 8 4 32、輸出結(jié)果：The list is： 2 5 6 7 9 8 4 3 Please input the number：8 5The list is： 2 5 6 7 9 8 4 3 Please input the number：1

9、 -13、輸出結(jié)果：The list is： 1 3 5 6 7 9 Input the insert number：8 The list after insertion is： 1 3 5 6 7 8 94、輸出結(jié)果：The list is： 1 3 5 7 2 4 6 8 2 9 Please input a number x：5 The list after deletion is： 1 3 7 2 4 6 8 2 9 The list is： 1 3 5 7 2 4 6 8 2 9 Please input a number x：11 Not found！五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦

10、法，編程后的心得體會(huì)）遇到問(wèn)題：讀取數(shù)據(jù)元素時(shí)，誤將=寫(xiě)成=，導(dǎo)致錯(cuò)誤。實(shí)驗(yàn)過(guò)程中，順序表的賦值沒(méi)有弄懂，以致輸出多個(gè)0或者少輸出。格式運(yùn)算符也要正確控制，否則系統(tǒng)會(huì)停止工作。實(shí)驗(yàn)體會(huì)：通過(guò)實(shí)驗(yàn)掌握了順序表的基本操作，如初始化、插入、讀取元素、刪除等等。并了解到線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，即邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，然而從另一方面來(lái)看，在做插入和刪除時(shí)需要移動(dòng)大量元素。本次實(shí)驗(yàn)基本完成了實(shí)驗(yàn)要求的目的，順序表的初始化，定義，插入，查找等，更好的了解了順序表基本操作的算法，以及更直觀的了解了數(shù)據(jù)結(jié)構(gòu)在C語(yǔ)言環(huán)境下的體現(xiàn)。實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 單鏈表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)

11、地點(diǎn)： 工科樓A205 實(shí)驗(yàn)日期： 2013年10月23日 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)2 單鏈表一、實(shí)驗(yàn)?zāi)康暮鸵?、實(shí)驗(yàn)?zāi)康恼莆諉捂湵淼亩ㄎ?、插入、刪除等操作。2、實(shí)驗(yàn)要求（1）注意鏈表的空間是動(dòng)態(tài)分配的，某結(jié)點(diǎn)不用之后要及時(shí)進(jìn)行物理刪除，以便釋放其內(nèi)存空間。（2）鏈表不能實(shí)現(xiàn)直接定位，一定注意指針的保存，防止丟失。二、實(shí)驗(yàn)儀器和設(shè)備Turbo C 2.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫(xiě)程序建立一個(gè)單鏈表，并逐個(gè)輸出單鏈表中所有數(shù)據(jù)元素。（2） 在遞增有序的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進(jìn)行插入操作；

12、從第一個(gè)結(jié)點(diǎn)開(kāi)始找到第一個(gè)大于該新結(jié)點(diǎn)值的結(jié)點(diǎn)即為插入位置；然后在找到的此結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；注意保留插入位置之前結(jié)點(diǎn)的指針才能完成插入操作。（3） 編寫(xiě)實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表就地逆置的子函數(shù)，并編寫(xiě)主函數(shù)測(cè)試結(jié)果。2、選做題已知指針LA和LB分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)單鏈表的首元結(jié)點(diǎn)。要求編一算法實(shí)現(xiàn)，從表LA中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表LB中第j個(gè)元素之前。程序清單：1、#include<stdlib.h>typedef int datattype;typedef struct node char data; struct node *next;linklist;

13、main() char ch;linklist *head,*s,*r,*p; head=malloc(sizeof(linklist); r=head; scanf("%c",&ch); while(ch!='$') s=malloc(sizeof(linklist); s->data=ch; r->next=s; r=s; scanf("%c",&ch); r->next=NULL; r=head->next; while(r!=NULL) printf("%c",r->

14、;data); r=r->next; 2、#include "stdio.h"#include "stdlib.h"typedef struct node int data; struct node *next;linklist;main() int x,y; linklist *head,*s,*r,*p,*q,*m,*n; clrscr(); head=malloc(sizeof(linklist); r=head; printf("input the order numbers :"); scanf("%d&qu

15、ot;,&x); while(x!=0) s=malloc(sizeof(linklist); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; printf("Please input the insert value:"); scanf("%d",&y); p=head->next; while(p!=NULL) if (p->data<y) p=p->next; else break; q=mallo

16、c(sizeof(linklist); q->data=y; m=head; while(m->next!=p) m=m->next; q->next=p; m->next=q; n=head->next; printf("the list are:"); while(n!=NULL) printf("%3d",n->data); n=n->next; 3、#include "stdio.h"#include "stdlib.h"typedef struct node

17、 int data; struct node *next;linklist;main() int a; linklist *head,*s,*r,*p,*q,*t; clrscr(); head=malloc(sizeof(linklist); r=head; printf("Input some numbers:"); scanf("%d",&a); while(a!=0) s=malloc(sizeof(linklist); s->data=a; r->next=s; r=s; scanf("%d",&

18、a); r->next=NULL; printf("n The linklist before changed is:n "); p=head->next; while(p) printf("%d",p->data); p=p->next; p=head->next; q=p->next; while(q!=NULL) t=q->next; q->next=p; p=q; q=t; head->next->next=NULL; head->next=p; printf("nAft

19、er changed:n"); p=head->next; while(p!=NULL) printf("%d",p->data); p=p->next; 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1、輸入：1 2 3 a b c $輸出結(jié)果：1 2 3 a b c 2、輸入：input the order numbers : 1 3 5 7 8 9 0Please input the insert value:：4 輸出結(jié)果：the list are: 1 3 4 5 7 8 93、輸入：Input some numbers:1 3 4 5 8

20、 0 輸出結(jié)果：The linklist before changed is: 13458After changed: 85431五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）遇到問(wèn)題：編寫(xiě)成功后運(yùn)行時(shí)，沒(méi)有加入$導(dǎo)致程序運(yùn)行不成功，不能夠退出。后注意到這個(gè)問(wèn)題才繼續(xù)運(yùn)行下去。實(shí)驗(yàn)體會(huì)：在編寫(xiě)程序時(shí)，設(shè)置了結(jié)束字符一定要牢牢記住，并且在輸入時(shí)觀察仔細(xì)類(lèi)型是什么，以及是否是輸入一串有順序的數(shù)字，編寫(xiě)成功不難，但是要規(guī)范格式，不能僅僅以完成程序?yàn)槟康?。而完成這一章的實(shí)驗(yàn)也讓我了解了，順序表便于查找不便于插入刪除，而鏈表恰恰相反，鏈表的插入刪除只需要移動(dòng)指針，而順序表要從后往前依次移動(dòng)，二者各

21、有優(yōu)劣。實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 堆棧和隊(duì)列 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 工科樓A205 實(shí)驗(yàn)日期： 2013年10月30日 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)3 堆棧和隊(duì)列一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握應(yīng)用棧解決問(wèn)題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。（3）掌握隊(duì)列的存儲(chǔ)結(jié)構(gòu)及基本操作實(shí)現(xiàn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。二、實(shí)驗(yàn)儀器和設(shè)備Turbo C 2.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 判斷一個(gè)算術(shù)表達(dá)式中開(kāi)括號(hào)和閉括號(hào)是否配對(duì)。（2） 測(cè)試“漢諾塔”問(wèn)題。（3） 假設(shè)稱(chēng)正讀和反讀都相同的字符序列為”回文”，試寫(xiě)一個(gè)算法判別讀入的一個(gè)以

22、為結(jié)束符的字符序列是否是“回文”。2、選做題在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)輸出受限的雙端循環(huán)隊(duì)列的入列和出列算法。設(shè)每個(gè)元素表示一個(gè)待處理的作業(yè)，元素值表示作業(yè)的預(yù)計(jì)時(shí)間。入隊(duì)列采取簡(jiǎn)化的短作業(yè)優(yōu)先原則，若一個(gè)新提交的作業(yè)的預(yù)計(jì)執(zhí)行時(shí)間小于隊(duì)頭和隊(duì)尾作業(yè)的平均時(shí)間，則插入在隊(duì)頭，否則插入在隊(duì)尾。程序清單：1、typedef int datatype;#define M 100typedef struct char dataM; int top; seqstack;main() char strM; int result=0,i=0; seqstack s; s.top=0; gets(str); whi

23、le(stri!='0') if(stri='(') s.top+; s.datas.top='(' if(stri=')') if(s.top=0)result=1;break; else s.top-; i+; if(result=0 && s.top=0) printf("Match!n"); else if(result=1) printf("Missing left!n"); else if(s.top>0) printf("Missing righ

24、t!n");2、#include<stdio.h>void hanoi(int n,char a,char b,char c) if(n=1) printf("n Move disk %d from pile %c to pile %c",n,a,c); else hanoi(n-1,a,c,b); printf("n Move disk %d from pile %c to pile %c",n,a,c); hanoi(n-1,b,a,c); void main() int n; clrscr(); printf("n

25、Please enter the number of disks to be moved:"); scanf("%d",&n); hanoi(n,'A','B','C');3、#include<stdio.h>#define M 100typedef struct char dataM; int top;seqstack;main() char strM; int i=0,n; seqstack s; s.top=0; gets(str); while(stri!='') i+;

26、if(i=1) printf("Yesn"); return; n=i; for(i=0;i<n/2;i+) s.top+; s.datas.top=stri; i=i-1; if(n%2=0) i+; else i=i+2; while(i<n && s.datas.top=stri) i+; s.top-; if(i=n) printf("Yesn"); else printf("Non");四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1、輸入：（a）輸出結(jié)果：Match！輸入：（a輸出結(jié)果：Missin

27、g right！輸入：a）輸出結(jié)果：Missing left！2、輸入：3 輸出結(jié)果：Move disk 1 from pile A to pile CMove disk 2 from pile A to pile BMove disk 1 from pile C to pile BMove disk 3 from pile A to pile CMove disk 1 from pile B to pile AMove disk 2 from pile B to pile CMove disk 1 from pile A to pile C3、輸入：qwewq 輸出結(jié)果：Yes 輸入：qwe

28、rewr 輸出結(jié)果No五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）遇到問(wèn)題：在本章棧和隊(duì)列中編程，有許多的if語(yǔ)句，編寫(xiě)時(shí)一不小心就會(huì)少加一個(gè)花括號(hào)，以致編寫(xiě)不成功。在本章漢諾塔問(wèn)題中，使用了棧以及函數(shù)的遞歸，這其中的過(guò)程一直不是很了解，在經(jīng)過(guò)老師的講解后，理解了大致過(guò)程。實(shí)驗(yàn)體會(huì)：遞歸函數(shù)是編程中經(jīng)常會(huì)用到的一種函數(shù)，它可以實(shí)現(xiàn)許多我們?cè)谄綍r(shí)言語(yǔ)和解釋上解決不了的問(wèn)題，我們需要理解并且可以熟練的使用它，這對(duì)我們之后的編程會(huì)有很大的幫助。而漢諾塔利用棧是一種很經(jīng)典的遞歸的算法，這讓我們理解棧和遞歸。實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 串 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 工科樓A205實(shí)驗(yàn)日期：

29、 2013年11月6日 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)4 串一、實(shí)驗(yàn)?zāi)康暮鸵笳莆沾拇鎯?chǔ)及應(yīng)用。二、實(shí)驗(yàn)儀器和設(shè)備Turbo C 2.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫(xiě)輸出字符串s中值等于字符ch的第一個(gè)字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。（2） 編寫(xiě)輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。解題思路：可以將第一題程序改進(jìn)成一個(gè)子函數(shù)，在本題中循環(huán)調(diào)用。（3） 設(shè)字符串采用單字符的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編程刪除串s從位置i開(kāi)始長(zhǎng)度為k的子串。2、選做題假設(shè)以鏈結(jié)構(gòu)表示串，編寫(xiě)算法實(shí)現(xiàn)將串S插入到串T中某個(gè)字符之后，若串T中不存在這個(gè)字符，則

30、將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計(jì)為從鍵盤(pán)輸入。程序清單：1、#define maxsize 100typedef struct char chmaxsize; int curlen;seqstring;main() int i; char ch; seqstring s="asdfghg",6; for(i=0;i<s.curlen;i+) printf("%c",s.chi); printf("nPlease input aa character ch:"); scanf("%c&

31、quot;,&ch); for(i=0;i<s.curlen;i+) if(s.chi=ch) printf("ch=s.ch%d=%cn",i,s.chi); break; if(i>=s.curlen) printf("Not find!n");2、#define maxsize 100typedef struct char chmaxsize; int curlen;seqstring;main() int i,flag=0; char ch; seqstring s="abadeag",6; for(i=0

32、;i<s.curlen;i+) printf("%c",s.chi); printf("nPlease input aa character ch:"); scanf("%c",&ch); for(i=0;i<s.curlen;i+) if(s.chi=ch) printf("ch=s.ch%d=%cn",i,s.chi); flag+; if(flag=0) printf("Not find!n");3、#include<stdio.h>#include<

33、stdlib.h>typedef struct linknode char data; struct linknode *next;linkstring;main() linkstring *head,*s,*r,*p,*q; int i,b,l,k=0; char ch; head=NULL;r=NULL; printf("n Next to creat LinkString,$ as end markn"); ch=getchar(); while(ch!='$') s=malloc(sizeof(linkstring); s->data=c

34、h; if(head=NULL) head=s; else r->next=s; r=s; ch=getchar(); if(r!=NULL) r->next=NULL; q=head; while(q) printf("%c",q->data); q=q->next; k+; printf("n Now input two int for stratpostion and length for deleted:"); scanf("%d %d",&b,&l); if(b>k-1|b+l&

35、gt;k) printf("Error!n"); return; p=head; for(i=0;i<b-1;i+) p=p->next; printf("%c %d %d %d n",p->data,b,l,k); for(i=b-1;i<b+l-1;i+) q=p->next;p->next=q->next;free(q); q=head; while(q) printf("%c",q->data); q=q->next; printf("n");四、實(shí)驗(yàn)結(jié)

36、果與分析（程序運(yùn)行結(jié)果及其分析）1、輸入：s 輸出結(jié)果：ch=s.ch1=s2、輸入：a 輸出結(jié)果：ch=s.ch0=a ch=s.ch2=a ch=s.ch5=a3、輸入：asdfghjkl$ 2 5 輸出結(jié)果：s 2 5 9 askl五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）實(shí)驗(yàn)體會(huì)：本章第一題可以作為第二題的子函數(shù)，使用調(diào)用；也可以從開(kāi)頭查找對(duì)應(yīng)的字符到結(jié)尾，最后全部輸出。前兩題使用順序串，后面一題是鏈串。串的存儲(chǔ)結(jié)構(gòu)包含有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在串的順序存儲(chǔ)結(jié)構(gòu)中，表示串的長(zhǎng)度通常有兩種方法：一種方法是設(shè)置一個(gè)串的長(zhǎng)度參數(shù)，其優(yōu)點(diǎn)在于便于在算法中用長(zhǎng)度參數(shù)控制循環(huán)過(guò)程；

37、另一種方法是在串值得末尾添加結(jié)束標(biāo)記，此種方法的優(yōu)點(diǎn)在于便于系統(tǒng)自動(dòng)實(shí)現(xiàn)。在串的存儲(chǔ)過(guò)程中，串值用雙引號(hào)引起來(lái)，系統(tǒng)將自動(dòng)在串值得末尾添加結(jié)束標(biāo)記0字符。實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 二叉樹(shù) 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 工科樓A205 實(shí)驗(yàn)日期： 2013年11月13日 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)5 二叉樹(shù)一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握二叉樹(shù)的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹(shù)遞歸遍歷思想解決問(wèn)題的方法。二、實(shí)驗(yàn)儀器和設(shè)備Turbo C 2.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 建立一棵二叉樹(shù)。對(duì)此樹(shù)進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍

38、歷序列。（2） 在第一題基礎(chǔ)上，求二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)。（3） 在第一題基礎(chǔ)上，求二叉樹(shù)中結(jié)點(diǎn)總數(shù)。（4） 在第一題基礎(chǔ)上，求二叉樹(shù)的深度。2、選做題已知一棵完全二叉樹(shù)存于順序表sa中，sa.elem1sa.last存儲(chǔ)結(jié)點(diǎn)的值。試編寫(xiě)算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹(shù)的二叉鏈表。解題思路：根據(jù)完全二叉樹(shù)順序存儲(chǔ)的性質(zhì)來(lái)確定二叉樹(shù)的父子關(guān)系即“還原”了二叉樹(shù)，之后再按照二叉樹(shù)二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹(shù)順序存儲(chǔ)的一個(gè)重要性質(zhì)為，第i個(gè)結(jié)點(diǎn)的左孩子是編號(hào)為2i的結(jié)點(diǎn)，第i個(gè)結(jié)點(diǎn)的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)。程序清單：1（1）#include<stdio.h>#include

39、<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n");

40、 ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar();

41、return root;void preorder(t)bitree *t; if(t) printf("%c",t->data); preorder(t->lchild); preorder(t->rchild); void inorder(t)bitree *t; if(t) inorder(t->lchild); printf("%c",t->data); inorder(t->rchild); void postorder(t)bitree *t; if(t) postorder(t->lchild);

42、postorder(t->rchild); printf("%c",t->data); main() bitree *root; clrscr(); root=Creatree(); printf("preorder is:");preorder(root); printf("n"); printf("inorder is:");inorder(root); printf("n"); printf("postorder is:");postorder(root);

43、 printf("n");（2）#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,inpu

44、t baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else

45、 Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int left(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t->lchild=NULL && t->rchild=NULL) return 1; else num1=left(t->lchild); num2=left(t->rchild); return(num1+num2); main() bitree *root; clrscr(); root

46、=Creatree(); printf("lefts is %dn",left(root);（3）#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=0; print

47、f("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfront)if(r

48、ear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int nodes(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t->lchild=NULL &&t->rchild=NULL) return 1; else num1=nodes(t->lchild); num2=nodes(t->rchild); return (num1+num2+1

49、); main() bitree *root; clrscr(); root=Creatree(); printf("nodes is %dn",nodes(root);（4）#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *r

50、oot,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) r

51、oot=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int depth(bitree *t) int dep1,dep2; if(t=NULL) return 0; else dep1=depth(t->lchild); dep2=depth(t->rchild); if(dep1>dep2) return (dep1+1); else return

52、(dep2+1); main() bitree *root; clrscr(); root=Creatree(); printf("depth is %dn",depth(root);四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）（1）Now Creat the bitree,input baseing the order top to bottom,left to right:abc#preorder is:abcinorder is:abcpostorder is:cba（2）Now Creat the bitree,input baseing the order top to bottom,left to right:abc#lefts is 1（3）Now Creat the bitre