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

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

數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第1頁。1.1算法算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第2頁。一.算法的基本特征可行性:執(zhí)行后能得到滿意結(jié)果。確定性:算法中每個(gè)步驟必須明確定義，不允許多義性。有窮性:算法必須在有限時(shí)間內(nèi)做完。擁有足夠的情報(bào):確保算法有效還取決于情報(bào)是否足夠。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第3頁。二.算法的基本要素算法對(duì)數(shù)據(jù)的運(yùn)算和操作：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu):順序、選擇、循環(huán)數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第4頁。四.算法復(fù)雜度算法的時(shí)間復(fù)雜度執(zhí)行算法所需要的計(jì)算工作量算法的空間復(fù)雜度執(zhí)行算法所需要的內(nèi)存空間數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第5頁。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究以下三個(gè)方面的問題:P71.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。2.在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中在存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。3.對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第6頁。一.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。更通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。P11一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩個(gè)方面的信息：元素的信息數(shù)據(jù)元素之間的前后件關(guān)系。所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。前后件：前驅(qū)、后件。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第7頁。二.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是在計(jì)算機(jī)存儲(chǔ)空間的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第8頁。三.數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCDEF其中D稱為是E的前件,C的后件.其他相同.父親兒子女兒其中“父親”是“兒子”和“女兒”的前件，“兒子”和“女兒”是“父親”的后件。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第9頁。四.線性結(jié)構(gòu)和非線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu):一個(gè)元素都沒有。數(shù)據(jù)結(jié)構(gòu)一般分為:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非空線性結(jié)構(gòu)滿足:有且只有一個(gè)根節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)最多有一個(gè)前件節(jié)點(diǎn)、也最多有一個(gè)后件節(jié)點(diǎn)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第10頁。1.3線性表與順序存儲(chǔ)結(jié)構(gòu)

線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是n(n>=0)個(gè)元素構(gòu)成的有限序列(a1,a2,……an)。(1)有且只有一個(gè)根結(jié)點(diǎn)a1,它無前件；(2)有且只有一個(gè)終端結(jié)點(diǎn)an,它無后件；(3)其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的長度,當(dāng)n=0時(shí)，稱為空表.數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第11頁。一.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表在計(jì)算機(jī)中采用順序存儲(chǔ)。線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)特點(diǎn):線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第12頁。二.線性表的插入運(yùn)算線性表為:(a1,a2

…ai-1,ai,ai+1…an)在第i個(gè)位置之前上插入新的結(jié)點(diǎn)x:線性表變?yōu)?(a1,a2

…ai-1,x,ai,ai+1…an)長度變?yōu)閚+1。在最好的情況下,不需要移動(dòng)表中的元素。在最壞的情況下,需要移動(dòng)表中的所有元素。在平均情況下,需要移動(dòng)表中一半的元素。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第13頁。三.線性表的刪除運(yùn)算線性表為:(a1,a2

……ai-1,ai,ai+1……an)在第i個(gè)位置上刪除新的結(jié)點(diǎn)ai:線性表變?yōu)?(a1,a2

……ai-1,ai+1……an)長度變?yōu)閚-1。在最好的情況下,不需要移動(dòng)表中的元素。在最壞的情況下,需要移動(dòng)表中的所有元素。在平均情況下,需要移動(dòng)表中一半的元素。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第14頁。1.4棧和隊(duì)列1.什么是棧？棧是限定在一端進(jìn)行插入和刪除運(yùn)算的線性表。允許插入與刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。假設(shè)棧s=(a1,a2,……an),則a1稱為棧底元素，an成為棧頂元素。棧也稱為先進(jìn)后出或后進(jìn)先出的線性表。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第15頁。1.4棧和隊(duì)列anan-1…a2a1進(jìn)棧退棧topbottom棧:后進(jìn)先出表數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第16頁。1.4棧和隊(duì)列2.棧的順序存儲(chǔ)及其運(yùn)算P21

棧空棧滿正常dcbagfedcba進(jìn)棧時(shí)會(huì)發(fā)生上溢錯(cuò)誤退棧時(shí)會(huì)發(fā)生下溢錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第17頁。1.4棧和隊(duì)列1.什么是隊(duì)列

隊(duì)列是指只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭.假設(shè)隊(duì)列q=(a1,a2,……an),則a1稱為隊(duì)頭元素，an成為隊(duì)尾元素。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第18頁。隊(duì)列(queue)的運(yùn)算示意ABCD一個(gè)隊(duì)列插入(入隊(duì))刪除(退隊(duì))BCDABCDEfrontrearfrontfrontrearrear數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第19頁。1.4棧和隊(duì)列2.循環(huán)隊(duì)列及其算法循環(huán)隊(duì)列：將隊(duì)列的存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。m…21frontrear數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第20頁。1.4棧和隊(duì)列frontrear123n分析可知：當(dāng)front=rear時(shí)，不能確定循環(huán)隊(duì)列是空還是滿，于是需要要一個(gè)標(biāo)記S,用來判斷隊(duì)列的狀態(tài):S=0

表示隊(duì)列為空S=1

表示隊(duì)列為非空由此得出：隊(duì)列為空的條件是:s=0隊(duì)列為滿的條件是:s=1且front=rear數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第21頁。1.5線性鏈表1.什么是鏈?zhǔn)酱鎯?chǔ)？線性表順序存儲(chǔ)的缺點(diǎn)：插入刪除時(shí)移動(dòng)大量元素；有“上溢”情況；空間不便于動(dòng)態(tài)分配。在鏈?zhǔn)酱鎯?chǔ)方式中,每個(gè)結(jié)點(diǎn)有兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱為數(shù)據(jù)域；另一部分存放指針,稱為指針域。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的.數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第22頁。2.線性單鏈表在線性單鏈表中,結(jié)點(diǎn)的數(shù)據(jù)域存放數(shù)據(jù)元素的值,指針域存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào),即指向后件結(jié)點(diǎn).V(i)Next(i)數(shù)據(jù)域指針域

數(shù)據(jù)1

數(shù)據(jù)nnull

數(shù)據(jù)2HEAD…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第23頁。1B1023A1456D878E910C6ABCDE1110106688數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第24頁。3.線性雙向鏈表在線性單鏈表中從一個(gè)結(jié)點(diǎn)只能找到它的下一個(gè)結(jié)點(diǎn),但找不到前一個(gè)結(jié)點(diǎn).為解決這一問題,將線性鏈表中每一個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針:左指針和右指針.這樣的鏈表稱為雙向鏈表.00head…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第25頁。4.帶鏈的棧和隊(duì)列P27(1)棧也是線性表。帶鏈的棧稱為可利用棧。(2)隊(duì)列也是線性表。也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。topa10an-1an…an0a2a1…frontrear數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第26頁。5.線性鏈表的基本運(yùn)算插入：刪除：合并：分解：逆轉(zhuǎn)：復(fù)制：排序：查找：數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第27頁。(1).在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值x的前一個(gè)結(jié)點(diǎn)p的基本方法:從頭結(jié)點(diǎn)指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描,直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止.數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第28頁。(2).線性鏈表的插入線性鏈表插入過程中不發(fā)生數(shù)據(jù)元素移動(dòng)現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，提高了效率。HEAD…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第29頁。(3).線性鏈表的刪除線性鏈表刪除過程中不發(fā)生數(shù)據(jù)元素移動(dòng)現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，提高了效率。HEAD…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第30頁。6.雙向鏈表的基本運(yùn)算(插入)00head…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第31頁。6.雙向鏈表的基本運(yùn)算(刪除)00head…數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第32頁。7.循環(huán)鏈表及其基本運(yùn)算單鏈表的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镠ULL;如果將它改為存放鏈表中頭結(jié)點(diǎn)的地址，這樣就構(gòu)成了一個(gè)環(huán)。HEAD…非空循環(huán)鏈表HEAD空循環(huán)鏈表其插入與刪除操作與單鏈表相同數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第33頁。1.6樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu).具有層次結(jié)構(gòu)。基本術(shù)語:P32父結(jié)點(diǎn)、根結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)。結(jié)點(diǎn)的度、樹的度，樹的深度、子樹。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第34頁。abcsdqwvxuverfghtpynm數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第35頁。1.二叉樹的定義非空二叉樹具有以下兩個(gè)特點(diǎn)：(1)非空二叉樹只有一個(gè)根結(jié)點(diǎn)(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹和右子樹。在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹也均為二叉樹。在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹，當(dāng)一個(gè)結(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，該結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第36頁。2.二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第k層上至多有2K-1個(gè)結(jié)點(diǎn)性質(zhì)2:深度為m的二叉樹至多有2m-1個(gè)結(jié)點(diǎn)。性質(zhì)3:對(duì)任意一棵二叉樹，度為0的結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)數(shù)多1。(n0=n2+1)性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度至少為[log2n]+1。(性質(zhì)2反推)數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第37頁。3.滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn).即所有層的結(jié)點(diǎn)數(shù)均達(dá)到最大值.完全二叉樹:除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值,在最后一層上只缺少右邊的若干結(jié)點(diǎn).數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第38頁。3.滿二叉樹與完全二叉樹完全二叉樹還具有以下兩個(gè)性質(zhì)：性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1性質(zhì)6:設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序用自然數(shù)1,2,3…n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k的結(jié)點(diǎn)有如下特點(diǎn)：若k=1則該結(jié)點(diǎn)為要根結(jié)點(diǎn)。若2k<=n，則編號(hào)為k的結(jié)點(diǎn)，其左子樹為2k,右結(jié)點(diǎn)為2k+1若2k+1<=n，則編號(hào)為k的結(jié)點(diǎn)的右子樹編號(hào)為2k+1。數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第39頁。123456789101112131415數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第40頁。4.二叉樹的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu):數(shù)據(jù)域,左指針域,右指針域。L(i)V(i)R(i)數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第41頁。ABCDEFGPY數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第42頁。5.二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn).(1)前序遍歷(根-左-右)(2)中序遍歷(左-根-右)(3)后序遍歷(左-右-根)ABCDEF數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第43頁。前序遍歷：中序遍歷：后序遍歷：FCEADBGHP數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第44頁。前序遍歷：中序遍歷：后序遍歷：ABCDEYXZF數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第45頁。1.7查找技術(shù)所謂查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。1.順序查找:從表的一端開始,順序掃描,依次將掃描的關(guān)鍵字和待尋找的k值比較,若相等,則查找成功;若掃描完畢,仍未找到,則掃描失敗。以下情況只能采用順序查找:(1)線性表示無序表；(2)有序線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)平均情況下，大約要與表中一半的元素進(jìn)行比較.最壞情況下，要查找n次.數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第46頁。1.7查找技術(shù)2.二分法查找:只適用于順序存儲(chǔ)的有序表.設(shè)有序表的長度為n,被查元素為x,則查找方法:將x與線性表的中間項(xiàng)相比較；若中間項(xiàng)等于x,則說明查到，查找結(jié)束；若x小于中間項(xiàng),則在線性表的前半部分查找;若x大于中間項(xiàng),則在線性表的后半部分查找.最壞的情況下，查找log2n

次數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第47頁。1.7查找技術(shù)8，17，25，44，68，77，98，100，115，125查找k=98一次查找后:二次查找后:midhighlow三次查找:lowmidhighlowmidhigh最壞的情況下，查找log2n

次成功數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第48頁。1.8排序技術(shù)所謂排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列.交換類排序法插入類排序法選擇類排序法數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第49頁。交換類排序法1.冒泡排序:是一種最簡單的交換類排序法,它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序.從表頭開始掃描整個(gè)線性表,比較相鄰兩個(gè)數(shù)據(jù)的大小,若前面的數(shù)大于后面的數(shù),則將它們進(jìn)行交換.依次進(jìn)行,則第一次可找出最大的數(shù).此后,將其余的數(shù)再進(jìn)行相同的比較.最壞的情況下，查找n(n-1)/2

次數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第50頁。原序列493865977613273038497697971327979730第1遍比較3849657613273097第2遍比較38496513273076

97第3遍比較38491327306576

97第4遍比較38132730496576

97第5遍比較13273038496576

97第6遍比較13273038496576

97第7遍比較13273038496576

97數(shù)據(jù)結(jié)構(gòu)與算法全文共59頁，當(dāng)前為第51頁。2.快速排序

任取待排序列中的某個(gè)元素（一般為第一個(gè)元素）作基準(zhǔn)，通過一趟排序，將待排元素分為左右兩個(gè)子序，左子序列元素排序碼均小于或等于基準(zhǔn)元素排序碼，右子序列元素