數(shù)據(jù)結(jié)構(gòu)的培訓(xùn)教程

1、樹和森林連通無回路的無向圖樹的遞歸定義一棵樹要么為空，要么由根和它的子樹組成森林樹的集合二叉樹左子樹、右子樹遍歷前序遍歷中序遍歷后序遍歷練習(xí) 前序遍歷和中序遍歷的序列，求后序遍歷的序列思考：隔三遍歷隔三遍歷:即遍歷得到的序列(a1,a2,.,an)滿足:序列中任意兩個相鄰點(diǎn)在樹上的距離小于或等于3.例如以下圖的一個合法遍歷為: 1 3 4 6 5 2 7隔三遍歷算法:由于規(guī)模大,考慮進(jìn)行構(gòu)造而不是搜索.由于是一般的樹,可以模仿二叉樹遍歷的方法.首先深度優(yōu)先遍歷無向圖成為一棵多叉樹,并標(biāo)上深度(depth),然后對每個結(jié)點(diǎn)x，考慮它的深度depth：如果depth為奇數(shù)，那么對結(jié)點(diǎn)x進(jìn)行先序遍歷

2、；如果depth為偶數(shù)，那么對結(jié)點(diǎn)x進(jìn)行后序遍歷。用數(shù)學(xué)歸納法可以得證。完全二叉樹除了底層，其他層都到達(dá)最大子節(jié)點(diǎn)個數(shù)自頂向下，同層從左往右編號0,1,2,n-1對任意序號ii的父節(jié)點(diǎn)是(i-1)/2i的左子節(jié)點(diǎn)i*2+1i的右子節(jié)點(diǎn)i*2+2堆以小根堆為例所有父節(jié)點(diǎn)的值都小于等于子節(jié)點(diǎn)的值向上維護(hù)(插入),O(logn)向下維護(hù)(刪除),O(logn)一般用完全二叉樹實(shí)現(xiàn)問題總共輸入n(n1000000)個不同的數(shù)，每個數(shù)介于(0-1000000)之間，輸入過程中會不定時修改某些數(shù)的大小，繼續(xù)維持堆的性質(zhì)。帶HASH的堆根據(jù)題中數(shù)據(jù)范圍以及兩兩不等。Ai代表元素大小為i的元素在堆中的位置這樣

3、修改的復(fù)雜度降為O(1)修改后調(diào)整復(fù)雜度為O(log n)總修改的復(fù)雜度為O(log n)應(yīng)用SPFA優(yōu)先隊(duì)列一般支持的操作：1.支持插入，刪除元素間接說明支持修改2.支持查找最大或最小元素 *3.不支持合并操作，但左偏樹等可并優(yōu)先隊(duì)列仍可以支持注意：所謂的支持的操作是指復(fù)雜度在線性以下可以完成，例如O(logN),O(1)，也有可以是O(N0.5)優(yōu)先隊(duì)列一般來說優(yōu)先隊(duì)列就是用堆例子dijkstra算法用優(yōu)先隊(duì)列優(yōu)化O(n+m)logn)動態(tài)維護(hù)中位數(shù)問題，一個集合，要支持插入操作和求當(dāng)前中位數(shù)的操作，容易想到的是編程極其復(fù)雜的平衡樹，但用優(yōu)先隊(duì)列會比較方便哈夫曼樹問題：給定104個數(shù)，每次

4、合并其中兩個數(shù)a,b，合并代價為a+b,現(xiàn)在求合并代價總和的最小值Huffman樹每次合并當(dāng)前數(shù)組中最小的兩個數(shù)Huffman樹的由來一種貪心的思想暴力復(fù)雜度O(n2)用優(yōu)先隊(duì)列優(yōu)化,復(fù)雜度為O(nlogn)排序算法插入排序O(n2)在已有有序序列中每次插入一個元素選擇排序O(n2)給每個位置選擇當(dāng)前元素最大(最小)歸并排序O(nlogn)把序列一分為二，對有序序列歸并快速排序根本思想 任取一個數(shù)把數(shù)列分成兩段它左邊的數(shù)都比它小，它右邊的數(shù)都比它大此時這個數(shù)就在目標(biāo)序列中它的位置上對兩個子段分別進(jìn)行排序時間復(fù)雜度最壞O(n2)，期望O(nlogn)其他排序法堆排序O(nlogn)基數(shù)排序.穩(wěn)定

5、性選擇排序不穩(wěn)定插入排序穩(wěn)定快速排序不穩(wěn)定歸并排序穩(wěn)定堆排序不穩(wěn)定哈希表Hash table,也叫散列表是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。Hash函數(shù)字符串的hash函數(shù)int ELFhash(char *key) unsigned long h=0; while(*key) h=(h24; h &= g; return h % M;沖突return h % M;一般來說M是一個大質(zhì)數(shù)沖突的解決開散列法閉散列法幾個例子給一個學(xué)生信息的列表，根據(jù)姓名查詢學(xué)生信息走迷宮的時候判斷某個格子是否走過H

6、ash表推薦閱讀2005年IOI國家集訓(xùn)隊(duì)論文李羽修?Hash函數(shù)的設(shè)計(jì)優(yōu)化?另外為圖方便，C+里用map實(shí)際是紅黑樹來實(shí)現(xiàn)hash的映射編程上會比較方便并查集查找一個元素在哪個集合中合并兩個集合用森林實(shí)現(xiàn)并查集，用樹根表示集合查找查找某個元素所在樹的樹根，同時壓縮路徑合并較小的集合樹根的父親設(shè)為較大集合的根并查集時間效率O(m*f(m,n),f是Ackermann函數(shù)的某個反函數(shù)，一般認(rèn)為小于5應(yīng)用查找兩個元素是否在同一個集合中poi9806相等的單詞讓二進(jìn)制串a(chǎn),b,c,d,e分別為長度為4，2，4，4，2的5個變量?？紤]以下等式：1bad1=acbe。問有多少種變量取值使得等式成立poi

7、98061bad1=acbe位置組：(1,4,7,12),(2,5,9),(3,6,10),(8),(11)這個等式有16種不同的解答方案。排序二叉樹又稱二叉搜索樹,二叉檢索樹具有以下性質(zhì)對于任意一個父親節(jié)點(diǎn)的值k它的左子樹所有節(jié)點(diǎn)的值都=k根本操作插入、刪除、查找平衡問題當(dāng)排序二叉樹的高度接近logn的時候，它是良態(tài)的，插入、刪除、查找O(logn)當(dāng)排序二叉樹的高度接近n的時候，比較像一個鏈，O(n)自平衡樹平衡樹源自普通的排序二叉樹(二叉排序樹，BST)平衡樹的純手寫版現(xiàn)今比賽比較少用沒有用到高級功能的話一般用set或map代替，非常方便 ,甚至用來當(dāng)作優(yōu)先隊(duì)列 如果要用到高級功能的話可

8、以嘗試用線段樹或樹狀數(shù)組代替手寫版種類： RB-tree, AVL, splay, treap=tree+heap, SBT(推薦)平衡樹旋轉(zhuǎn)操作2007IOI國家集訓(xùn)隊(duì)論文陳啟峰 Size Balanced Tree平衡樹平衡樹常用根本功能：1.插入，刪除2.求最大，最小，求排序后的前驅(qū)和后繼平衡樹不太常用的高級功能1.求第K大2.合并NOI2004郁悶的出納員線段樹線段樹區(qū)間統(tǒng)計(jì)問題線段覆蓋根本操作建樹、插入或刪除一條線段RMQ求數(shù)列任意區(qū)間的最大值、最小值離散化統(tǒng)計(jì)例子在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段a,b上涂上顏色，另一種將a,b上的顏色擦去。問經(jīng)過一系列的操作

9、后，有多少條單位線段k,k+1被涂上了顏色。刪除的改進(jìn)一般來說線段樹中線段的刪除只能把已經(jīng)放入的線段刪掉改進(jìn)的實(shí)現(xiàn)方法見IOI2004國家集訓(xùn)隊(duì)論文薛矛?解決動態(tài)統(tǒng)計(jì)問題的兩把利刃?推廣這是一棵以矩形(1,1,4,3)為根的矩形樹：(1,1)(4,3)(1,2)(2,3)(2,2)(4,3)(1,1)(2,2)(2,1)(4,2)(2,2)(3,3)(3,2)(4,3)(2,1)(3,2)(3,1)(4,2)樹狀數(shù)組相對于線段樹而言： 局限性：修改操作必須針對點(diǎn)查詢操作區(qū)間左端點(diǎn)必須是起點(diǎn)優(yōu)點(diǎn)：編程復(fù)雜度巨低時空效率遠(yuǎn)高于線段樹問題給定1000個字符串，每個長度不超過10000，現(xiàn)在請統(tǒng)計(jì)出現(xiàn)次數(shù)在前100次的字符串內(nèi)容，并將其內(nèi)容以及次數(shù)輸出注：只有小寫字母Trie字典樹struct nodechar c;struct node *a26;考慮時間？考慮空間？時間復(fù)雜度1000*10000*對當(dāng)前所有字符串取出前100個)加堆優(yōu)化以后(1000*10000*log100)=7*1075S可以通過空間復(fù)雜度(最壞不到107)，實(shí)際中大大節(jié)省空間Trie樹優(yōu)化字符串查找，查找復(fù)雜度為字符