數(shù)據(jù)結(jié)構(gòu)課程設計--兩種常用查找算法的比較與實現(xiàn)(已修改)
2025-01-30 17:17 本頁面
【正文】 兩種常用查找算法的比較與實現(xiàn)摘 要：本次課程設計主要研究幾種常用查找算法的比較與實現(xiàn)，查找的算法有很多種：靜態(tài)查找表的順序表、有序表、索引順序表等查找結(jié)構(gòu)；動態(tài)查找表的二叉排序樹、哈希查找等查找結(jié)構(gòu)。本次的課程設計主要研究兩種常見的查找算法：順序查找和折半查找，分析比較它們的時間復雜度，并且在此基礎上用C語言對它們進行算法編程、調(diào)試和運行。關(guān)鍵詞：C語言；順序查找；折半查找。時間復雜度。1 引 言 “數(shù)據(jù)結(jié)構(gòu)”在計算機科學中是一門綜合性的專業(yè)基礎課，“數(shù)據(jù)結(jié)構(gòu)”的研究不僅涉及到計算機硬件的研究范圍，而且和計算機軟件的研究有著密切的關(guān)系無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，一遍查找和存取數(shù)據(jù)元素更為方便。因此，可以認為“數(shù)據(jù)結(jié)構(gòu)”是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。課程設計是我們專業(yè)課程知識綜合應用的實踐訓練，是實踐性教學的一個重要環(huán)節(jié)。而數(shù)據(jù)結(jié)構(gòu)的課程設計，更要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。在日常生活中，人們幾乎每天都要進行“查找”工作。例如，在電話號碼薄中查閱“某單位”或“某人”的電話號碼；在字典中查閱“某個詞”的讀音和含義等等。而同樣地，在各種系統(tǒng)軟件和應用軟件中，也存在“查找”：如編譯程序中符號表、信息處理表中相關(guān)信息的查找。所以，“查找”就是在一個含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄）【1】。在計算機中進行查找的方法也會隨數(shù)據(jù)結(jié)構(gòu)不同而不同。在此，引入“查找表”的概念：同類數(shù)據(jù)元素構(gòu)成的集合。所以，這次的課程設計就可以從靜態(tài)查找表的幾種典型的算法來實現(xiàn)對數(shù)據(jù)元素的查找的算法和操作的實現(xiàn)和比較。 《數(shù)據(jù)結(jié)構(gòu)》課程設計作為獨立的教學環(huán)節(jié)，是計算機相關(guān)專業(yè)集中實踐環(huán)節(jié)系列之一，是學習完《數(shù)據(jù)結(jié)構(gòu)》課程后進行的一次全面的綜合練習。所以需要我們了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，并且具備初步的獨立分析和設計能力，同時要掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼測試等基本方法和技能，提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力。所以這次課程設計的目的在于：加強學生對C語言的基本知識和技能；加深對數(shù)據(jù)結(jié)構(gòu)基礎理論和基本知識的理解，提高解決實際問題的實踐能力；同時幫助調(diào)動學生的積極性和能動性，培養(yǎng)學生的自學、動手能力。 本次課程設計，我準備用不同的兩種常見的查找方法：針對順序查找表中查找方法，如順序查找、折半查找等。并且通過用這些算法實現(xiàn)對某個“特定的”數(shù)據(jù)元素（關(guān)鍵字）的查找，分析這些操作的性能：它們各自的時間復雜度、空間復雜度和其它的一些性能，同時記錄每種查找方法的優(yōu)缺點，比較得出它們的查找效率和查找范圍。2 設計概要 問題描述對于不同的查找算法，它們各自的時間復雜度和空間復雜度不同，查找的思想和算法也明顯不同，所以要分析它們的特點和效率，我們要多方面比較：要比較時間復雜度，我們可以從它們的查找長度側(cè)面比較出來；而它們算法的實現(xiàn)就要熟悉它們的查找思想，熟練應用C語言編寫合適的程序。 設計思路靜態(tài)查找表有順序表和鏈式表兩種表示方法，在這次的課程設計里，我用順序存儲表來表示這兩種查找算法的程序。我的設計思路及步驟如下：（1）熟悉兩種算法的編程思想,畫出流程圖。（2）先編寫兩種算法的子程序，再遍寫主程序調(diào)用它們。（3）分步調(diào)試子程序和主程序，直到不再出現(xiàn)錯誤，然后運行程序，檢查是否和 自己當初的設想一樣，一直到結(jié)果能讓自己滿意。（4）比較得出兩種查找算法的優(yōu)缺。 相關(guān)的知識點（1）C語言表示靜態(tài)查找表的順序存儲結(jié)構(gòu)typedef struct {Ele
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1