數(shù)據(jù)結(jié)構(gòu)筆記_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)筆記_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)筆記_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)筆記_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)筆記_第5頁(yè)
已閱讀5頁(yè),還剩26頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

文檔可能無(wú)法思考全面,請(qǐng)瀏覽后下載!文檔可能無(wú)法思考全面,請(qǐng)瀏覽后下載!/文檔可能無(wú)法思考全面,請(qǐng)瀏覽后下載!數(shù)據(jù)結(jié)構(gòu)筆記基礎(chǔ):數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)(data):是對(duì)客觀(guān)事物的符號(hào)表示,在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)總稱(chēng)數(shù)據(jù)元素(dataelement):是數(shù)據(jù)的基本單位,在計(jì)算機(jī)中通常被當(dāng)做一個(gè)整體進(jìn)行考慮和處理數(shù)據(jù)對(duì)象(dataobject):性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集數(shù)據(jù)結(jié)構(gòu)(datastructure):相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合4類(lèi)基本結(jié)構(gòu):集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形(網(wǎng)狀)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組DataStructure=(D,S),其中D是數(shù)據(jù)元素的有限集,S是D上關(guān)系的有限集數(shù)據(jù)結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系,因此又稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映像)稱(chēng)為物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))計(jì)算機(jī)中表示信息的最小單位是二進(jìn)制中的一位,叫做位(bit),一到若干位組成一個(gè)位串表示一個(gè)數(shù)據(jù)元素,這個(gè)位串稱(chēng)為元素或結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系在計(jì)算機(jī)中的表示有兩種:順序映像、非順序映像,并由此得到兩種存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ),前者運(yùn)用相對(duì)位置表示數(shù)據(jù)元素間的邏輯結(jié)構(gòu),后者借助指針任何一個(gè)算法的設(shè)計(jì)取決于數(shù)據(jù)(邏輯)結(jié)構(gòu),而實(shí)現(xiàn)依賴(lài)于存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱(chēng)數(shù)據(jù)類(lèi)型分兩種:原子類(lèi)型、結(jié)構(gòu)類(lèi)型,前者不可分解(例如int、char、float、void),后者結(jié)構(gòu)類(lèi)型由若干成分按某種結(jié)構(gòu)組成,可分解,成分既可以是非結(jié)構(gòu)的也可以是結(jié)構(gòu)的(例:數(shù)組)抽象數(shù)據(jù)類(lèi)型(AbstractDataType):是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作(P8)抽象數(shù)據(jù)類(lèi)型格式如下:ADT抽象數(shù)據(jù)類(lèi)型名{數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系:<數(shù)據(jù)關(guān)系的定義>數(shù)據(jù)操作:<數(shù)據(jù)操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名基本操作格式如下:基本操作名(參數(shù)表)初始條件:<初始條件描述>操作結(jié)果:<操作結(jié)果描述>多形數(shù)據(jù)類(lèi)型(polymorphicdatatype):是指其值得成分不確定的數(shù)據(jù)類(lèi)型(P9)抽象數(shù)據(jù)類(lèi)型可由固有數(shù)據(jù)類(lèi)型來(lái)表示和實(shí)現(xiàn)算法(概念)和算法分析(時(shí)、空性能)算法(algorithm):對(duì)特定問(wèn)題求解步驟的一種描述算法5特性:有窮、確定、可行、輸入、輸出1、有窮性:算法必須在可接受的時(shí)間內(nèi)執(zhí)行有窮步后結(jié)束2、確定性:每條指令必須要有確切含義,無(wú)二義性,并且只有唯一執(zhí)行路徑,即對(duì)相同的輸入只能得相同輸出3、可行性:算法中的操作都可通過(guò)已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)完成4、輸入:一個(gè)算法有一到多個(gè)輸入,并取自某個(gè)特定對(duì)象合集5、輸出:一個(gè)算法有一到多個(gè)輸出,這些輸出與輸入有著某些特定關(guān)系的量算法設(shè)計(jì)要求(好算法):正確性、可讀性、健壯性、效率與低存儲(chǔ)需求健壯性是指對(duì)于規(guī)范要求以外的輸入能夠判斷出這個(gè)輸入不符合規(guī)范要求,并能有合理的處理方式。算法效率的度量:事后統(tǒng)計(jì):程序運(yùn)行結(jié)束后借助計(jì)算機(jī)內(nèi)部計(jì)時(shí)功能,缺點(diǎn)一是必須先運(yùn)行依據(jù)算法編制的程序,二是受限于計(jì)算機(jī)軟硬件,導(dǎo)致掩蓋了算法本身的優(yōu)劣事前分析估計(jì):消耗時(shí)間影響因素:算法策略、問(wèn)題規(guī)模、編程語(yǔ)言、編譯程序產(chǎn)生的機(jī)器碼質(zhì)量、機(jī)器執(zhí)行指令的速度撇開(kāi)各種影響因素只考慮問(wèn)題的規(guī)模(通常用整數(shù)量n表示),記為問(wèn)題規(guī)模的函數(shù)算法時(shí)間取決于控制結(jié)構(gòu)(順序,分支,循環(huán))和固有數(shù)據(jù)類(lèi)型操作的綜合效果書(shū)寫(xiě)格式:T(n)=O(f(n))f(n)為n的某個(gè)函數(shù)時(shí)間復(fù)雜度:算法的漸近時(shí)間復(fù)雜度(asymptotictimecomplexity),它表示隨問(wèn)題規(guī)模的增大,算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同以循環(huán)最深層原操作為度量基準(zhǔn)頻度:該語(yǔ)句重復(fù)執(zhí)行的次數(shù)算法的存儲(chǔ)空間需求:空間復(fù)雜度(spacecomplexity):算法所需存儲(chǔ)空間度量,記作S(n)=O(f(n)),其中n為問(wèn)題規(guī)模的大小一、線(xiàn)性表線(xiàn)性表基本概念線(xiàn)性表(linear_list):n個(gè)數(shù)據(jù)元素的有限序列結(jié)構(gòu)特點(diǎn):存在唯一的被稱(chēng)作“第一個(gè)”、“最后一個(gè)”的數(shù)據(jù)元素,且除了第一個(gè)以外每個(gè)元素都有唯一前驅(qū),除最后一個(gè)以外都有唯一后繼在復(fù)雜線(xiàn)性表中存在:數(shù)據(jù)項(xiàng)->記錄->文件,例如每個(gè)學(xué)生情況為一個(gè)記錄,它由學(xué)號(hào)、性別數(shù)據(jù)項(xiàng)組成,多個(gè)學(xué)生記錄組成一個(gè)文件在形如(a1,...,ai-1,ai,ai+1,...,an)中,ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1,且形成直接前驅(qū)元素,直接后繼元素關(guān)系元素個(gè)數(shù)n定義為線(xiàn)性表長(zhǎng)度,n=0為空表相關(guān)操作算法見(jiàn)書(shū)(P20)線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(1)線(xiàn)性表順序表示和實(shí)現(xiàn)線(xiàn)性表順序存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中,鏈?zhǔn)酱鎯?chǔ)則不要求;順序結(jié)構(gòu)可以隨機(jī)訪(fǎng)問(wèn),鏈?zhǔn)浇Y(jié)構(gòu)可以無(wú)限擴(kuò)容確定存儲(chǔ)位置(計(jì)算公式):第i個(gè)元素:LOC(ai)=LOC(a1)+(i-1)*LL是偏移量,即每個(gè)元素占用存儲(chǔ)單元第ai+1個(gè)元素:LOC(ai+1)=LOC(ai)+La1(起始位置或基位置)C語(yǔ)言下標(biāo)從“0”開(kāi)始,則表中第i個(gè)元素是L.elem[i-1]當(dāng)對(duì)線(xiàn)性表進(jìn)行操作時(shí),被操作元素后面的元素角標(biāo)會(huì)相應(yīng)變化(前移、后移),算法(P24)(2)線(xiàn)性表鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)特點(diǎn):用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素(存儲(chǔ)單元不一定連續(xù))結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素及直接后繼的存儲(chǔ)位置信息,兩個(gè)域:數(shù)據(jù)域和指針域,指針域中存儲(chǔ)的信息稱(chēng)為指針或鏈,僅含有一個(gè)指針域故又稱(chēng)線(xiàn)性鏈表或單鏈表鏈表的插入:先增加一條指針再修改原指針頭指針指向第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置,最后一個(gè)結(jié)點(diǎn)的指針為空(NULL)鏈表表示方法及算法(P28)單鏈表第一個(gè)結(jié)點(diǎn)前加一個(gè)頭結(jié)點(diǎn)Head,其數(shù)據(jù)域可為空也可存儲(chǔ)一些附加信息(鏈長(zhǎng)等)假設(shè)p是指向線(xiàn)性表中i個(gè)元素(ai)的指針,則p->next是指向i+1個(gè)數(shù)據(jù)元素在單鏈表中,取得第i個(gè)元素必須從頭指針開(kāi)始尋找,因此單鏈表是非隨機(jī)的存儲(chǔ)結(jié)構(gòu)線(xiàn)性表指邏輯結(jié)構(gòu),從抽象數(shù)據(jù)層面來(lái)說(shuō)順序表和鏈表指物理存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu):離散、線(xiàn)性、層次、網(wǎng)狀應(yīng)用見(jiàn)書(shū)算法二、棧和隊(duì)列棧的基本概念棧(stack)是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表表尾為棧頂,表頭為棧底,遵循后進(jìn)先出原理((lastinfirston,LIFO),不含元素則為空棧操作:在棧頂插入(入棧)和刪除(出棧),棧初始化、判空、取棧頂元素(算法P45)棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)順序棧,即棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置初始棧時(shí)不應(yīng)限定棧的最大容量,基本做法是先為棧分配一個(gè)基本容量,然后在應(yīng)用過(guò)程中,不夠用再逐段擴(kuò)大(算法P46)遞歸棧與遞歸的實(shí)現(xiàn):一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù),稱(chēng)為遞歸函數(shù)階乘函數(shù)、2階Fibonacci數(shù)列、Ackerman函數(shù)、3階Hanoi問(wèn)題(多階呢?)(P54)函數(shù)調(diào)用函數(shù)執(zhí)行過(guò)程筆記(P56)隊(duì)列隊(duì)列先進(jìn)先出(firstinfirstout,F(xiàn)IFO),隊(duì)尾一端插入,隊(duì)首一端刪除元素(日常排隊(duì))隊(duì)列與棧均有八種基本操作(P59),隊(duì)列一般用鏈表實(shí)現(xiàn),棧用順序表實(shí)現(xiàn)雙端隊(duì)列(限定操作的隊(duì)列)(P60)棧和隊(duì)列的應(yīng)用鏈隊(duì)列、循環(huán)隊(duì)列(P60),離散事件模擬(銀行接待工作(P65))特殊矩陣的壓縮存儲(chǔ)如何存儲(chǔ)矩陣的元,使矩陣的運(yùn)算有效進(jìn)行。高級(jí)語(yǔ)言常用二維數(shù)組存儲(chǔ)陣元面對(duì)如高階矩陣,多值相同矩陣和多零元素矩陣進(jìn)行壓縮存儲(chǔ)節(jié)省空間壓縮存儲(chǔ):為多個(gè)值相同的元只分配一個(gè)空間,對(duì)零元不分配值相同元素或零元素具有分布規(guī)律則稱(chēng)為特殊矩陣,反之為稀疏矩陣具體應(yīng)用與算法(P95)三、樹(shù)與二叉樹(shù)樹(shù)的基本概念樹(shù)是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu),以分支關(guān)系定義的層次結(jié)構(gòu)樹(shù)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集詳見(jiàn)(P118),基本術(shù)語(yǔ)(P120)二叉樹(shù)二叉樹(shù)的定義及其主要特征:二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱(chēng)作“左子樹(shù)”(leftsubtree)和“右子樹(shù)”(rightsubtree)。性質(zhì):1.2.3.滿(mǎn)二叉樹(shù):完全二叉樹(shù):4.5.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ),用一組位置連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素,即將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)依次存儲(chǔ)在如上定義的一位數(shù)組下標(biāo)為i-1的分量中。123456789鏈?zhǔn)酱鎯?chǔ),每個(gè)結(jié)點(diǎn)中至少包含三個(gè)域,[左指針,數(shù)據(jù),右指針],稱(chēng)作“二叉鏈表”增加一個(gè)雙親指針域,則稱(chēng)作“三叉鏈表”詳見(jiàn)P126-127二叉樹(shù)的遍歷遍歷二叉樹(shù),每個(gè)結(jié)點(diǎn)均被訪(fǎng)問(wèn)一次,且僅有一次。在限定先左后右的訪(fǎng)問(wèn)序列后,有三種遍歷方式:先序(DLR),中序(LDR),后續(xù)(LRD)P129算法6.1(波蘭式)層次遍歷,無(wú)論那種遍歷方式,對(duì)含n個(gè)結(jié)點(diǎn)的二叉樹(shù),時(shí)間復(fù)雜度都為O(n),空間復(fù)雜度也為O(n)。線(xiàn)索二叉樹(shù)的基本概念和構(gòu)造摘要:對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹(shù),在二叉鏈存儲(chǔ)結(jié)構(gòu)中有n+1(2n-(n-1))個(gè)空鏈域,利用這些空鏈域存放在某種遍歷次序下該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這些指針?lè)Q為線(xiàn)索概念:加上了線(xiàn)索的二叉鏈表稱(chēng)為線(xiàn)索鏈表,相應(yīng)的二叉樹(shù)稱(chēng)為線(xiàn)索二叉樹(shù)(ThreadedBinaryTree)。構(gòu)造方法:樹(shù)與森林樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈表結(jié)構(gòu):1.雙親表示法2.孩子表示法3.孩子兄弟表示法詳見(jiàn)P135森林與二叉樹(shù)轉(zhuǎn)換左孩子右兄弟樹(shù)與森林的遍歷先序、中序遍歷,詳見(jiàn)P139當(dāng)以二叉鏈表做樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí),樹(shù)的先序=二叉樹(shù)先序、樹(shù)的后序=二叉樹(shù)中序樹(shù)與二叉樹(shù)的應(yīng)用二叉排序樹(shù)二叉排序樹(shù)(BinarySortTree),又稱(chēng)二叉查找樹(shù)(BinarySearchTree),亦稱(chēng)二叉搜索樹(shù)。定義:二叉排序樹(shù)或者是一棵空樹(shù),或者是具有下列性質(zhì)的二叉樹(shù):(1)若左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;(2)若右子樹(shù)不空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;(3)左、右子樹(shù)也分別為二叉排序樹(shù);(4)沒(méi)有鍵值相等的節(jié)點(diǎn)。查找:步驟:若根結(jié)點(diǎn)的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"關(guān)鍵字值等于查找的關(guān)鍵字,\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"成功。否則,若小于根結(jié)點(diǎn)的關(guān)鍵字值,\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"遞歸查左子樹(shù)。若大于根結(jié)點(diǎn)的關(guān)鍵字值,遞歸查右子樹(shù)。若子樹(shù)為空,查找不成功。平衡二叉樹(shù)(AVL)定義:它或者是一顆空樹(shù),或者具有以下性質(zhì)的二叉樹(shù):它的左子樹(shù)和右子樹(shù)的深度之差(平衡因子)的絕對(duì)值不超過(guò)1,且它的左子樹(shù)和右子樹(shù)都是一顆平衡二叉樹(shù)。平衡因子(bf):結(jié)點(diǎn)的左子樹(shù)的深度減去右子樹(shù)的深度,那么顯然-1<=bf<=1圖一,圖二都是BST,但只有圖一是AVLtree哈夫曼(Huffman)樹(shù)和哈夫曼編碼哈夫曼樹(shù)是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù),又稱(chēng)最優(yōu)樹(shù)。路徑和路徑長(zhǎng)度概念:從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑,路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。推廣到一般情況,考慮帶權(quán)結(jié)點(diǎn):結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上的權(quán)值的乘積,樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和,記作WPL=△帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)或哈夫曼樹(shù)哈夫曼算法構(gòu)造哈夫曼樹(shù)(P145)哈夫曼編碼前綴編碼:設(shè)計(jì)長(zhǎng)短不等的編碼,任一字符的編碼都不是另一個(gè)字符的編碼的前綴利用二叉樹(shù)來(lái)設(shè)計(jì)前綴編碼約定左分支表示字符“0”右分支表示字符“1”則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。一般情況,當(dāng)帶有權(quán)值時(shí),本質(zhì)上就是設(shè)計(jì)一棵哈夫曼樹(shù),得到二進(jìn)制前綴編碼=哈夫曼編碼算法詳見(jiàn)P147圖圖的基本概念圖是一種數(shù)據(jù)結(jié)構(gòu),加上一組基本操作,構(gòu)成的一種抽象數(shù)據(jù)類(lèi)型詳見(jiàn)(P156)途中數(shù)據(jù)元素通常稱(chēng)為頂點(diǎn),V是頂點(diǎn)的有窮非空集合;VR是兩個(gè)頂點(diǎn)的關(guān)系集合,若<v,w>屬于VR,則<v,w>表示從v到w的弧,稱(chēng)v為弧尾(初始點(diǎn)),w尾弧頭(終結(jié)點(diǎn))此時(shí)圖是有向圖,若<v,w>屬于VR必有<w,v>屬于VR,則以無(wú)序?qū)?lt;v,w>,表示v和w的一條邊,此時(shí)稱(chēng)圖為無(wú)向圖完全圖有向完全圖邊或弧很少(e<nlogn)的圖,稱(chēng)為稀疏圖,反之為稠密圖邊或弧所具有的相關(guān)數(shù)稱(chēng)為權(quán),帶權(quán)的圖稱(chēng)為網(wǎng)子圖連通圖(二)圖的存儲(chǔ)及基本操作1.鄰接矩陣法用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素(頂點(diǎn))的信息,和數(shù)據(jù)元素之間的關(guān)系(邊或?。┑男畔⑺惴ㄔ斠?jiàn)(P161)鄰接表法鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。算法詳見(jiàn)(P163)(三)圖的遍歷1.深度優(yōu)先搜索(DFS)類(lèi)似于樹(shù)的先根遍歷,可把圖轉(zhuǎn)化為樹(shù)操作。圖示及算法(P168)2.廣度優(yōu)先搜索類(lèi)似于樹(shù)的層次遍歷,可把圖轉(zhuǎn)為樹(shù)操作。詳見(jiàn)(P169)(四)圖的基本應(yīng)用1.最小(代價(jià))生成樹(shù)(P173)普里姆算法構(gòu)造最小生成樹(shù):克魯斯卡爾算法構(gòu)造最小生成樹(shù):2.最短路徑(P186)在圖中從頂點(diǎn)A到B,找一條所含邊(?。┳钌俚穆窂?,從A開(kāi)始做廣度優(yōu)先搜索,直到B結(jié)束,則稱(chēng)為最短路徑??赏茝V的含權(quán)值的情形,此時(shí)最短路徑度量是路徑上權(quán)值之和帶權(quán)有向圖:源點(diǎn)->終點(diǎn)迪杰斯特拉算法:3.拓?fù)渑判蛴赡硞€(gè)集合上的偏序得到該集合的全序偏序:若集合X上的關(guān)系R是自反的、反對(duì)稱(chēng)的和傳遞的,則稱(chēng)R是集合X上的偏序關(guān)系;設(shè)R是集合上的偏序,如果對(duì)每個(gè)x,y屬于X必有xRy或yRx,則稱(chēng)R是集合X上的全序關(guān)系。詳見(jiàn)(P180)4.關(guān)鍵路徑(最長(zhǎng)路徑)(P183)查找查找的基本概念在一些(有序的/無(wú)序的)\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"數(shù)據(jù)元素中,通過(guò)一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素的過(guò)程叫做查找。也就是根據(jù)給定的某個(gè)值,在\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"查找表中確定一個(gè)\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。順序查找法順序查找:

核心:從數(shù)據(jù)的第一個(gè)元素開(kāi)始,依次比較,直到找到目標(biāo)數(shù)據(jù)或查找失敗。

1.從表中的第一個(gè)元素開(kāi)始,依次與關(guān)鍵字比較。

2.若某個(gè)元素匹配關(guān)鍵字,則查找成功。

3.若查找到最后一個(gè)元素還未匹配關(guān)鍵字,則查找失敗。時(shí)間復(fù)雜度:順序查找平均關(guān)鍵字匹配次數(shù)為表長(zhǎng)的一半,其時(shí)間復(fù)雜度為O(n)。3.順序查找的評(píng)估:順序查找的優(yōu)點(diǎn)是對(duì)表無(wú)要求,插入數(shù)據(jù)可在O(1)內(nèi)完成。缺點(diǎn)是時(shí)間復(fù)雜度較大,數(shù)據(jù)規(guī)模較大時(shí),效率較低。折半查找法算法要求:折半查找要求線(xiàn)性表必須采用順序存儲(chǔ)結(jié)構(gòu),而且表中元素按關(guān)鍵字有序排列。查找過(guò)程:首先,假設(shè)表中元素是按升序排列,將表中間位置記錄的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"關(guān)鍵字與查找關(guān)鍵字比較,如果兩者相等,則查找成功否則利用中間位置\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄將表分成前、后兩個(gè)子表,如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字,則進(jìn)一步查找前一子表,否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程,直到找到滿(mǎn)足條件的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄,使查找成功,或直到子表不存在為止,此時(shí)查找不成功。散列(Hash)表哈希表定義:是根據(jù)關(guān)鍵碼值(Keyvalue)而直接進(jìn)行訪(fǎng)問(wèn)的\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō),它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄,以加快查找的速度。這個(gè)映射函數(shù)叫做\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列函數(shù),存放記錄的\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)組叫做\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列表。給定表M,存在函數(shù)f(key),對(duì)任意給定的關(guān)鍵字值key,代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的位置,則稱(chēng)表M為哈希(Hash)表,函數(shù)f(key)為哈希(Hash)函數(shù)?;靖拍睿喝絷P(guān)鍵字為k,則其值存放在f(k)的存儲(chǔ)位置上。由此,不需比較便可直接取得所查記錄。稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù),按這個(gè)思想建立的表為散列表。對(duì)不同的關(guān)鍵字可能得到同一散列位置,即k1≠k2,而f(k1)=f(k2),這種現(xiàn)象稱(chēng)為沖突(英語(yǔ):Collision)。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱(chēng)做同義詞。綜上所述,根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的位置集(區(qū)間)上,并以關(guān)鍵字在位置集中的“像”作為記錄在表中的存儲(chǔ)位置,這種表便稱(chēng)為散列表,這一映射過(guò)程稱(chēng)為散列造表或散列,所得的存儲(chǔ)位置稱(chēng)散列位置。若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字,經(jīng)散列函數(shù)映象到位置集合中任何一個(gè)位置的概率是相等的,則稱(chēng)此類(lèi)散列函數(shù)為均勻散列函數(shù)(UniformHashfunction),這就是使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)“隨機(jī)的位置”,從而減少?zèng)_突。字符串模式匹配子串的定位操作是要在主串S中找出一個(gè)與子串T相同的子串,通常把主串S稱(chēng)為目標(biāo),把子串T稱(chēng)為模式,把從目標(biāo)S中查找模式為T(mén)的子串的過(guò)程稱(chēng)為“模式匹配”。Brute-Force算法的設(shè)計(jì)思想

Brute-Force是普通的模式匹配算法。將主串S的第1個(gè)字符和模式T的第1個(gè)字符比較,若相等,繼續(xù)逐個(gè)比較后續(xù)字符;若不等,從主串的下一字符起,重新與模式的第一個(gè)字符比較,直到主串的一個(gè)連續(xù)子串字符序列與模式相等,返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào),即匹配成功;否則,匹配失敗,返回值0。Brute-Force算法的特點(diǎn):

每次遇到匹配不成功的情況,指針i都要移到本次匹配的開(kāi)始位置的下一位,稱(chēng)這樣的指針移動(dòng)為回溯。指針的回溯越多,簡(jiǎn)單模式匹配的執(zhí)行次數(shù)越多Brute-Force匹配算法的最壞時(shí)間復(fù)雜度為O(n*m),一般情況下BF算法的時(shí)間復(fù)雜度為O(n+m)3.KMP算法的改進(jìn)

每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí),不需回溯指針i,而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后,繼續(xù)比較

KMP算法的時(shí)間復(fù)雜度可以達(dá)到O(m+n)

4.KMP算法的設(shè)計(jì)思想假設(shè)以指針i和j分別指示主串和模式中正待比較的字符,令i的初值為0,j的初值為0

若在匹配過(guò)程中,Si=Pj,則i和j分別增1,否則i不變,而j退到next[j]的位置再比較,若相等,則指針各自增1,否則j再退到下一個(gè)next值的位置,依次類(lèi)推

若令next[j]=k,則next[j]表明當(dāng)模式中第j個(gè)字符與主串中相應(yīng)字符失配時(shí),在模式中需重新和主串中該字符進(jìn)行比較的字符的位置

模式串的next函數(shù)定義為查找算法的分析及應(yīng)用排序排序的基本概念將雜亂無(wú)章的數(shù)據(jù)元素,通過(guò)一定的方法按關(guān)鍵字順序排列的過(guò)程叫做排序。分\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"內(nèi)部排序和\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"外部排序,若整個(gè)排序過(guò)程不需要訪(fǎng)問(wèn)外存便能完成,則稱(chēng)此類(lèi)排序問(wèn)題為內(nèi)部排序。反之,若參加排序的記錄數(shù)量很大,整個(gè)序列的排序過(guò)程不可能在\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"內(nèi)存中完成,則稱(chēng)此類(lèi)排序問(wèn)題為外部排序。內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。

插入排序直接插入排序基本思想是每一步將一個(gè)待排序的記錄,插入到前面已經(jīng)排好序的有序序列中去,直到插完所有元素為止。氣泡排序冒泡排序的基本思想是,對(duì)相鄰的元素進(jìn)行兩兩比較,順序相反則進(jìn)行交換,這樣,每一趟會(huì)將最小或最大的元素“浮”到頂端,最終達(dá)到完全有序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序是最簡(jiǎn)單直觀(guān)的一種算法,基本思想為每一趟從待排序的數(shù)據(jù)元素中選擇最?。ɑ蜃畲螅┑囊粋€(gè)元素作為首元素,直到所有元素排完為止,簡(jiǎn)單選擇排序是不穩(wěn)定排序。在算法實(shí)現(xiàn)時(shí),每一趟確定最小元素的時(shí)候會(huì)通過(guò)不斷地比較交換來(lái)使得首位置為當(dāng)前最小,交換是個(gè)比較耗時(shí)的操作。其實(shí)我們很容易發(fā)現(xiàn),在還未完全確定當(dāng)前最小元素之前,這些交換都是無(wú)意義的。我們可以通過(guò)設(shè)置一個(gè)變量min,每一次比較僅存儲(chǔ)較小元素的數(shù)組下標(biāo),當(dāng)輪循環(huán)結(jié)束之后,那這個(gè)變量存儲(chǔ)的就是當(dāng)前最小元素的下標(biāo),此時(shí)再執(zhí)行交換操作即可。代碼實(shí)現(xiàn)很簡(jiǎn)單,一起來(lái)看下。希爾排序希爾排序是基于插入排序的,首先回顧一下插入排序,假設(shè)插入是從左向右執(zhí)行的,待插入元素的左邊是有序的,且假如待插入元素比左邊的都小,就需要挪動(dòng)左邊的所有元素,如下圖所示:相比簡(jiǎn)單插入排序,大間隔地做插入排序有兩個(gè)好處:一、大間隔直接導(dǎo)致需要挪動(dòng)的數(shù)據(jù)稀少,且數(shù)據(jù)挪動(dòng)的效率高,圖5中一次挪動(dòng)可以跨越40個(gè)位置;二、經(jīng)過(guò)前一步大間隔的插入排序后,整個(gè)數(shù)組從整體上粗略地看已經(jīng)有了明顯的順序,后一步小間隔的插入排序時(shí),一部分操作是不需要挪動(dòng)數(shù)據(jù)的,再次減少了挪動(dòng)數(shù)據(jù)的次數(shù)。間隔的序列:間隔的常用序列,通過(guò)遞歸表示:h=3*h+1。(1,4,13,40,121...)希爾排序的效率:“沒(méi)有理論上分析希爾排序的效率的結(jié)論,各種基于實(shí)驗(yàn)的評(píng)估,估計(jì)它的時(shí)間級(jí)從O(N^(3/2))到O(N^(7/6))”--[1]??焖倥判蚩焖倥判蛩惴ǖ牟呗允沁@樣的:首先把數(shù)組用某個(gè)值分為兩個(gè)子數(shù)組,且稱(chēng)這個(gè)值為分組值,一個(gè)子數(shù)組中的元素均小于分組值,另一子數(shù)組則均大于等于分組值,這里的子組內(nèi)并不排序;然后,再分別對(duì)兩個(gè)子組進(jìn)行再分組,重復(fù)遞歸這個(gè)過(guò)程,直到最后每?jī)蓚€(gè)元素作為一組進(jìn)行再分組,整個(gè)數(shù)組就排好序了。分組過(guò)程具體如下:同時(shí)從左往右和從右往左掃描數(shù)組,記掃描標(biāo)記位為L(zhǎng)P和RP。在LP一邊,若發(fā)現(xiàn)元素小于分組值則跳過(guò)(即向右移動(dòng)一位檢查下一個(gè)元素),否則等待RP的掃描;RP若發(fā)現(xiàn)元素大于等于分組值跳過(guò),直到找到小于分組值的元素,然后LP和RP位置的元素交換,重復(fù)這個(gè)過(guò)程,直到LP和RP相遇。如圖7,8所示,以11號(hào)元素為分組值,LP停在0號(hào)位置,RP跳過(guò)10號(hào),停在圖7中的9號(hào)位置(粉色柱),然后0號(hào)和9號(hào)交換,后續(xù)重復(fù)這個(gè)過(guò)程。分組值的選擇,可以想見(jiàn),理想的分組值應(yīng)該是待分組元素的中值,這樣分組后子組在數(shù)量少幾乎是一半對(duì)一半,不過(guò)找中值無(wú)疑增加了算法的工作量。圖7中采用了更簡(jiǎn)單的方式,直接選數(shù)組最右邊的元素為分組值,分組結(jié)束后,再把這個(gè)值交換到LP和RP相遇的位置,假如初始數(shù)組是從大到小排序的,這種情況下,選擇最右邊的元素作為分組值,其區(qū)分度就很差了。更好用的方法是所謂的取首尾中三項(xiàng)數(shù)據(jù)的中值或者平均值。通過(guò)對(duì)算法過(guò)程的描述可知,其時(shí)間復(fù)雜度應(yīng)該為:O(N*logN),比簡(jiǎn)單排序和希爾排序都要快。堆排序堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法,堆排序是一種選擇排序,它的最壞,最好,平均時(shí)間復(fù)雜度均為O(nlogn),它也是不穩(wěn)定排序。首先簡(jiǎn)單了解下堆結(jié)構(gòu)。堆是具有以下性質(zhì)的完全二叉樹(shù):每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值,稱(chēng)為大頂堆;或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值,稱(chēng)為小頂堆。如下圖:同時(shí),我們對(duì)堆中的結(jié)點(diǎn)按層進(jìn)行編號(hào),將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個(gè)樣子該數(shù)組從邏輯上講就是一個(gè)堆結(jié)構(gòu),我們用簡(jiǎn)單的公式來(lái)描述一下堆的定義就是:大頂堆:arr

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論