tft每日頭條

 > 科技

 > 數據結構有哪些重要的算法

數據結構有哪些重要的算法

科技 更新时间:2024-08-08 09:15:43
最早的算法

算法是對解決問題的策略,從廣義上說隻要問題的解決過程中有邏輯思維的介入,那麼就會産生算法。算法的思想自古就有,公認的世界上最早的算法是歐幾裡得算法,又叫輾轉相除法,其作用是計算兩個整數的最大公約數(兩個整數都能被整除的那個最大的約數)。我國古代算學著作《九章算術》中也有求最大公約數的算法,叫做更相減損術,從本質上說兩者是等價的,應用了相同的思想。

數據結構有哪些重要的算法(從最早的算法到數據結構)1

歐幾裡得算法和增相減損術

計算機算法

現今,我們所說的算法專指使用計算機解決特定問題的指令的集合。上世紀四五十年代,最初發明電子計算機的目的是為了科學計算和工程計算,那個時候,計算機處理的數據對象是純數字的,解決的問題也很單純,主要為方程求解、微積分計算等。這裡,我們舉一個例子,使用下圖公式來計算π的值,在公式中,正負号隔項改變,通過死闆的計算即可得到我們想要的結果。從這個例子就可以發現,數值計算一般都會使用一些數學公式。

數據結構有哪些重要的算法(從最早的算法到數據結構)2

計算π的公式

非數值計算問題

與數值計算相反的就是非數值計算。計算機高速發展到現在,可以輸入計算機中的數據已不局限于數字,符号、聲音、圖像等各種信息都可以經過編碼後存儲到計算機中,這類數據及數據之間的關系一般無法使用公式或方程來表示,要處理這類非數值計算問題就需要用到算法了

讓我們來看幾個例子:

  • 從客戶信息表中查找客戶電話通信公司通過客戶登記表記錄每個客戶的各項信息,要求按照給定的姓名查找客戶的電話号碼。要解決這個問題,我們需要把客戶信息按照順序依次錄入到計算機中,然後遍曆查找到我們要查的客戶,這裡的信息結構的特點是線性的,要使用的結構就是線性表

數據結構有哪些重要的算法(從最早的算法到數據結構)3

線性表表示客戶信息

  • 計算機的文件系統結構計算機的文件結構是由文件夾組織起來的,這些文件夾的特點是每個文件夾除了根文件夾都最多隻有一個父文件夾。這種一對多的關系就不适合使用線性結構來存儲,這裡使用的結構是樹形結構

數據結構有哪些重要的算法(從最早的算法到數據結構)4

計算機文件系統結構

  • 社交網絡好友問題在社交軟件中,兩個人可以互相關注,如何用來存儲這些好友的關注狀況呢?好友的關系互相構成網狀,他們是多對多的關系,這裡要用到的結構就是圖形結構

數據結構有哪些重要的算法(從最早的算法到數據結構)5

社交網絡

數據結構

以上這些非數值問題中的表、樹、圖模型,無法使用方程或公式來描述,處理此類問題我們需要先找出數據之間的組織方式、表示方式、處理方式等,然後再将其轉化為計算機模型,這就是數據結構。

1968年,美國唐納德·歐·克努特教授開創了數據結構的最初立體,他著作的《計算機程序設計藝術》是第一本系統闡述數據邏輯結構和存儲結構的著作。

數據結構有哪些重要的算法(從最早的算法到數據結構)6

唐納德·歐·克努特教授

數據結構是由某一數據對象及該對象中所有數據成員之間的關系組成。數據結構包含三個要素:數據的邏輯結構、數據的存儲結構、數據的運算。邏輯結構反映了我們對數據含義的解釋,它可以用一組數據及這些數據之間的關系表示。存儲結構又稱物理結構,是數據及邏輯結構在計算機中的表示方式,實際上是内存單元的分配。數據的運算有兩方面的含義,運算的定義和運算的實現。運算的定義取決于數據的邏輯結構,運算的實現則與數據的存儲形式密切相關。

數據結構有哪些重要的算法(從最早的算法到數據結構)7

數據結構的三要素

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关科技资讯推荐

热门科技资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved