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

1、金陵科技學(xué)院實(shí)驗(yàn)報(bào)告學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊(cè)（理工類）課程名稱：算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級(jí) 學(xué)生學(xué)號(hào)： 學(xué)生姓名： 所屬院部： 計(jì)算機(jī)工程學(xué)院 指導(dǎo)教師： 章海鷗 2016 2017 學(xué)年 第 1 學(xué)期 金陵科技學(xué)院教務(wù)處制實(shí)驗(yàn)報(bào)告書寫要求實(shí)驗(yàn)報(bào)告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點(diǎn)需打印的，要遵照以下字體、字號(hào)、間距等的具體要求。紙張一律采用A4的紙張。實(shí)驗(yàn)報(bào)告書寫說(shuō)明實(shí)驗(yàn)報(bào)告中一至四項(xiàng)內(nèi)容為必填項(xiàng)，包括實(shí)驗(yàn)?zāi)康暮鸵?；?shí)驗(yàn)儀器和設(shè)備；實(shí)驗(yàn)內(nèi)容與過(guò)程；實(shí)驗(yàn)結(jié)果與分析。各院部可根據(jù)學(xué)科特點(diǎn)和實(shí)驗(yàn)具體要求增加項(xiàng)目。填寫注意事項(xiàng)（1）細(xì)致觀察，及時(shí)、準(zhǔn)確、如實(shí)記錄。（2）準(zhǔn)確說(shuō)明，層次清

2、晰。（3）盡量采用專用術(shù)語(yǔ)來(lái)說(shuō)明事物。（4）外文、符號(hào)、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號(hào)。（5）應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。實(shí)驗(yàn)報(bào)告批改說(shuō)明實(shí)驗(yàn)報(bào)告的批改要及時(shí)、認(rèn)真、仔細(xì)，一律用紅色筆批改。實(shí)驗(yàn)報(bào)告的批改成績(jī)采用百分制，具體評(píng)分標(biāo)準(zhǔn)由各院部自行制定。實(shí)驗(yàn)報(bào)告裝訂要求實(shí)驗(yàn)批改完畢后，任課老師將每門課程的每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)報(bào)告以自然班為單位、按學(xué)號(hào)升序排列，裝訂成冊(cè)，并附上一份該門課程的實(shí)驗(yàn)大綱。實(shí)驗(yàn)項(xiàng)目名稱： 順序表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)1 順序表一、實(shí)驗(yàn)?zāi)康暮鸵笳莆枕樞虮淼?/p>

3、定位、插入、刪除等操作。二、實(shí)驗(yàn)儀器和設(shè)備VC6.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測(cè)試結(jié)果。（2） 編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號(hào)（序號(hào)從0開(kāi)始編號(hào)）；如果不存在，返回1。編寫主函數(shù)測(cè)試結(jié)果。（3） 在遞增有序的順序表中插入一個(gè)新結(jié)點(diǎn)x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；從第一個(gè)元素開(kāi)始找到第一個(gè)大于該新結(jié)點(diǎn)值x的元素位置i即為插入位置；然后將從表尾開(kāi)始依次將元素后移一個(gè)位

4、置直至元素i；最后將新結(jié)點(diǎn)x插入到i位置。（4） 刪除順序表中所有等于X的數(shù)據(jù)元素。2、選做題（5） 已知兩個(gè)順序表A和B按元素值遞增有序排列，要求寫一算法實(shí)現(xiàn)將A和B歸并成一個(gè)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。程序清單：(1)#include <stdio.h>#define maxsize 20typedef int datatype;typedef structdatatype datamaxsize;int last; sequenlist; void CreateList(sequenlist *L,int n)int i;printf("

5、;please input n numbersn");for(i=0;i<n;i+) scanf("%d",&L->datai); (*L).last=n; void PrintList(sequenlist *L,int n)int i; printf("the sequenlist isn"); for(i=0;i<n;i+) printf("%d ",L->datai);main() int i,x; int n=10; sequenlist L; CreateList(&L,n

6、); PrintList(&L,n); getchar(); (2)#include<stdio.h> typedef int datatype; #define maxsize 1024 typedef struct datatype datamaxsize; int last; sequenlist; int fun(sequenlist L,int x,int n) int i;for(i=0;i<n;i+)if(L.datai=x)return i;return -1;void main()sequenlist L;int i,n,y;int x;printf

7、("請(qǐng)輸入元素的個(gè)數(shù)：");scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&L.datai);printf("n請(qǐng)輸入要查找的數(shù)據(jù)元素：");scanf("%d",&x);y = fun(L,x,n);if (y=1)printf("n所要查找的數(shù)據(jù)元素不存在n");elseprintf("n數(shù)據(jù)元素%d所在的位置為%dn",x,y);(3)#include <stdio.h>#

8、define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main() int i,x,j; sequenlist l=1,2,4,5,6,7,8,6; printf("n插入元素前的數(shù)據(jù)為:");for(i=0;i<=l.last;i+) printf("%2d",l.datai); printf("n請(qǐng)輸入要插入的元素:"); scanf("%d",&x); for(i=1;i<=l.last;i+) i

9、f(l.datai-1>x) break; if(i>l.last ) l.data l.last +1=x; else for(j=l.last;j>=i-1;j-) l.dataj+1=l.dataj; l.datai-1=x; l.last+; printf("插入元素后的數(shù)據(jù)為:n"); for(j=0;j<=l.last;j+) printf("%3d",l.dataj); printf("n");return 0; (4)#include <stdio.h>#define maxsize

10、 100 typedef 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;printf("n原數(shù)據(jù)為:"); for(i=0;i<=L.last;i+) printf("%3d",L.datai); printf("n請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):"); scanf("%d",&x); for(i=1;i<=L.last+1;i+) if(L.d

11、atai-1=x)for(j=i;j<=L.last+1;j+) L.dataj-1=L.dataj; L.last-; i-; k=1; if(k=1) printf("刪除后的數(shù)據(jù)為:n"); for(j=0;j<=L.last;j+) printf("%3d",L.dataj); else printf("Not found!n"); printf("n"); 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1.11.21.31.4五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）遇到問(wèn)題：讀取數(shù)據(jù)元

12、素時(shí)，誤將=寫成=，導(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)目名稱： 單鏈表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績(jī)： 批改教師：

13、 批改時(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è)備Visual C+6.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個(gè)單鏈表，并逐個(gè)輸出單鏈表中所有數(shù)據(jù)元素。（2） 在遞增有序的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進(jìn)行插入操作；從第一個(gè)結(jié)點(diǎn)開(kāi)始找到第一個(gè)大于該新結(jié)點(diǎn)值的結(jié)點(diǎn)即為插入位置；然后在找到的此結(jié)點(diǎn)之

14、前插入新結(jié)點(diǎn)；注意保留插入位置之前結(jié)點(diǎn)的指針才能完成插入操作。（3） 編寫實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表就地逆置的子函數(shù)，并編寫主函數(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<stdio.h> #include<stdlib.h> typedef struct node int data; struct node *next; *Linklist,Node; Linklist creat(int n) Linklis

15、t head,r,p; int x,i; head=(Node*)malloc(sizeof(Node); r=head; printf("輸入數(shù)字:n"); for(i=n;i>0;i-) scanf("%d",&x); p=(Node*)malloc(sizeof(Node); p->data=x; r->next=p; r=p; r->next=NULL; return head; void output(Linklist head) Linklist p; p=head->next; do printf(&q

16、uot;%3d",p->data); p=p->next; while(p); printf("n"); void main() Linklist head;int x,n; printf("輸入數(shù)字的個(gè)數(shù)(n):n"); scanf("%d",&n); head=creat(n); printf("輸出數(shù)字:n"); output(head); （2）#include <stdio.h>#include <stdlib.h>typedef struct nod

17、e int data; struct node *next;linklist;main() int x,y; linklist *h,*s,*r,*p,*q,*m,*n; h=malloc(sizeof(linklist); r=h; printf("請(qǐng)輸入一個(gè)數(shù)組 :"); scanf("%d",&x); while(x!=0) s=malloc(sizeof(linklist); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; pr

18、intf("請(qǐng)輸入插入值:"); scanf("%d",&y); p=h->next; while(p!=NULL) if (p->data)<y) p=p->next; else break; q=malloc(sizeof(linklist); q->data=y; m=h; while(m->next!=p) m=m->next; q->next=p; m->next=q; n=h->next; printf("這個(gè)鏈表是:"); while(n!=NULL)

19、printf("%2d",n->data); n=n->next; （3）#include <stdio.h>#include <stdlib.h>typedef struct node int data; struct node *next;linklist;main() int x; linklist *h,*s,*r,*p,*q,*t; h=malloc(sizeof(linklist); r=h; printf("請(qǐng)輸入一個(gè)數(shù)組:"); scanf("%d",&x); while(x

20、!=-1) s=malloc(sizeof(linklist); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; printf("n這個(gè)鏈表是:n"); p=h->next; while(p!=NULL) printf("%2d",p->data); p=p->next; p=h->next; q=p->next; while(q!=NULL) t=q->next; q->next=p; p=q; q=

21、t; h->next->next=NULL; h->next=p; printf("n翻轉(zhuǎn)轉(zhuǎn)后的鏈表是:n"); p=h->next; while(p!=NULL) printf("%2d",p->data); p=p->next; 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）(1)(2)(3)五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）遇到問(wèn)題：編寫成功后運(yùn)行時(shí)，沒(méi)有加入$導(dǎo)致程序運(yùn)行不成功，不能夠退出。后注意到這個(gè)問(wèn)題才繼續(xù)運(yùn)行下去。實(shí)驗(yàn)體會(huì)：在編寫程序時(shí)，設(shè)置了結(jié)束字符一定要牢牢記住，并且在輸入時(shí)觀察仔細(xì)類

22、型是什么，以及是否是輸入一串有順序的數(shù)字，編寫成功不難，但是要規(guī)范格式，不能僅僅以完成程序?yàn)槟康?。而完成這一章的實(shí)驗(yàn)也讓我了解了，順序表便于查找不便于插入刪除，而鏈表恰恰相反，鏈表的插入刪除只需要移動(dòng)指針，而順序表要從后往前依次移動(dòng)，二者各有優(yōu)劣.實(shí)驗(yàn)項(xiàng)目名稱： 堆棧和隊(duì)列 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(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è)備Visual C+6.0三、實(shí)驗(yàn)

23、內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 判斷一個(gè)算術(shù)表達(dá)式中開(kāi)括號(hào)和閉括號(hào)是否配對(duì)。（2） 測(cè)試“漢諾塔”問(wèn)題。（3） 假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個(gè)算法判別讀入的一個(gè)以為結(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）#include <stdio.h>#include <stdlib.h>

24、;typedef char datatype;#define maxsize 64typedef struct datatype datamaxsize; int top; seqstack;int match(char exp,int n)char stmaxsize; /設(shè)置一個(gè)棧，用來(lái)存放掃描表達(dá)式中的括號(hào) int top=-1,i=0,tag=1; while(i<n&&tag=1) if(expi='('|expi=''|expi='') /遇到'(''''',則將其

25、入棧 top+; sttop=expi; if(expi=')') /遇到')',若棧頂是'(',則繼續(xù)處理，否則以不配對(duì)返回 if(sttop='(') top-; else tag=0; if(expi='') if(sttop='') top-; else tag=0; if(expi='') if(sttop='') top-; else tag=0; i+; if(top>=0) tag=0; /若棧不空，則不配對(duì)return tag;main()in

26、t tag,i; char exp7='+','(','2','-','4',')' printf("請(qǐng)輸入一個(gè)算式表達(dá)式：n"); for(i=0;i<7;i+) expi=getchar(); tag=match(exp,7); if(tag) printf("算式表達(dá)式中的開(kāi)括號(hào)和閉括號(hào)配對(duì)。"); else printf("算式表達(dá)式中的開(kāi)括號(hào)和閉括號(hào)不配對(duì)！");(2)#include <stdio.h>void

27、 move(char x,char z)printf("%c->",x); printf("%cn",z);void Hanoi(int n,char x, char y,char z) if(n=1) move(x,z); else Hanoi(n-1,x,z,y); move(x,z); Hanoi(n-1,y,x,z); main() int m; printf("請(qǐng)你輸入A上面的碟子總數(shù)"); scanf("%d",&m); Hanoi(m,'A','B',&#

28、39;C'); getchar(); getchar();(3)#include<stdio.h>#define N 100typedef struct char dataN; int top;seqstack;main() char strN; int i=0,n; seqstack a; a.top=0; gets(str); while(stri!='') i+; n=i; for(i=0;i<n/2;i+) a.top+; a.dataa.top=stri; i=i-1; if(n%2=0) i+; else i=i+2; while(i<

29、;n && a.dataa.top=stri) i+; a.top-; if(i=n) printf("是回文數(shù)組n"); else printf("不是回文數(shù)組n");四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）123五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）遇到問(wèn)題：在本章棧和隊(duì)列中編程，有許多的if語(yǔ)句，編寫時(shí)一不小心就會(huì)少加一個(gè)花括號(hào)，以致編寫不成功。在本章漢諾塔問(wèn)題中，使用了棧以及函數(shù)的遞歸，這其中的過(guò)程一直不是很了解，在經(jīng)過(guò)老師的講解后，理解了大致過(guò)程。實(shí)驗(yàn)體會(huì)：遞歸函數(shù)是編程中經(jīng)常會(huì)用到的一種函數(shù)，它可以實(shí)現(xiàn)許多我們

30、在平時(shí)言語(yǔ)和解釋上解決不了的問(wèn)題，我們需要理解并且可以熟練的使用它，這對(duì)我們之后的編程會(huì)有很大的幫助。而漢諾塔利用棧是一種很經(jīng)典的遞歸的算法，這讓我們理解棧和遞歸。實(shí)驗(yàn)項(xiàng)目名稱： 串 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)4 串一、實(shí)驗(yàn)?zāi)康暮鸵笳莆沾拇鎯?chǔ)及應(yīng)用。二、實(shí)驗(yàn)儀器和設(shè)備Visual C+6.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 編寫輸出字符串s中值等于字符ch的第一個(gè)字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。（2） 編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。解題思路：可以將第一題程序

31、改進(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)表示串，編寫算法實(shí)現(xiàn)將串S插入到串T中某個(gè)字符之后，若串T中不存在這個(gè)字符，則將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計(jì)為從鍵盤輸入。程序清單：(1)#include <stdio.h>void search(char *s,char ch)int i=0,n=0;while (*(s+i)if(*(s+i)=ch)printf("第一個(gè)字符：s%d=%cn",i,ch);n+;break;i+;i

32、f(!n) printf("No Found!n");void main()char s20,ch;printf("請(qǐng)輸入一個(gè)串:");gets(s);printf("請(qǐng)輸入要找的元素:");scanf("%c",&ch);search(s,ch);(2)#include <stdio.h>void search(char *s,char ch)int i=0,n=0;while (*(s+i)if(*(s+i)=ch)n+;printf("第%d個(gè)%c在串中的下標(biāo)為：%dn"

33、;,n,ch,i);i+;if(!n) printf("No Found!n");void main()char s20,ch;printf("請(qǐng)輸入串元素：");gets(s);printf("請(qǐng)輸入要找的元素：");scanf("%c",&ch);search(s,ch);(3)#include<stdio.h>#include<stdlib.h>typedef struct linknodechar data;struct linknode *next;linkstring;l

34、inkstring *CREAT()linkstring *head = NULL,*p = NULL,*s = NULL;int a;printf("請(qǐng)輸入順序表的值，'-1'表示輸入結(jié)束：n");scanf ("%d",&a);while (a!=-1)s= (linkstring *)malloc(sizeof(linkstring);if (s = NULL)exit(0);s->data = a;if(head = NULL)head = s;else p->next = s;p=s;scanf ("

35、;%d",&a);p->next = NULL;printf("建立完畢！n");return head;int SEARCH(linkstring *s,int i, int k)linkstring *p =s;int j= 0;for(;j<i+k-2&&p->next!=NULL;j+)p = p->next;if(j=i+k-2)return 1;return 0;void DELETE(linkstring *s,int i,int k)linkstring *p = s,*q = NULL;int j=

36、1;for(;j<i-1;j+)p=p->next;for(j=0;j<k;j+)q= p->next;p->next = q->next;free(q);printf("成功刪除！");void PRINT(linkstring *head)linkstring *s = NULL;s = head;while (s)printf("%d ",s->data);s= s->next;printf("打印完畢！nn");int main()linkstring *ls;int i,k,m

37、;ls = CREAT();PRINT(ls);printf("輸入你想刪除第幾個(gè)字符起的連續(xù)的多少個(gè)字符：");scanf ("%d%d",&i,&k);m = SEARCH(ls,i,k);if(m=0)printf("不存在這樣的子串，刪除失??！");elseDELETE(ls,i,k);PRINT(ls);return 0;四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）(1) (2)(3)五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）實(shí)驗(yàn)體會(huì)：本章第一題可以作為第二題的子函數(shù)，使用調(diào)用；也可以從開(kāi)頭查找對(duì)應(yīng)的

38、字符到結(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ò)程；另一種方法是在串值得末尾添加結(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)目名稱： 二叉樹(shù) 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績(jī)： 批改教師： 批改時(shí)間： 實(shí)驗(yàn)5 二叉樹(shù)一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握二叉樹(shù)的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用

39、二叉樹(shù)遞歸遍歷思想解決問(wèn)題的方法。二、實(shí)驗(yàn)儀器和設(shè)備Visual C+6.0三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）1、必做題（1） 建立一棵二叉樹(shù)。對(duì)此樹(shù)進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。（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)的值。試編寫算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹(shù)的二叉鏈表。解題思路：根據(jù)完全二叉樹(shù)順序存儲(chǔ)的性質(zhì)來(lái)確定二叉樹(shù)的父子關(guān)系即“還原”了二叉樹(shù)，之后再按照二叉樹(shù)二叉鏈表的構(gòu)造方法進(jìn)行建立。

40、完全二叉樹(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）#include <stdio.h>#include <stdlib.h>#define maxsize 20typedef 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=

41、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) root=s; else if(s && Qfr

42、ont)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); 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&quo

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

44、inorder(root); printf("n"); printf("postorder is:");postorder(root); 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

45、,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"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear

46、=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(); 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->

47、lchild); num2=left(t->rchild); return(num1+num2); main() bitree *root; root=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 *Creatr

48、ee() 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"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rc

49、hild=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(); return root;int nodes(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t->lchild=NULL &&t->rchild=NULL) return 1

50、; else num1=nodes(t->lchild); num2=nodes(t->rchild); return (num1+num2+1); main() bitree *root; 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;bi

51、tree *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"); 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