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

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

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

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

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

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

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

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

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

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