北大數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)報(bào)告

1、實(shí)習(xí)報(bào)告這個(gè)題目就是要根據(jù)一個(gè)中序遍歷和一個(gè)構(gòu)樹(shù)的規(guī)則構(gòu)造一棵BST，我采用的算法是o(nlogn) + o(n)的算法， 其中o(nlogn)是指將label按照從小到大的順序排列， 我用到了庫(kù)函數(shù)的快速排序。而o(n)是指將結(jié)點(diǎn)構(gòu)造成一個(gè)BST。下面的內(nèi)容分為兩個(gè)方面， 一是構(gòu)造二叉樹(shù)的算法分析， 二是代碼的優(yōu)化。一 、o(n)的建樹(shù)方法首先確定我們從題目中知道的信息，即二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)， 以及每個(gè)結(jié)點(diǎn)的描述， 題目要求我們建立一棵BST， 其中BST又滿足heap的性質(zhì)， 即父親結(jié)點(diǎn)的priority必須大于它的子結(jié)點(diǎn)的priority值， 輸出按照二叉樹(shù)的中序遍歷形式。顯然這道題不可能

2、用我們常規(guī)的建樹(shù)方法， 即建BST或heap的常規(guī)方法，由于結(jié)點(diǎn)有50000，所以我們建樹(shù)的算法必須為o(nlogn) 或者o(n)。首先我們將結(jié)點(diǎn)按照l(shuí)abel排序， 這樣排好序的序列就是我們要構(gòu)造的BST的中序遍歷。然后我們根據(jù)中序遍歷建樹(shù)。從中序遍歷中的第一個(gè)結(jié)點(diǎn)到最后一個(gè)結(jié)點(diǎn)， 逐一加入我們構(gòu)造的樹(shù)中，第一個(gè)結(jié)點(diǎn)可以獨(dú)立構(gòu)成一棵滿足條件的樹(shù)。按照中序遍歷的定義，第二個(gè)結(jié)點(diǎn)可以是第一個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)（其左兒子為第一個(gè)結(jié)點(diǎn)） 或者是第一個(gè)結(jié)點(diǎn)的右兒子， 然后又可以根據(jù)兩個(gè)結(jié)點(diǎn)的priority確定到底是放在那里。加入第三個(gè)結(jié)點(diǎn)也是這樣操作的， 首先根據(jù)中序遍歷的定義確定它可以放的位置， 然

3、后再根據(jù)heap的性質(zhì)確定到底是放在哪個(gè)位置。依此類推， 當(dāng)加入第I + 1個(gè)結(jié)點(diǎn)時(shí)， 我們知道，前面I個(gè)結(jié)點(diǎn)已經(jīng)構(gòu)造成了一棵滿足條件的BST， 由中序遍歷的定義， 可知第I個(gè)結(jié)點(diǎn)肯定在已經(jīng)構(gòu)造的樹(shù)的最右邊， 且沒(méi)有右兒子。對(duì)于第I + 1個(gè)結(jié)點(diǎn)， 它可以放的方式有兩種， 一是作為整棵已經(jīng)構(gòu)造好的樹(shù)的根， 其中前面構(gòu)造好的樹(shù)為它的左子樹(shù)， 二是從已構(gòu)造好的BST的根結(jié)點(diǎn)到它的最右邊的那個(gè)結(jié)點(diǎn)， 有一條“斜線”，如圖所示： root temp i由于新加入的結(jié)點(diǎn)要使新構(gòu)造成的二叉樹(shù)滿足中序遍歷，那么第I+1 個(gè)結(jié)點(diǎn)， 可以作為這條“斜線”上任一個(gè)結(jié)點(diǎn)temp的右兒子， 然后原來(lái)temp的右子樹(shù)作

4、為它的左子樹(shù)，這樣樹(shù)中已經(jīng)加入的 I +1 個(gè)結(jié)點(diǎn)就仍然滿足中序遍歷的條件。顯然除了這兩種情況，就不可能有其他的方式了。然后根據(jù)heap確定到底是插在哪里。如果第I + 1個(gè)結(jié)點(diǎn)的priority大于原來(lái)根結(jié)點(diǎn)的priority那么肯定是第一種情況， 否則， 我們應(yīng)該在“斜線中”由第I個(gè)結(jié)點(diǎn)開(kāi)始向上查找， 直到查找到的結(jié)點(diǎn)的priority大于第I + 1個(gè)結(jié)點(diǎn)的priority， 然后進(jìn)行插入操作。整個(gè)算法完成。復(fù)雜度分析 顯然我們需要對(duì)每個(gè)結(jié)點(diǎn)都進(jìn)行一次插入， 然后每次插入的時(shí)候“代價(jià)”是多少呢？由于我們是從第I個(gè)結(jié)點(diǎn)向上查找， 并且每次查找完以后， 此次查找過(guò)的結(jié)點(diǎn)除了最后一個(gè)查找到的結(jié)

5、點(diǎn)， 都會(huì)成為新加入結(jié)點(diǎn)的左子樹(shù)，也就是說(shuō)以后在每次查找中，不可能遍歷到他們了， 換句話來(lái)說(shuō)，就是在查找的過(guò)程中， 每個(gè)結(jié)點(diǎn)最多可能被一次或兩次遍歷到， 綜合起來(lái)， 構(gòu)造樹(shù)的復(fù)雜度為o(n)， 而快排需要o(nlogn)的復(fù)雜度， 所以整個(gè)算法的復(fù)雜度為o(nlogn)。下面為主要構(gòu)樹(shù)的代碼：struct NodeType/二叉樹(shù)結(jié)點(diǎn)類型char label12;int priority;int RightChild, LeftChild, father;root = 0;/從0結(jié)點(diǎn)開(kāi)始構(gòu)造樹(shù)i = 1;/然后將0后面的結(jié)點(diǎn)依次插入while (i NodeAmount) /*查找新插入結(jié)點(diǎn)應(yīng)

6、該插入的位置從i - 1， 開(kāi)始查找， 一直沿著它的父親指針， 查找到一個(gè)比新插入結(jié)點(diǎn)priority大的結(jié)點(diǎn)那么i 就插在它后面， 而它原來(lái)的右子樹(shù)就成為i結(jié)點(diǎn)的左子樹(shù)*/TempNode = i - 1;CurrPriority = BinaryTreei.priority;while (BinaryTreeTempNode.father != -1 & BinaryTreeTempNode.priority CurrPriority) BinaryTreei.LeftChild = BinaryTreeTempNode.RightChild;/查找到結(jié)點(diǎn)的右子樹(shù)成為i的左子樹(shù)Binary

7、TreeBinaryTreei.LeftChild.father = i;/紀(jì)錄父親結(jié)點(diǎn)BinaryTreeTempNode.RightChild = i;/查找到的結(jié)點(diǎn)的右兒子為 iBinaryTreei.father = TempNode;/紀(jì)錄父親結(jié)點(diǎn)else BinaryTreeroot.father = i;BinaryTreei.LeftChild = root;root = i;i+;二 、代碼的優(yōu)化雖然算法已經(jīng)得出， 但是對(duì)于這道題來(lái)說(shuō)， 要在規(guī)定的時(shí)間內(nèi)通過(guò)還是有一點(diǎn)問(wèn)題的。那么到底是什么地方浪費(fèi)了時(shí)間呢？顯然不可能是構(gòu)造樹(shù)的過(guò)程，在這里由于已知結(jié)點(diǎn)的個(gè)數(shù)，我采用的是靜態(tài)的數(shù)

8、組來(lái)存儲(chǔ)樹(shù)結(jié)構(gòu)，這樣就有幾點(diǎn)好處：編程容易， 不用考慮繁瑣的指針操作。速度快， 指針操作的速度顯然要比數(shù)組慢。 那么原因就只可能是快排或者輸入的時(shí)候比較慢了，由于輸入要以字符串的形式讀入， 而且讀入的字符串的數(shù)目也比較多，由常識(shí)可以知道， 如果用c+的讀入會(huì)比較慢， 而改用c的讀入就會(huì)比較快了， 這個(gè)題目的輸入還要注意的一點(diǎn)是要把字符串進(jìn)行分析， 因?yàn)榘凑誧的讀入， 我們只能將一個(gè)結(jié)點(diǎn)/用一個(gè)字符串讀入，但是我們顯然要得到每個(gè)結(jié)點(diǎn)的priority，這里有兩種方法， 一種是遍歷字符串中/后面的所有字符， 然后將后面的轉(zhuǎn)化為整數(shù)， 另外一種方法是用c+的庫(kù)函數(shù)itoa（）將字符串轉(zhuǎn)化， 這里后面

9、一種方法顯然更好一些。不過(guò)輸入并不是最主要的原因， 我們都知道快速排序是一種比較快的排序方法， c+提供了qsort 和 sort兩種快排， 但是兩者又有區(qū)別， 即qsort和sort都需要提供一個(gè)比較函數(shù)，但是qsort稍微“死”一點(diǎn)，就是函數(shù)的定義格式已經(jīng)規(guī)定了， 當(dāng)我們傳入兩個(gè)參數(shù)時(shí)是傳入兩個(gè)地址實(shí)參， 而sort則比較靈活， 它是傳入兩個(gè)要比較的序列元素類型參數(shù)， 并且可以利用引用傳參。可以想象， 如果是用qsort的話，由于是傳入實(shí)參，所以每次傳入總會(huì)要進(jìn)行兩個(gè)賦值操作， 極為浪費(fèi)時(shí)間， 但是sort就可以利用引用傳參，避免了不必要的賦值操作，相比于qsort快了很多。其他的優(yōu)化就是純粹代碼上的優(yōu)化了， 比如說(shuō)if語(yǔ)句括號(hào)里面的表達(dá)式誰(shuí)先誰(shuí)后等等， 這個(gè)不再贅述。下面是關(guān)于各個(gè)優(yōu)化的效果， 從這個(gè)表中可以看出上面的一些不起眼的小聰明有多大的用處。各個(gè)不同的實(shí)現(xiàn)方法在poj上所用時(shí)間，空間完全用c+的輸入，用string存儲(chǔ)label，快排沒(méi)有用引用Time Limit Exceed/4992K用c+輸入， 用string存儲(chǔ)label，快排用了引用1593MS/4992K用c輸入， char數(shù)組存label，快排用引用343MS/17