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

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

andAlgorithm1.1數(shù)據(jù)結(jié)構(gòu)研究對(duì)象◆計(jì)算機(jī)科學(xué)：信息在計(jì)算機(jī)內(nèi)使用數(shù)據(jù)來(lái)表示,

研究信息表示和信息處理。◆數(shù)據(jù)：是用以描述客觀事物的數(shù)值、字符，以及一切可以輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序加以處理的符號(hào)的集合。數(shù)據(jù)的基本單位稱(chēng)為數(shù)據(jù)元素?cái)?shù)據(jù)的最小單位稱(chēng)為數(shù)據(jù)項(xiàng)◆數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合◆數(shù)據(jù)特征：數(shù)值、文本、多媒體、超媒體、實(shí)時(shí)、海量◆數(shù)據(jù)類(lèi)型?高級(jí)語(yǔ)言中變量的取值范圍和允許的操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

非順序映象，或稱(chēng)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)計(jì)算機(jī)解題過(guò)程：?jiǎn)栴}→數(shù)學(xué)模型→算法→程序→測(cè)試→計(jì)算分析數(shù)據(jù)并確定存儲(chǔ)結(jié)構(gòu)輸入到計(jì)算機(jī)中1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況●數(shù)據(jù)結(jié)構(gòu)側(cè)重解決非數(shù)值問(wèn)題■FORTRAN,ALGOL等高級(jí)語(yǔ)言是以程序?yàn)橹行膫?cè)重于解決數(shù)值問(wèn)題■LISP,SONBOL表或串處理語(yǔ)言是以數(shù)據(jù)為中心側(cè)重于解決非數(shù)值問(wèn)題●1968年以前，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容大多包含在形如表、樹(shù)、圖論、集合代數(shù)論、格、關(guān)系等方面。1968年開(kāi)始，“數(shù)據(jù)結(jié)構(gòu)”逐漸開(kāi)始成為獨(dú)立的一門(mén)課程。●作為一門(mén)專(zhuān)業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專(zhuān)業(yè)的核心課程之一，是其他專(zhuān)業(yè)課的基礎(chǔ)。是數(shù)學(xué)、硬件和軟件三者的交叉，很受重視。■從PASCAL語(yǔ)言開(kāi)始逐漸形成二者結(jié)合知識(shí)結(jié)構(gòu)1.3抽象數(shù)據(jù)型AbstractDataTypes（ADT）

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

的操作的集合ADT特點(diǎn)：①降低了軟件設(shè)計(jì)的復(fù)雜性②提高了程序的可讀性和可維護(hù)性③程序的正確性容易保證抽象：從眾多事物中舍棄個(gè)別的、非本質(zhì)的屬性，抽出共同的、本質(zhì)性的特征。是形成概念的重要手段，其目的是使復(fù)雜度降低。線性表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的型為L(zhǎng)IST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變量。所有操作描述為：①I(mǎi)NSERT(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）舉例㈠定義任意線性表類(lèi)型為L(zhǎng)IST，其中元素類(lèi)型為Elementtype，設(shè)有線性表L，函數(shù)PURGE用以刪除線性表L中所有重復(fù)出現(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)，不自相矛盾△通用性：適用于盡量廣泛的對(duì)象△不依賴(lài)性：不依賴(lài)于程序設(shè)計(jì)語(yǔ)言，可以用任意的語(yǔ)言來(lái)描述規(guī)格描述的兩個(gè)方面:語(yǔ)法和語(yǔ)義△語(yǔ)法：給出操作的名稱(chēng)、I/O參數(shù)的數(shù)目和類(lèi)型△語(yǔ)義：由一組等式組成，定義各種操作的功能及相互間的關(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ù)型——棧語(yǔ)法：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ù)型——棧語(yǔ)義：

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

②有盡可能好的通用性

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

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

①限制使用GOTO語(yǔ)句（基于三種基本結(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ì)問(wèn)題環(huán)境數(shù)據(jù)結(jié)構(gòu)程序結(jié)構(gòu)讀和寫(xiě)

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

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

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

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

——用計(jì)算機(jī)模擬實(shí)際場(chǎng)景，經(jīng)常用于與概率有關(guān)的問(wèn)題貪心算法

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

——被稱(chēng)為“萬(wàn)能算法”的算法設(shè)計(jì)策略隨機(jī)算法

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

①正確性，算法能滿(mǎn)足具體問(wèn)題的需求

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

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

④效率與低存儲(chǔ)量要求算法的特征：

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

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

②對(duì)于幾組輸入數(shù)據(jù)能得到滿(mǎn)足要求的結(jié)果；

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

④對(duì)于一切合法的輸入均得到滿(mǎn)足要求的結(jié)果；算法描述：

①自然語(yǔ)言；②程序設(shè)計(jì)語(yǔ)言；③類(lèi)語(yǔ)言*；關(guān)于本書(shū)采用的類(lèi)語(yǔ)言描述：

①結(jié)構(gòu)類(lèi)型說(shuō)明

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

③new和delete

④引入引用類(lèi)型

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

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

①程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量②對(duì)源程序編譯所需的時(shí)間③計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間④程序中指令重復(fù)執(zhí)行的次數(shù)*[定義]語(yǔ)句頻度：語(yǔ)句重復(fù)執(zhí)行的次數(shù)程序運(yùn)行時(shí)間漸近時(shí)間復(fù)雜度（時(shí)間復(fù)雜度）T（n）

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

T（n）=O（f（n））它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率相同。漸近空間復(fù)雜度（空間復(fù)雜度）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)：取變量或常量x之值所消耗時(shí)間T(.V)：取變量V之地址所消耗的時(shí)間T(=)：賦值所消耗時(shí)間T(θ)：執(zhí)行基本運(yùn)算θ所耗時(shí)間T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時(shí)間T(par)：將參數(shù)par傳給函數(shù)所消耗時(shí)間～(1)表達(dá)式和賦值語(yǔ)句

exp::=常數(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)的匯編程序?yàn)椋?/p>

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

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

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語(yǔ)句設(shè)語(yǔ)句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語(yǔ)句

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

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

設(shè)RT0表示某一次循環(huán)開(kāi)始執(zhí)行時(shí)的絕對(duì)時(shí)間關(guān)于循環(huán)的定時(shí)不變式RT為

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

其中：T(while)代表測(cè)試循環(huán)終止條件所耗時(shí)間

T(j)代表跳回循環(huán)頭所耗時(shí)間可簡(jiǎn)化成：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語(yǔ)句

goto語(yǔ)句破壞了程序結(jié)構(gòu)一般對(duì)goto語(yǔ)句限制使用對(duì)有條件的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)存儲(chǔ)結(jié)構(gòu)特殊結(jié)構(gòu)結(jié)構(gòu)應(yīng)用舉例

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

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

(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n為線性表中元素個(gè)數(shù)，稱(chēng)為線性表的長(zhǎng)度；當(dāng)n=0時(shí)，為空表，記為（）。②ai為線性表中的元素，類(lèi)型定義為elementtype③a1為表中第1個(gè)元素，無(wú)前驅(qū)元素；an為表中最后一個(gè)元素，無(wú)后繼元素；對(duì)于…ai-1,ai,ai+1…(1<i<n)，稱(chēng)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的型為L(zhǎng)IST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變量。所有操作描述為：①I(mǎi)NSERT(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)問(wèn)題：確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)型LIST，并在此基礎(chǔ)上實(shí)現(xiàn)各個(gè)基本操作。存儲(chǔ)結(jié)構(gòu)的三種方式：①連續(xù)的存儲(chǔ)空間（數(shù)組）→靜態(tài)存儲(chǔ)②非連續(xù)存儲(chǔ)空間——指針（鏈表）→動(dòng)態(tài)存儲(chǔ)③游標(biāo)（連續(xù)存儲(chǔ)空間+動(dòng)態(tài)管理思想）→靜態(tài)鏈表2.2.1指針和游標(biāo)指針：地址量，其值為另一存儲(chǔ)空間的地址；游標(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)表的最大長(zhǎng)度

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

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

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)類(lèi)型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;}舉例：遍歷線性鏈表，按照線性表中元素的順序，依次訪問(wèn)表中的每一個(gè)元素，每個(gè)元素只能被訪問(wèn)一次。VoidVISITE(LISTL){positionp;p=L→next;while(p!=NULL){cout<<p→data;p=p→next;}}線性表靜態(tài)存儲(chǔ)與動(dòng)態(tài)存儲(chǔ)的比較比較參數(shù)←表的容量→←存取操作→←時(shí)間→←空間→…鏈?zhǔn)酱鎯?chǔ)靈活，易擴(kuò)充順序存取訪問(wèn)元素費(fèi)時(shí)間實(shí)際長(zhǎng)度，節(jié)省空間…順序存儲(chǔ)固定，不易擴(kuò)充隨機(jī)存取插入刪除費(fèi)時(shí)間估算表長(zhǎng)度，浪費(fèi)空間…2.2.4線性表的游標(biāo)實(shí)現(xiàn)結(jié)點(diǎn)形式datanext結(jié)點(diǎn)信息下一結(jié)點(diǎn)位置spacestr結(jié)點(diǎn)類(lèi)型structspacestr{elementtypedata;intnext;};線性表：spacestrSPACE[maxsize];typedefintposition;元素：SPACE[i].data→“型”為elementtype(基本、復(fù)合)下一元素位置：SPACE[i].next→“型”為int類(lèi)似指針鏈表，對(duì)游標(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)類(lèi)型

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)形鏈表單向線性鏈表雙向線性鏈表單向循環(huán)鏈表雙向循環(huán)鏈表對(duì)線性鏈表的改進(jìn)，解決“單向操作”的問(wèn)題；改進(jìn)后的鏈表，能夠從任意位置元素開(kāi)始，訪問(wèn)表中的每一個(gè)元素。單向環(huán)形鏈表：a1a2a3an…R

其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識(shí)鏈表，從而省去了表頭結(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)形鏈表，對(duì)鏈表的操作變得更加靈活。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)形鏈表反向。頭元素變成尾元素，尾元素變成新的頭元素，依次類(lèi)推。2.3棧（Stack）

棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對(duì)線性表的操作加以限制后，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。定義：是限定只在表尾進(jìn)行插入和刪除操作的線性表。棧又稱(chēng)為后進(jìn)先出(LastInFirstOut)的線性表。簡(jiǎn)稱(chēng)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è)定符號(hào)“#”為擦訖符，用以刪除“#”前的字符；符號(hào)“@”為刪行符，用以刪除當(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、順序存儲(chǔ)順序棧示意圖an···ai···a3a2a1---maxlength-1······3210top結(jié)構(gòu)類(lèi)型：

typedefstruct{elementtypedata[maxlength];inttop;}STACK;STACKS;棧的容量：maxlength–1;?？眨篠.top=0;棧滿(mǎn)：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(“棧滿(mǎn)”);else{S.top=S.top+1;S.data[S.top]=x;}};2、鏈?zhǔn)酱鎯?chǔ)

采用由指針形成的線性鏈表來(lái)實(shí)現(xiàn)棧的存儲(chǔ),要考慮鏈表的哪一端實(shí)現(xiàn)元素的插入和刪除比較方便。實(shí)現(xiàn)的方式如右圖所示，其操作與線性鏈表的表頭插入和刪除元素相同。anan-1a2······a1∧top3、多個(gè)棧共用一個(gè)存儲(chǔ)空間的討論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è)棧是否滿(mǎn)，滿(mǎn)返回1，否則返回0*/{……}VoidMove_Stack_i(STACK&S,int&bot,int&top,inti,intdt)/*移動(dòng)第i個(gè)棧，dt為位移量*/{……}…CallB…主程序A…CallC…主程序B…CallD…主程序C……i…主程序DBeginEndDaDaDbDcDbDc棧入棧出棧例1：子程序的嵌套調(diào)用2.3.2棧的應(yīng)用1、棧和遞歸過(guò)程調(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在執(zhí)行，C執(zhí)行完畢成(5)B返回到C，C