《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)教案(1-13).doc

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告學(xué)號(hào)：2016031124 姓名：鄭世林 班級(jí)： 16軟件 同組者： 課程名稱：數(shù)據(jù)結(jié)構(gòu) 指導(dǎo)老師： 武洪萍 實(shí)驗(yàn)成績(jī)： 數(shù) 據(jù) 結(jié) 構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程： 數(shù)據(jù)結(jié)構(gòu) 學(xué) 號(hào)： 2016031124 學(xué)生姓名： 鄭世林 班 級(jí)： 16軟件 2017年 月 日實(shí)驗(yàn)一 函數(shù)與結(jié)構(gòu)體（復(fù)習(xí)）一、實(shí)驗(yàn)?zāi)康模红柟虖?fù)習(xí)前期所學(xué)C語(yǔ)言的函數(shù)參數(shù)傳遞、指針和結(jié)構(gòu)體等知識(shí)點(diǎn)，加強(qiáng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)語(yǔ)言基礎(chǔ)。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容：1. 用數(shù)組處理Fibonacci數(shù)列問(wèn)題。已知Fibonacci數(shù)列：1 1 2 3 5 8 13 21 34 輸出數(shù)列的前20項(xiàng)。#include int main() int a22,i,n; a0=a1=1; for(i=2;i21;i+) ai=ai-1+ai-2; printf(%d,a0); for(i=1;i21;i+) printf( %d,ai); printf(n); return 0;2. 下面的程序的功能是：輸入三個(gè)整數(shù)，輸出其中最大的數(shù)，補(bǔ)足所缺語(yǔ)句。#include int max(int x,int y); /*函數(shù)max的聲明*/int max3(int x,int y,int z); /*函數(shù)max3的聲明*/void main()int a,b,c,m;printf(請(qǐng)輸入三個(gè)整數(shù)，用逗號(hào)隔開：n);scanf(%d,%d,%d,&a,&b,&c); /*從鍵盤接收3個(gè)整數(shù)*/m=max3(a,b,c);printf(Max is %dn,m);getch();int max(int x, int y) /*函數(shù)功能：返回x、y的最大值*/ return (xy?x:y);int max3(int x, int y, int z) /*函數(shù)功能：返回x、y、z的最大值*/int m; m=max(max(x,y),z); return m;3.學(xué)生信息的顯示，具體要求如下：1）定義一個(gè)結(jié)構(gòu)體描述學(xué)生信息(學(xué)號(hào),姓名,性別,年齡,住址)；2）設(shè)計(jì)一個(gè)函數(shù)，用于顯示單個(gè)學(xué)生信息，函數(shù)的參數(shù)為前面定義的結(jié)構(gòu)體類型；3）設(shè)計(jì)一個(gè)主函數(shù)，在主函數(shù)中輸入學(xué)生的信息，并調(diào)用前面定義的函數(shù)進(jìn)行顯示（學(xué)生人數(shù)不少于5人）。提示：可用結(jié)構(gòu)體數(shù)組保存學(xué)生信息。4. 輸入若干個(gè)整數(shù)作為數(shù)組元素值，然后按輸入時(shí)順序的就地逆置排序，最后打印出逆置后的元素值。例如 輸入：10 2 30 4 5，逆置后顯示為：5 4 30 2 10。四、 程序運(yùn)行結(jié)果和源代碼為：此處寫程序源代碼，請(qǐng)?jiān)诔绦蛑羞m當(dāng)注釋，便于老師更快地看懂你的程序。此處寫出程序運(yùn)行的結(jié)果，即輸入數(shù)據(jù)是什么，輸出數(shù)據(jù)是什么，分析結(jié)果是否正確，如果不正確是什么原因。五、實(shí)驗(yàn)總結(jié)1、收獲2、存在的問(wèn)題實(shí)驗(yàn)二 線性表的算法實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康模?、掌握線性表的定義方法；2、.掌握線性表基本操作的實(shí)現(xiàn)方法；二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。1、線性表的定義：#define MAX 最大長(zhǎng)度值typedef struct datatype dataMAX; int last; list;2、線性表的初始化思路：順序表的初始化就是構(gòu)造一個(gè)空表，或者說(shuō)是為了給線性表l分配存儲(chǔ)空間。由于采用的是靜態(tài)存儲(chǔ)結(jié)構(gòu)（數(shù)組），線性表的存儲(chǔ)空間是由編譯系統(tǒng)分配的，因此，只要對(duì)線性表的長(zhǎng)度進(jìn)行初始化即可。3、求線性表的長(zhǎng)度4、插入運(yùn)算思路：在保證所給插入位置i合理的前提下，必須先將第i個(gè)及其以后的數(shù)據(jù)元素，向后移動(dòng)一個(gè)元素的位置，然后才能將新的元素x存入留出的空位置上，插入后使原表長(zhǎng)last的長(zhǎng)度值加1。5、刪除運(yùn)算思路：在此討論線性表的刪除運(yùn)算是指將表中第 i 個(gè)元素從線性表中去掉，因?yàn)槭琼樞虼鎯?chǔ)結(jié)構(gòu)，在保證所給刪除位置i合理的前提下，刪除后必須將第i+1個(gè)及其以后的元素前移一個(gè)位置，最后表的長(zhǎng)度減1。6、查找思路：在此討論線性表的查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。從線性表的第一個(gè)元素 l-data1 起依次和x比較，直到找到一個(gè)與x相等的數(shù)據(jù)元素，則返回它在線性表中的存儲(chǔ)下標(biāo)；或者查遍整個(gè)表都沒(méi)有找到與 x 相等的元素，返回0。7、線性表元素的輸出8、主函數(shù)main()程序結(jié)構(gòu)：（1） 聲明變量及線性表；（2） 初始化線性表；（3） 輸入線性表的元素（提示：用插入算法來(lái)實(shí)現(xiàn)）；（4） 輸出線性表中的元素；（5） 顯示線性表的長(zhǎng)度；（6） 在線性表中進(jìn)行元素查找（可提供元素值，也可以提供元素位置）；（7） 往線性表中插入數(shù)據(jù)元素（提供元素值及位置）；（8） 刪除線性表中的數(shù)據(jù)元素（提供元素值或位置）；（9） 輸出線性表中最后的結(jié)果。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)三 線性表的應(yīng)用一、實(shí)驗(yàn)?zāi)康模?、進(jìn)一步掌握線性表的定義方法；2、進(jìn)一步掌握線性表基本操作的實(shí)現(xiàn)方法；3、掌握線性表的應(yīng)用。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。1、有兩個(gè)線性表la和lb，類型為list。編寫一個(gè)算法將它們合并成一個(gè)線性表la ，要求將lb接到la的后面，并且要求lb中的元素在la中已存在，則不把該元素合進(jìn)去。算法思路：把線性表la和lb的長(zhǎng)度分別賦給n和m；從lb中的第一個(gè)元素起，對(duì)每一個(gè)元素與la中的每一個(gè)元素進(jìn)行查找比較，若未找到則將這個(gè)lb元素插入到la表尾，否則繼續(xù)比較下一個(gè)，直到lb中所有元素比較完，則合并完成；并應(yīng)保證la表足夠長(zhǎng)。2、已知一個(gè)線性表la中的元素已按升序排列，其類型為list。編寫一個(gè)算法將該線性表中的重復(fù)元素刪除（即在表中不能有相同的元素）。算法思路：由于線性表la中的元素已按升序排列，所以值相同的元素必為相鄰的元素，因此依次比較相鄰的兩個(gè)元素，若值相等，則刪除其中的一個(gè)，否則繼續(xù)向后比較，直到表尾。3、有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也是從小到大的升序排列。算法思路：依次掃描通過(guò)A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此址到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表相加的長(zhǎng)度。4、主函數(shù)main()程序結(jié)構(gòu)：（1） 聲明變量及線性表；（2） 初始化線性表；（3） 輸入線性表的元素（提示：用插入算法來(lái)實(shí)現(xiàn)）；（4） 輸出線性表中的元素；（5） 對(duì)兩個(gè)線性表進(jìn)行按升序合并（6） 輸出合并后線性表中元素。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)四 棧的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康模?、理解棧的線性結(jié)構(gòu)的特點(diǎn)；2、掌握棧的順序表示；2、掌握?；静僮鞯膶?shí)現(xiàn)方法；3、能夠應(yīng)用棧設(shè)計(jì)算法解決實(shí)際問(wèn)題。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。1、棧的定義：#define MAX 棧中允許存放元素的最大個(gè)數(shù)typedef struct datatype dataMAX; int top;stack;2、棧的基本算法的實(shí)現(xiàn) 棧初始化：init(s) 構(gòu)造了一個(gè)空棧； 判棧空：empty(s) 若棧s為空棧返回為1，否則返回為0； 入棧：push(s,x) 在棧s的頂部插入一個(gè)新元素x，使x成為新的棧頂元素； 出棧：pop(s) 棧s的頂部元素從棧中刪除； 讀棧頂元素：get(s) 取棧頂元素作為結(jié)果返回； 置?？眨篶lear(s) 清除棧s中的所有元素，使之成為空棧。利用主函數(shù)main()調(diào)用上述函數(shù)。3、利用棧結(jié)構(gòu)實(shí)現(xiàn)“數(shù)制轉(zhuǎn)換”問(wèn)題要求：輸入的一個(gè)十進(jìn)制數(shù)，能夠轉(zhuǎn)換成相應(yīng)的八進(jìn)制數(shù)，并輸出。思路：把十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)采用的方法是“除8取余”，直到商為0。依次得到的余數(shù)是k1,k2,k3,km,而轉(zhuǎn)換后的八進(jìn)制數(shù)是km km-1k3 k2 k1，從結(jié)果看恰好與計(jì)算過(guò)程相反，因此轉(zhuǎn)換過(guò)程中每得到一位八進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。此種方法同樣適用于將十進(jìn)制數(shù)轉(zhuǎn)換為r進(jìn)制的數(shù)。把十進(jìn)制整數(shù)11轉(zhuǎn)換為八進(jìn)制的過(guò)程如下：（1）定義“?！钡慕Y(jié)構(gòu)（2）實(shí)現(xiàn)“?！钡幕静僮鳁３跏蓟僮鱅nitStack進(jìn)棧操作Push出棧操作Pop判斷棧是否為空操作Empty（3）實(shí)現(xiàn)主程序main()主程序主要是用來(lái)控制程序的執(zhí)行過(guò)程，實(shí)現(xiàn)數(shù)制的轉(zhuǎn)換操作，以及輸入、輸出。程序結(jié)構(gòu)：聲明變量及棧；初始化棧；輸入要轉(zhuǎn)換的十進(jìn)制數(shù)；進(jìn)行進(jìn)制轉(zhuǎn)換，余數(shù)入棧，商作為被除數(shù)繼續(xù)運(yùn)算；顯示轉(zhuǎn)換后的八進(jìn)制數(shù)（利用出棧）。（4）程序的編譯、鏈接（5）程序的調(diào)試4、雙棧操作設(shè)有兩個(gè)棧s1和s2共享一個(gè)連續(xù)的存儲(chǔ)空間ds1dsm，它們對(duì)應(yīng) 的棧頂指針?lè)謩e是top1和top2，s1的棧底設(shè)在ds1處，s2的棧底設(shè)在dsm處，分別編寫s1和s2的進(jìn)棧函數(shù)push(ds,x,k)和出棧函數(shù)pop(ds,k)。提示：利用一個(gè)變量判斷應(yīng)對(duì)s1還是s2進(jìn)行操作。算法思路： 按提示設(shè)當(dāng)K=1時(shí)對(duì)s1進(jìn)行操作，否則對(duì)s2進(jìn)行操作。當(dāng)top2=top1+1表示棧滿，都不能進(jìn)棧，當(dāng)top1=0時(shí)s1不能出棧，而top2=m+1時(shí)s2不能出棧。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)五 棧的應(yīng)用和隊(duì)列的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康模?、理解棧和隊(duì)列的定義及線性存儲(chǔ)；2、掌握棧和隊(duì)列的運(yùn)算方法；3、了解循環(huán)隊(duì)列的定義及相關(guān)算法；3、能夠應(yīng)用棧和隊(duì)列設(shè)計(jì)算法，解決實(shí)際問(wèn)題。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。1、隊(duì)列的定義：#define MAX 隊(duì)列的最大容量typedef struct datatype dataMAX; int f,r; queue;2、隊(duì)列的基本算法的實(shí)現(xiàn)（1）隊(duì)列初始化：init(q)（2）入隊(duì)操作：insert(q,x)思路：入隊(duì)時(shí)，首先判隊(duì)是否滿了，隊(duì)滿的條件為：q-r= =MAX-1，隊(duì)滿時(shí)，不能入隊(duì)，可以進(jìn)行溢出錯(cuò)誤處理，若可以入隊(duì)則先將隊(duì)尾指針后移(q-r+)，再將元素賦給隊(duì)尾單元。（3）出隊(duì)操作：delete(q,x)思路：先判隊(duì)列是否為空，為空時(shí)不能出隊(duì)，若可以出隊(duì)，則可先將隊(duì)首元素賦給指定變量（若不需要保留，可以省去這一步），隊(duì)首指針后移（q-f-）。（4）讀隊(duì)頭元素：get(q,x)思路：先判隊(duì)列是否為空，為空時(shí)不能取元素，否則取出隊(duì)首元素，但隊(duì)首指針保持不變。（5）判隊(duì)空操作：empty(q)（6）置隊(duì)空：clear (q)3、利用棧結(jié)構(gòu)實(shí)現(xiàn)“算術(shù)表達(dá)式”問(wèn)題要求：輸入的一個(gè)十進(jìn)制數(shù)，能夠轉(zhuǎn)換成相應(yīng)的八進(jìn)制數(shù)，并輸出。思路：1、先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)字符存于c變量中，對(duì)于每一個(gè)c變量的值做如下處理： 若c為數(shù)字，則存于數(shù)組b中； 若c為左括號(hào)(，則將其壓入棧s; 若c為右括號(hào))，則將棧s中左括號(hào)(以后的運(yùn)算符依次出棧，存于數(shù)組b中，然后將左括號(hào)(出棧； 若c為+或-，則將棧s中左括號(hào)(以后的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c壓入棧s中； 若c為*或/，則將棧s中的棧頂端連續(xù)的*或/出棧，存于數(shù)組b中，然后將c壓入棧s中 若c為=，則將棧S中的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c存于數(shù)組b中，最后得到的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中。2、后綴表達(dá)式求值具體思路：需要一個(gè)存放數(shù)值的棧s1，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存，每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)棧頂存放的值就是后綴表達(dá)式的結(jié)果。4、主程序主要是用來(lái)控制程序的執(zhí)行過(guò)程。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)六八 鏈表的建立及應(yīng)用、鏈棧及鏈隊(duì)列一、實(shí)驗(yàn)?zāi)康模?、理解單鏈表的定義及存儲(chǔ)結(jié)構(gòu)；2、掌握單鏈表的基本運(yùn)算方法；3、了解鏈棧和鏈隊(duì)列的應(yīng)用方法；4、能夠應(yīng)用單鏈表設(shè)計(jì)算法，解決實(shí)際問(wèn)題。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。單鏈表的定義：typedef struct node datatype data; struct node *next; linklist ;1、利用首插法和尾插法實(shí)現(xiàn)單鏈表的創(chuàng)建。2、單鏈表的插入運(yùn)算。 要求： 在單鏈表的第i個(gè)元素之前插入一個(gè)元素x。實(shí)現(xiàn)思想：（1）找到第i-1個(gè)元素（2）在i-1個(gè)元素之后插入x3、在單鏈表中按值查找。算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)其值是否等于x，若是，返回該結(jié)點(diǎn)的地址，否則繼續(xù)向后查找，直到鏈表結(jié)束為止。找不到時(shí)返回空。4、單鏈表的刪除運(yùn)算。（1）在指定位置刪除。要求：刪除單鏈表的第i個(gè)元素實(shí)現(xiàn)思想：1、找到第i-1個(gè)元素；2、刪除第i個(gè)元素。（2）根據(jù)所給條件找到位置再進(jìn)行刪除。5、試寫一算法求帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度。思路：?jiǎn)捂湵淼拈L(zhǎng)度是指單鏈表中結(jié)點(diǎn)的個(gè)數(shù)。求單鏈表表長(zhǎng)的基本操作是移動(dòng)指針，將指針從表頭移動(dòng)到表尾。在指針移動(dòng)過(guò)程中，累計(jì)掃描過(guò)的結(jié)點(diǎn)數(shù)即為表長(zhǎng)。由此需要設(shè)一個(gè)指針p，順鏈向后移動(dòng)；還要設(shè)一個(gè)整型變量j，作為計(jì)數(shù)器。指針p的初始值指向頭結(jié)點(diǎn)，計(jì)數(shù)器j的初始值為0。程序參考：int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向頭結(jié)點(diǎn)*/ int j=0; while (p-next) p=p-next; j+ /* p所指的是第 j 個(gè)結(jié)點(diǎn)*/ return j;6、已知帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值為x的結(jié)點(diǎn)插人表中，使L仍然有序。 7、試寫一算法對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。算法描述：（1）空表或長(zhǎng)度為1的表不做任何處理（2）長(zhǎng)度大于等于2時(shí)，做如下處理：從表中第二個(gè)結(jié)點(diǎn)開始，依次取原鏈表中的結(jié)點(diǎn)，將其作為第一個(gè)結(jié)點(diǎn)插入到新鏈表中去。8、編程序判斷一個(gè)字符序列是否是回文，要求采用鏈?zhǔn)疥?duì)列和鏈?zhǔn)蕉褩?。算法提示：設(shè)字符數(shù)組str中存放了要判斷的字符串。把字符數(shù)組中的字符逐個(gè)分別存入隊(duì)列和堆棧，然后逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)九十 二叉樹的建立及遍歷一、實(shí)驗(yàn)?zāi)康模?、熟悉二叉鏈表表示的二叉樹結(jié)構(gòu)及其遞歸遍歷；2、掌握建立二叉鏈表要領(lǐng)；3、理解遞歸遍歷二叉鏈表的執(zhí)行路徑；4、掌握二叉樹的中序遍歷的非遞歸思路；了解二叉樹的后序遍歷的非遞歸思路5、能利用二叉樹的遍歷策略解決實(shí)際問(wèn)題；6、了解哈夫曼編碼的思路及方法。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。二叉樹的二叉鏈表存儲(chǔ)表示可描述為：typedef struct bitnode elemtype data; struct bitnode *lchild,*rchild; /*左、右孩子指針*/ bintree;1、建立一顆二叉鏈表表示的二叉樹。思路：先將二叉樹通過(guò)加入虛節(jié)點(diǎn)的方式使其完全化，然后按層將其輸入?？梢杂枚鏄渲胁粫?huì)出現(xiàn)字符表示虛節(jié)點(diǎn)例如#，用例二叉樹如圖1所示。圖1輸入該二叉鏈表時(shí)，應(yīng)按如下順序：AB#DE#C#。2、對(duì)其進(jìn)行先序，中序，后序輸出。（用遞歸方法實(shí)現(xiàn)）（1）先序遍歷（2）中序遍歷（3）后序遍歷3、實(shí)現(xiàn)二叉樹的中序遍歷的非遞歸算法。提示：二叉樹以二叉鏈表存放，一維數(shù)組stackMAX用以實(shí)現(xiàn)棧，變量top用來(lái)表示當(dāng)前棧頂?shù)奈恢谩?4、統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的數(shù)目算法思想：（1）若二叉樹為空，則它的葉結(jié)點(diǎn)的數(shù)目為0（2）若二叉樹只有一個(gè)結(jié)點(diǎn)，則它的葉結(jié)點(diǎn)的數(shù)目為1（3）否則，它的葉結(jié)點(diǎn)的數(shù)目等于左子樹的葉結(jié)點(diǎn)的數(shù)目和右子樹葉結(jié)點(diǎn)的數(shù)目之和。5、求二叉樹的深度算法思想：（1）若二叉樹為空，則它的深度等于0（2）否則，它的深度等于左子樹和右子樹中的最大深度加1。6、在二叉樹中查找數(shù)據(jù)元素算法思想：在二叉樹中查找數(shù)據(jù)元素x。查找成功時(shí)返回該結(jié)點(diǎn)的指針；查找失敗時(shí)返回空指針。 7、實(shí)現(xiàn)哈夫曼編碼實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分： （1）構(gòu)造哈夫曼樹；（2）在哈夫曼樹上求葉子結(jié)點(diǎn)的編碼。求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉 子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過(guò)了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼?？梢栽O(shè)置一結(jié)構(gòu)數(shù)組huffcode用來(lái)存放各字符的哈夫曼編碼信息，數(shù)組元素的結(jié)構(gòu)如下：bitstart其中，分量bit為一維數(shù)組，用來(lái)保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開始位置。所以，對(duì)于第i個(gè)字符，它的哈夫曼編碼存放在huffcodei.bit中的從huffcodei.start到n的分量上。 8、完成知識(shí)實(shí)踐九。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)十一 靜態(tài)查找一、實(shí)驗(yàn)?zāi)康模?、加深對(duì)查找的理解；2、掌握靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)；3、掌握順序查找、二分查找及其查找的算法。4、了解分塊查找的思路。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu) typedef struct elemtype elemMAX; /*數(shù)組基址*/ int length; /*表長(zhǎng)度*/s_tbl; 靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) typedef struct node elemtype elem; /*結(jié)點(diǎn)的值域*/ struct node *next; /*下一個(gè)結(jié)點(diǎn)指針域*/nodetype;（一）順序查找算法的實(shí)現(xiàn)1、正確設(shè)計(jì)程序，并編譯、鏈接成可執(zhí)行文件（1）首先正確寫出查找表的結(jié)構(gòu)體 typedef struct SSTable（2）正確寫出順序查找算法 Search_Seq（3）寫出主程序 main ，提供輸入與輸出操作本程序的特點(diǎn)是對(duì)于用戶給定的一組關(guān)鍵字序列（64，80，13，56，37，92，19，05，88，21，75），采用順序查找算法找到給定的關(guān)鍵字，并返回其在查找表中的下標(biāo)。2、進(jìn)行程序測(cè)試直接運(yùn)行可執(zhí)行文件，通過(guò)不同的值來(lái)觀察輸出結(jié)果。（二）折半查找算法的實(shí)現(xiàn)1、正確設(shè)計(jì)程序，并編譯、鏈接成可執(zhí)行文件（1）首先正確寫出查找表的結(jié)構(gòu)體 typedef struct SSTable（2）正確寫出折半查找算法 Search_Bin（3）寫出主程序 main ，提供輸入與輸出操作本程序的特點(diǎn)是對(duì)于用戶給定的一組有序的關(guān)鍵字序列（05，13，19，21，37，56，64，75，80，88，92），采用折半查找算法找到給定的關(guān)鍵字，并返回其在查找表中的下標(biāo)。2、進(jìn)行程序測(cè)試直接運(yùn)行可執(zhí)行文件，通過(guò)不同的值來(lái)觀察輸出結(jié)果。四、 程序運(yùn)行結(jié)果和源代碼為：五、實(shí)驗(yàn)總結(jié)：1、收獲2、存在的問(wèn)題實(shí)驗(yàn)十二十三 排序一、實(shí)驗(yàn)?zāi)康模?理解排序的定義和各種排序方法的特點(diǎn)，并能靈活運(yùn)用。2.掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法。3.了解各種方法的排序過(guò)程及其依據(jù)的原則。二、實(shí)驗(yàn)要求1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；3、12人為1小組，實(shí)驗(yàn)過(guò)程中獨(dú)立操作、相互學(xué)習(xí)。三、實(shí)驗(yàn)內(nèi)容及思路：要求：將調(diào)試好的代碼存放到各算法的空白處。1、對(duì)于給定的整數(shù)序列（49，38，65，97，76，13，27，49），實(shí)現(xiàn)直接插入排序。思路：將Ri插入到有序表R1.i-1中，進(jìn)行如下操作：