數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義全課件

數(shù)據(jù)結(jié)構(gòu)--肖興貴傳智播客數(shù)據(jù)結(jié)構(gòu)--肖興貴傳智播客11概要2線性表3棧和隊(duì)列4樹和二叉樹5查找和排序主要內(nèi)容1概要主要內(nèi)容21.1討論的范疇算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)

處理問題的策略給出問題的數(shù)學(xué)模型編制出的指令集處理問題用計(jì)算機(jī)問題構(gòu)建數(shù)學(xué)模型程序?qū)崿F(xiàn)1.1討論的范疇算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)處理問題的策31.1討論的范疇例1求小紅C語言和數(shù)據(jù)結(jié)構(gòu)兩門語言的考試的平均成績成績和總成績。全省的呢？例2酒店管理中的客房分配問題。例3煤氣管道的鋪設(shè)問題。等等……例子中的數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問題。1.1討論的范疇例1求小紅C語言和數(shù)據(jù)結(jié)構(gòu)兩門語言的考試41.2定義

數(shù)據(jù)結(jié)構(gòu)是一門討論"描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)"的學(xué)科。

a.在解決問題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）b.邏輯結(jié)構(gòu)的存儲映象（存儲實(shí)現(xiàn)）c.數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。(算法)通俗點(diǎn)講，數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)的存儲和操作。1.2定義數(shù)據(jù)結(jié)構(gòu)是一門討論"描述現(xiàn)實(shí)世51.3三個(gè)方面

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯?/p>

線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)1.3三個(gè)方面數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)61.3邏輯和物理結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)1.3邏輯和物理結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)7數(shù)學(xué)模型集合和關(guān)系數(shù)據(jù)和信息數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)關(guān)鍵碼抽象數(shù)據(jù)類型1.4相關(guān)概念數(shù)學(xué)模型1.4相關(guān)概念8算法是特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，算法是獨(dú)立存在的一種解決問題的方法和思想。對于算法而言，語言并不重要，重要的是思想。數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系：數(shù)據(jù)結(jié)構(gòu)是專門研究數(shù)據(jù)的存儲問題，而對存儲后的數(shù)據(jù)進(jìn)行相應(yīng)的操作就是算法。1.5算法的定義算法是特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列91.5算法效率的度量我們通過大O表示法來表示算法的效率：時(shí)間復(fù)雜度、空間復(fù)雜度。規(guī)則如下：（1）只關(guān)注最高次項(xiàng)，常數(shù)項(xiàng)和次要項(xiàng)忽略；（2）時(shí)間復(fù)雜度是指最壞時(shí)間復(fù)雜度；（3）只有常數(shù)項(xiàng)記做1。執(zhí)行次數(shù)函數(shù)階非正式術(shù)語12O(1)常數(shù)階2n+3O(n)線性階3n2+2n+1O(n2)平方階5log2n+20O(logn)對數(shù)階2n+3nlog2n+19O(nlogn)nlogn階6n3+2n2+3n+4O(n3)立方階2nO(2n)指數(shù)階1.5算法效率的度量我們通過大O表示法來表示算法的效率：時(shí)101.6時(shí)間復(fù)雜度舉例線性階：O(n)平方階:O(n2)1.6時(shí)間復(fù)雜度舉例線性階：O(n)平方階:O(n2)111.6空間復(fù)雜度舉例空間復(fù)雜度：O(n)1.6空間復(fù)雜度舉例空間復(fù)雜度：O(n)122.1線性表概念線性結(jié)構(gòu)的基本特點(diǎn)是節(jié)點(diǎn)之間滿足線性關(guān)系。數(shù)組、鏈表、棧、隊(duì)列都屬于線性結(jié)構(gòu)。他們的共同之處，是節(jié)點(diǎn)中有且只有一個(gè)開始節(jié)點(diǎn)和終端節(jié)點(diǎn)。他們分別屬于幾種不同的抽象數(shù)據(jù)類型實(shí)現(xiàn)，它們之間的區(qū)別，主要就是操作的不同。線性表是零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是有順序的，數(shù)據(jù)元素個(gè)數(shù)是有限的，數(shù)據(jù)元素的類型必須相同2.1線性表概念線性結(jié)構(gòu)的基本特點(diǎn)是節(jié)點(diǎn)之間滿足線性關(guān)系。132.1編程實(shí)戰(zhàn)動態(tài)數(shù)組數(shù)組到底應(yīng)該有多大才合適，通常不得而知。所以希望能夠在運(yùn)行時(shí)具有改變數(shù)組大小的能力。（基本操作：創(chuàng)建、銷毀、插入、刪除、遍歷打?。﹩蜗蜴湵?.1編程實(shí)戰(zhàn)動態(tài)數(shù)組142.3編程實(shí)戰(zhàn)經(jīng)典雙向鏈表主要操作：初始化頭結(jié)點(diǎn)、添加、刪除、獲取元素、遍歷2.3編程實(shí)戰(zhàn)經(jīng)典雙向鏈表15Q1.創(chuàng)建兩循環(huán)單向鏈表并將它們合為一各鏈表？Q2.

頭指針和頭節(jié)點(diǎn)有什么區(qū)別？頭結(jié)點(diǎn)和其他節(jié)點(diǎn)有什么區(qū)別？第1天習(xí)題Q1.創(chuàng)建兩循環(huán)單向鏈表并將它們合為一各鏈表？第1天習(xí)題163.1棧的特點(diǎn)棧為一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)，凡是對數(shù)據(jù)的處理具有“后進(jìn)先出(LIFO)”的特點(diǎn)，都可以用棧這種數(shù)據(jù)結(jié)構(gòu)來操作。棧的特殊之處在于限制了這個(gè)線性表的插入和刪除的位置，它始終只在棧頂進(jìn)行。3.1棧的特點(diǎn)棧為一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)，凡是173.2編程實(shí)戰(zhàn)棧的順序存儲利用一組地址連續(xù)的的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top只是棧頂元素在順序表中的位置。棧的鏈?zhǔn)酱鎯?.2編程實(shí)戰(zhàn)棧的順序存儲183.4隊(duì)列的特點(diǎn)隊(duì)列為一種可以實(shí)現(xiàn)“先進(jìn)先出”(FIFO)的存儲結(jié)構(gòu)。隊(duì)列是一種特殊的受限制的線性表，只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表，隊(duì)列不允許在中間部位進(jìn)行操作。3.4隊(duì)列的特點(diǎn)隊(duì)列為一種可以實(shí)現(xiàn)“先進(jìn)先出”(FIFO)193.5編程實(shí)戰(zhàn)隊(duì)列的順序存儲3.5編程實(shí)戰(zhàn)隊(duì)列的順序存儲203.6編程實(shí)戰(zhàn)隊(duì)列的鏈?zhǔn)酱鎯?.6編程實(shí)戰(zhàn)隊(duì)列的鏈?zhǔn)酱鎯?1Q1.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并又只設(shè)一個(gè)指針指向隊(duì)尾元音結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。Q2.

假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，”aba”和”abcba”是回文，”abcde”和”ababab”則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以“@”為結(jié)束符的字符序列是否是“回文”。第2天習(xí)題Q1.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并又只設(shè)一個(gè)指針指224.1樹的定義定義：-由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根，其余的結(jié)點(diǎn)分為m個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹。樹的特點(diǎn)：非線性結(jié)構(gòu)，有一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1:n）樹的定義具有遞歸性，樹中還有樹樹可以為空，即節(jié)點(diǎn)個(gè)數(shù)為04.1樹的定義定義：234.2樹的術(shù)語專業(yè)術(shù)語含義根也叫根結(jié)點(diǎn)(沒有前驅(qū))葉子也叫終端結(jié)點(diǎn)(沒有后繼)森林指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))有序樹結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）無序樹結(jié)點(diǎn)各子樹可互換位置雙親即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))parent孩子即下層結(jié)點(diǎn)的子樹(直接后繼)child兄弟同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）sibling堂兄弟即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）cousin祖先即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)子孫即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)結(jié)點(diǎn)也叫節(jié)點(diǎn)，即樹的數(shù)據(jù)元素結(jié)點(diǎn)的度、樹的度結(jié)點(diǎn)掛接的子樹數(shù)、所有結(jié)點(diǎn)度中的最大值結(jié)點(diǎn)的層次從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）終端結(jié)點(diǎn)即度為0的結(jié)點(diǎn)，即葉子分支結(jié)點(diǎn)除樹根以外的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）樹的深度(或高度)指所有結(jié)點(diǎn)中最大的層數(shù)(從根節(jié)點(diǎn)到最低層的結(jié)點(diǎn)層數(shù))4.2樹的術(shù)語專業(yè)術(shù)語含義根也叫根結(jié)點(diǎn)(沒有前驅(qū))葉子也叫244.3樹的表示法4.3樹的表示法254.4樹的表示法4.4樹的表示法264.5二叉樹的概念二叉樹由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的互不相交的樹組成：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）左子樹和右子樹次序不能顛倒（有序樹）4.5二叉樹的概念二叉樹由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹274.6樹轉(zhuǎn)化為二叉樹左孩子右兄弟表示法可以將一顆多叉樹轉(zhuǎn)化為一顆二叉樹。4.6樹轉(zhuǎn)化為二叉樹左孩子右兄弟表示法可以將一顆多叉樹轉(zhuǎn)化284.7滿二叉樹和完全二叉樹4.7滿二叉樹和完全二叉樹294.7樹的順序存儲多叉樹順序存儲的缺陷4.7樹的順序存儲多叉樹順序存儲的缺陷304.7完全二叉樹的順序存儲非完全二叉樹存儲缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便完全二叉樹存儲4.7完全二叉樹的順序存儲非完全二叉樹存儲缺點(diǎn)：完全二叉樹314.7二叉樹的鏈?zhǔn)酱鎯Χ骀湸鎯?.7二叉樹的鏈?zhǔn)酱鎯Χ骀湸鎯?24.7二叉樹的鏈?zhǔn)酱鎯θ骀湸鎯?.7二叉樹的鏈?zhǔn)酱鎯θ骀湸鎯?34.8二叉樹的遍歷遍歷是指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游），遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。牢記一種約定，對每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。遍歷方式特點(diǎn)先序遍歷(先根遍歷，DLR)根->左子樹->右子樹中序遍歷(中根遍歷，LDR)左子樹->根->右子樹后序遍歷(后根遍歷，LRD)左子樹->右子樹->根4.8二叉樹的遍歷遍歷是指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重344.8二叉樹的遍歷4.8二叉樹的遍歷354.8編程實(shí)戰(zhàn)二叉樹的動態(tài)創(chuàng)建和釋放二叉樹的遞歸遍歷計(jì)算二叉樹葉子節(jié)點(diǎn)數(shù)目計(jì)算二叉樹高度4.8編程實(shí)戰(zhàn)二叉樹的動態(tài)創(chuàng)建和釋放36第3天習(xí)題Q1編寫遞歸算法，在二叉樹中求位于先序序列中第A個(gè)位置的結(jié)點(diǎn)的值。Q2編寫遞歸算法，計(jì)算二又樹中葉子結(jié)點(diǎn)的數(shù)目。Q3編寫遞歸算法，將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。第3天習(xí)題Q1編寫遞歸算法，在二叉樹中求位于先序序列中第375.1查找的概念根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素，若表中存在這樣的一個(gè)記錄，則稱查找是成功的。5.1查找的概念根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵385.2編程實(shí)戰(zhàn)順序查找二分查找5.2編程實(shí)戰(zhàn)順序查找395.3排序的概念排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的數(shù)據(jù)元素調(diào)整為“有序”的數(shù)據(jù)元素。排序是高效查詢的前提。5.3排序的概念排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是405.4編程實(shí)戰(zhàn)冒泡選擇插入排序5.4編程實(shí)戰(zhàn)冒泡415.5排序算法比較5.5排序算法比較42第4天習(xí)題Q1編寫一個(gè)雙向起泡的排序算法，即相鄰兩遍分別向相反方向起泡。Q2當(dāng)記錄序列基本有序時(shí)，用哪種排序才法效率較高?簡單選擇排序與起泡排序兩者在什么情況下的執(zhí)行效率差別較大?Q3畫出對長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長度。第4天習(xí)題Q1編寫一個(gè)雙向起泡的排序算法，即相鄰兩遍43謝謝大家！謝謝大家！446學(xué)習(xí)拓展圖和廣義表文件實(shí)戰(zhàn)吧，實(shí)踐出真知！肖興貴xiaoyouheng@6學(xué)習(xí)拓展圖和廣義表實(shí)戰(zhàn)吧，實(shí)踐出真知！肖興貴45知識回顧KnowledgeReview祝您成功！知識回顧KnowledgeReview祝您成功！數(shù)據(jù)結(jié)構(gòu)--肖興貴傳智播客數(shù)據(jù)結(jié)構(gòu)--肖興貴傳智播客471概要2線性表3棧和隊(duì)列4樹和二叉樹5查找和排序主要內(nèi)容1概要主要內(nèi)容481.1討論的范疇算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)

處理問題的策略給出問題的數(shù)學(xué)模型編制出的指令集處理問題用計(jì)算機(jī)問題構(gòu)建數(shù)學(xué)模型程序?qū)崿F(xiàn)1.1討論的范疇算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)處理問題的策491.1討論的范疇例1求小紅C語言和數(shù)據(jù)結(jié)構(gòu)兩門語言的考試的平均成績成績和總成績。全省的呢？例2酒店管理中的客房分配問題。例3煤氣管道的鋪設(shè)問題。等等……例子中的數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問題。1.1討論的范疇例1求小紅C語言和數(shù)據(jù)結(jié)構(gòu)兩門語言的考試501.2定義

數(shù)據(jù)結(jié)構(gòu)是一門討論"描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)"的學(xué)科。

a.在解決問題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）b.邏輯結(jié)構(gòu)的存儲映象（存儲實(shí)現(xiàn)）c.數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。(算法)通俗點(diǎn)講，數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)的存儲和操作。1.2定義數(shù)據(jù)結(jié)構(gòu)是一門討論"描述現(xiàn)實(shí)世511.3三個(gè)方面

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯?/p>

線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)1.3三個(gè)方面數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)521.3邏輯和物理結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)1.3邏輯和物理結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)53數(shù)學(xué)模型集合和關(guān)系數(shù)據(jù)和信息數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)關(guān)鍵碼抽象數(shù)據(jù)類型1.4相關(guān)概念數(shù)學(xué)模型1.4相關(guān)概念54算法是特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，算法是獨(dú)立存在的一種解決問題的方法和思想。對于算法而言，語言并不重要，重要的是思想。數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系：數(shù)據(jù)結(jié)構(gòu)是專門研究數(shù)據(jù)的存儲問題，而對存儲后的數(shù)據(jù)進(jìn)行相應(yīng)的操作就是算法。1.5算法的定義算法是特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列551.5算法效率的度量我們通過大O表示法來表示算法的效率：時(shí)間復(fù)雜度、空間復(fù)雜度。規(guī)則如下：（1）只關(guān)注最高次項(xiàng)，常數(shù)項(xiàng)和次要項(xiàng)忽略；（2）時(shí)間復(fù)雜度是指最壞時(shí)間復(fù)雜度；（3）只有常數(shù)項(xiàng)記做1。執(zhí)行次數(shù)函數(shù)階非正式術(shù)語12O(1)常數(shù)階2n+3O(n)線性階3n2+2n+1O(n2)平方階5log2n+20O(logn)對數(shù)階2n+3nlog2n+19O(nlogn)nlogn階6n3+2n2+3n+4O(n3)立方階2nO(2n)指數(shù)階1.5算法效率的度量我們通過大O表示法來表示算法的效率：時(shí)561.6時(shí)間復(fù)雜度舉例線性階：O(n)平方階:O(n2)1.6時(shí)間復(fù)雜度舉例線性階：O(n)平方階:O(n2)571.6空間復(fù)雜度舉例空間復(fù)雜度：O(n)1.6空間復(fù)雜度舉例空間復(fù)雜度：O(n)582.1線性表概念線性結(jié)構(gòu)的基本特點(diǎn)是節(jié)點(diǎn)之間滿足線性關(guān)系。數(shù)組、鏈表、棧、隊(duì)列都屬于線性結(jié)構(gòu)。他們的共同之處，是節(jié)點(diǎn)中有且只有一個(gè)開始節(jié)點(diǎn)和終端節(jié)點(diǎn)。他們分別屬于幾種不同的抽象數(shù)據(jù)類型實(shí)現(xiàn)，它們之間的區(qū)別，主要就是操作的不同。線性表是零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是有順序的，數(shù)據(jù)元素個(gè)數(shù)是有限的，數(shù)據(jù)元素的類型必須相同2.1線性表概念線性結(jié)構(gòu)的基本特點(diǎn)是節(jié)點(diǎn)之間滿足線性關(guān)系。592.1編程實(shí)戰(zhàn)動態(tài)數(shù)組數(shù)組到底應(yīng)該有多大才合適，通常不得而知。所以希望能夠在運(yùn)行時(shí)具有改變數(shù)組大小的能力。（基本操作：創(chuàng)建、銷毀、插入、刪除、遍歷打?。﹩蜗蜴湵?.1編程實(shí)戰(zhàn)動態(tài)數(shù)組602.3編程實(shí)戰(zhàn)經(jīng)典雙向鏈表主要操作：初始化頭結(jié)點(diǎn)、添加、刪除、獲取元素、遍歷2.3編程實(shí)戰(zhàn)經(jīng)典雙向鏈表61Q1.創(chuàng)建兩循環(huán)單向鏈表并將它們合為一各鏈表？Q2.

頭指針和頭節(jié)點(diǎn)有什么區(qū)別？頭結(jié)點(diǎn)和其他節(jié)點(diǎn)有什么區(qū)別？第1天習(xí)題Q1.創(chuàng)建兩循環(huán)單向鏈表并將它們合為一各鏈表？第1天習(xí)題623.1棧的特點(diǎn)棧為一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)，凡是對數(shù)據(jù)的處理具有“后進(jìn)先出(LIFO)”的特點(diǎn)，都可以用棧這種數(shù)據(jù)結(jié)構(gòu)來操作。棧的特殊之處在于限制了這個(gè)線性表的插入和刪除的位置，它始終只在棧頂進(jìn)行。3.1棧的特點(diǎn)棧為一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)，凡是633.2編程實(shí)戰(zhàn)棧的順序存儲利用一組地址連續(xù)的的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top只是棧頂元素在順序表中的位置。棧的鏈?zhǔn)酱鎯?.2編程實(shí)戰(zhàn)棧的順序存儲643.4隊(duì)列的特點(diǎn)隊(duì)列為一種可以實(shí)現(xiàn)“先進(jìn)先出”(FIFO)的存儲結(jié)構(gòu)。隊(duì)列是一種特殊的受限制的線性表，只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表，隊(duì)列不允許在中間部位進(jìn)行操作。3.4隊(duì)列的特點(diǎn)隊(duì)列為一種可以實(shí)現(xiàn)“先進(jìn)先出”(FIFO)653.5編程實(shí)戰(zhàn)隊(duì)列的順序存儲3.5編程實(shí)戰(zhàn)隊(duì)列的順序存儲663.6編程實(shí)戰(zhàn)隊(duì)列的鏈?zhǔn)酱鎯?.6編程實(shí)戰(zhàn)隊(duì)列的鏈?zhǔn)酱鎯?7Q1.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并又只設(shè)一個(gè)指針指向隊(duì)尾元音結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。Q2.

假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，”aba”和”abcba”是回文，”abcde”和”ababab”則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以“@”為結(jié)束符的字符序列是否是“回文”。第2天習(xí)題Q1.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并又只設(shè)一個(gè)指針指684.1樹的定義定義：-由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根，其余的結(jié)點(diǎn)分為m個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹。樹的特點(diǎn)：非線性結(jié)構(gòu)，有一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1:n）樹的定義具有遞歸性，樹中還有樹樹可以為空，即節(jié)點(diǎn)個(gè)數(shù)為04.1樹的定義定義：694.2樹的術(shù)語專業(yè)術(shù)語含義根也叫根結(jié)點(diǎn)(沒有前驅(qū))葉子也叫終端結(jié)點(diǎn)(沒有后繼)森林指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))有序樹結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）無序樹結(jié)點(diǎn)各子樹可互換位置雙親即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))parent孩子即下層結(jié)點(diǎn)的子樹(直接后繼)child兄弟同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）sibling堂兄弟即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）cousin祖先即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)子孫即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)結(jié)點(diǎn)也叫節(jié)點(diǎn)，即樹的數(shù)據(jù)元素結(jié)點(diǎn)的度、樹的度結(jié)點(diǎn)掛接的子樹數(shù)、所有結(jié)點(diǎn)度中的最大值結(jié)點(diǎn)的層次從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）終端結(jié)點(diǎn)即度為0的結(jié)點(diǎn)，即葉子分支結(jié)點(diǎn)除樹根以外的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）樹的深度(或高度)指所有結(jié)點(diǎn)中最大的層數(shù)(從根節(jié)點(diǎn)到最低層的結(jié)點(diǎn)層數(shù))4.2樹的術(shù)語專業(yè)術(shù)語含義根也叫根結(jié)點(diǎn)(沒有前驅(qū))葉子也叫704.3樹的表示法4.3樹的表示法714.4樹的表示法4.4樹的表示法724.5二叉樹的概念二叉樹由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的互不相交的樹組成：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）左子樹和右子樹次序不能顛倒（有序樹）4.5二叉樹的概念二叉樹由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹734.6樹轉(zhuǎn)化為二叉樹左孩子右兄弟表示法可以將一顆多叉樹轉(zhuǎn)化為一顆二叉樹。4.6樹轉(zhuǎn)化為二叉樹左孩子右兄弟表示法可以將一顆多叉樹轉(zhuǎn)化744.7滿二叉樹和完全二叉樹4.7滿二叉樹和完全二叉樹754.7樹的順序存儲多叉樹順序存儲的缺陷4.7樹的順序存儲多叉樹順序存儲的缺陷764.7完全二叉樹的順序存儲非完全二叉樹存儲缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便完全二叉樹存儲4.7完全二叉樹的順序存儲非完全二叉樹存儲缺點(diǎn)：完全二叉樹774.7二叉樹的鏈?zhǔn)酱鎯Χ骀湸鎯?.7二叉樹的鏈?zhǔn)酱鎯Χ骀湸鎯?84.7二叉樹的鏈?zhǔn)酱鎯θ骀湸鎯?.7二叉樹的鏈?zhǔn)酱鎯θ骀湸鎯?94.8二叉樹的遍歷遍歷是指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游），遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。牢記一種約定，對每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。遍歷方式特點(diǎn)先序遍歷(先根遍歷，DLR)根->左子樹->右子樹中序遍歷(中根