數據結構與演算法教程c

① 數據結構與演算法分析 —— C 語言描述：二叉樹

二叉樹（binary tree）是一棵樹，其中每個節點的兒子都不能多於兩個。

二叉樹的一個性質是平均二叉樹的深度要比 N 小的多，這個性質有時很重要。分析表明，這個平均深度為 ，而對於特殊類型的二叉樹，即二叉查找樹(binary search tree)。其深度的平均值是 。不幸的是，在最壞情況下，這個深度可以大到 N-1 的。

因為一棵二叉樹最多有兩個兒子，所以我們可以用指針直接指向它們。樹節點的聲明在結構上類似於雙鏈表的聲明，在聲明中，一個節點就是由 key（關鍵字）信息加上兩個指向其他節點的指針（Left 和 Right）組成的結構。

應用於鏈表上的許多法則也可以應用到樹上。特別地，當進行一次插入時，必須調用 malloc 創建一個節點。節點可以在調用 free 刪除後釋放。

我們可以用在畫鏈表時常用的矩形框畫出二叉樹，但是，樹一般畫成圓圈並用一些直線連接起來，因為二叉樹實際上就是圖（graph）。當涉及樹時，我們也不顯示地畫出 NULL 指針，因為具有 N 個節點的每一棵二叉樹都將需要 N+1 個 NULL 指針。

二叉樹有許多與搜索無關的重要應用。二叉樹的主要用處之一是在編譯器的設計領域。

上圖就是一個表達式樹（expression tree）。表達式樹的樹葉是操作樹（operand），比如常數或者變數，而其他的節點為操作符（operator）。由於這里所有的操作都是二元的，因此這棵特定的樹正好是二叉樹，雖然這是最簡單的情況，但是節點含有的兒子還是有可能多於兩個的。一個節點也有可能只有一個兒子，如果有一目減算符（unary minus operator）的情形。可以將通過遞歸計算左子樹和右子樹所得到的值應用在根處的算符操作中而算出表達式樹 T 的值。上面里的例子中，左子樹的值是「((3+1) 3)/((9-5)+2)」，右子樹的值是「(3 (7-4)+6)」，因此整棵樹的表達式就是圖上的結果。

我們可以通過遞歸產生一個帶括弧的左表達式，然後列印出在根處的運算符，最後再遞歸地產生一個帶括弧的右表達式而得到一個（對兩個括弧整體進行計算的）中綴表達式（infix expression）。這種一般的方法（左，節點，右）稱為中序遍歷（inorder traversal）；由於其產生的表達式類型，這種遍歷很容易記憶。

另一個遍歷策略是遞歸列印出左子樹、右子樹，然後列印運算符。如果我們應用這種策略於上面的樹，則輸出將是「31+3 95-2+/743- 6+-」。這種遍歷策略一般稱為後序遍歷（postorder traversal）。

第三種遍歷策略是先列印出運演算法，然後遞歸地列印出右子樹和左子樹。同樣的，應用這種策略於上面的樹，則輸出將是「-/ ++313-952+ 3-746」，這是一種不太常用前綴（prefix）記法，這種遍歷策略為先序遍歷（preorder traversal）。

這里我們只給出一種演算法，來把後綴表達式轉變成表達式樹。這里的要點是，一次一個符號地讀入表達式。如果符號是操作符，那麼我們就建立一個單節點樹並將一個指向它的指針推入棧中。如果符號是操作符，那麼我們就從棧中彈出指向兩棵樹 和 的那兩個指針( 的先彈出)並形成一棵新的樹，該樹的根就是操作符，它的左、右兒子分別指向 和 。然後將這棵新樹的指針壓入棧中。

② 數據結構（C語言版）的內容簡介

《數據結構》（C語言版）是為「數據結構」課程編寫的教材，也可作為學習數據結構及其演算法的C程序設計的參數教材。
本書的前半部分從抽象數據類型的角度討論各種基本類型的數據結構及其應用；後半部分主要討論查找和排序的各種實現方法及其綜合分析比較。其內容和章節編排1992年4月出版的《數據結構》（第二版）基本一致，但在本書中更突出了抽象數據類型的概念。全書採用類C語言作為數據結構和演算法的描述語言。
本書概念表述嚴謹，邏輯推理嚴密，語言精煉，用詞達意，並有配套出版的《數據結構題集》（C語言版），便於教學，又便於自學。
本書後附有光碟。光碟內容可在DOS環境下運行的以類C語言描述的「數據結構演算法動態模擬輔助教學軟體，以及在Windows環境下運行的以類PASCAL或類C兩種語言描述的「數據結構演算法動態模擬輔助教學軟體」。
本書可作為計算機類專業或信息類相關專業的本科或專科教材，也可供從事計算機工程與應用工作的科技工作者參考。

③ 數據結構與演算法分析 —— C 語言描述：開放定址法

分離鏈接散列演算法的缺點是需要指針，由於給新單元分配地址需要時間，因此這就導致演算法的速度多少有些緩慢，同時演算法實際上還要求實現另一種數據結構。除使用鏈表解決沖突外，開放定址散列法（open addressing hashing）是另外一種用鏈表解決沖突的方法。在開放定址散列演算法系統中，如果有沖突發生，那麼就要嘗試選擇另外的單元，直到找出空的單元為止。更一般地，單元 相繼試選，其中 ，且 。函數 F 是沖突解決方法，因為所有的數據都要置入表內，所以開放定址散列法所需要的表要比分離鏈接散列用的表大。一般說來，對開放定址散列演算法來說，裝填因子應該低於 。開放定址散列法有三種常用的沖突解決辦法：

在線性探測法中，函數 F 是 的線性函數，典型的情形是 。這相當於逐個探測每個單元（必要時可以繞回）以查找出一個空空單元。即插入一個第一個沖突關鍵字，它將被放入下一個空閑地址，即地址 0，該地址是開放的。之後插入的沖突關鍵字，會對表進行試選，只要表足夠大，總能夠找到一個自由單元，但是如此花費的時間是相當多的。更糟的是，即使表相對較空，這樣占據的單元也會開始形成一些區塊，其結果稱為一次聚集（primary clustering），於是，散列到區塊中的任何關鍵字都需要多次試選單元才能解決沖突，然後該關鍵字被添加到相應的區塊中。

可以證明，使用線性探測的預期探測次數對於插入和不成功的查找來說大約為 ，而對於成功的查找來說則是 。略加思考不難得出，成功查找應該比不成功查找平均花費較少的時間。

如果聚算不算是問題，那麼對應的公式就不難得到。我們假設有一個很大的表，並設每次探測都與前面的探測無關。對於隨機沖突解決辦法而言，這些假設是成立的，並且當 不是非常接近 1 時也是合理的。首先，我們導出在一次不成功查找中探測的期望次數，而這正是直到我們找到一個空單元的探測次數。由於空單元所佔的份額為 ，因此我們預計要探測的單元數是 。一次成功查找的探測次數等於該特定元素插入時所需要的探測次數。當一個元素被插入時，可以看成是一次不成功查找的結果。因此，我們可以使用一次不成功查找的開銷來計算一次成功查找的平均開銷。

需要指出， 在 0 到當前值之間的變化，因此早期的插入操作開銷較少，從而降低平均開銷。我可以通過使用積分計算插入時間平均值的方法來估計平均值，如此得到

這些公式顯然優於線性探測相應的公式，聚集不僅是理論上的問題，而且實際上也發生在具體的實現中。線性探測的預計探測次數與 呈正比，即 越小，插入操作平均次數越少。

平方探測是消除線性探測中一次聚集問題的沖突解決辦法。平方探測就是沖突函數為二次函數的探測方法。流行的選擇是 。

對於線性探測，讓元素幾乎填滿散列表並不是個好主意，因為此時表的性能會降低。對於平方探測情況甚至更糟：一旦表被填滿超過一半，當表的大小不是素數時甚至在表被填滿超過一半之前，就不能保證一次找到一個空單元了。這是因為最多有一半的表可以用作解決沖突的備選位置。

定理：如果使用平方探測，且表的大小是素數，那麼當表至少有一半是空的時候，總能夠插入一個新的元素。

哪怕表有比一半多一個的位置被填滿，那麼插入都有可能失敗（雖然這是非常難以見到的，但是把它記住很重要。）。另外，表的大小是素數也非常重要，如果表的大小不是素數，則備選單元的個數可能會銳減。

在開放定址散列表中，標準的刪除操作不能施行，因為相應的單元可能已經引起過沖突，元素繞過它存在了別處。例如，如果我們刪除一個沖突的中間元素，那麼實際上所有其他的 Find 常式都將不能正確運行。因此，開放定址散列表需要懶惰刪除，雖然在這種情況下並不存在真正意義上的懶惰。

開放定址散列表的類型聲明如下，這里，我們不用鏈表數組，而是使用散列表項單元的數組，與在分離鏈接散列中一樣，這些單元也是動態分配地址的。

初始化開放定址散列表的常式如下，由分配空間（第1～10行）及其後將每個單元的 Info 域設置為 Empty 組成。

使用平方探測散列法的 Find 常式如下。如果分裂鏈接散列法一樣， 將返回 Key 在散列表中的位置。如果 Key 不出現，那麼 Find 將返回最後的單元。該單元就是當需要時，Key 將被插入的地方。此外，因為被標記了 Empty，所以表達 Find 失敗很容易。為了方便起見，我們假設散列表的大小至少為表中元素個數的兩倍，因此平方探測方法總能夠實現。否則，我們就要在第 4 行前測試 。在下面的常式中，標記為刪除的那些元素被認為還在表內，這可能引起一些問題，因為該表可能提前過滿。

第 4～6 行為進行平方探測的快速方法。由平方解決函數的定義可知， ，因此，下一個要探測的單元可以用乘以 2（實際上就是進行一位二進制移位）並減 1 來確定。如果新的定位越過數組，那麼可以通過減去 TableSize 把它拉回到數組范圍內。這比通常的方法要快，因為它避免了看似需要的乘法和除法。注意一條重要的警告：第 3 行的測試順序很重要，切勿改變它。

下面的常式是插入。正如分離鏈接散列方法那樣，若 Key 已經存在，則我們就什麼也不做。其他工作只是簡單的修改。否則，我們就把要插入的元素放在 Find 常式指出的地方。

雖然平方探測排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元。這叫做二次聚集（secondary clustering）。二次聚集是理論上的一個小缺憾，模擬結果指出，對每次查找，它一般要引起另外的少於一半的探測。

雙散列（double hashing）能夠解決平方探測中的二次聚集問題，不過也需要花費另外的一些乘法和除法形銷。對於雙散列，一種流行的選擇是 。這個公式是說，我們將第二個散列函數應用到 X 並在距離 , 等處探測。 選擇的不好將會是災難性的。

在雙散列時，保證表的帶下為素數是非常重要的。假設我們在插入一個關鍵字的時候，發現它已經引發沖突，就會選擇備選位置，如果表的大小不是素數，那麼備選單元就很有可能提前用完。然後，如果雙散列正確實現，則模擬表明，預期的探測次數幾乎和隨機沖突解決方法的情形相同。這使得雙散列理論上很有吸引力，不過，平方探測不需要使用第二個散列函數，從而在實踐中可能更簡單並且更快。

④ 數據結構與演算法分析：C語言描述的內容簡介

《數據結構與演算法分析:C語言描述(原書第2版)》內容簡介：書中詳細介紹了當前流行的論題和新的變化，討論了演算法設計技巧，並在研究演算法的性能、效率以及對運行時間分析的基礎上考查了一些高級數據結構，從歷史的角度和近年的進展對數據結構的活躍領域進行了簡要的概括。由於《數據結構與演算法分析:C語言描述(原書第2版)》選材新穎，方法實用，題例豐富，取捨得當。《數據結構與演算法分析:C語言描述(原書第2版)》的目的是培養學生良好的程序設計技巧和熟練的演算法分析能力，使得他們能夠開發出高效率的程序。從服務於實踐又鍛煉學生實際能力出發，書中提供了大部演算法的C程序和偽碼常式，但並不是全部。一些程序可從互聯網上獲得。
《數據結構與演算法分析:C語言描述(原書第2版)》是《Data Structures and Algorithm Analysis in C》一書第2版的簡體中譯本。原書曾被評為20世紀頂尖的30部計算機著作之一，作者Mark Allen Weiss在數據結構和演算法分析方面卓有建樹，他的數據結構和演算法分析的著作尤其暢銷，並受到廣泛好評．已被世界500餘所大學用作教材。
在《數據結構與演算法分析:C語言描述(原書第2版)》中，作者更加精煉並強化了他對演算法和數據結構方面創新的處理方法。通過C程序的實現，著重闡述了抽象數據類型的概念，並對演算法的效率、性能和運行時間進行了分析。
全書特點如下：
●專用一章來討論演算法設計技巧，包括貪婪演算法、分治演算法、動態規劃、隨機化演算法以及回溯演算法
●介紹了當前流行的論題和新的數據結構，如斐波那契堆、斜堆、二項隊列、跳躍表和伸展樹
●安排一章專門討論攤還分析，考查書中介紹的一些高級數據結構
●新開辟一章討論高級數據結構以及它們的實現，其中包括紅黑樹、自頂向下伸展樹。treap樹、k-d樹、配對堆以及其他相關內容
●合並了堆排序平均情況分析的一些新結果
《數據結構與演算法分析:C語言描述(原書第2版)》是國外數據結構與演算法分析方面的標准教材，介紹了數據結構(大量數據的組織方法)以及演算法分析(演算法運行時間的估算)。《數據結構與演算法分析:C語言描述(原書第2版)》的編寫目標是同時講授好的程序設計和演算法分析技巧，使讀者可以開發出具有最高效率的程序。 《數據結構與演算法分析:C語言描述(原書第2版)》可作為高級數據結構課程或研究生一年級演算法分析課程的教材，使用《數據結構與演算法分析:C語言描述(原書第2版)》需具有一些中級程序設計知識，還需要離散數學的一些背景知識。