《數(shù)據(jù)結構》實驗教案(1-13).doc

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