數(shù)據(jù)結(jié)構(gòu)詳解課件

“”數(shù)據(jù)結(jié)構(gòu)1“”數(shù)據(jù)結(jié)構(gòu)1知識導(dǎo)入全程目標(biāo)數(shù)據(jù)結(jié)構(gòu)的基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)運算結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本實現(xiàn)堆棧隊列鏈表二叉樹2知全程目標(biāo)數(shù)據(jù)結(jié)構(gòu)的基本概念2知識講解數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)的集合數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式數(shù)據(jù)結(jié)構(gòu)的選擇直接影響計算機程序的運行效率(時間復(fù)雜度)和存儲效率(空間復(fù)雜度)計算機程序設(shè)計=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個層次抽象層——邏輯結(jié)構(gòu)結(jié)構(gòu)層——物理結(jié)構(gòu)實現(xiàn)層——運算結(jié)構(gòu)3知數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系知識講解邏輯結(jié)構(gòu)集合結(jié)構(gòu)(集)結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外沒有其它關(guān)系4知邏輯結(jié)構(gòu)集合結(jié)構(gòu)(集)4知識講解邏輯結(jié)構(gòu)線性結(jié)構(gòu)(表)結(jié)構(gòu)中的數(shù)據(jù)元素具有一對一的前后關(guān)系5知邏輯結(jié)構(gòu)線性結(jié)構(gòu)(表)5知識講解邏輯結(jié)構(gòu)樹型結(jié)構(gòu)(樹)結(jié)構(gòu)中的數(shù)據(jù)元素具有一對多的父子關(guān)系6知邏輯結(jié)構(gòu)樹型結(jié)構(gòu)(樹)6知識講解邏輯結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)(圖)結(jié)構(gòu)中的數(shù)據(jù)元素具有多對多的交叉映射關(guān)系7知邏輯結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)(圖)7知識講解物理結(jié)構(gòu)順序結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素存放在一段連續(xù)的地址空間中8知物理結(jié)構(gòu)順序結(jié)構(gòu)8知識講解物理結(jié)構(gòu)順序結(jié)構(gòu)隨機訪問方便，空間利用率低，插入刪除不方便9知物理結(jié)構(gòu)順序結(jié)構(gòu)9知識講解物理結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素存放在彼此獨立的地址空間中每個獨立的地址空間稱為節(jié)點節(jié)點除保存數(shù)據(jù)外，還需要保存相關(guān)節(jié)點的地址10知物理結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)10知識講解物理結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插入刪除方便，空間利用率高，隨機訪問不方便11知物理結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)11知識講解邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系每種邏輯結(jié)構(gòu)采用何種物理結(jié)構(gòu)實現(xiàn)，并沒有一定之規(guī)，通常根據(jù)實現(xiàn)的難易程度，以及在時間和空間復(fù)雜度方面的要求，選擇最適合的物理結(jié)構(gòu)，亦不排除復(fù)合多種物理結(jié)構(gòu)實現(xiàn)一種邏輯結(jié)構(gòu)的可能12知邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系12知識講解運算結(jié)構(gòu)創(chuàng)建與銷毀分配資源、建立結(jié)構(gòu)、釋放資源插入與刪除增加、減少數(shù)據(jù)元素獲取與修改遍歷、迭代、隨機訪問排序與查找算法應(yīng)用13知運算結(jié)構(gòu)創(chuàng)建與銷毀13知識講解數(shù)據(jù)結(jié)構(gòu)的基本實現(xiàn)堆?；陧樞虮淼膶崿F(xiàn)基于鏈?zhǔn)奖淼膶崿F(xiàn)隊列基于順序表的實現(xiàn)基于鏈?zhǔn)奖淼膶崿F(xiàn)鏈表雙向線性鏈表的實現(xiàn)二叉樹有序二叉樹(二叉搜索樹)的實現(xiàn)14知數(shù)據(jù)結(jié)構(gòu)的基本實現(xiàn)堆棧14知識講解堆棧后進(jìn)(壓入/push)先出(彈出/pop)15知堆棧后進(jìn)(壓入/push)先出(彈出/pop)15知識講解實現(xiàn)基于順序表的堆棧初始化空間、棧頂指針、判空判滿16知實現(xiàn)基于順序表的堆棧初始化空間、棧頂指針、判空判滿16知識講解實現(xiàn)基于鏈?zhǔn)奖淼亩褩討B(tài)分配、棧頂指針、注意判空17知實現(xiàn)基于鏈?zhǔn)奖淼亩褩討B(tài)分配、棧頂指針、注意判空17知識講解隊列先進(jìn)(壓入/push)先出(彈出/pop)18知隊列先進(jìn)(壓入/push)先出(彈出/pop)18知識講解實現(xiàn)基于順序表的隊列初始化空間、前彈后壓、循環(huán)使用、判空判滿19知實現(xiàn)基于順序表的隊列初始化空間、前彈后壓、循環(huán)使用、判空判知識講解實現(xiàn)基于鏈?zhǔn)奖淼年犃袆討B(tài)分配、前后指針、注意判空20知實現(xiàn)基于鏈?zhǔn)奖淼年犃袆討B(tài)分配、前后指針、注意判空20知識講解鏈表地址不連續(xù)的節(jié)點序列，彼此通過指針相互連接根據(jù)不同的結(jié)構(gòu)特征，將鏈表分為：單向線性鏈表單向循環(huán)鏈表雙向線性鏈表雙線循環(huán)鏈表數(shù)組鏈表鏈表數(shù)組二維鏈表21知鏈表地址不連續(xù)的節(jié)點序列，彼此通過指針相互連接21知識講解鏈表單向線性鏈表22知鏈表單向線性鏈表22知識講解鏈表單向循環(huán)鏈表23知鏈表單向循環(huán)鏈表23知識講解鏈表雙向線性鏈表24知鏈表雙向線性鏈表24知識講解鏈表雙向循環(huán)鏈表25知鏈表雙向循環(huán)鏈表25知識講解鏈表數(shù)組鏈表26知鏈表數(shù)組鏈表26知識講解鏈表鏈表數(shù)組27知鏈表鏈表數(shù)組27知識講解鏈表二維鏈表28知鏈表二維鏈表28知識講解實現(xiàn)雙向線性鏈表結(jié)構(gòu)模型29知實現(xiàn)雙向線性鏈表結(jié)構(gòu)模型29知識講解實現(xiàn)雙向線性鏈表插入節(jié)點30知實現(xiàn)雙向線性鏈表插入節(jié)點30知識講解實現(xiàn)雙向線性鏈表刪除節(jié)點31知實現(xiàn)雙向線性鏈表刪除節(jié)點31知識講解二叉樹樹形結(jié)構(gòu)的最簡模型，每個節(jié)點最多有兩個子節(jié)點每個子節(jié)點有且僅有一個父節(jié)點，整棵樹只有一個根節(jié)點具有遞歸的結(jié)構(gòu)特征，用遞歸的方法處理，可以簡化算法三種遍歷序前序遍歷：D-L-R中序遍歷：L-D-R后序遍歷：L-R-D32知二叉樹樹形結(jié)構(gòu)的最簡模型，每個節(jié)點最多有兩個子節(jié)點32知識講解二叉樹二叉樹的一般形式根節(jié)點、枝節(jié)點和葉節(jié)點父節(jié)點和子節(jié)點左子節(jié)點和右子節(jié)點左子樹和右子樹大小和高度(深度)33知二叉樹二叉樹的一般形式33知識講解二叉樹滿二叉樹每層節(jié)點數(shù)均達(dá)到最大值所有枝節(jié)點均有左右子樹34知二叉樹滿二叉樹34知識講解二叉樹完全二叉樹除最下層外，各層節(jié)點數(shù)均達(dá)到最大值最下層的節(jié)點都連續(xù)集中在左邊35知二叉樹完全二叉樹35知識講解二叉樹的存儲結(jié)構(gòu)順序存儲從上到下、從左到右，依次存放非完全二叉樹需用虛節(jié)點補成完全二叉樹36知二叉樹的存儲結(jié)構(gòu)順序存儲36知識講解二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Χ骀湵?，每個節(jié)點包括三個域，一個數(shù)據(jù)域和兩個分別指向其左右子節(jié)點的指針域37知二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯?7知識講解二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯θ骀湵?，每個節(jié)點包括四個域，一個數(shù)據(jù)域、兩個分別指向其左右子節(jié)點的指針域和一個指向其父節(jié)點的指針域38知二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯?8知識講解實現(xiàn)有序二叉樹有序二叉樹亦稱二叉搜索樹，若非空樹則滿足：若左子