《大數(shù)據(jù)結構》實驗報告材料

《《大數(shù)據(jù)結構》實驗報告材料》由會員分享，可在線閱讀，更多相關《《大數(shù)據(jù)結構》實驗報告材料（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 某某科技學院 數(shù)據(jù)結構〔C語言版〕 實驗報告 專業(yè)班級測繪1011 學 號10201151 姓 名XX 實習地點 C1 機房 指導教師 史守正 目 錄 封面………………………………………………………………………1 目錄………………………………………………………………………2 實驗一 線性表……………………

2、……………………………………3 一、程序設計的根本思想，原理和算法描述…………………………………3 二、源程序與注釋〔打包上傳〕……………………………………………3 三、運行輸出結果………………………………………………………… 4 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………6 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓…………………6 實驗二 棧和隊列……………………………7 一、程序設計的根本思想，原理和算法描述……………………………8 二、源程序與注釋〔打包上傳〕……………………………8 三、運行輸出結果……………………………………………

3、……………8 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………10 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓………………10 實驗三 樹和二叉樹………………………………………………11 一、程序設計的根本思想，原理和算法描述………………………………11 二、源程序與注釋〔打包上傳〕……………………………………………12 三、運行輸出結果…………………………………………………………12 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………12 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓………………12 實驗四 圖………………

4、…………………………………………13 一、程序設計的根本思想，原理和算法描述………………………………13 二、源程序與注釋〔打包上傳〕……………………………………………14 三、運行輸出結果…………………………………………………………14 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………15 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓………………16 實驗五 查找…………………………………………………………17 一、程序設計的根本思想，原理和算法描述………………………………17 二、源程序與注釋〔打包上傳〕……………………………………………18 三

5、、運行輸出結果…………………………………………………………18 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………19 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓………………19 實驗六 排序…………………………………………………………20 一、程序設計的根本思想，原理和算法描述………………………………20 二、源程序與注釋〔打包上傳〕……………………………………………21 三、運行輸出結果…………………………………………………………21 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施………………………24 五、對算法的程序的討論、分析，改良設想，其它

6、經(jīng)驗教訓………………24 實驗一 線性表 一、程序設計的根本思想，原理和算法描述： 程序的主要分為自定義函數(shù)、主函數(shù)。自定義函數(shù)有InitList_Sq、Out_List、ListInsert_Sq、ListDelete_Sq、LocateElem_Sq、pare。主函數(shù)在運行中調用上述的自定義函數(shù)，每個自定義函數(shù)實現(xiàn)程序的每局部的小功能。 用c語言編譯程序，利用順序存儲方式實現(xiàn)如下功能：根據(jù)鍵盤輸入數(shù)據(jù)建立一個線性表，并輸出該線性表；然后根據(jù)屏幕菜單的選擇，可以進展數(shù)據(jù)的插入、刪除、查找，并在插入或刪除數(shù)據(jù)后，再輸出線性表；最后在屏幕菜單中選擇完畢按鈕，即可完畢程序的運行。

7、 2．原理 線性表通過順序表現(xiàn)，鏈式表示，一元多項式表示，其中鏈式表示又分為靜態(tài)鏈表，雙向鏈表，循環(huán)鏈表等，在不同的情況下各不一樣，他可以是一個數(shù)字，也可以是一個符號，通過符號或數(shù)字來實現(xiàn)程序的運行。 〔1〕輸入的形式和輸入值的X圍：執(zhí)行插入操作時，需要輸入插入的位置的元素的值；執(zhí)行刪除操作時，需要輸入待刪除元素的位置；執(zhí)行查找操作時，需要輸入待查找元素的值。在所有輸入中，元素的值都是整數(shù)。 〔2〕輸出的形式：在所有操作中都要求顯示相關操作是否正確以與操作后單鏈表的內容。其中刪除操作完成后，要顯示刪除元素的值；查找操作完成后，假如找到待查元素，如此顯示該元素在單鏈表中的位置。反之，給

8、出不能找到的信息。 〔3〕程序功能：完成單鏈表的生成、插入、刪除、查找操作。 〔4〕測試數(shù)據(jù)： ①依次輸入元素12，34，56， 78， 90，生成一個單鏈表。 ②插入操作中在位置4上插入元素10。 ③刪除操作中輸入5 78，刪除位于5的元素78。 ④查找操作中輸入56，輸出元素在單鏈表中的位置是3。 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果： 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施： 開始調試過程中遇到不清楚的指針函數(shù)，為此，將其改為自己熟悉的函數(shù)，實現(xiàn)相應的功能。 〔

9、1〕通過書本的例題以與理論知識來分析錯誤的原因。 〔2〕認真復習教師上課的ppt課件，找出教師上課的主要思想，通過教師的提醒來解決問題。 〔3〕與同學分析與交流。 〔4〕向教師請教 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 我們上課必須認真聽講，課后也要仔細復習教師的ppt以與上課的筆記，這樣才能更加深刻地了解教師的解題思想以與考試的重點，上機課更要獨立完成教師布置的作業(yè)。對于算法的程序，要充分發(fā)揮函數(shù)庫的功能。對于自己不清楚的函數(shù)，可以向教師詢問或者去上網(wǎng)查找相關的方法。 實驗二 棧和隊列 一、程序設計的根本思想，原理和算法描述： 〔包括程序的結構，數(shù)據(jù)

10、結構，輸入/輸出設計，符號名說明等〕 程序主要由自定義函數(shù)，主函數(shù)構成。自定義函數(shù)是實現(xiàn)程序每個小功能的一局部，自定義函數(shù)有：Status InitStack、Status GetTop、Status Push、Status Pop、Out_Stack。 1．程序設計根本思想 編寫一個程序實現(xiàn)順序棧的各種根本運算，并在此根底上設計一個主程序，完成如下功能： 2．程序設計的原理 通過了解棧和隊列的特性，來掌握棧的順序表示和實現(xiàn)和棧的鏈式表示，實現(xiàn)掌握隊列的順序表示以與實現(xiàn)掌握隊列的鏈式表示，最后要實現(xiàn)掌握棧和隊列在實際問題中的應用。 3．程序設計的算法描述 〔1〕建立棧：構造一個空

11、棧,并插入元素 〔2〕入棧，插入元素 〔3〕出棧，刪除棧頂元素 〔4〕取棧頂元素 〔5〕輸出顯示棧內元素，從棧底到棧頂 4．測試數(shù)據(jù) ①依次輸入元素12，34，56， 78， 90，123，456，789，生成一個棧。 ②入棧操作中輸入入棧元素100。 ③出棧操作中輸入5，刪除從棧頂開始的5個的元素。 ④取棧頂元素操作中，輸出棧頂元素是78。 ⑤依次輸出從棧底到棧頂元素：12，34，56，78。 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果： 四、調試和運行程序過程中產(chǎn)生的

12、問題與采取的措施： 問題〔1〕有時會有不能夠認識的語句和不能理解表達的。 〔2〕對題目的主要程序編寫會無法下手。 措施〔1〕認真復習教師上課的內容與思想。 〔2〕與教師或者同學進展深刻的討論。 〔3〕認真地分析實驗的主要目的與主要方法以與主要思想。 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 對于一段程序，一個人的理解還是比擬局限的。幾個人一起討論，會達到很好的改良程序的效果。能夠鍛煉提高學生的實踐能力，在實習課上，同學把理論課上的很多算法得以實現(xiàn)，上課更加積極的討論。大家在歡樂的氣氛下，達到了理論與實踐水平共同提高目的，日后同學之間談起來，都很懷念。 實驗

13、三 樹和二叉樹 一、程序設計的根本思想，原理和算法描述： 〔包括程序的結構，數(shù)據(jù)結構，輸入/輸出設計，符號名說明等〕 1. 程序設計根本思想 通過用C語言編寫程序來掌握二叉樹的結構特征，以與各種存儲結構的特點和適用X圍，更要能夠用指針類型描述、訪問和處理二叉樹的運算。 2. 編寫設計的原理 通過輸入二叉樹的先序序列字符，建立二叉鏈表〔輸入時，必須參加結點以示空指針的位置；假設虛結點輸入時用空格字符表示〕然后按先序、中序和后序遍歷二叉樹求二叉樹結點總數(shù)，觀察輸出結果。不但要求二叉樹葉子數(shù)，還要求求二叉樹的深度〔或稱高度〕。交換二叉樹的左右子樹在主函數(shù)中設計一個簡單的菜單，分別調試上

14、述算法。二叉樹采用存儲結構，其根結點指針為T，設計一個算法對這棵二叉樹的每個結點賦值 〔1〕 輸入二叉樹的先序序列字符，建立二叉鏈表。注意：輸入時，必須〔2〕參加虛結點以示空指針的位置；假設虛結點輸入時用空格字符表示。 〔3〕按先序、中序和后序遍歷二叉樹 〔4〕求二叉樹結點總數(shù)，觀察輸出結果。 〔5〕求二叉樹葉子數(shù)，觀察輸出結果。 〔6〕求二叉樹的深度〔或稱高度〕，觀察輸出結果。 〔7〕交換二叉樹的左右子樹 〔8〕在主函數(shù)中設計一個簡單的菜單，分別調試上述算法。 二叉樹采用存儲結構，其根結點指針為T，設計一個算法對這棵二叉樹的每個結點賦值：〔注意要修改DataTyp

15、e類型〕 a) 葉結點的值為3 b) 只有左孩子或右孩子的結點如此其值分別等于左孩子或右孩子的值 c) 左、右孩子均有的結點，如此其值等于左、右孩子結點的值之和 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果： 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施： 調試中在初始輸入數(shù)據(jù)的時候格式非常的要注意，在實驗時經(jīng)常會遇到在調試的過程中會經(jīng)常遇到類型不匹配等問題。但是通過看書以與向其他同學的請教，實在不行可以向教師請教，最終都能夠很好地解決問題。 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 通過這次實驗，我能夠很好的掌握了二叉樹的前序、中序、后續(xù)遍歷、計算總

16、結點數(shù)、計算葉子結點數(shù)和交換左右子數(shù)等操作。要認真復習上課的筆記之后才可以去做題目。通過實驗的練習，也可以將學到的知識在實驗中進展實際運用，將理論與實際相結合。算法要做到簡潔，便于理解，不能夠太死板。 實驗四 圖 一、程序設計的根本思想，原理和算法描述： 用c語言編譯程序，是一種較線性表和樹更為浮渣的數(shù)據(jù)結構。在線性表中，數(shù)據(jù)元素之間有著明顯的層次關系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關。掌握圖的根本存儲方法。掌握有關圖的操作算法，并用c語言實現(xiàn)；熟練掌握圖的兩種搜索路徑的遍歷方法并掌握圖的有關應用。 2. 程序設計的原理 建立無向網(wǎng)的鄰接矩陣存儲并輸出，參考程序

17、清單，實現(xiàn)無向圖的鄰接矩陣表示。 建立圖的鄰接表存儲并在此根底上實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷 備注：無向圖已完成，無向網(wǎng)需要自己建立(參照算法7.2)；參照算法7.4， 7.5，7.6完成圖的深度遍歷，廣度遍歷；請?zhí)砑舆m當?shù)淖⑨尅? 〔1〕認真閱讀和掌握本實驗的程序思想 〔2〕對課本的深度和廣度遍歷有深刻了解 〔3〕結合書本對程序進展填寫，并結合程序進展分析 〔4〕按照對圖的操作需要，重新改寫主程序并運行，打印出文件清單和運算結果。 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果： 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施：

18、在調試的時候發(fā)現(xiàn)這個程序不能夠返回選擇菜單，但是沒能進展相應的改正。 運行時運用了深度遍歷和廣度遍歷是圖的兩種根本的遍歷算法，但有時會把來年各種算法混亂，從而造成運行錯誤，不斷的修改但不能得出正確答案，從而會讓心情變壞，對此產(chǎn)生排斥，所以要與時對問題進展清理。 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 算法不能都是對著書上的照抄寫下來，書上的有些也是不全面的，應該相互討論，完善代碼。 深度遍歷和廣度遍歷是圖的兩種根本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷〞對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種根本的遍歷算法而設計的

19、，比如：“求最長的最短路徑問題〞和“判斷兩頂點間是否存在長為K的簡單路徑問題〞，就分別用到了廣度遍歷和深度遍歷算法。實驗中遇到難題要與時去請教教師。 實驗五 查找 一、程序設計的根本思想，原理和算法描述： 〔包括程序的結構，數(shù)據(jù)結構，輸入/輸出設計，符號名說明等〕 用c語言編譯程序，掌握幾種典型的查找方法〔折半查找、二叉排序樹的查找、哈希查找〕，對各種算法的特點、使用X圍和效率有進一步的了解，并能用高級語言實現(xiàn)查找算法。 2. 程序設計原理 認真閱讀和掌握本實驗的程序，上機

20、運行本程序保存和打印出程序的運行結構，并結合程序進展分析按照查找操作要求，重新改寫主程序并運行，打印出文件清單和運算結果。用二叉鏈表做存儲結構，輸入鍵值序列，利用查找、插入算法建立一棵二叉排序樹，按中序遍歷這棵二叉排序樹，在二叉排序樹上插入結點，刪除二叉排序樹上的結點。 〔1〕 首先要了解本次程序的運行結果與方案 〔2〕對程序進展分析，修改錯誤的程序 〔3〕結合書本例題，對程序的二叉樹排序進展編寫 〔4〕按中序遍歷在二叉樹上的刪除節(jié)點 〔5〕保存程序 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果： 四、調試和運行程序過程中產(chǎn)生的問題與采取的措

21、施： 在運行的過程中，對于結點的刪除功能的實現(xiàn)一開始不能成功，之后再討論后發(fā)現(xiàn)是一個指針標志錯誤，改正后就好了。 書本上的知識與教師的講解都比擬容易理解，但是當自己采用剛學的知識點編寫程序時卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后，只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況，我會嚴格要求自己，熟練掌握算法思想，盡量獨立完成程序的編寫與修改工作，只有這樣，才能夠提高運用知識，解決問題的能力。 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 代碼在調試和運行中改良，對于一個功能，應該選擇簡潔的代碼，不能追求

22、代碼的長度。在不少數(shù)據(jù)結構的教材中，是把查找與排序放入高級數(shù)據(jù)結構中的。應該說，查找和排序兩章是前面我們所學的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數(shù)據(jù)結構某一方面的運用就構成了查找和排序。現(xiàn)實生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡時代，萬事離不開search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大局部時間。 實驗六 排序 一、程序設計的根本思想，原理和算法描述： 〔包括程序的結構，數(shù)據(jù)結構，輸入/輸出設計，符號名說明等〕 用c語言編譯程序，每次將一個待排序的記錄，按其關鍵字的大小插入到前面已經(jīng)排好序的子表中的

23、適當位置，知道全部記錄插入完成為止。 2. 程序設計原理 它是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成按關鍵字排列的序列，認真閱讀和掌握本實驗的程序，上機運行本程序，保存和打印出程序的運行結構，并結合程序進展分析，按照排序操作要求，編寫主程序并運行，打印出運行結果。 〔1〕編寫主函數(shù) 〔2〕分別實現(xiàn)直接插入 〔3〕冒泡排序〔算法在P16〕 〔4〕快速排序 〔5〕簡單項選擇擇排序 〔6〕堆排序等排序算法 二、源程序與注釋〔打包上傳〕： 三、運行輸出結果：

24、 四、調試和運行程序過程中產(chǎn)生的問題與采取的措施： 調試的過程中，對于錯誤不斷的改良和相互交流，從而改良程序和實現(xiàn)功能。運行時可能會對程序的方法有些模糊，這樣就可能無從下手，比如冒泡等方法會混淆，所以要經(jīng)常翻書了解數(shù)據(jù)結構的思想，從而對排序能夠全面掌握。 五、對算法的程序的討論、分析，改良設想，其它經(jīng)驗教訓： 代碼的調試要注意值的運算，迭代過程。這個程序的主要思想是將一個數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個按關鍵字有序的序列。穩(wěn)定排序：如果在排序文件中存在多個關鍵詞一樣的記錄，經(jīng)過排序后這些只有一樣關鍵字的記錄之間的相對次序保持不變的排序方法。不穩(wěn)定排序：具有一樣關鍵字的記錄之間在排序完畢后，其相對次序發(fā)生變化的排序方法。內部排序：排序過程中，整個文件都是放在內存中處理，排序時不涉與數(shù)據(jù)的內、外存交換。外部排序：排序過程中，假如整個文件排序過程中要進展數(shù)據(jù)的內、外存交換。通過此次實驗可以是排序與VB，VC相結合。 - 25 - / 25