緒論講解(上課)

數(shù)據(jù)結(jié)構(gòu)教材:數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程嚴(yán)蔚敏等，清華大學(xué)出版社參考書:1、《大話數(shù)據(jù)結(jié)構(gòu)》，程杰，清華大學(xué)出版社2、《零根底學(xué)數(shù)據(jù)結(jié)構(gòu)》，機(jī)械出版社3、《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》嚴(yán)蔚敏，吳偉民清華大學(xué)出版社。4、《數(shù)據(jù)結(jié)構(gòu)〔用面向?qū)ο蠓椒ㄅcC++描述〕》殷人昆等清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)是什么？高級(jí)程序語言數(shù)據(jù)結(jié)構(gòu)算法程序？三者關(guān)系內(nèi)容數(shù)據(jù)結(jié)構(gòu)的作用和地位考核要求授課的方法數(shù)據(jù)結(jié)構(gòu)的定義授課的思路〔學(xué)習(xí)思路〕數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)內(nèi)容算法程序預(yù)備知識(shí)C語言數(shù)據(jù)結(jié)構(gòu)軟件工程掌握根本編程方法掌握數(shù)據(jù)組織和數(shù)據(jù)處理的方法掌握大型軟件開發(fā)方法英語單詞英語語法英語作文，小說根本要求課程關(guān)系與語言學(xué)習(xí)過程類比動(dòng)手能力〔上機(jī)〕數(shù)據(jù)結(jié)構(gòu)的作用與地位前期課程數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)根底C語言離散數(shù)學(xué)后期課程操作系統(tǒng)編譯原理數(shù)據(jù)庫(kù)原理軟件工程…承上啟下計(jì)算機(jī)科學(xué)課程體系〔偏軟〕

數(shù)據(jù)結(jié)構(gòu)課程的地位

圖1.7數(shù)據(jù)結(jié)構(gòu)與其它課程的關(guān)系編寫程序1編寫程序2編寫程序n...具有編程的基本能力用計(jì)算機(jī)求解問題的基本思路講授課時(shí)：36上機(jī)課時(shí)：36評(píng)分方式：平時(shí)：10％作業(yè)：20％期末考試：70％授課安排及考核要求學(xué)習(xí)和講授方法

演譯法先學(xué)習(xí)/講授理論知識(shí)，用知識(shí)解決問題。

歸納法先解決具體問題，由此歸納出解決問題的理論知識(shí)。只有歸納法才能產(chǎn)生新的知識(shí)！?。?shù)據(jù)結(jié)構(gòu)是什么？高級(jí)程序語言數(shù)據(jù)結(jié)構(gòu)算法程序？三者關(guān)系高級(jí)程序語言學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)目的：如何編好大型程序高級(jí)程序語言----學(xué)語法〔英語語法〕數(shù)據(jù)結(jié)構(gòu)：前人總結(jié)出的規(guī)那么，學(xué)后能標(biāo)準(zhǔn)編程。高級(jí)語言〔C,C++,java，pascal〕高級(jí)語言，編譯后成--計(jì)算機(jī)語言編譯成01代碼發(fā)生語法錯(cuò)誤執(zhí)行錯(cuò)誤計(jì)算機(jī)語言應(yīng)包含兩種根本結(jié)構(gòu)：循環(huán)語句〔for，while〕條件語句〔if……else…..〕有循環(huán)語句一定有if語句，否那么是死循環(huán)。人的思維VS計(jì)算機(jī)思維編程時(shí)，要多加考慮能否用循環(huán)實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)

簡(jiǎn)單定義：利用計(jì)算機(jī)編程語言〔C語言〕來描述〔定義〕所要處理的編程對(duì)象的方法，這個(gè)方法就是數(shù)據(jù)結(jié)構(gòu)。定義：處理對(duì)象之間的關(guān)系〔邏輯結(jié)構(gòu)〕+對(duì)象及對(duì)象關(guān)系如何存放在計(jì)算機(jī)中〔物理結(jié)構(gòu)〕利用計(jì)算機(jī)求解問題，涉及兩大核心方法：1、在計(jì)算機(jī)中如何描述處理的對(duì)象—數(shù)據(jù)結(jié)構(gòu)2、處理這些對(duì)象的步驟----算法程序=數(shù)據(jù)結(jié)構(gòu)+算法〔N.Wirth(沃斯)〕學(xué)習(xí)內(nèi)容：本書學(xué)習(xí)的內(nèi)容及學(xué)習(xí)思路：數(shù)據(jù)結(jié)構(gòu)+算法〔將一種數(shù)據(jù)結(jié)構(gòu)----結(jié)合講這個(gè)結(jié)構(gòu)的根本算法---綜合根本算法的運(yùn)用〕只有三種數(shù)據(jù)結(jié)構(gòu)〔邏輯結(jié)構(gòu)〕：線性結(jié)構(gòu)：成績(jī)表，圖書管理，病歷卡樹狀結(jié)構(gòu)：博弈類游戲，組織結(jié)構(gòu)。。圖狀結(jié)構(gòu)：公路網(wǎng)，通信網(wǎng)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)內(nèi)容：對(duì)象的數(shù)據(jù)結(jié)構(gòu)，如何定義它這些結(jié)構(gòu)的根本操作例：磚的種類---堆砌方法---建樓數(shù)據(jù)結(jié)構(gòu)---根本方法---寫大程序數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)內(nèi)容：定義根本操作，每個(gè)用函數(shù)數(shù)如何實(shí)現(xiàn)做大程序數(shù)據(jù)結(jié)構(gòu)的應(yīng)用：1、分析對(duì)象〔數(shù)據(jù)data〕2、分析對(duì)象關(guān)系〔結(jié)構(gòu)structs，邏輯結(jié)構(gòu)〕3、儲(chǔ)存對(duì)象及關(guān)系到計(jì)算機(jī)中〔物理結(jié)構(gòu)〕4、該結(jié)構(gòu)的根本運(yùn)算〔算法〕5、編寫復(fù)雜程序〔程序應(yīng)用〕思考：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)有什么不同？算法的五個(gè)重要的特性

〔1〕有窮性：在有窮步之后結(jié)束?！?〕確定性：無二義性?！?〕可行性：可通過根本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)?！?〕有輸入〔5〕有輸出表示存在數(shù)據(jù)處理概念：計(jì)算機(jī)求解問題的步驟〔含循環(huán)〕算法例如，考慮以下兩段描述：〔1〕描述一 voidexam1() {intn＝2; while(n%2＝＝0) n＝n+2; printf("%d\n",n); }華中科大考研題〔2〕描述二 voidexam2() {intx,y; y=0; x=5/y; printf(“%d,%d\n〞,x,y); }這兩段描述均不能滿足算法的特征，試問它們違反了哪些特征？解：〔1〕算法是一個(gè)死循環(huán)，違反了算法的有窮性特征?！?〕算法包含除零錯(cuò)誤，違反了算法的可行性特征。

思考題：

算法和程序有什么不同？算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)應(yīng)滿足以下幾條目標(biāo)：〔1〕正確性要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要也是最根本的標(biāo)準(zhǔn)?！?〕可使用性要求算法能夠很方便地使用。這個(gè)特性也叫做用戶友好性?！?〕可讀性算法應(yīng)該易于人的理解，也就是可讀性好。為了到達(dá)這個(gè)要求，算法的邏輯必須是清晰的、簡(jiǎn)單的和結(jié)構(gòu)化的?！?〕健壯性要求算法具有很好的容錯(cuò)性，即提供異常處理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。不經(jīng)常出現(xiàn)異常中斷或死機(jī)現(xiàn)象?！?〕高效率與低存儲(chǔ)量需求通常算法的效率主要指算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問題如果有多種算法可以求解，執(zhí)行時(shí)間短的算法效率高。算法存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。效率和低存儲(chǔ)量這兩者都與問題的規(guī)模有關(guān)。一個(gè)算法是由控制結(jié)構(gòu)〔順序、分支和循環(huán)三種〕和原操作〔指固有數(shù)據(jù)類型的操作，如n++等〕構(gòu)成的，那么算法時(shí)間取決于兩者的綜合效果。

算法時(shí)間復(fù)雜度分析

控制語句1原操作控制語句n原操作…一個(gè)算法的構(gòu)成例如：voidfun(inta[],intn){inti;for(i=0;i<n;i++)a[i]=2*i;for(i=0;i<n;i++)printf(“%d“,a[i]);printf(“\n〞);}算法描述的語言不同算法執(zhí)行的環(huán)境不同其他因素所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較。同一問題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？為了便于比較同一問題的不同算法，通常從算法中選取一種對(duì)于所研究的問題來說是根本運(yùn)算的原操作〔以下將根本運(yùn)算的原操作簡(jiǎn)稱為根本運(yùn)算〕。算法執(zhí)行時(shí)間大致為根本運(yùn)算所需的時(shí)間與其運(yùn)算次數(shù)〔也稱為頻度〕的乘積。被視為算法根本運(yùn)算的一般是最深層循環(huán)內(nèi)的語句。在一個(gè)算法中,進(jìn)行根本運(yùn)算的次數(shù)越少,其運(yùn)行時(shí)間也就相對(duì)地越少；根本運(yùn)算次數(shù)越多,其運(yùn)行時(shí)間也就相對(duì)地越多。所以,通常把算法中包含根本運(yùn)算次數(shù)的多少稱為算法的時(shí)間復(fù)雜度，也就是說，一個(gè)算法的時(shí)間復(fù)雜度是指該算法的根本運(yùn)算次數(shù)。算法中根本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O〞讀作“大O〞，它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同?！癘〞的形式定義為：假設(shè)f(n)是正整數(shù)n的一個(gè)函數(shù)，那么T(n)=O(f(n))表示存在一個(gè)正的常數(shù)M，使得當(dāng)n≥n0時(shí)都滿足：|T(n)|≤M|f(n)|

也就是只求出T(n)的最高階，忽略其低階項(xiàng)和常系數(shù)，這樣既可簡(jiǎn)化T(n)的計(jì)算，又能比較客觀地反映出當(dāng)n很大時(shí)算法的時(shí)間性能。例如，T(n)=3n2-5n+10000=O(n2)本質(zhì)上講，是一種最高數(shù)量級(jí)的比較一個(gè)沒有循環(huán)的算法的根本運(yùn)算次數(shù)與問題規(guī)模n無關(guān)，記作O(1)，也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法的根本運(yùn)算次數(shù)與問題規(guī)模n的增長(zhǎng)呈線性增大