第一章--學習數(shù)據(jù)結構的意義

1、 1.1 基本概念和術語 1.2 學習數(shù)據(jù)結構的意義 1.3 算法的描述和分析1.2 學習數(shù)據(jù)結構的意義 1、數(shù)據(jù)結構在軟件系統(tǒng)中的作用 數(shù)據(jù)結構是計算機軟件和計算機應用專業(yè)的核心課程之一，在眾多的計算機系統(tǒng)軟件中都要用到各種數(shù)據(jù)結構。數(shù)據(jù)結構非線性程序設計專業(yè)基礎課計算機原理語言程序設計離散數(shù)學編譯原理操作系統(tǒng)數(shù)據(jù)庫人工智能1.2 學習數(shù)據(jù)結構的意義 2、選擇合適的的數(shù)據(jù)結構 早期，人們使用計算機鎮(zhèn)壓要處理數(shù)值計算問題，隨著“非數(shù)值性問題”問題的出現(xiàn)，解決問題的關鍵從分析數(shù)學和計算方法轉變?yōu)樵O計出合適的數(shù)據(jù)結構，選擇合適的數(shù)據(jù)結構能成為有效地解決應用問題的關鍵。1.2 學習數(shù)據(jù)結構的意義 3

2、、程序、算法和數(shù)據(jù)結構的關系 瑞士人Niklaus Wirth于1934提出： 算法+數(shù)據(jù)結構=程序 其中，數(shù)據(jù)結構指數(shù)據(jù)的邏輯結構和存儲結構，算法則是對數(shù)據(jù)運算的描述。 程序的實質是選擇一種好的數(shù)據(jù)結構，設計一個好的算法，而好的算法在很大程度上取決于描述實際問題的的數(shù)據(jù)結構。1.2 學習數(shù)據(jù)結構的意義姓氏地址張李姓名地址張三張林張潔李四李中 例1.2 電話號碼查詢問題 編寫程序,查詢某個城市或單位的私人電話號碼 取決于構造的電話號碼表的結構及存儲方式。 先構造姓氏索引表，再查電話號碼登記表比直接按姓氏查詢電話號碼表的查找算法更有效。1.2 學習數(shù)據(jù)結構的意義 設有6個比賽項目，規(guī)定每個選手至

3、多可參加3個項目，有5人報名參加比賽（如下表所示）設計比賽日程表，使得在盡可能短的時間內完成比賽。選手選擇項目的表如下，要求設計競賽日程表，使得在盡可能短的時間內安排完比賽。 例1.3 田徑賽的時間安排問題1.2 學習數(shù)據(jù)結構的意義 田徑賽的時間安排問題解法 設用以下代號代表6個項目： 跳高 跳遠 標槍 鉛球 100米 200米 A B C D E F 用頂點代表比賽項目 不能同時進行比賽的項目之間連上一條邊。 某選手比賽的項目必定有邊相連（不能同時比賽） 競賽的時間安排問題可以抽象為對該無向圖進行著色操作，即使用盡可能少的顏色給圖中每個頂點著色，使任意兩個有邊連接的相鄰頂點著上不同的顏色。1.2 學習數(shù)據(jù)結構的意義姓名項目1項目2項目3丁一 A B E馬二 C D 張三 C E F李四 D F A王