數(shù)據(jù)結(jié)構(gòu)與算法課件

數(shù)據(jù)結(jié)構(gòu)與演算法DataStructures

andAlgorithm1.1數(shù)據(jù)結(jié)構(gòu)研究對象◆電腦科學(xué)：資訊在電腦內(nèi)使用數(shù)據(jù)來表示,

研究資訊表示和資訊處理?！魯?shù)據(jù)：是用以描述客觀事物的數(shù)值、字元，以及一切可以輸入到電腦中並由電腦程式加以處理的符號的集合。數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素?cái)?shù)據(jù)的最小單位稱為資料項(xiàng)目◆數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合◆數(shù)據(jù)特徵：數(shù)值、文本、多媒體、超媒體、即時(shí)、海量◆數(shù)據(jù)類型?高級語言中變數(shù)的取值範(fàn)圍和允許的操作

什麼是數(shù)據(jù)？大數(shù)據(jù)(bigdata)大數(shù)據(jù)可分成：大數(shù)據(jù)技術(shù)大數(shù)據(jù)工程：大數(shù)據(jù)工程指大數(shù)據(jù)的規(guī)劃建設(shè)運(yùn)營管理的系統(tǒng)工程；大數(shù)據(jù)科學(xué)：大數(shù)據(jù)科學(xué)關(guān)注大數(shù)據(jù)網(wǎng)路發(fā)展和運(yùn)營過程中發(fā)現(xiàn)和驗(yàn)證大數(shù)據(jù)

的規(guī)律及其與自然和社會活動之間的關(guān)係大數(shù)據(jù)應(yīng)用大數(shù)據(jù)的4個(gè)“V”：—Volume：數(shù)據(jù)體量巨大。從TB級別，躍升到PB級別；—Variety：數(shù)據(jù)類型繁多。網(wǎng)路日誌、視頻、圖片、地理位置資訊等—Value：價(jià)值密度低。以視頻為例，連續(xù)不間斷監(jiān)控過程中，可能有用的數(shù)據(jù)

僅僅有一兩秒?！猇elocity：處理速度快，1秒定律。第一，大數(shù)據(jù)的基本概念第二，大數(shù)據(jù)電腦其挑戰(zhàn)第三，研究問題與部分解大數(shù)據(jù)無處不在：因特網(wǎng)有很多的大數(shù)據(jù)，在科學(xué)研究領(lǐng)域、醫(yī)療領(lǐng)域、商業(yè)領(lǐng)域、製造業(yè)、智慧城市都有大量的數(shù)據(jù)。全世界的感知數(shù)據(jù)增長率是每年58%全世界擁有的存儲能力或者是存儲總量的增長率是每年只有40%2007年，全世界的感知數(shù)據(jù)已經(jīng)超過了全世界所擁有的記憶體的容量2010年，全世界的感知數(shù)據(jù)是1.25千萬PB2011年產(chǎn)生的感知數(shù)據(jù)已經(jīng)二倍於我們?nèi)祟愃鶕碛械挠洃涹w的容量結(jié)論：大數(shù)據(jù)無處不在，數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超出了現(xiàn)有的存儲能力大數(shù)據(jù)的輸入是大數(shù)據(jù)D，問題的解是f（D）。李建中教授談大數(shù)據(jù)◆數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)對象中的數(shù)據(jù)元素彼此之間抽象的相互關(guān)係，並不涉及數(shù)據(jù)元素的具體內(nèi)容◆數(shù)據(jù)結(jié)構(gòu)分類：線性表：(a1,a2,a3,……ai-1,ai,ai+1……an-1,an)→線性結(jié)構(gòu)線性表的一般概念、字串、數(shù)組，廣義表等樹：

→層次結(jié)構(gòu)二叉樹，樹等圖：

→網(wǎng)狀結(jié)構(gòu)有向圖、無向圖等①②③⑤

二叉樹①②③④有向圖◆結(jié)構(gòu)：關(guān)係

國際象棋：每次需要考慮的合乎規(guī)則的著法平均只有35

步“回合”，計(jì)算機(jī)預(yù)先分析7至8個(gè)回合的著

法。若設(shè)為7個(gè)回合，則有超過1億億億個(gè)不

同的變化，經(jīng)簡化後，仍有500億至600億個(gè)

變化。多分析一步，增加18億個(gè)變化資料：下棋程式圍棋：分析7個(gè)回合的著法，則需要考慮超過200的

14次方個(gè)變化，經(jīng)簡化後，仍有1000億億個(gè)

變化。多分析一步，增加64萬億個(gè)變化根據(jù)電腦“深藍(lán)”的速度，平均5分鐘走一步根據(jù)電腦“深藍(lán)”的速度，平均1.5年走一步BlueGene,共裝有32個(gè)並行處理器，速度：2億步棋/秒深藍(lán)vs

卡斯帕羅夫:第一次1996年：2月10日—17日，比分2:4第二次1997年：5月3日—11日，比分3.5:2.5雙方先後共進(jìn)行6局對弈第一局，卡斯帕羅夫執(zhí)白先行，經(jīng)過3個(gè)多小時(shí)的苦戰(zhàn)擊敗“深藍(lán)”，力拔頭籌；第二局，“深藍(lán)”卻以淩厲的攻勢和明顯的優(yōu)勢戰(zhàn)勝卡氏，扳回一局；第三、第四和第五局，雙方下得異常激烈，鏖戰(zhàn)數(shù)小時(shí)，平局；第六局，“深藍(lán)”執(zhí)白先行，一路強(qiáng)攻，僅用一個(gè)多小時(shí)，雙方僅走19步，就讓卡氏俯首稱臣，取得了決定性的勝利。IBM：“深藍(lán)”與棋王卡斯帕羅夫的對比:身高：卡斯帕羅夫5英尺10英寸，“深藍(lán)”6英尺5英寸；體重：卡斯帕羅夫176磅，“深藍(lán)”1.4噸；年齡：卡斯帕羅夫34歲，“深藍(lán)”4歲；每秒行棋速度：卡斯帕羅夫2步，“深藍(lán)”2億步。“神來之手”1.1數(shù)據(jù)結(jié)構(gòu)研究對象◆數(shù)據(jù)結(jié)構(gòu)研究方法：邏輯結(jié)構(gòu)：對操作對象的一種數(shù)學(xué)描述，或從操作對象中抽象出的數(shù)學(xué)模型，用以描述數(shù)據(jù)元素之間的邏輯關(guān)係物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在電腦中的表示或映象，

物理結(jié)構(gòu)又稱存儲結(jié)構(gòu)，分為順序映象和

非順序映象，或稱順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)電腦解題過程：問題→數(shù)學(xué)模型→演算法→程式→測試→計(jì)算分析數(shù)據(jù)並確定存儲結(jié)構(gòu)輸入到電腦中1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況●數(shù)據(jù)結(jié)構(gòu)側(cè)重解決非數(shù)值問題■FORTRAN,ALGOL等高級語言是以程式為中心側(cè)重於解決數(shù)值問題■LISP,SONBOL表或串處理語言是以數(shù)據(jù)為中心側(cè)重於解決非數(shù)值問題●1968年以前，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容大多包含在形如表、樹、圖論、集合代數(shù)論、格、關(guān)係等方面。1968年開始，“數(shù)據(jù)結(jié)構(gòu)”逐漸開始成為獨(dú)立的一門課程?！褡鳛橐婚T專業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”是電腦專業(yè)的核心課程之一，是其他專業(yè)課的基礎(chǔ)。是數(shù)學(xué)、硬體和軟體三者的交叉，很受重視?！鰪腜ASCAL語言開始逐漸形成二者結(jié)合知識結(jié)構(gòu)1.3抽象數(shù)據(jù)型AbstractDataTypes（ADT）

●軟體系統(tǒng)由數(shù)據(jù)結(jié)構(gòu)、操作過程和控制機(jī)能三者組成，軟體設(shè)計(jì)是對三者的抽象過程，即數(shù)據(jù)抽象、過程抽象和控制抽象。[定義]：抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型和在該模型上定義

的操作的集合ADT特點(diǎn)：①降低了軟體設(shè)計(jì)的複雜性②提高了程式的可讀性和可維護(hù)性③程式的正確性容易保證抽象：從眾多事物中捨棄個(gè)別的、非本質(zhì)的屬性，抽出共同的、本質(zhì)性的特徵。是形成概念的重要手段，其目的是使複雜度降低。線性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：設(shè)L的型為LIST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變數(shù)。所有操作描述為：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數(shù)學(xué)模型1.3抽象數(shù)據(jù)型（ADT）舉例㈠定義任意線性表類型為LIST，其中元素類型為Elementtype，設(shè)有線性表L，函數(shù)PURGE用以刪除線性表L中所有重複出現(xiàn)的元素。VoidPURGE(LISTL){Positionp,q;p=FIRST(L);while(p!=END(L)){q=NEXT(p,L);while(q!=END(L))if(same(RETRIEVE(p,L),RETRIEVE(q,L)))

DELETE(q,L);elseq=NEXT(q,L);p=NEXT(p,L);}}1.3抽象數(shù)據(jù)型（ADT）舉例㈡假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合，設(shè)計(jì)演算法求一個(gè)新的集合A=A∪B。VoidUNION(LIST&A；LISTB){positionp;elementtypee;p=FIRST(B);while(p!=END(B);{e=RETRIEVE(p,B);if(same(LOCATE(e,A),END(A)))

INSERT(e,END(A),A);p=NEXT(p,B);}}1.3抽象數(shù)據(jù)型（ADT）抽象數(shù)據(jù)型的規(guī)格描述△完整性：反映所定義的抽象數(shù)據(jù)型的全部特徵△統(tǒng)一性：前後協(xié)調(diào)，不自相矛盾△通用性：適用於儘量廣泛的對象△不依賴性：不依賴於程式設(shè)計(jì)語言，可以用任意的語言來描述規(guī)格描述的兩個(gè)方面:語法和語義△語法：給出操作的名稱、I/O參數(shù)的數(shù)目和類型△語義：由一組等式組成，定義各種操作的功能及相互間的關(guān)係例如：抽象數(shù)據(jù)型——棧(Stack)定義：棧是一個(gè)後進(jìn)先出（LIFO）的線性表，所有插入、刪除操作是在表的一端（棧頂）進(jìn)行聚集數(shù)組，鏈表(結(jié)構(gòu)體、記錄)，檔1.3抽象數(shù)據(jù)型（ADT）a1a2······an-1anInsertDeletetopbottom棧底棧頂棧示意圖棧(Stack)示意圖1.3抽象數(shù)據(jù)型（ADT）1.3抽象數(shù)據(jù)型（ADT）typeStack[Elementtype];NEWSTACK()→Stack,PUSH(Elementtype,Stack)→Stack,POP(Stack)→Stack∪{UNDEFINED},TOP(Stack)→Elementtype∪{UNDEFINED},EMPTY(Stack)→Boolean;抽象數(shù)據(jù)型——棧語法：declarestk:Stack,elm:Elementtype;POP(NEWSTACK)=NEWSTACK,POP(PUSH(elm,stk))=stk,TOP(NEWSTACK)=UNDEFINED,TOP(PUSH(elm,stk))=elm,EMPTY(NEWSTACK)=TRUE,EMPTY(PUSH(elm,stk))=FALSE;抽象數(shù)據(jù)型——棧語義：

規(guī)格描述給出操作的名稱,I/O參數(shù)的數(shù)目和類型定義各種操作的功能及相互間的關(guān)係抽象數(shù)據(jù)型的實(shí)現(xiàn)抽象描述→（高級語言）編寫的程式三條原則：①符合規(guī)格描述的定義

②有盡可能好的通用性

③盡可能獨(dú)立於程式的其他部分多層次抽象技術(shù)自底向上與自頂向下相結(jié)合、由簡單到複雜1.3抽象數(shù)據(jù)型（ADT）1.4數(shù)據(jù)結(jié)構(gòu)與程式設(shè)計(jì)問題解決問題的演算法實(shí)現(xiàn)演算法的程式問題總是先於演算法程式設(shè)計(jì)的四個(gè)里程碑

①副程式、②高級語言、③結(jié)構(gòu)程式設(shè)計(jì)、④面向?qū)ο?OOP)結(jié)構(gòu)程式設(shè)計(jì)

①限制使用GOTO語句（基於三種基本結(jié)構(gòu)）

②逐步求精的設(shè)計(jì)方法

③自頂向下的設(shè)計(jì)、編碼與調(diào)試

④主程序員組的組織形式N.Wirth：Programming=Algorithm+DataStructure

程式設(shè)計(jì)=演算法+數(shù)據(jù)結(jié)構(gòu)1.4數(shù)據(jù)結(jié)構(gòu)與程式設(shè)計(jì)問題環(huán)境數(shù)據(jù)結(jié)構(gòu)程式結(jié)構(gòu)讀和寫

程序要完成的任務(wù)可執(zhí)行的操作程式結(jié)構(gòu)基於數(shù)據(jù)結(jié)構(gòu)的根源1.4數(shù)據(jù)結(jié)構(gòu)與程式設(shè)計(jì)

“我們對複雜性問題的最重要的辦法是抽象，對一個(gè)複雜問題，不應(yīng)馬上用電腦指令、數(shù)字與邏輯字來表示，而應(yīng)該用較為自然的抽象語句來表示，從而得出抽象程式。抽象程式對抽象的數(shù)據(jù)進(jìn)行某些特定的運(yùn)算並用某些合適的記號（可能是自然語言）來表示。對抽象程式作進(jìn)一步的分解，並進(jìn)入下一層的抽象，這樣的精細(xì)化過程一直進(jìn)行下去，直到程式能被電腦接受為止。此時(shí)的程式可能是某種高級語言或機(jī)器指令書寫的?！薄狽.wirth基於數(shù)據(jù)結(jié)構(gòu)的jackson設(shè)計(jì)方法：①研究問題環(huán)境，確定要處理的數(shù)據(jù)結(jié)構(gòu)②基於數(shù)據(jù)結(jié)構(gòu)，形成程式結(jié)構(gòu)（骨架）③用初等操作來定義要完成的任務(wù)，並分配初等操作“從上到下，逐步求精”演算法（Algorithm）：是對特定問題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。演算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說,就是電腦解題的過程。在這個(gè)過程中，無論是形成解題思路還是編寫程式,都是在實(shí)施某種演算法。前者是推理實(shí)現(xiàn)的演算法，後者是操作實(shí)現(xiàn)的演算法。PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibnM?saal-Khowarizm（約西元前825年）——從字面上看，這個(gè)名字的意思是“Ja'far的父親，Mohammed和M?sa的兒子，Khowarizm的本地人”。Khowarizm是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm寫了著名的書Kitabaljabrw'al-muqabala(《復(fù)原和化簡的規(guī)則》)；1.5演算法描述與演算法分析資料：Algorithm與Logarithm這個(gè)詞一直到1957年之前在Webster'sNewWorldDictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術(shù))，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程。在中世紀(jì)時(shí)，珠算家用算盤進(jìn)行計(jì)算，而算術(shù)家用算術(shù)進(jìn)行計(jì)算。中世紀(jì)之後，對這個(gè)詞的起源已經(jīng)拿不準(zhǔn)了，早期的語言學(xué)家試圖推斷它的來歷，認(rèn)為它是從把a(bǔ)lgiros(費(fèi)力的)+arithmos(數(shù)字)組合起來派生而成的，但另一些人則不同意這種說法，認(rèn)為這個(gè)詞是從“喀斯迪爾國王Algor”派生而來的。最後，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實(shí)起源：它來源於著名的PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibnM?saal-Khowarizm（約西元前825年）——從字面上看，這個(gè)名字的意思是“Ja'far的父親，Mohammed和M?sa的兒子，Khowarizm的本地人”。Khowarizm是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm寫了著名的書Kitabaljabrw'al-muqabala(《復(fù)原和化簡的規(guī)則》)；另一個(gè)詞，“algebra”(代數(shù))，是從他的書的標(biāo)題引出來的，儘管這本書實(shí)際上根本不是講代數(shù)的。逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個(gè)詞是由於同arithmetic(算術(shù))相混淆而形成的錯(cuò)拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學(xué)詞典VollstandigesMathematischesLexicon(《數(shù)學(xué)大全辭典》)，給出了Algorithmus(演算法)一詞的如下定義：“在這個(gè)名稱之下，組合了四種類型的算術(shù)計(jì)算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmusinfinitesimalis(無限小方法)，在當(dāng)時(shí)就用來表示Leibnitz(萊布尼茲)所發(fā)明的以無限小量進(jìn)行計(jì)算的微積分方法。1950年左右，algorithm一詞經(jīng)常地同歐幾裏德演算法(Euclid'salgorithm)聯(lián)繫在一起。這個(gè)演算法就是在歐幾裏德的《幾何原本》(Euclid'sElements,第VII卷，命題i和ii)中所闡述的求兩個(gè)數(shù)的最大公約數(shù)的過程(即輾轉(zhuǎn)相除法)。遞歸技術(shù)

——最常用的演算法設(shè)計(jì)思想，體現(xiàn)於許多優(yōu)秀演算法之中分治法

——分而制之的演算法思想，體現(xiàn)了一分為二的哲學(xué)思想模擬法

——用電腦模擬實(shí)際場景，經(jīng)常用於與概率有關(guān)的問題貪心演算法

——採用貪心策略的演算法設(shè)計(jì)狀態(tài)空間搜索法

——被稱為“萬能演算法”的演算法設(shè)計(jì)策略隨機(jī)演算法

——利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向動態(tài)規(guī)劃——常用的最優(yōu)化問題解決方法“好”的演算法的標(biāo)準(zhǔn)：

①正確性，演算法能滿足具體問題的需求

②可讀性，首先方便閱讀與交流，其次才是機(jī)器執(zhí)行

③健壯性，輸入錯(cuò)誤時(shí)，能作出反應(yīng)，避免異常出錯(cuò)

④效率與低存儲量要求演算法的特徵：

①有窮性、②確定性、③輸入、④輸出、⑤能行性對演算法“正確性”的要求：

①不含語法錯(cuò)誤；

②對於幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果；

③對精心選擇苛刻並帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果；

④對於一切合法的輸入均得到滿足要求的結(jié)果；演算法描述：

①自然語言；②程式設(shè)計(jì)語言；③類語言*；關(guān)於本書採用的類語言描述：

①結(jié)構(gòu)類型說明

②輸入輸出約定(cin>>v,cout<<v)

③new和delete

④引入引用類型

⑤其他影響演算法執(zhí)行的因素：

①演算法實(shí)現(xiàn)後所消耗的時(shí)間**②演算法實(shí)現(xiàn)後所占存儲空間的大小*③演算法是否易讀、易移植等等其他問題影響時(shí)間特性的四個(gè)因素：

①程式運(yùn)行時(shí)輸入數(shù)據(jù)的總量②對根源程式編譯所需的時(shí)間③電腦執(zhí)行每條指令所需的時(shí)間④程式中指令重複執(zhí)行的次數(shù)*[定義]語句頻度：語句重複執(zhí)行的次數(shù)程式運(yùn)行時(shí)間漸近時(shí)間複雜度（時(shí)間複雜度）T（n）

演算法中基本操作重複執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），演算法的時(shí)間度量記作：

T（n）=O（f（n））它表示隨問題規(guī)模n的增大，演算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同。漸近空間複雜度（空間複雜度）S（n）S（n）=O（g（n））運(yùn)算法則：設(shè)：T1(n)=O(f(n))，T2(n)=O(g(n))

加法規(guī)則：T1(n)+T2(n)=O(max{f(n),g(n)})

乘法規(guī)則：T1(n)·T2(n)=O(f(n)·g(n))程式運(yùn)行時(shí)間比較T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△T(n)設(shè)：T(x)：取變數(shù)或常量x之值所消耗時(shí)間T(.V)：取變數(shù)V之地址所消耗的時(shí)間T(=)：賦值所消耗時(shí)間T(θ)：執(zhí)行基本運(yùn)算θ所耗時(shí)間T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時(shí)間T(par)：將參數(shù)par傳給函數(shù)所消耗時(shí)間～(1)運(yùn)算式和賦值語句

exp::=常數(shù)|變數(shù)|F-name(e1,e2,…,em)|(expθexp)T(v=exp)=T(.v)+T(=)+T(exp)T(expθ

exp)=T(exp)+T(θ)+T(exp)

T(F-name(e1,e2,…,em))=T(call/return)+mT(par)+T(F-body)

例：

T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)

相應(yīng)的組合語言程式為：

loadainR1loadbinR2addR2toR1load.cinR2storeR1inR2～～通常取O(1)(2)語句序列

T(s1,s2,…,sk)=max{T(s1),T(s2),…,T(sk))(3)條件語句

T(if(B)s1elses2)=T(B)+T(else)+max{T(s1),T(s2)}

通常取T(B)+T(else)=O(1)T(if(B)s)=O(1)+T(s)(4)Switch語句設(shè)語句sswitch(E){caseE1:S1;…caseEk:Sk;default:Sm}T(s)=T(E)+∑T(Ei)+max{T(s1),…,T(sk),T(sm)}

O(1)ki=1(5)for語句

T(for(i=1;i<=n;i++)s)=∑(T(s)+T(i=1)+T(i<=n)+T(i++)+T(for))O(1)(6)while語句

while(B)si=0;while(B){s;i++}

設(shè)RT0表示某一次迴圈開始執(zhí)行時(shí)的絕對時(shí)間關(guān)於迴圈的定時(shí)不變式RT為

RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j))

其中：T(while)代表測試迴圈終止條件所耗時(shí)間

T(j)代表跳回迴圈頭所耗時(shí)間可簡化成：T(j)=T(while)T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while)(7)函數(shù)調(diào)用非遞歸調(diào)用：∑被調(diào)用子函數(shù)運(yùn)行時(shí)間遞歸調(diào)用：求解遞歸方程(8)goto語句

goto語句破壞了程式結(jié)構(gòu)一般對goto語句限制使用對有條件的goto轉(zhuǎn)移可忽略不計(jì)舉例：

①s=0;→f(n)=1;T1(n)=O(f(n))=O(1)常量階

②for(i=1;i<=n;++i){++x;s+=x;}→f(n)=3n+1;T2(n)=O(f(n))=O(n)線性階

③for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}→f(n)=3n2+2n+1;T3(n)=O(f(n))=O(n2)平方階

④for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}→f(n)=2n3+3n2+2n+1;T4(n)=O(f(n))=O(n3)立方階VoidBUBBLE(A)intA[n];{intI,j,temp;for(i=0;i<n-1;i++)for(j=n-1;j>=i+1;j--)O(∑(n-i-1))if(A[j-1]>A[j]){O((n-i-1)×1)≤O(n(n-1)/2)temp=A[j-1];O(1)O(1)=(n-i-1)=O(n2)A[j-1]=A[j];O(1)O(1)A[j]=temp;O(1)}}n-2i=0舉例：

⑤Longfact

(intn)

{if(n==0)||(n==1)return(1);elsereturn(n*fact(n–1));}f(n)=C當(dāng)n=0,n=1G+f(n–1)當(dāng)n>1f(n)=G1+f(n–1)f(n–1)=G2+f(n–2)f(n–2)=G3+f(n–3)……f(2)=Gn-1+f(1)+f(1)=Cf(n)=G1+G2+G3+……+Gn-1+Cf(n)=nG’∴T(n)=O(f(n))=O(n)數(shù)據(jù)結(jié)構(gòu)基本思路

數(shù)學(xué)模型ADT抽象數(shù)據(jù)型操作邏輯結(jié)構(gòu)存儲結(jié)構(gòu)特殊結(jié)構(gòu)結(jié)構(gòu)應(yīng)用舉例

解決問題的演算法型●線性表線性結(jié)構(gòu)樹及二元樹層次結(jié)構(gòu)圖網(wǎng)狀結(jié)構(gòu)三大數(shù)據(jù)結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表樹圖2.1抽象數(shù)據(jù)型線性表[定義]

線性表是由n(n≥0)個(gè)相同類型的元素組成的有序集合。記為：

(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n為線性表中元素個(gè)數(shù)，稱為線性表的長度；當(dāng)n=0時(shí)，為空表，記為（）。②ai為線性表中的元素，類型定義為elementtype③a1為表中第1個(gè)元素，無前驅(qū)元素；an為表中最後一個(gè)元素，無後繼元素；對於…ai-1,ai,ai+1…(1<i<n)，稱ai-1

為ai的直接前驅(qū)，ai+1為ai的直接後繼。④線性表是有限的，也是有序的。線性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：設(shè)L的型為LIST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變數(shù)。所有操作描述為：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數(shù)學(xué)模型舉例：設(shè)計(jì)函數(shù)DELEVAL（LIST&L,elementtyped)其功能為刪除L中所有值為d的元素。

VoidDELEVAL(LIST&L,elementtyped){positionp;p=FIRST(L);while(P!=END(L)){if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);}}2.2線性表的實(shí)現(xiàn)問題：確定數(shù)據(jù)結(jié)構(gòu)（存儲結(jié)構(gòu)）實(shí)現(xiàn)型LIST，並在此基礎(chǔ)上實(shí)現(xiàn)各個(gè)基本操作。存儲結(jié)構(gòu)的三種方式：①連續(xù)的存儲空間（數(shù)組）→靜態(tài)存儲②非連續(xù)存儲空間——指針（鏈表）→動態(tài)存儲③游標(biāo)（連續(xù)存儲空間+動態(tài)管理思想）→靜態(tài)鏈表2.2.1指針和游標(biāo)指針：地址量，其值為另一存儲空間的地址；游標(biāo)：整型量，其值為數(shù)組的下標(biāo)，用以表示指定元素的“地址”或“位置”2.2.2線性表的數(shù)組實(shí)現(xiàn)

第1個(gè)元素第2個(gè)元素

……

最後1個(gè)元素……012maxlength-1last表空單元圖2-1線性表的數(shù)組實(shí)現(xiàn)表的最大長度

……第i個(gè)元素1≤i≤last類型定義：#definemaxlength100structLIST{elementtypedata[maxlength];intlast;};位置類型：

typedefintposition;線性表L:LISTL;操作：①VoidINSERT(elementtypex,positionp,LIST&L){positionq;if(L.last>=maxlength–1)error(“表滿”)；

elseif((P>L.last+1)||(p<1))error(“指定位置不存在”)；

else{for(q=L.last;q>=p;q--)L.data[q+1]=L.data[q];L.last=L.last+1;L.data[p]=x;}}②positionLOCATE(elementtypex,LISTL){positionq;for(q=1;q<=L.last;q++)if(L.data[q]==x)return(q);return(L.last+1);}③elementtypeRETRIEVE(positionp,LISTL){if(p>L.last)error(“指定元素不存在”);elsereturn(L.data[p]);}④VoidDELETE(positionp,LIST&L){positionq;if((p>L.last)||(p<1))error(“指定位置不存在”)；

else{L.last=L.last–1;for(q=p;q<=L.last;q++)L.data[q]=L.data[q+1];}}⑤positionPREVIOUS(positionp,LISTL){if((p<=1)||(p>L.last))error(“前驅(qū)元素不存在”);elsereturn(p–1);}⑧positionEND(LISTL){return(L.last+1);}⑦

positionFIRST(LISTL){return(1);}positionNEXT(positionp,LISTL){if((p<1)||(p>=L.last))error(“前驅(qū)元素不存在”);elsereturn(p+1);}⑥

positionMAKENULL(LIST&L){L.last=0;return(L.last+1);}

2.2.3線性表的指針實(shí)現(xiàn)結(jié)點(diǎn)形式datanext結(jié)點(diǎn)資訊下一結(jié)點(diǎn)地址NODE結(jié)點(diǎn)類型structNODE{elementtypedata;structNODE*next;};typedefNODE*LIST;typedefNODE*position;LISTheader;positionp,q;a1a2a3an∧…h(huán)eaderqpa2:(*p).data;q:(*p).next;a2:p->data;q:p->next;記法:操作討論：插入元素:pa1xheaderqai-1aixpqan∧x∧qp(a)表頭插入元素(b)中間插入元素(c)表尾插入元素q=newNODE;q->data=x;q->next=p->next;p→next=q;或:temp=p->next;P->next=newNODE;P->next->data=x;P->next->next=temp;討論表頭結(jié)點(diǎn)的作用操作討論：刪除元素:q=p->next;P->next=q->next;deleteq;或：q=p->next;P->next=p->next->next;deleteq;討論結(jié)點(diǎn)ai的位置pa1header(a)刪除第一個(gè)元素a2qpai-1aipq(b)刪除中間元素ai+1an∧an-1qp(c)刪除表尾元素∧ADT操作：①positionEND(LIST){positionq;q=L;while(q→next!=NULL)q=q→next;return(q);};②VoidINSERT(elementtypex,positionp,LIST&L){positionq;q=newNODE;q→data=x;q→next=p→next;p→next=q;}③positionLOCATE(elementtypex,LISTL){positionp;p=L;while(p→next!=NULL)if(p→next→data==x)returnp;elsep=p→next;returnp;}④elementtypeRETRIEVE(positionp,LISTL){return(p→next→data);}⑤VoidDELETE(positionp,LIST&L){positionq;if(p→next!=NULL){q=p→next;p→next=q→next;deleteq;}};⑥positionPREVIOUS(positionp,LISTL){positionq;if(p==L→next)error(“不存在前驅(qū)元素”)；

else{q=L;while(q→next!=p)q=q→next;returnq;}}⑦positionNEXT(positionp,LISTL){positionq;if(p→next==NULL)error(“不存在後繼元素”)；

else{q=p→next;returnq;}}⑧positionMAKENULL(LIST&L){L=newNODE;L→next=NULL;returnL;}⑨positionFIRST(LISTL){returnL;}舉例：遍曆線性鏈表，按照線性表中元素的順序，依次訪問表中的每一個(gè)元素，每個(gè)元素只能被訪問一次。VoidVISITE(LISTL){positionp;p=L→next;while(p!=NULL){cout<<p→data;p=p→next;}}線性表靜態(tài)存儲與動態(tài)存儲的比較比較參數(shù)←表的容量→←存取操作→←時(shí)間→←空間→…鏈?zhǔn)酱鎯`活，易擴(kuò)充順序存取訪問元素費(fèi)時(shí)間實(shí)際長度，節(jié)省空間…順序存儲固定，不易擴(kuò)充隨機(jī)存取插入刪除費(fèi)時(shí)間估算表長度，浪費(fèi)空間…2.2.4線性表的游標(biāo)實(shí)現(xiàn)結(jié)點(diǎn)形式datanext結(jié)點(diǎn)資訊下一結(jié)點(diǎn)位置spacestr結(jié)點(diǎn)類型structspacestr{elementtypedata;intnext;};線性表：spacestrSPACE[maxsize];typedefintposition;元素：SPACE[i].data→“型”為elementtype(基本、複合)下一元素位置：SPACE[i].next→“型”為int類似指針鏈表，對游標(biāo)實(shí)現(xiàn)的線性表仍設(shè)表頭結(jié)點(diǎn)。d65c-1--0a108e-1--4-1--11b21210123456789101112SPACE73LM9available線性表：

L=(a,b,c)L=7M=(d,e)M=3空閒表：available=9q=newspacestr;q=SPACE[available].next;SPACE[available].next=SPACE[q].next;deleteq;SPACE[q].next=SPACE[available].next;SPACE[available].next=q;①VoidINSERT(elementtypex,positionp,spacestr*SPACE){positionq;q=newspacestr;SPACE[q].data=x;SPACE[q].next=SPACE[p].next;SPACE[p].next=q;}②VoidDELETE(positionp,spacestr*SPACE){positionq;if(SPACE[p].next!=-1){SPACE[q]=SPACE[p].next;SPACE[p].next=SPACE[q].next;deleteq;}};操作：2.2.5雙向鏈表結(jié)點(diǎn)形式datanext結(jié)點(diǎn)資訊後繼結(jié)點(diǎn)指針dcelltypeprevious前驅(qū)結(jié)點(diǎn)指針結(jié)點(diǎn)類型

structdnodetype{elementtypedata;dnodetype*next,*previous;};typedefdnodetype*DLIST;typedefdnodetype*position;ai-1

ai

ai+1

p刪除位置p的元素：p→previous→next=p→next;p→next→previous=p→previous;

∧header

an

∧tail操作：VoidINSERT(elementtypex,positionp,DLIST&L)；{positionq;q=newdnodetype;q→data=x;P→previous→next=q;q→previous=p→previous;q→next=p;p→previous=q;};討論：元素的位置？2.2.6環(huán)形鏈表單向線性鏈表雙向線性鏈表單向迴圈鏈表雙向迴圈鏈表對線性鏈表的改進(jìn)，解決“單向操作”的問題；改進(jìn)後的鏈表，能夠從任意位置元素開始，訪問表中的每一個(gè)元素。單向環(huán)形鏈表：a1a2a3an…R

其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識鏈表，從而省去了表頭結(jié)點(diǎn)。表頭：R→next(亦即表中的一個(gè)元素a1)操作：①在表左端插入結(jié)點(diǎn)INSERT(x,FIRST(R),R);→LINSERT(x,R)VoidLINSERT(elementtypex,LIST&R){celltype*p;p=newNODE;p→data=x;if(R==NULL){p→next=p;R=p;}else{p→next=R→next;R→next=p;}};②在表右端插入結(jié)點(diǎn)INSERT(x,END(R),R);→RINSERT(x,R)VoidRINSERT(elementtypex,LISTR){LINSERT(x,R);R=R→next;}③從表左端刪除結(jié)點(diǎn)DELETE(FIRST(R),R);→LDELETE(R)VoidLDELETE(LIST&R){structNODE*p;if(R==NULL)error(“空表”);else{p=R→next;R→next=p→next;if(p==R)R=NULL;deletep;}};雙向環(huán)形鏈表：a1

ai

an

……R

雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同，只是將表頭元素的空previous域指向表尾，同時(shí)將表尾的空next域指向表頭結(jié)點(diǎn)，從而形成向前和向後的兩個(gè)環(huán)形鏈表，對鏈表的操作變得更加靈活。a1a2a3an…Ranan-1an-2a1…RVoidREVERS(LIST&R){positionp,q;p=R→next;R→next=p→next;p→next=p;while(R!=NULL){q=R→next;R→next=q→next;q→next=p→next;p→next=q;}R=p;}；演算法如下：舉例：設(shè)計(jì)演算法，將一個(gè)單向環(huán)形鏈表反向。頭元素變成尾元素，尾元素變成新的頭元素，依次類推。2.3棧（Stack）

棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對線性表的操作加以限制後，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。定義：是限定只在表尾進(jìn)行插入和刪除操作的線性表。棧又稱為後進(jìn)先出(LastInFirstOut)的線性表。簡稱LIFO結(jié)構(gòu)。棧舉例a1a2······an-1anInsertDeletetopbottom棧底棧頂棧示意圖棧的基本①M(fèi)AKENULL(S)

操作②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)例2：利用棧實(shí)現(xiàn)行編輯處理。設(shè)定符號“#”為擦訖符，用以刪除“#”前的字元；符號“@”為刪行符，用以刪除當(dāng)前編輯行。原理：一般字元進(jìn)棧；讀字元擦訖符退棧；刪行符則清棧演算法：VoidLINEEDIT(){STACKＳ；

charc;MAKENULL(S);c=getchar();while(c!=‘\n’){if(c==‘#’)POP(S);elseif(c==‘@’)MAKENULL(S);elsePUSH(c,S);c=getchar();}

逆序輸出棧中所有元素；｝2.3.1棧的實(shí)現(xiàn)1、順序存儲順序棧示意圖an···ai···a3a2a1---maxlength-1······3210top結(jié)構(gòu)類型：

typedefstruct{elementtypedata[maxlength];inttop;}STACK;STACKS;棧的容量：maxlength–1;?？眨篠.top=0;棧滿：S.top=maxlength–1;棧頂元素：S.data[S.top];操作：①VoidMAKENULL(STACK&S){S.top=0;};②BooleanEMPTY(STACKS){if(S.top<1)returnTRUEelsereturnFALSE;};③elementtypeTOP(STACKS){ifEMPTY(S)returnNULL;elsereturn(S.data[S.top]);};操作：④elementtypePOP(STACK&S){if(EMPTY(S))error(“棧空”);elseS.top=S.top–1;};⑤VoidPUSH(elementtypex,STACK&S){if(S.top==maxlength-1)error(“棧滿”);else{S.top=S.top+1;S.data[S.top]=x;}};2、鏈?zhǔn)酱鎯?/p>

採用由指針形成的線性鏈表來實(shí)現(xiàn)棧的存儲,要考慮鏈表的哪一端實(shí)現(xiàn)元素的插入和刪除比較方便。實(shí)現(xiàn)的方式如右圖所示，其操作與線性鏈表的表頭插入和刪除元素相同。anan-1a2······a1∧top3、多個(gè)棧共用一個(gè)存儲空間的討論STACK[maxlength]bot[1]top[1]bot[2]top[2]bot[3]top[3]top[2]bot[n]top[n]············0Maxlength-1bot[n+1]bot[i]top[i]IntIs_Stack_i_Full(STACKS,intbot,inttop,inti)/*判斷第i個(gè)棧是否滿，滿返回1，否則返回0*/{……}VoidMove_Stack_i(STACK&S,int&bot,int&top,inti,intdt)/*移動第i個(gè)棧，dt為位移量*/{……}…CallB…主程序A…CallC…主程序B…CallD…主程序C……i…主程序DBeginEndDaDaDbDcDbDc棧入棧出棧例1：副程式的嵌套調(diào)用2.3.2棧的應(yīng)用1、棧和遞歸過程調(diào)用Bα

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβ

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβγ

βγδ調(diào)用C調(diào)用BABC棧A的返回點(diǎn)(1)副程式A正在執(zhí)行(2)A調(diào)用B，B在執(zhí)行(3)B調(diào)用C，C在執(zhí)行先進(jìn)先出的規(guī)則：在執(zhí)行的任何點(diǎn)處，若一個(gè)程式要將控制返回到調(diào)用程式，則該程式一定是最末一個(gè)進(jìn)入的。例2：間接遞歸3個(gè)程式A、B、C，其中A調(diào)用B，B調(diào)用C，而C又遞歸調(diào)用B。調(diào)用Bαβ

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβγ

βγδ調(diào)用C調(diào)用BABC棧(6)C返回到B，（第一次調(diào)用）

B在