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

“〞數(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ì)列鏈表二叉樹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í)講解邏輯結(jié)構(gòu)集合結(jié)構(gòu)(集)結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外沒有其它關(guān)系知識(shí)講解邏輯結(jié)構(gòu)線性結(jié)構(gòu)(表)結(jié)構(gòu)中的數(shù)據(jù)元素具有一對(duì)一的前后關(guān)系知識(shí)講解邏輯結(jié)構(gòu)樹型結(jié)構(gòu)(樹)結(jié)構(gòu)中的數(shù)據(jù)元素具有一對(duì)多的父子關(guān)系知識(shí)講解邏輯結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)(圖)結(jié)構(gòu)中的數(shù)據(jù)元素具有多對(duì)多的交叉映射關(guān)系知識(shí)講解物理結(jié)構(gòu)順序結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素存放在一段連續(xù)的地址空間中知識(shí)講解物理結(jié)構(gòu)順序結(jié)構(gòu)隨機(jī)訪問方便，空間利用率低，插入刪除不方便知識(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)的地址知識(shí)講解物理結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插入刪除方便，空間利用率高，隨機(jī)訪問不方便知識(shí)講解邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系每種邏輯結(jié)構(gòu)采用何種物理結(jié)構(gòu)實(shí)現(xiàn)，并沒有一定之規(guī)，通常根據(jù)實(shí)現(xiàn)的難易程度，以及在時(shí)間和空間復(fù)雜度方面的要求，選擇最適合的物理結(jié)構(gòu)，亦不排除復(fù)合多種物理結(jié)構(gòu)實(shí)現(xiàn)一種邏輯結(jié)構(gòu)的可能知識(shí)講解運(yùn)算結(jié)構(gòu)創(chuàng)立與銷毀分配資源、建立結(jié)構(gòu)、釋放資源插入與刪除增加、減少數(shù)據(jù)元素獲取與修改遍歷、迭代、隨機(jī)訪問排序與查找算法應(yīng)用知識(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í)現(xiàn)知識(shí)講解堆棧后進(jìn)(壓入/push)先出(彈出/pop)知識(shí)講解實(shí)現(xiàn)基于順序表的堆棧初始化空間、棧頂指針、判空判滿知識(shí)講解實(shí)現(xiàn)基于鏈?zhǔn)奖淼亩褩?dòng)態(tài)分配、棧頂指針、注意判空知識(shí)講解隊(duì)列先進(jìn)(壓入/push)先出(彈出/pop)18知識(shí)講解實(shí)現(xiàn)基于順序表的隊(duì)列初始化空間、前彈后壓、循環(huán)使用、判空判滿知識(shí)講解實(shí)現(xiàn)基于鏈?zhǔn)奖淼年?duì)列動(dòng)態(tài)分配、前后指針、注意判空知識(shí)講解鏈表地址不連續(xù)的節(jié)點(diǎn)序列，彼此通過指針相互連接根據(jù)不同的結(jié)構(gòu)特征，將鏈表分為：?jiǎn)蜗蚓€性鏈表單向循環(huán)鏈表雙向線性鏈表雙線循環(huán)鏈表數(shù)組鏈表鏈表數(shù)組二維鏈表21知識(shí)講解鏈表單向線性鏈表知識(shí)講解鏈表單向循環(huán)鏈表知識(shí)講解鏈表雙向線性鏈表知識(shí)講解鏈表雙向循環(huán)鏈表知識(shí)講解鏈表數(shù)組鏈表知識(shí)講解鏈表鏈表數(shù)組知識(shí)講解鏈表二維鏈表知識(shí)講解實(shí)現(xiàn)雙向線性鏈表結(jié)構(gòu)模型知識(shí)講解實(shí)現(xiàn)雙向線性鏈表插入節(jié)點(diǎn)知識(shí)講解實(shí)現(xiàn)雙向線性鏈表刪除節(jié)點(diǎn)知識(shí)講解二叉樹樹形結(jié)構(gòu)的最簡(jiǎn)模型，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)每個(gè)子節(jié)點(diǎn)有且僅有一個(gè)父節(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)具有遞歸的結(jié)構(gòu)特征，用遞歸的方法處理，可以簡(jiǎn)化算法三種遍歷序前序遍歷：D-L-R中序遍歷：L-D-R后序遍歷：L-R-D32知識(shí)講解二叉樹二叉樹的一般形式根節(jié)點(diǎn)、枝節(jié)點(diǎn)和葉節(jié)點(diǎn)父節(jié)點(diǎn)和子節(jié)點(diǎn)左子節(jié)點(diǎn)和右子節(jié)點(diǎn)左子樹和右子樹大小和高度(深度)知識(shí)講解二叉樹滿二叉樹每層節(jié)點(diǎn)數(shù)均到達(dá)最大值所有枝節(jié)點(diǎn)均有左右子樹知識(shí)講解二叉樹完全二叉樹除最下層外，各層節(jié)點(diǎn)數(shù)均到達(dá)最大值最下層的節(jié)點(diǎn)都連續(xù)集中在左邊知識(shí)講解二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)從上到下、從左到右，依次存放非完全二叉樹需用虛節(jié)點(diǎn)補(bǔ)成完全二叉樹知識(shí)講解二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)二叉鏈表，每個(gè)節(jié)點(diǎn)包括三個(gè)域，一個(gè)數(shù)據(jù)域和兩個(gè)分別指向其左右子節(jié)點(diǎn)的指針域知識(shí)講解二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)三叉鏈表，每個(gè)節(jié)點(diǎn)包括四個(gè)域，一個(gè)數(shù)據(jù)域、兩個(gè)分別指向其左右子節(jié)點(diǎn)的指針域和一個(gè)指向其父節(jié)點(diǎn)的指針域知識(shí)講解實(shí)現(xiàn)有序二叉樹有序二叉樹亦稱二叉搜索樹，假設(shè)非空樹那么滿足：假設(shè)左子樹非