數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)基礎(chǔ)講義基礎(chǔ)講義第一頁(yè)，共45頁(yè)。第1頁(yè)/共45頁(yè)第二頁(yè)，共45頁(yè)。算法+數(shù)據(jù)結(jié)構(gòu)(sh j ji u) = 程序設(shè)計(jì) 處理問題的策略給出問題的數(shù)學(xué)模型編制出的指令集處理問題用計(jì)算機(jī)問題問題(wnt)(wnt)構(gòu)建數(shù)學(xué)模型構(gòu)建數(shù)學(xué)模型程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)第2頁(yè)/共45頁(yè)第三頁(yè)，共45頁(yè)。第3頁(yè)/共45頁(yè)第四頁(yè)，共45頁(yè)。 第4頁(yè)/共45頁(yè)第五頁(yè)，共45頁(yè)。 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲(chǔ)順序

2、存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)列隊(duì)列樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)第5頁(yè)/共45頁(yè)第六頁(yè)，共45頁(yè)。物理(wl)結(jié)構(gòu)第6頁(yè)/共45頁(yè)第七頁(yè)，共45頁(yè)。第7頁(yè)/共45頁(yè)第八頁(yè)，共45頁(yè)。第8頁(yè)/共45頁(yè)第九頁(yè)，共45頁(yè)。執(zhí)行次數(shù)函數(shù)執(zhí)行次數(shù)函數(shù)階階非正式術(shù)語(yǔ)非正式術(shù)語(yǔ)12O(1)常數(shù)階2n+3O(n)線性階3n2+2n+1O(n2)平方階5log2n+20O(logn)對(duì)數(shù)階2n+3nlog2n+19O(nlogn)nlogn階6n3+2n2+3n+4O(n3)立方階2nO(2n)指數(shù)階第9頁(yè)/共45頁(yè)第十頁(yè)，共45頁(yè)。平方(pngfng)階: O(n2)第10頁(yè)/共45頁(yè)第十一頁(yè)

3、，共45頁(yè)。第11頁(yè)/共45頁(yè)第十二頁(yè)，共45頁(yè)。第12頁(yè)/共45頁(yè)第十三頁(yè)，共45頁(yè)。頭指針頭指針a0a1an1( a )( b )第13頁(yè)/共45頁(yè)第十四頁(yè)，共45頁(yè)。頭指針頭指針a0a1an1( a )( b )第14頁(yè)/共45頁(yè)第十五頁(yè)，共45頁(yè)。第15頁(yè)/共45頁(yè)第十六頁(yè)，共45頁(yè)。第16頁(yè)/共45頁(yè)第十七頁(yè)，共45頁(yè)。第17頁(yè)/共45頁(yè)第十八頁(yè)，共45頁(yè)。第18頁(yè)/共45頁(yè)第十九頁(yè)，共45頁(yè)。隊(duì)列(duli)的順序存儲(chǔ)第19頁(yè)/共45頁(yè)第二十頁(yè)，共45頁(yè)。隊(duì)列(duli)的鏈?zhǔn)酱鎯?chǔ)第20頁(yè)/共45頁(yè)第二十一頁(yè)，共45頁(yè)。第21頁(yè)/共45頁(yè)第二十二頁(yè)，共45頁(yè)。第22頁(yè)/共45頁(yè)第二

4、十三頁(yè)，共45頁(yè)。專業(yè)術(shù)語(yǔ)專業(yè)術(shù)語(yǔ)含義含義根也叫根結(jié)點(diǎn)(沒有前驅(qū))葉子也叫終端結(jié)點(diǎn)(沒有后繼)森林指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))有序樹結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）無(wú)序樹結(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)的層次從根到該

5、結(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ù))第23頁(yè)/共45頁(yè)第二十四頁(yè)，共45頁(yè)。第24頁(yè)/共45頁(yè)第二十五頁(yè)，共45頁(yè)。第25頁(yè)/共45頁(yè)第二十六頁(yè)，共45頁(yè)。第26頁(yè)/共45頁(yè)第二十七頁(yè)，共45頁(yè)。第27頁(yè)/共45頁(yè)第二十八頁(yè)，共45頁(yè)。第28頁(yè)/共45頁(yè)第二十九頁(yè)，共45頁(yè)。第29頁(yè)/共45頁(yè)第三十頁(yè)，共45頁(yè)。完全(wnqun)二叉樹存儲(chǔ)第30頁(yè)/共45頁(yè)第三十一頁(yè)，共45頁(yè)。二叉鏈存儲(chǔ)(cn ch)第31頁(yè)/共45頁(yè)第三十二頁(yè)，共45頁(yè)。三叉鏈存儲(chǔ)(cn

6、ch)第32頁(yè)/共45頁(yè)第三十三頁(yè)，共45頁(yè)。遍歷是指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游），遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算(yn sun)的前提，是二叉樹一切運(yùn)算(yn sun)的基礎(chǔ)和核心。牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。 遍歷方式遍歷方式特點(diǎn)特點(diǎn)先序遍歷(先根遍歷，DLR)根 - 左子樹 - 右子樹中序遍歷(中根遍歷，LDR)左子樹 - 根 - 右子樹后序遍歷(后根遍歷，LRD)左子樹 - 右子樹 - 根第33頁(yè)/共45頁(yè)第三十四頁(yè)，共45頁(yè)。第34頁(yè)/共45頁(yè)第三十五頁(yè)，共45頁(yè)。二叉樹的動(dòng)態(tài)創(chuàng)建和釋放二叉樹的遞歸遍歷計(jì)算二叉樹葉子節(jié)點(diǎn)數(shù)目(shm)計(jì)算二叉樹高度第35頁(yè)/共45頁(yè)第三十六頁(yè)，共45頁(yè)。第36頁(yè)/共45頁(yè)第三十七頁(yè)，共45頁(yè)。第37頁(yè)/共45頁(yè)第三十八頁(yè)，共45頁(yè)。順序查找(ch zho)二分查找(ch zho)第38頁(yè)/共45頁(yè)第三十九頁(yè)，共45頁(yè)。第39頁(yè)/共45頁(yè)第四十頁(yè)，共45頁(yè)。冒泡選擇(xunz)插入排序第40頁(yè)/共45頁(yè)第四十一頁(yè)，共4