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

第一章數(shù)據(jù)結(jié)構(gòu)與算法11.1算法算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。1.1算法算法的基本概念2一.算法的基本特征可行性:執(zhí)行后能得到滿意結(jié)果。確定性:算法中每個步驟必須明確定義，不允許多義性。有窮性:算法必須在有限時間內(nèi)做完。擁有足夠的情報:確保算法有效還取決于情報是否足夠。一.算法的基本特征可行性:執(zhí)行后能得到滿意結(jié)果。3二.算法的基本要素算法對數(shù)據(jù)的運算和操作：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu):順序、選擇、循環(huán)二.算法的基本要素算法對數(shù)據(jù)的運算和操作：算術(shù)運算、邏輯運算4四.算法復(fù)雜度算法的時間復(fù)雜度執(zhí)行算法所需要的計算工作量算法的空間復(fù)雜度執(zhí)行算法所需要的內(nèi)存空間四.算法復(fù)雜度算法的時間復(fù)雜度51.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究以下三個方面的問題:P71.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。2.在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中在存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。3.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研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一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩個方面的信息：元素的信息數(shù)據(jù)元素之間的前后件關(guān)系。所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。前后件：前驅(qū)、后件。一.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。更7二.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是在計算機存儲空間的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。二.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是在計算機存儲空間的存放形8三.數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCDEF其中D稱為是E的前件,C的后件.其他相同.父親兒子女兒其中“父親”是“兒子”和“女兒”的前件，“兒子”和“女兒”是“父親”的后件。三.數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCDEF其中D稱為是E的前件,C的9四.線性結(jié)構(gòu)和非線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu):一個元素都沒有。數(shù)據(jù)結(jié)構(gòu)一般分為:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非空線性結(jié)構(gòu)滿足:有且只有一個根節(jié)點；每個節(jié)點最多有一個前件節(jié)點、也最多有一個后件節(jié)點。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。四.線性結(jié)構(gòu)和非線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu):一個元素都沒有。101.3線性表與順序存儲結(jié)構(gòu)

線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是n(n>=0)個元素構(gòu)成的有限序列(a1,a2,……an)。(1)有且只有一個根結(jié)點a1,它無前件；(2)有且只有一個終端結(jié)點an,它無后件；(3)其他所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表中結(jié)點的個數(shù)稱為線性表的長度,當(dāng)n=0時，稱為空表.1.3線性表與順序存儲結(jié)構(gòu)線性表是最簡單、最常用的一種數(shù)11一.線性表的順序存儲結(jié)構(gòu)線性表在計算機中采用順序存儲。線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具有以下兩個特點:線性表中所有元素所占的存儲空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。一.線性表的順序存儲結(jié)構(gòu)線性表在計算機中采用順序存儲。12二.線性表的插入運算線性表為:(a1,a2…ai-1,ai,ai+1…an)在第i個位置之前上插入新的結(jié)點x:線性表變?yōu)?(a1,a2…ai-1,x,ai,ai+1…an)長度變?yōu)閚+1。在最好的情況下,不需要移動表中的元素。在最壞的情況下,需要移動表中的所有元素。在平均情況下,需要移動表中一半的元素。二.線性表的插入運算線性表為:(a1,a2…ai-1,ai13三.線性表的刪除運算線性表為:(a1,a2……ai-1,ai,ai+1……an)在第i個位置上刪除新的結(jié)點ai:線性表變?yōu)?(a1,a2……ai-1,ai+1……an)長度變?yōu)閚-1。在最好的情況下,不需要移動表中的元素。在最壞的情況下,需要移動表中的所有元素。在平均情況下,需要移動表中一半的元素。三.線性表的刪除運算線性表為:(a1,a2……ai-1,a141.4棧和隊列1.什么是棧？棧是限定在一端進行插入和刪除運算的線性表。允許插入與刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。假設(shè)棧s=(a1,a2,……an),則a1稱為棧底元素，an成為棧頂元素。棧也稱為先進后出或后進先出的線性表。1.4棧和隊列1.什么是棧？151.4棧和隊列anan-1…a2a1進棧退棧topbottom棧:后進先出表1.4棧和隊列anan-1…a2a1進棧退棧topbotto161.4棧和隊列2.棧的順序存儲及其運算P21

?？諚M正常dcbagfedcba進棧時會發(fā)生上溢錯誤退棧時會發(fā)生下溢錯誤1.4棧和隊列2.棧的順序存儲及其運算P21?？諚M正常d171.4棧和隊列1.什么是隊列

隊列是指只允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭.假設(shè)隊列q=(a1,a2,……an),則a1稱為隊頭元素，an成為隊尾元素。1.4棧和隊列1.什么是隊列18隊列(queue)的運算示意ABCD一個隊列插入(入隊)刪除(退隊)BCDABCDEfrontrearfrontfrontrearrear隊列(queue)的運算示意ABCD一個隊列插入(入隊)刪除191.4棧和隊列2.循環(huán)隊列及其算法循環(huán)隊列：將隊列的存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。m…21frontrear1.4棧和隊列2.循環(huán)隊列及其算法m…21frontrear201.4棧和隊列frontrear123n分析可知：當(dāng)front=rear時，不能確定循環(huán)隊列是空還是滿，于是需要要一個標(biāo)記S,用來判斷隊列的狀態(tài):S=0表示隊列為空S=1表示隊列為非空由此得出：隊列為空的條件是:s=0隊列為滿的條件是:s=1且front=rear1.4棧和隊列frontrear123n分析可知：當(dāng)fron211.5線性鏈表1.什么是鏈?zhǔn)酱鎯Γ烤€性表順序存儲的缺點：插入刪除時移動大量元素；有“上溢”情況；空間不便于動態(tài)分配。在鏈?zhǔn)酱鎯Ψ绞街?每個結(jié)點有兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱為數(shù)據(jù)域；另一部分存放指針,稱為指針域。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中,存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的.1.5線性鏈表1.什么是鏈?zhǔn)酱鎯Γ?22.線性單鏈表在線性單鏈表中,結(jié)點的數(shù)據(jù)域存放數(shù)據(jù)元素的值,指針域存放下一個數(shù)據(jù)元素的存儲序號,即指向后件結(jié)點.V(i)Next(i)數(shù)據(jù)域指針域數(shù)據(jù)1數(shù)據(jù)nnull數(shù)據(jù)2HEAD…2.線性單鏈表在線性單鏈表中,結(jié)點的數(shù)據(jù)域存放數(shù)據(jù)元素的值,231B1023A1456D878E910C6ABCDE11101066881B1023A1456D878E910C6ABCDE1110243.線性雙向鏈表在線性單鏈表中從一個結(jié)點只能找到它的下一個結(jié)點,但找不到前一個結(jié)點.為解決這一問題,將線性鏈表中每一個結(jié)點設(shè)置兩個指針:左指針和右指針.這樣的鏈表稱為雙向鏈表.00head…3.線性雙向鏈表在線性單鏈表中從一個結(jié)點只能找到它的下一個結(jié)254.帶鏈的棧和隊列P27(1)棧也是線性表。帶鏈的棧稱為可利用棧。(2)隊列也是線性表。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。topa10an-1an…an0a2a1…frontrear4.帶鏈的棧和隊列P27(1)棧也是線性表。帶鏈的棧稱265.線性鏈表的基本運算插入：刪除：合并：分解：逆轉(zhuǎn)：復(fù)制：排序：查找：5.線性鏈表的基本運算插入：27(1).在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值x的前一個結(jié)點p的基本方法:從頭結(jié)點指向的結(jié)點開始往后沿指針進行掃描,直到后面已沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止.(1).在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定28(2).線性鏈表的插入線性鏈表插入過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只要改變有關(guān)結(jié)點的指針即可，提高了效率。HEAD…(2).線性鏈表的插入線性鏈表插入過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)29(3).線性鏈表的刪除線性鏈表刪除過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只要改變有關(guān)結(jié)點的指針即可，提高了效率。HEAD…(3).線性鏈表的刪除線性鏈表刪除過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)306.雙向鏈表的基本運算(插入)00head…6.雙向鏈表的基本運算(插入)00head…316.雙向鏈表的基本運算(刪除)00head…6.雙向鏈表的基本運算(刪除)00head…327.循環(huán)鏈表及其基本運算單鏈表的最后一個結(jié)點的指針域為HULL;如果將它改為存放鏈表中頭結(jié)點的地址，這樣就構(gòu)成了一個環(huán)。HEAD…非空循環(huán)鏈表HEAD空循環(huán)鏈表其插入與刪除操作與單鏈表相同7.循環(huán)鏈表及其基本運算單鏈表的最后一個結(jié)點的指針域為HUL331.6樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu).具有層次結(jié)構(gòu)。基本術(shù)語:P32父結(jié)點、根結(jié)點、子結(jié)點、葉子結(jié)點。結(jié)點的度、樹的度，樹的深度、子樹。1.6樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu).具有層次結(jié)構(gòu)。34abcsdqwvxuverfghtpynmabcsdqwvxuverfghtpynm351.二叉樹的定義非空二叉樹具有以下兩個特點：(1)非空二叉樹只有一個根結(jié)點(2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。在二叉樹中，每一個結(jié)點的度最大為2，即所有子樹也均為二叉樹。在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹，當(dāng)一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點稱為葉子結(jié)點。1.二叉樹的定義非空二叉樹具有以下兩個特點：362.二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第k層上至多有2K-1個結(jié)點性質(zhì)2:深度為m的二叉樹至多有2m-1個結(jié)點。性質(zhì)3:對任意一棵二叉樹，度為0的結(jié)點數(shù)總比度為2的結(jié)點數(shù)多1。(n0=n2+1)性質(zhì)4:具有n個結(jié)點的完全二叉樹深度至少為[log2n]+1。(性質(zhì)2反推)2.二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第k層上至多有2K-1373.滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點.即所有層的結(jié)點數(shù)均達到最大值.完全二叉樹:除最后一層外,每一層上的結(jié)點數(shù)均達到最大值,在最后一層上只缺少右邊的若干結(jié)點.3.滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所383.滿二叉樹與完全二叉樹完全二叉樹還具有以下兩個性質(zhì)：性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為[log2n]+1性質(zhì)6:設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序用自然數(shù)1,2,3…n給結(jié)點進行編號，則對于編號為k的結(jié)點有如下特點：若k=1則該結(jié)點為要根結(jié)點。若2k<=n，則編號為k的結(jié)點，其左子樹為2k,右結(jié)點為2k+1若2k+1<=n，則編號為k的結(jié)點的右子樹編號為2k+1。3.滿二叉樹與完全二叉樹完全二叉樹還具有以下兩個性質(zhì)：39123456789101112131415123456789101112131415404.二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)點的結(jié)構(gòu):數(shù)據(jù)域,左指針域,右指針域。L(i)V(i)R(i)4.二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。41ABCDEFGPYABCDEFGPY425.二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點.(1)前序遍歷(根-左-右)(2)中序遍歷(左-根-右)(3)后序遍歷(左-右-根)ABCDEF5.二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)43前序遍歷：中序遍歷：后序遍歷：FCEADBGHP前序遍歷：FCEADBGHP44前序遍歷：中序遍歷：后序遍歷：ABCDEYXZF前序遍歷：ABCDEYXZF451.7查找技術(shù)所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。1.順序查找:從表的一端開始,順序掃描,依次將掃描的關(guān)鍵字和待尋找的k值比較,若相等,則查找成功;若掃描完畢,仍未找到,則掃描失敗。以下情況只能采用順序查找:(1)線性表示無序表；(2)有序線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)平均情況下，大約要與表中一半的元素進行比較.最壞情況下，要查找n次.1.7查找技術(shù)所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定461.7查找技術(shù)2.二分法查找:只適用于順序存儲的有序表.設(shè)有序表的長度為n,被查元素為x,則查找方法:將x與線性表的中間項相比較；若中間項等于x,則說明查到，查找結(jié)束；若x小于中間項,則在線性表的前半部分查找;若x大于中間項,則在線性表的后半部分查找.最壞的情況下，查找log2n

次1.7查找技術(shù)2.二分法查找:只適用于順序存儲的有序表.最壞471.7查找技術(shù)8，17，25，44，68，77，98，100，115，125查找k=98一次查找后:二次查找后:midhighlow三次查找:lowmidhighlowmidhigh最壞的情況下，查找log2n

次成功1.7查找技術(shù)8，17，25，44，68，77，98，100481.8排序技術(shù)所謂排序是指將一個無序序列整理成按值非遞減順序排列的有序序列.交換類排序法插入類排序法選擇類排序法1.8排序技術(shù)所謂排序是指將一個無序序列整理成按值非遞減順序49交換類排序法1.冒泡排序:是一種最簡單的交換類排序法,它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序.從表頭開始掃描整個線性表,比較相鄰兩個數(shù)據(jù)的大小,若前面的數(shù)大于后面的數(shù),則將它們進行交換.依次進行,則第一次可找出最大的數(shù).此后,將其余的數(shù)再進行相同的比較.最壞的情況下，查找n(n-1)/2次交換類排序法1.冒泡排序:是一種最簡單的交換類排序法,它是通50原序列493865977613273038497697971327979730第1遍比較3849657613273097第2遍比較38496513273076

97第3遍比較38491327306576

97第4遍比較38132730496576

97第5遍比較13273038496576

97第6遍比較13273038496576

97第7遍比較13273038496576

97原序列493865977613512.快速排序任取待排序列中的某個元素（一般為第一個元素）作基準(zhǔn)，通過一趟排序，將待排元素分為左右兩個子序，左子序列元素排序碼均小于或等于基準(zhǔn)元素排序碼，右子序列元素排序碼均大于基準(zhǔn)元素排序碼。然后分別對兩個子序排序，直至整個序列有序。2.快速排序任取待排序列中的某個元素（一般為第一個元素）作52插入類排序每次將一個待排的紀(jì)錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。簡單插入排序法希爾排序法插入類排序每次將一個待排的紀(jì)錄，按其關(guān)鍵字大小插入到前面已經(jīng)53一、簡單插入排序示例簡單的插入類排序最壞的情況：n(n-1)/2一、簡單插入排序示例簡單的插入類排序最壞的情況：n(n-1)542.希爾排序法先將整個待排元素序列分割成若干個子序列，分別進行直接插入排序，待整個序列中的元素基本有序時，再對全體元素進行一次直接插入排序。在最壞的情況下：

希爾排序法需要的比較次數(shù)是O(n1.5)2.希爾排序法先將整個待排元素序列分割成若干個子序列，分別進55選擇類排序每一趟從待排序的記錄中選出關(guān)鍵字最小的紀(jì)錄，順序放在已排好序的子序列最后。直到全部記錄排序完畢。簡單選擇排序法堆排序法選擇類排序每一趟從待排序的記錄中選出關(guān)鍵字最小的紀(jì)錄，順序放56簡單的選擇排序的過程示例最壞的簡單選擇類排序法需要比較n(n-1)/2次簡單的選擇排序的過程示例最壞的簡單選擇類排序法需要比較n(n571.堆排序圖9185533647302412所有根結(jié)點的大于或等于左右孩子的值-大根堆。所有根結(jié)點的小于或等于左右孩子的值-小根堆。在最壞的情況下：堆排序法需要的比較次數(shù)是O(nlog2n)1.堆排序圖9185533647302412所有根結(jié)點的大于58查找技術(shù)排序技術(shù)順序查找二分法查找交換類排序插入類排序選擇類排序快速排序法冒泡排序法希爾排序法簡單插入排序法簡單選擇排序法堆排序法nlog2nO(nlog2n)n(n-1)/2最快情況下的次數(shù)（時間復(fù)雜度）查找技術(shù)排序技術(shù)順序查找二分法查找交換類排序插入類排序選擇59第一章數(shù)據(jù)結(jié)構(gòu)與算法

第一章數(shù)據(jù)結(jié)構(gòu)與算法601.1算法算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。1.1算法算法的基本概念61一.算法的基本特征可行性:執(zhí)行后能得到滿意結(jié)果。確定性:算法中每個步驟必須明確定義，不允許多義性。有窮性:算法必須在有限時間內(nèi)做完。擁有足夠的情報:確保算法有效還取決于情報是否足夠。一.算法的基本特征可行性:執(zhí)行后能得到滿意結(jié)果。62二.算法的基本要素算法對數(shù)據(jù)的運算和操作：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu):順序、選擇、循環(huán)二.算法的基本要素算法對數(shù)據(jù)的運算和操作：算術(shù)運算、邏輯運算63四.算法復(fù)雜度算法的時間復(fù)雜度執(zhí)行算法所需要的計算工作量算法的空間復(fù)雜度執(zhí)行算法所需要的內(nèi)存空間四.算法復(fù)雜度算法的時間復(fù)雜度641.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究以下三個方面的問題:P71.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。2.在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中在存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。3.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研65一.數(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一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩個方面的信息：元素的信息數(shù)據(jù)元素之間的前后件關(guān)系。所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。前后件：前驅(qū)、后件。一.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。更66二.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是在計算機存儲空間的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。二.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是在計算機存儲空間的存放形67三.數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCDEF其中D稱為是E的前件,C的后件.其他相同.父親兒子女兒其中“父親”是“兒子”和“女兒”的前件，“兒子”和“女兒”是“父親”的后件。三.數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCDEF其中D稱為是E的前件,C的68四.線性結(jié)構(gòu)和非線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu):一個元素都沒有。數(shù)據(jù)結(jié)構(gòu)一般分為:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非空線性結(jié)構(gòu)滿足:有且只有一個根節(jié)點；每個節(jié)點最多有一個前件節(jié)點、也最多有一個后件節(jié)點。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。四.線性結(jié)構(gòu)和非線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu):一個元素都沒有。691.3線性表與順序存儲結(jié)構(gòu)

線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是n(n>=0)個元素構(gòu)成的有限序列(a1,a2,……an)。(1)有且只有一個根結(jié)點a1,它無前件；(2)有且只有一個終端結(jié)點an,它無后件；(3)其他所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表中結(jié)點的個數(shù)稱為線性表的長度,當(dāng)n=0時，稱為空表.1.3線性表與順序存儲結(jié)構(gòu)線性表是最簡單、最常用的一種數(shù)70一.線性表的順序存儲結(jié)構(gòu)線性表在計算機中采用順序存儲。線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具有以下兩個特點:線性表中所有元素所占的存儲空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。一.線性表的順序存儲結(jié)構(gòu)線性表在計算機中采用順序存儲。71二.線性表的插入運算線性表為:(a1,a2…ai-1,ai,ai+1…an)在第i個位置之前上插入新的結(jié)點x:線性表變?yōu)?(a1,a2…ai-1,x,ai,ai+1…an)長度變?yōu)閚+1。在最好的情況下,不需要移動表中的元素。在最壞的情況下,需要移動表中的所有元素。在平均情況下,需要移動表中一半的元素。二.線性表的插入運算線性表為:(a1,a2…ai-1,ai72三.線性表的刪除運算線性表為:(a1,a2……ai-1,ai,ai+1……an)在第i個位置上刪除新的結(jié)點ai:線性表變?yōu)?(a1,a2……ai-1,ai+1……an)長度變?yōu)閚-1。在最好的情況下,不需要移動表中的元素。在最壞的情況下,需要移動表中的所有元素。在平均情況下,需要移動表中一半的元素。三.線性表的刪除運算線性表為:(a1,a2……ai-1,a731.4棧和隊列1.什么是棧？棧是限定在一端進行插入和刪除運算的線性表。允許插入與刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。假設(shè)棧s=(a1,a2,……an),則a1稱為棧底元素，an成為棧頂元素。棧也稱為先進后出或后進先出的線性表。1.4棧和隊列1.什么是棧？741.4棧和隊列anan-1…a2a1進棧退棧topbottom棧:后進先出表1.4棧和隊列anan-1…a2a1進棧退棧topbotto751.4棧和隊列2.棧的順序存儲及其運算P21

?？諚M正常dcbagfedcba進棧時會發(fā)生上溢錯誤退棧時會發(fā)生下溢錯誤1.4棧和隊列2.棧的順序存儲及其運算P21?？諚M正常d761.4棧和隊列1.什么是隊列

隊列是指只允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭.假設(shè)隊列q=(a1,a2,……an),則a1稱為隊頭元素，an成為隊尾元素。1.4棧和隊列1.什么是隊列77隊列(queue)的運算示意ABCD一個隊列插入(入隊)刪除(退隊)BCDABCDEfrontrearfrontfrontrearrear隊列(queue)的運算示意ABCD一個隊列插入(入隊)刪除781.4棧和隊列2.循環(huán)隊列及其算法循環(huán)隊列：將隊列的存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。m…21frontrear1.4棧和隊列2.循環(huán)隊列及其算法m…21frontrear791.4棧和隊列frontrear123n分析可知：當(dāng)front=rear時，不能確定循環(huán)隊列是空還是滿，于是需要要一個標(biāo)記S,用來判斷隊列的狀態(tài):S=0表示隊列為空S=1表示隊列為非空由此得出：隊列為空的條件是:s=0隊列為滿的條件是:s=1且front=rear1.4棧和隊列frontrear123n分析可知：當(dāng)fron801.5線性鏈表1.什么是鏈?zhǔn)酱鎯?？線性表順序存儲的缺點：插入刪除時移動大量元素；有“上溢”情況；空間不便于動態(tài)分配。在鏈?zhǔn)酱鎯Ψ绞街?每個結(jié)點有兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱為數(shù)據(jù)域；另一部分存放指針,稱為指針域。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中,存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的.1.5線性鏈表1.什么是鏈?zhǔn)酱鎯Γ?12.線性單鏈表在線性單鏈表中,結(jié)點的數(shù)據(jù)域存放數(shù)據(jù)元素的值,指針域存放下一個數(shù)據(jù)元素的存儲序號,即指向后件結(jié)點.V(i)Next(i)數(shù)據(jù)域指針域數(shù)據(jù)1數(shù)據(jù)nnull數(shù)據(jù)2HEAD…2.線性單鏈表在線性單鏈表中,結(jié)點的數(shù)據(jù)域存放數(shù)據(jù)元素的值,821B1023A1456D878E910C6ABCDE11101066881B1023A1456D878E910C6ABCDE1110833.線性雙向鏈表在線性單鏈表中從一個結(jié)點只能找到它的下一個結(jié)點,但找不到前一個結(jié)點.為解決這一問題,將線性鏈表中每一個結(jié)點設(shè)置兩個指針:左指針和右指針.這樣的鏈表稱為雙向鏈表.00head…3.線性雙向鏈表在線性單鏈表中從一個結(jié)點只能找到它的下一個結(jié)844.帶鏈的棧和隊列P27(1)棧也是線性表。帶鏈的棧稱為可利用棧。(2)隊列也是線性表。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。topa10an-1an…an0a2a1…frontrear4.帶鏈的棧和隊列P27(1)棧也是線性表。帶鏈的棧稱855.線性鏈表的基本運算插入：刪除：合并：分解：逆轉(zhuǎn)：復(fù)制：排序：查找：5.線性鏈表的基本運算插入：86(1).在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值x的前一個結(jié)點p的基本方法:從頭結(jié)點指向的結(jié)點開始往后沿指針進行掃描,直到后面已沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止.(1).在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定87(2).線性鏈表的插入線性鏈表插入過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只要改變有關(guān)結(jié)點的指針即可，提高了效率。HEAD…(2).線性鏈表的插入線性鏈表插入過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)88(3).線性鏈表的刪除線性鏈表刪除過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只要改變有關(guān)結(jié)點的指針即可，提高了效率。HEAD…(3).線性鏈表的刪除線性鏈表刪除過程中不發(fā)生數(shù)據(jù)元素移動現(xiàn)896.雙向鏈表的基本運算(插入)00head…6.雙向鏈表的基本運算(插入)00head…906.雙向鏈表的基本運算(刪除)00head…6.雙向鏈表的基本運算(刪除)00head…917.循環(huán)鏈表及其基本運算單鏈表的最后一個結(jié)點的指針域為HULL;如果將它改為存放鏈表中頭結(jié)點的地址，這樣就構(gòu)成了一個環(huán)。HEAD…非空循環(huán)鏈表HEAD空循環(huán)鏈表其插入與刪除操作與單鏈表相同7.循環(huán)鏈表及其基本運算單鏈表的最后一個結(jié)點的指針域為HUL921.6樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu).具有層次結(jié)構(gòu)?；拘g(shù)語:P32父結(jié)點、根結(jié)點、子結(jié)點、葉子結(jié)點。結(jié)點的度、樹的度，樹的深度、子樹。1.6樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu).具有層次結(jié)構(gòu)。93abcsdqwvxuverfghtpynmabcsdqwvxuverfghtpynm941.二叉樹的定義非空二叉樹具有以下兩個特點：(1)非空二叉樹只有一個根結(jié)點(2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。在二叉樹中，每一個結(jié)點的度最大為2，即所有子樹也均為二叉樹。在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹，當(dāng)一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點稱為葉子結(jié)點。1.二叉樹的定義非空二叉樹具有以下兩個特點：952.二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第k層上至多有2K-1個結(jié)點性質(zhì)2:深度為m的二叉樹至多有2m-1個結(jié)點。性質(zhì)3:對任意一棵二叉樹，度為0的結(jié)點數(shù)總比度為2的結(jié)點數(shù)多1。(n0=n2+1)性質(zhì)4:具有n個結(jié)點的完全二叉樹深度至少為[log2n]+1。(性質(zhì)2反推)2.二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第k層上至多有2K-1963.滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點.即所有層的結(jié)點數(shù)均達到最大值.完全二叉樹:除最后一層外,每一層上的結(jié)點數(shù)均達到最大值,在最后一層上只缺少右邊的若干結(jié)點.3.滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所973.滿二叉樹與完全二叉樹完全二叉樹還具有以下兩個性質(zhì)：性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為[log2n]+1性質(zhì)6:設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序用自然數(shù)1,2,3…n給結(jié)點進行編號，則對于編號為k的結(jié)點有如下特點：若k=1則該結(jié)點為要根結(jié)點。若2k<=n，則編號為k的結(jié)點，其左子樹為2k,右結(jié)點為2k+1若2k+1<=n，則編號為k的結(jié)點的右子樹編號為2k+1。3.滿二叉樹與完全二叉樹完全二叉樹還具有以下兩個性質(zhì)：98123456789101112131415123456789101112131415994.二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)點的結(jié)構(gòu):數(shù)據(jù)域,左指針域,右指針域。L(i)V(i)R(i)4.二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。100ABCDEFGPYABCDEFGPY1015.二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點.(1)前序遍歷(根-左-右)(2)中序遍歷(左-根-右)(3)后序遍歷(左-右-根)ABCDEF5.二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)102前序遍歷：中序遍歷：后序遍歷：FCEADBGHP前序遍歷：FCEADBGHP103前序遍歷：中序遍歷：后序遍歷：ABCDEYXZF前序遍歷：ABCDEYXZF1041.7查找技術(shù)所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。1.順序查找:從表的一端開始,順序掃描,依次將掃描的關(guān)鍵字和待尋找的k值比較,若相等,則查找成功;若掃描完畢,仍未找到,則掃描失敗。以下情況只能采用順序查找:(1)線性表示無序表；(2)有序線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)平均情況下，大約要與表中一半的元素進行比較.最壞情況下，要查找n次.1.7查找技術(shù)所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定1051.7查找技術(shù)2.二分法查找:只適用于順序存儲的有序表.設(shè)有序表的長度為n,被查元素為x,則查找方法:將x與線性表的中間項相比較；若中間項等于x,則說明查到，查找結(jié)束；若x小于中間項,則在線性表的前半部分查找;若x大于中間項,則在線性表的后半部分查找.最壞的情況下，查找log2n

次1.7查找技術(shù)2.二分法查找:只適用于順序存儲的有序表.最壞1061.7查找技術(shù)8，17，25，44，68，77，98，100，115，125查找k=98一次查找后:二次查找后:midhighlow三次查找:lowmidhighlowmidhigh最壞的情況下，查找log2n

次成功1.7查找技術(shù)8，17，25，44，68，77，98，1001071.8排序技術(shù)所謂排序是指將一個無序序列整理成按值非遞減順序排列的有序序列.交換類排序法插入類排序法選擇類排序法1.8排序技術(shù)所謂排序是指將