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

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