第一章--學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

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

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

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