數(shù)據(jù)結(jié)構(gòu)基礎講義PPT學習教案

1、會計學1數(shù)據(jù)結(jié)構(gòu)基礎講義數(shù)據(jù)結(jié)構(gòu)基礎講義第1頁/共45頁算法+數(shù)據(jù)結(jié)構(gòu) = 程序設計 處理問題的策略給出問題的數(shù)學模型編制出的指令集處理問題用計算機問題問題構(gòu)建數(shù)學模型構(gòu)建數(shù)學模型程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)第2頁/共45頁第3頁/共45頁 第4頁/共45頁 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算：查找、排序、插入、刪除、修改等數(shù)據(jù)的運算：查找、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈式存儲鏈式存儲 線性表線性表棧棧隊列隊列樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)第5頁/共45頁物理結(jié)構(gòu)第6頁/共45頁第7頁/共45頁第8頁/共45頁執(zhí)

2、行次數(shù)函數(shù)執(zhí)行次數(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ù)階第9頁/共45頁平方階: O(n2)第10頁/共45頁第11頁/共45頁第12頁/共45頁頭指針頭指針a0a1an1( a )( b )第13頁/共45頁頭指針頭指針a0a1an1( a )( b )第14頁/共45頁第15頁/共45頁第16頁/共45頁第17頁/共45頁第18頁/共45頁隊列的順序存儲第19頁/共45頁隊列的鏈

3、式存儲第20頁/共45頁第21頁/共45頁第22頁/共45頁專業(yè)術語專業(yè)術語含義含義根也叫根結(jié)點(沒有前驅(qū))葉子也叫終端結(jié)點(沒有后繼)森林指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))有序樹結(jié)點各子樹從左至右有序，不能互換（左為第一）無序樹結(jié)點各子樹可互換位置雙親 即上層的那個結(jié)點(直接前驅(qū)) parent孩子即下層結(jié)點的子樹 (直接后繼) child兄弟同一雙親下的同層結(jié)點（孩子之間互稱兄弟）sibling堂兄弟即雙親位于同一層的結(jié)點（但并非同一雙親）cousin祖先即從根到該結(jié)點所經(jīng)分支的所有結(jié)點子孫即該結(jié)點下層子樹中的任一結(jié)點結(jié)點也叫節(jié)點，即樹的數(shù)據(jù)元素結(jié)點的度、樹的度結(jié)點掛接的子樹

4、數(shù)、所有結(jié)點度中的最大值結(jié)點的層次從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）終端結(jié)點即度為0的結(jié)點，即葉子 分支結(jié)點除樹根以外的結(jié)點（也稱為內(nèi)部結(jié)點）樹的深度(或高度)指所有結(jié)點中最大的層數(shù)(從根節(jié)點到最低層的結(jié)點層數(shù))第23頁/共45頁第24頁/共45頁第25頁/共45頁第26頁/共45頁第27頁/共45頁第28頁/共45頁第29頁/共45頁完全二叉樹存儲第30頁/共45頁二叉鏈存儲第31頁/共45頁三叉鏈存儲第32頁/共45頁遍歷是指按某條搜索路線遍訪每個結(jié)點且不重復（又稱周游），遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。牢記一種約定，對每個結(jié)點的查看都是“先左后右”。 遍歷方式遍歷方式特點特點先序遍歷(先根遍歷，DLR)根 - 左子樹 - 右子樹中序遍歷(中根遍歷，LDR)左子樹 - 根 - 右子樹后序遍歷(后根遍歷，LRD)左子樹 - 右子樹 - 根第33頁/共45頁第34頁/共45頁二叉樹的動態(tài)創(chuàng)建和釋放二叉樹的遞歸遍歷計算二叉樹葉子節(jié)點數(shù)目計算二叉樹高度第35頁/共45頁第36頁/共45頁第37頁/共45頁順序查找二分查找第38頁/共45頁第3