數(shù)據(jù)結(jié)構(gòu)-郝斌

數(shù)據(jù)結(jié)構(gòu)的概述定義我們?nèi)绾伟熏F(xiàn)實中大量而反復(fù)的問題以特定的數(shù)據(jù)類型和特定的存儲結(jié)構(gòu)保存到主存儲器(內(nèi)存)中，以及在此根底上為實現(xiàn)某個功能〔比方查找某個元素，刪除某個元素，對所有元素進行排序〕而執(zhí)行的相應(yīng)的操作，這個相應(yīng)的操作也叫做算法。數(shù)據(jù)結(jié)構(gòu)=個體+個體的關(guān)系算法=對存儲數(shù)據(jù)的操作狹義：數(shù)據(jù)結(jié)構(gòu)是專門研究數(shù)據(jù)存儲的問題數(shù)據(jù)的存儲包含兩方面：個體的存儲+個體關(guān)系的存儲廣義：數(shù)據(jù)結(jié)構(gòu)既包含數(shù)據(jù)的存儲也包含數(shù)據(jù)的操作對存儲數(shù)據(jù)的操作就是算法算法狹義：算法是和數(shù)據(jù)的存儲方式密切相關(guān)廣義：算法和數(shù)據(jù)的存儲方式無關(guān)，這就是泛型思想衡量算法的標(biāo)準(zhǔn)：時間復(fù)雜度大概程序要執(zhí)行的次數(shù)，而并非是執(zhí)行的時間〔因為同一程序在不同機器上執(zhí)行的時間是不一樣的，有差異〕空間復(fù)雜度算法執(zhí)行過程中大概所占用的最大內(nèi)存難易程度健壯性數(shù)據(jù)結(jié)構(gòu)的地位：數(shù)據(jù)結(jié)構(gòu)是軟件中最核心的課程程序=數(shù)據(jù)的存儲+數(shù)據(jù)的操作+可以被計算機執(zhí)行的語言泛型對于同一種邏輯結(jié)構(gòu)，無論該邏輯結(jié)構(gòu)的物理存儲是什么樣子的，我們可以對它執(zhí)行相同的操作。數(shù)據(jù)的存儲有幾種：線性：連續(xù)存儲：【數(shù)組】優(yōu)點：存取速度快缺點：事先必須知道數(shù)組的長度插入刪除元素很慢空間通常是有限的需要大塊連續(xù)的內(nèi)存塊離散存儲【鏈表】優(yōu)點：空間沒有限制插入刪除元素很快缺點：存取速度很慢棧和隊列是一種特殊的線性結(jié)構(gòu)，是連續(xù)存儲或離散存儲的一種應(yīng)用線性結(jié)構(gòu)的應(yīng)用------棧定義：一種可以實現(xiàn)“先進后出“的存儲結(jié)構(gòu)，類似于箱子分類：靜態(tài)棧動態(tài)棧算法：出棧壓棧應(yīng)用：函數(shù)調(diào)用中斷表達式求值內(nèi)存分配緩沖處理迷宮intmain(void){intp;int*m=(int*)malloc(100);}如靜態(tài)變量p和m是在棧中分配，有操作系統(tǒng)自動分配和釋放。而(int*)malloc(100);執(zhí)行后，將在堆中分配一塊100字節(jié)的內(nèi)存，由程序員手動分配。棧的示意圖pToppToppBottom33無效數(shù)據(jù)nullNulNULL3333線性結(jié)構(gòu)的應(yīng)用------隊列定義：一種可以實現(xiàn)“先進先出”的存儲結(jié)構(gòu)分類：鏈?zhǔn)疥犃校?----用鏈表實現(xiàn)〔比擬簡單〕靜態(tài)隊列：-----用數(shù)組實現(xiàn)靜態(tài)隊列通常都必須是循環(huán)隊列應(yīng)用：所有和時間有關(guān)的事件都有隊列的影子循環(huán)隊列的講解〔1〕靜態(tài)隊列為什么必須是循環(huán)隊列665第四個4第三個3第二個2第一個10Frontrear現(xiàn)在如果一個數(shù)組里面存了四個元素，那么front就只想第一個有效元素，而real指向最后一個元素的下一個元素，當(dāng)增加元素時，只能在rear一端增加，即rear向上移。刪除元素時，只能在front一端刪除元素，即front向上移。但是如果一直增增刪刪，那么就會造成rear端溢出，而front端浪費，所以對于這種情況，可以采用循環(huán)隊列的形式，即當(dāng)rear已經(jīng)指向數(shù)組最后一個元素時，那么就可以轉(zhuǎn)而將rear指向數(shù)組的第一個空出來的空間?！?〕循環(huán)隊列需要幾個參數(shù)來確定需要2個參數(shù)來確定：front和rear〔3〕循環(huán)隊列各個參數(shù)的含義：2個參數(shù)在不同場合有不同的含義隊列初始化front和rear的值都為零隊列非空front代表的是隊列的第一個元素rear代表的是隊列的最后一個有效元素的下一個元素隊列為空front和real的值相等，但不一定為零〔4〕循環(huán)隊列入隊偽算法講解：兩步完成：將值存入rear所代表的位置錯誤的寫法：rear=rear+1;正確的寫法是：rear=(rear+1)%數(shù)組的長度〔5〕循環(huán)隊列出隊偽算法講解Front=〔front+1〕%數(shù)組的長度(6)如何判斷循環(huán)隊列是否為空如果front與rear的值相等，那么該隊列就一定為空〔7〕如何判斷循環(huán)隊列是否已滿因為front的值可能比rear大，也可能比他小，也可能相等所以有兩種方式:多增加一個標(biāo)識是否滿的參數(shù)少用一個元素【通常用此種方式】如果front和rear的值相差1，且front>rear,那么證明隊列已滿。用C語言偽算法表示為：if((rear+1)%數(shù)組長度==front)已滿else未滿專題：遞歸：知識點一：函數(shù)的調(diào)用當(dāng)在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行被調(diào)函數(shù)之前，系統(tǒng)需要完成三件事：將所有的實際參數(shù)，返回地址等信息傳遞給被調(diào)函數(shù)。為被調(diào)函數(shù)的局部變量〔也包括形參〕分配存儲空間將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口從被調(diào)函數(shù)返回主調(diào)函數(shù)之前，系統(tǒng)也要完成三件事：保存被調(diào)函數(shù)的返回結(jié)果釋放被調(diào)函數(shù)所占的存儲空間依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)當(dāng)有多個函數(shù)相互調(diào)用時，按照“后調(diào)用先返回”的原那么，上述函數(shù)之間信息傳遞和控制轉(zhuǎn)移必須借助“?！眮韺崿F(xiàn)，即系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每當(dāng)調(diào)用一個函數(shù)時，將在棧頂分配一個存儲區(qū)，進行壓棧操作，每當(dāng)一個函數(shù)退出時，就釋放它的存儲區(qū)，就進行出棧操作，當(dāng)前運行的函數(shù)永遠都在棧頂位置。A函數(shù)調(diào)用A函數(shù)和A函數(shù)調(diào)用B函數(shù)在計算機看來是沒有任何區(qū)別的，只不過用我們?nèi)粘５乃季S方式比擬怪異而已。知識點二：遞歸必須滿足的三個條件遞歸必須得有一個明確的終止條件該函數(shù)所處理的數(shù)據(jù)規(guī)模必須在遞減這個轉(zhuǎn)化必須是可解的知識點三：遞歸和循環(huán)的優(yōu)缺點比擬遞歸：易于理解速度慢存儲空間大循環(huán)不易理解速度快存儲空間小知識點四：遞歸的應(yīng)用樹和森林就是以遞歸的方式定義的樹和圖的很多算法都是以遞歸來實現(xiàn)的很多數(shù)學(xué)公式就是以遞歸的方式定義的斐波拉契序列：12358132134非線性：樹定義：專業(yè)定義：有且只有一個稱為根的節(jié)點有假設(shè)干個互不相交的子樹，這些子樹本身也是一棵樹。通俗的定義：樹是由節(jié)點和邊組成。每個節(jié)點只有一個父節(jié)點但可以有多個子節(jié)點但有一個節(jié)點例外，該節(jié)點沒有父節(jié)點，此節(jié)點稱為根節(jié)點。樹相關(guān)的專業(yè)術(shù)語節(jié)點根節(jié)點父節(jié)點子節(jié)點有直接父子關(guān)系的才能叫子節(jié)點子孫節(jié)點堂兄弟節(jié)點其父節(jié)點是兄弟節(jié)點的為堂兄弟節(jié)點深度從根節(jié)點到對底層節(jié)點的層數(shù)稱之為深度根節(jié)點是第一層葉子節(jié)點沒有子節(jié)點的節(jié)點非終端節(jié)點實際就是非葉子節(jié)點度子節(jié)點的個數(shù)稱為度，整個樹的度就是所有節(jié)點的度數(shù)中，度數(shù)最大的那個為整個樹的度數(shù)樹的分類一般樹任意一個節(jié)點的子節(jié)點的個數(shù)都不受限制，子節(jié)點的順序可以更改也可以不能更改，能更改的樹為無序一般樹，不能更改的為有序一般樹二叉樹任意一個節(jié)點的子節(jié)點個數(shù)最多兩個，且子節(jié)點的位置不可更改，即左子樹和右子樹的位置不可更改。分類：一般二叉樹滿二叉樹在不增加樹的層數(shù)的前提下，無法再多添加一個節(jié)點的二叉樹就是滿二叉樹，及所有的節(jié)點都是兩個度數(shù)〔兩個子節(jié)點〕完全二叉樹如果只是刪除了滿二叉樹最底層最右邊的連續(xù)假設(shè)干個節(jié)點，這樣形成的二叉樹就是完全二叉樹。滿二叉樹只是完全二叉樹的一個特例。森林n個互不相交的樹的集合樹的存儲二叉樹的存儲連續(xù)存儲用數(shù)組存儲【適用于完全二叉樹，不是完全二叉樹的樹補充為完全二叉樹】優(yōu)點:查找某個節(jié)點的父節(jié)點和子節(jié)點〔也包括判斷有沒有子節(jié)點〕方便快速缺點：耗用內(nèi)存空間過大鏈?zhǔn)酱鎯蓚€指針域分別指向兩個子節(jié)點，沒有子節(jié)點的為空優(yōu)點：耗用內(nèi)存空間小缺點：查找父節(jié)點不方便一般樹的存儲雙親表示法AABCDEFGACDEFGB-1006620此方法求父節(jié)點方便，但求子節(jié)點不方便。注意：此方法是用連續(xù)存儲空間的數(shù)組來存儲的，只不過數(shù)組的元素是C語言的struct或java和C++的對象，struct或?qū)ο罄镉钟袃蓚€元素數(shù)值域父節(jié)點下標(biāo)0123456孩子表示法AABCDEFGACDEFGB&B->&C->&DNULL&GNULLNULLNULL&E->&F此方法求子節(jié)點方便，但求父節(jié)點不方便。數(shù)值域子節(jié)點指針域鏈表0123456雙親孩子表示法ABABCDEFG&B->&C->&DNULL&GNULLNULLNULL&E->&F此方法求父節(jié)點和子節(jié)點都很方便，這也是用一塊連續(xù)數(shù)組存儲空間實現(xiàn)的數(shù)值域父節(jié)點下標(biāo)子節(jié)點指針域鏈表0123456A-1C0D0E6

F6G2B0二叉樹表示法(1)先把一個普通樹轉(zhuǎn)換為二叉樹，再存儲二叉樹。具體轉(zhuǎn)換方法：設(shè)法保證任意一個節(jié)點的左指針域指向它的第一個孩子右指針域指向它的下一個兄弟只要能滿足條件，就可以把一個普通樹轉(zhuǎn)化為二叉樹。一個普通樹轉(zhuǎn)化成的二叉樹一定沒有右子樹森林的存儲〔1〕先把森林轉(zhuǎn)化為二叉樹，再存儲二叉樹具體轉(zhuǎn)換方法：將森林中的每個樹的節(jié)點當(dāng)做兄弟存儲；設(shè)法保證任意一個節(jié)點的左指針域指向它的第一個孩子,右指針域指向它的下一個兄弟只要滿足條件，就可以把一個森林轉(zhuǎn)化為二叉樹AA

AE

AF

AI

AG

AH

AC

AB

AD

AK

AJ

A森林轉(zhuǎn)化為二叉樹為A

AF

AH

AD

AE

AC

AB

AJ

AG

AI

AK

A

二叉樹的遍歷：先序遍歷【先訪問根節(jié)點】方法：(1)先訪問根節(jié)點(2)再先序訪問左子樹(3)再先序訪問右子樹AABCDEGFI先序遍歷順序：ABDGEHCFIH中序遍歷【中間訪問根節(jié)點】方法：(1)中序遍歷左子樹(2)再訪問根節(jié)點(3)再中序遍歷右子樹AABCDEGFI中序遍歷順序：GDBHEACIFH后序遍歷【最后訪問根節(jié)點】方法：(1)先中序