2021學年第15課數(shù)據(jù)結構與算法優(yōu)秀教學課件ppt-課件下載-教習網(wǎng)

算法是解決問題方法和步驟，而數(shù)據(jù)結構是算法中所用數(shù)據(jù)的組織結構。因此，解決某個問題的算法會根據(jù)處理對象的數(shù)據(jù)結構不同而發(fā)生變化。
在現(xiàn)實中表示一批序列數(shù)據(jù),常采用線性表的數(shù)據(jù)結構來組織與存儲。對線性表的常用操作有訪問元素、插人元素、刪除元素等。針對某種操作，其對應的算法根據(jù)數(shù)據(jù)組織方式的不同而存在差異。以訪問元素為例，若要查看超市中某個商品的銷售數(shù)據(jù)，在設計數(shù)據(jù)結構時，可以將超市中萬余種商品的銷售數(shù)據(jù)采用數(shù)組或鏈表來組織。
0 45 46 47 48 11023
若采用數(shù)組的方式來組織與存儲，數(shù)據(jù)按照一定的順序存儲在連續(xù)的物理空間中。可以通過元素下標來直接訪問數(shù)組中的某個元素，例如要查看鋼筆的銷售數(shù)據(jù)，若a47存儲的是鋼筆的銷售數(shù)據(jù)，則可直接用a47來表示,相當于訪問1次即完成操作。
若采用鏈表的方式來組織與存儲,數(shù)據(jù)分散地存儲在物理空間中。鏈表中,訪問任意一個元素都必須從第一個節(jié)點（或最后一個節(jié)點）開始進行按序訪問，直到找到指定元素，例如仍然查看鋼筆的銷售數(shù)據(jù)，可以按照“a0→a1…"a46→a47”的次序訪問，即相當于訪問48次,操作完成。如果數(shù)據(jù)的組織與存儲方式不同,那么相同的操作對應的算法一般也不同。
算法效率是指算法執(zhí)行的時間。對于同一個問題，如果有多個解決問題的算法，那么執(zhí)行時間短的算法效率高，反之執(zhí)行時間長的算法效率低。
例如：超市購物付款，當收銀員掃描一件商品的條形碼時，計算機需要在幾萬種商品尋找這件商品，然后顯示相應的商品名稱和價格。
在計算機科學中定義為：在一些（有序的/無序的）數(shù)據(jù)元素中，通過一定的方法找出與給定關鍵字相同的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在查找表中確定一個關鍵字等于給定值的記錄或數(shù)據(jù)元素，又稱檢索。
能否設計出高效率的查找算法，取決于這些商品數(shù)據(jù)的組織及存儲方式。最簡單的方式是將這些數(shù)據(jù)按序存儲在計算機中。查找時從頭開始依次查找商品名稱，直到找出正確的商品名稱或是找遍整個表均沒有找到為止。這種查找算法，對于一個商品種類不多的超市或許是可行的,但對一個有成千上萬種商品的大型超市就不適用了。
如何根據(jù)問題設計適合的查找算法？
若這些數(shù)據(jù)是按商品類別排列的,則可另構建一張商品類別表，采用如圖所示的存儲結構。查找時，首先在類別表中查找類別,然后根據(jù)類別表中的地址到商品登記表中核查商品名稱，這樣在查找商品登記表時就無須查找其他商品的名稱了。與前一種算法相比,基于這種數(shù)據(jù)結構的查找算法的時間效率更為高效,但存儲類別表則需要額外的存儲空間。
常用的查找算法：順序查找：在一組數(shù)據(jù)中，從第一個數(shù)據(jù)開始，按照這組數(shù)據(jù)的排列順序?qū)⒚總€數(shù)據(jù)逐個與給定的值進行比較。若某個數(shù)據(jù)與給定值相等，則查找成功，找到所查數(shù)據(jù)的位置;反之查找不成功。
原始數(shù)據(jù)：int[]a={4,6,2,8,1,9,0,3}; 要查找數(shù)字：8
常用的查找算法：二分法查找：二分查找又稱折半查找，它是一種效率較高的查找方法。【二分查找要求】：1.必須采用順序存儲結構2.必須按關鍵字大小有序排列。