1.1　為什么要學習數據結構

1．數據結構的前世今生

數據結構作為一門獨立的課程是從1968年開始在美國設立的。1968年，算法和程序設計技術的先驅，美國的唐·歐·克努特（Donald Ervin Knuth）教授開創了數據結構的最初體系，他所著的《計算機程序設計藝術》第一卷《基本算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。從20世紀60年代末到70年代初，隨著大型程序的出現，軟件也相對獨立，結構化程序設計成為程序設計方法學的主要內容，數據結構顯得越來越重要。

從20世紀70年代中期到80年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展并未就此止步，隨著大數據和人工智能時代的到來，數據結構開始在新的應用領域發揮重要作用。面對爆炸性增長的數據和計算機技術的發展，人工智能、大數據、機器學習等各應用領域中需要處理的大量多維數據就需要對數據進行組織和處理，數據結構的重要性不言而喻。

高德納（Donald Ervin Knuth）寫出了計算機科學理論與技術的經典巨著《計算機程序設計藝術》（The Art of Computer Programming）（共五卷），該著作被《美國科學家》雜志列為20世紀最重要的12本物理科學類專著之一，與愛因斯坦《相對論》、狄拉克《量子力學》、理查·費曼《量子電動力學》等經典比肩。因此，高德納在他36歲時就榮獲ACM 1974年年度的圖靈獎，迄今為止，他仍然是最年輕的圖靈獎獲得者紀錄保持者。高德納肖像如圖1.1所示。

圖1.1　高德納肖像

此外，高德納花了整整9年的時間，完成了對西文印刷行業具有革命性變革的TeX排版軟件和METAFONT字型設計軟件，并因此獲得了ACM的軟件系統獎（Software System Award）。《計算機程序設計藝術》推出之后，可真正能讀完讀懂的人為數并不多，據說比爾·蓋茨花費了幾個月才讀完第一卷，然后說，“如果你覺得自己是一名優秀的程序員，那就去讀《計算機程序設計藝術》吧。對我來說，讀完這本書不僅花了好幾個月，而且還要求我有極高的自律性。如果你能讀完這本書，不妨給我發個簡歷”。

2．數據結構的作用與地位

數據結構是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。數據結構已經不僅僅是計算機相關專業的核心課程，還是其他非計算機專業的主要選修課程之一，其重要性不言而喻。數據結構與計算機軟件的研究有著更密切的關系，開發計算機系統軟件和應用軟件都會用到各種類型的數據結構。例如，算術表達式求值問題、迷宮求解、機器學習中的決策樹分類等分別利用了數據結構中的棧、樹進行解決，因此，要想更好地運用計算機來解決實際問題，使編寫出的程序更高效、具有通用性，僅掌握計算機程序設計語言是難以應付眾多復雜問題的，還必須學習和掌握好數據結構方面的有關知識。數據結構也是學習操作系統、軟件工程、人工智能、算法設計與分析、機器學習、大數據等眾多后繼課程的重要基礎。

在計算機剛出現的那些年，人們使用計算機的目的主要是處理數值計算問題。當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，程序設計者的主要精力是集中于程序設計的技巧上。隨著計算機應用領域的擴大和軟、硬件的發展，非數值計算問題成為各研究領域要處理的主要對象。這類問題涉及的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式描述，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，然后選擇合適的算法。因此，學習數據結構與算法有利于培養我們的邏輯思維能力和解決復雜軟件工程問題的能力。