數(shù)據(jù)結構基礎講義學習教案

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

2、存儲 鏈式存儲鏈式存儲 線性表線性表棧棧隊列隊列樹形結構樹形結構圖形結構圖形結構第5頁/共45頁第六頁，共45頁。物理(wl)結構第6頁/共45頁第七頁，共45頁。第7頁/共45頁第八頁，共45頁。第8頁/共45頁第九頁，共45頁。執(zhí)行次數(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頁第十頁，共45頁。平方(pngfng)階: O(n2)第10頁/共45頁第十一頁

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

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

5、結點的層數(shù)（根結點算第一層）終端結點即度為0的結點，即葉子 分支結點除樹根以外的結點（也稱為內部結點）樹的深度(或高度)指所有結點中最大的層數(shù)(從根節(jié)點到最低層的結點層數(shù))第23頁/共45頁第二十四頁，共45頁。第24頁/共45頁第二十五頁，共45頁。第25頁/共45頁第二十六頁，共45頁。第26頁/共45頁第二十七頁，共45頁。第27頁/共45頁第二十八頁，共45頁。第28頁/共45頁第二十九頁，共45頁。第29頁/共45頁第三十頁，共45頁。完全(wnqun)二叉樹存儲第30頁/共45頁第三十一頁，共45頁。二叉鏈存儲(cn ch)第31頁/共45頁第三十二頁，共45頁。三叉鏈存儲(cn

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