數(shù)據(jù)結構查找算法課程設計(已修改)
2025-08-17 06:29 本頁面
【正文】 存檔編號： 西安********課程設計說明書設計題目：查找算法性能分析系別：計算機學院專業(yè)：計算機科學班級：計科***姓名：王***（共 頁）2015年 01月07 日***** 計算機科學 專業(yè)課程設計任務書姓名：***班級：計科****學號：****一、設計或?qū)嵺`題目查找算法性能分析二、內(nèi)容及要求設計程序，對比分析順序查找、折半查找、索引查找、二叉排序樹查找和散列查找五種查找算法的性能測試數(shù)據(jù)的個數(shù)不少于50個；對每一種查找算法設計實現(xiàn)適應的存儲結構；輸出每種查找算法的查找成功時的平均長度三、完成形式設計報告；源程序四、系（部）審核意見指導教師：****發(fā)題日期：20150105完成日期：20150109一 需求分析1. 1問題描述查找又稱檢索，是指在某種數(shù)據(jù)結構中找出滿足給定條件的元素。查找是一種十分有用的操作。而查找也有內(nèi)外之分，若整個查找過程只在內(nèi)存中進行稱為內(nèi)查找；若查找過程中需要訪問外存，則稱為外查找，若在查找的同時對表做修改運算（插入或刪除），則相應的表成為動態(tài)查找表，反之稱為靜態(tài)查找表。由于查找運算的主要運算是關鍵字的比較，所以通常把查找過程中對關鍵字的平均比較次數(shù)（也叫平均查找長度）作為一個查找算法效率優(yōu)劣的標準。平均查找程度ASL定義為： ASL=∑PiCi（i從1到n）其中Pi代表查找第i個元素的概率，一般認為每個元素的查找概率相等，Ci代表找到第i個元素所需要比較的次數(shù)。查找算法有順序查找、折半查找、索引查找、二叉樹查找和散列查找（又叫哈希查找），它們的性能各有千秋，對數(shù)據(jù)的存儲結構要求也不同，譬如在順序查找中對表的結果沒有嚴格的要求，無論用順序表或鏈式表存儲元素都可以查找成功；折半查找要求則是需要順序表；索引表則需要建立索引表；動態(tài)查找需要的樹表查找則需要建立建立相應的二叉樹鏈表；哈希查找相應的需要建立一個哈希表。1. 2基本要求（1） 輸入的形式和輸入值的范圍；在設計查找算法性能分析的過程中，我們調(diào)用產(chǎn)生隨機數(shù)函數(shù)： srand((int)time(0))。產(chǎn)生N個隨機數(shù)。注：折半查找中需要對產(chǎn)生的隨機數(shù)進行排序，需要進行排序后再進行輸入，N50。（2） 輸出形式；查找算法分析過程中，只要對查找算法稍作修改就可以利用平均查找長度的公式： ASL=∑PiCi（i從1到n）輸出各種查找算法的平均查找長度。注：平均查找長度=總的平均查找長度/N；（3） 程序所能達到的功能通過輸出幾種查找算法的ASL，我們很顯然能得在數(shù)據(jù)量較小時（N100）我們在實現(xiàn)靜態(tài)查找時應該選擇如何調(diào)用哪種查找算法。二 概要設計說明本程序中用到的所有抽象數(shù)據(jù)類型的定義。主程序的流程以及各程序模塊之間的層次(調(diào)用)關系。 數(shù)據(jù)結構順序查找：在進行順序查找順序表類型定時需要定義typedef int KeyType；順序表類型為SeqList類型。 typedef NodeType SeqList【MaxSize】；/它的基本思路是：從表的一端開始，順序掃描線性表，依次將掃描到的關鍵字和給定值k相比較，若當前掃描到的關鍵字與k相等，查找成功。折半查找：在進行順序查找順序表類型定時需要定義typedef int KeyType，并且需要調(diào)用排序函數(shù)對其進行排序。折半查找類型為SeqList類型。 typedef NodeType SeqList【MaxSize】；折半查找又叫二分查找，效率較高，但折半查找要求被查找的表示順序表，它的基本思路是：設R【low…..high】是當前的查找區(qū)間，首先確定該區(qū)間的中點位置mid= ┖（low+high）/2 ┘，然后將待查的k值與R【mid】.key。① 如果中點值的值是k，返回該元素的邏輯符號；② 如果中點值k，則中點值之后的數(shù)都大于k，所以k值在該表的左邊，所以確定一個新的查找區(qū)間；③ 如果中點值k，則中點值之后的數(shù)都小于k，k值在該表的右邊，再在該表的右邊確定一個新的查找區(qū)間；④ 依次循環(huán)。索引查找：/索引存儲結構是在存儲數(shù)據(jù)的同時還建立附加的索引表，索引表包括關鍵字和地址。索引表的數(shù)據(jù)類型 KeyType key、int link，link代表對應塊的起始下標。typedef IdxType IDX[MaxSize] //索引表的類型分塊查找又稱索引順序查找，它的性能介于順序查找和折半查找之間的一種算法，它的分塊的思想是：① 將表均分成b塊，前b1塊中的關鍵字個數(shù)為s=┏n/b┐；② 每一塊的關鍵字不一定有序，但前一塊中的最大關鍵字必須小于后
環(huán)評公示相關推薦
鄂ICP備17016276號-1