數據結構和演算法分析

⑴ 數據結構與演算法分析2.表、棧、隊列、字元串

線性表是 n 個數據元素的有限隊列，同一線性表中的元素必定具有相同的特性，即屬於同一數據對象，相鄰數據元素之間存在著序偶關系。

線性表的順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素，通常是用數組實現。在java語言中，主要是 java.util.ArrayList 實現。

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的），所以對數據元素而言，除了存儲其本身的信息之外，還需要一個指示其後繼數據元素的信息。

棧（Stack）是限定只能在表尾進行插入或刪除的線性表。對棧來說， 表尾稱為棧頂，表頭稱為棧底 。棧又稱為後進先出線性表（LIFO，Last In First Out）。Java中由於 java.util.Stack 和 java.util.Vector 先天的設計問題，並不推薦使用；一般使用LinkedList來當作棧。
[圖片上傳失敗...(image-b267ad-1582731953399)]
[圖片上傳失敗...(image-72fd67-1582731953399)]

假設一個算術表達式中可以包含兩種括弧：圓括弧和方括弧，且這兩種括弧可按任意的次序嵌套使用，編寫判別給定表達式中所含括弧是否正確配對出現的演算法。

迷宮問題是棧的典型應用，棧通常也與回溯演算法連用，回溯演算法的基本描述是：

尚需說明一點的是，所謂當前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置不僅是通道塊，而且既不在當前路徑上（否則所求路徑就不是簡單路徑），也不是曾經納入過路徑的通道塊（否則只能在死胡同內轉圈）。

為實現算符優先演算法，可以使用兩個工作棧。一個稱做OPTR，用以寄存運算符；另一個稱做OPND，用以寄存操作數或運算結果。演算法的基本思想如下：
(1) 首先置操作數棧OPND為空棧，表達式起始符"#"為運算符棧OPTR的棧底元素；
(2) 依次讀入表達式中每個字元，若是操作數則進OPND棧，若是運算符則和OPTR的棧頂元素符比較優先權後作相應操作，直至整個表達式求值完畢(即OPTR棧的棧頂元素和當前讀入的字元均為"#")。

一個直接調用自己或通過一系列的調用語句間接地調用自己的函數。

假設有3個分別命名為X、Y和Z的塔座，在塔座X上插有n階Hanoi塔個直徑大小各不相同、依小到大編號1,2,...,n的圓盤。現要求將X軸上的n階Hanoi塔個圓盤移至塔座Z上並仍按同樣順序疊排，圓盤移動時必須遵循下列規則：

用鏈表表示的隊列簡稱為鏈隊列。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為頭指針和尾指針）才能唯一確定。和線性表的單鏈表一樣，為了操作方便起見，我們也給鏈隊列添加一個 頭結點 ，並令頭指針指向頭結點。由此，空的鏈隊列的判斷條件為頭指針和尾指針均指向頭結點，如圖所示：

在實際使用隊列時，為了使隊列空間能重復使用，往往對隊列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把隊列空間想像成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。
在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環隊列最多隻能有MaxSize-1個隊列元素，當循環隊列中只剩下一個空存儲單元時，隊列就已經滿了。因此，隊列判空的條件時front=rear，而隊列判滿的條件時front=（rear+1）%MaxSize。隊空和隊滿的情況如圖：

雙端隊列，是限定插入和刪除操作在表的兩端進行的線性表，盡管雙端隊列看起來比棧和隊列靈活，但實際上在應用程序中遠不及棧和隊列有用。

⑵ 數據結構與演算法分析 —— 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 並在距離 , 等處探測。 選擇的不好將會是災難性的。

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

⑶ 演算法和數據結構有什麼區別

一、指代不同

1、演算法：是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令。

2、數據結構：指相互之間存在一種或多種特定關系的數據元素的集合。

二、目的不同

1、演算法：指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。

2、數據結構：研究的是數據的邏輯結構和數據的物理結構之間的相互關系，並對這種結構定義相適應的運算，設計出相應的演算法，並確保經過這些運算以後所得到的新結構仍保持原來的結構類型。

三、特點不同

1、演算法：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟，即每個計算步驟都可以在有限時間內完成。

2、數據結構：核心技術是分解與抽象。通過分解可以劃分出數據的3個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。

⑷ 數據結構與演算法的內容簡介

本書是國家級雙語教學示範課程《數據結構》的配套教材，根據教育部高等學校計算機科學與技術教學指導委員會制定的《高等學校計算機科學與技術專業發展戰略研究報告暨專業規范》編寫。全書每章均以數據的邏輯結構、存儲結構和相應的演算法實現為主線，並對演算法的運算效率進行分析。全書分為8章，涵蓋了各種常見數據結構。第1章主要介紹數據結構和演算法分析的基本概念，第2～6章主要介紹典型的線性結構、樹型結構和圖型結構，第7～8章分別介紹查找和排序操作。另外，每章後面附有習題和上機實驗內容，上機實驗提供了完整的、可運行的程序上機實驗供讀者參考，以加深讀者對所學知識的理解和應用。本書既可作為高等院校計算機及相關專業數據結構課程的教學用書，也可作為從事計算機工程與應用的廣大讀者的參考書。

⑸ 數據結構與演算法分析

本文出自：

www點54manong點com

請尊重原創，轉載請註明出處，謝謝！

什麼是數據結構，為什麼要學習數據結構？數據結構是否是一門純數學課程？它在專業課程體系中起什麼樣的作用？我們要怎麼才能學好數據結構？… 相信同學們在剛開始《數據結構》這門課的學習時，心裡有著類似前面幾個問題的這樣那樣的疑問。希望下面的內容能幫助大家消除疑惑，下定決心堅持學好這門課：

1 學習數據數據結構的意義

數據結構是計算機科學與技術專業、計算機信息管理與應用專業，電子商務等專業的基礎課，是十分重要的核心課程。所有的計算機系統軟體和應用軟體都要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付當前眾多復雜的課題。要想有效地使用計算機、充分發揮計算機的性能，還必須學習和掌握好數據結構的有關知識。打好「數據結構」這門課程的扎實基礎，對於學習計算機專業的其他課程，如操作系統、資料庫管理系統、軟體工程、編譯原理、人工智慧、圖視學等都是十分有益的。

2 為什麼要學習數據結構

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出一個適當的數學模型，然後設計或選擇一個解此數學模型的演算法，最後編出程序進行調試、測試，直至得到最終的解答。例如，求解梁架結構中應力的數學模型的線性方程組，可以使用迭代演算法來求解。

由於當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，所以程序設計者的主要精力是集中於程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟、硬體的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題佔用了85%以上的機器時間。這類問題涉及到的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，才能有效地解決問題。下面所列舉的就是屬於這一類的具體問題。

例1：圖書館信息檢索系統。當我們根據書名查找某本書有關情況的時候；或者根據作者或某個出版社查找有關書籍的時候，或根據書刊號查找作者和出版社等有關情況的時候，只要我們建立了相關的數據結構，按照某種演算法編寫了相關程序，就可以實現計算機自動檢索。由此，可以在圖書館信息檢索系統中建立一張按書刊號順序排列的圖書信息表和分別按作者、書名、出版社順序排列的索引表，如圖1.1所示。由這四張表構成的文件便是圖書信息檢索的數學模型，計算機的主要操作便是按照某個特定要求（如給定書名）對圖書館藏書信息文件進行查詢。

諸如此類的還有學生信息查詢系統、商場商品管理系統、倉庫物資管理系統等。在這類文檔管理的數學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關系，這類數學模型可稱為線性的數據結構。

例2：八皇後問題。在八皇後問題中，處理過程不是根據某種確定的計演算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步形成一個新的狀態，整個試探過程形成了一棵隱含的狀態樹。如圖1.2所示（為了描述方便，將八皇後問題簡化為四皇後問題）。回溯法求解過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。

例3：教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規定的先後次序進行，有些則沒有次序要求。即有些課程之間有先修和後續的關系，有些課程可以任意安排次序。這種各個課程之間的次序關系可用一個稱作圖的數據結構來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先於課程j進行。由以上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹、圖之類的數據結構。因此，可以說數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。

學習數據結構的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來並對它們進行處理。與此同時，通過演算法訓練來提高學生的思維能力，通過程序設計的技能訓練來促進學生的綜合應用能力和專業素質的提高。

3數據結構課程的內容

數據結構與數學、計算機硬體和軟體有十分密切的關系，它是介於數學、計算機硬體和計算機軟體之間的一門計算機專業的核心課程，是高級程序設計語言、操作系統、編譯原理、資料庫、人工智慧、圖視學等課程的基礎。同時，數據結構技術也廣泛應用於信息科學、系統工程、應用數學以及各種工程技術領域。

數據結構課程重在討論軟體開發過程中的方案設計階段、同時設計編碼和分析階段的若干基本問題。此外，為了構造出好的數據結構及其實現，還需考慮數據結構及其實現的評價與選擇。因此，數據結構的內容包括三個層次的五個「要素」，如圖1.3所示。

數據結構的核心技術是分解與抽象。通過分解可以劃分出數據的三個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現細節，就得到運算的定義。上述兩個方面的結合使我們將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然後，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。熟練地掌握這兩個過程是數據結構課程在專業技能培養方面的基本目標。

結束語：數據結構作為一門獨立的課程在國外是從1968年才開始的，但在此之前其有關內容已散見於編譯原理及操作系統之中。20世紀60年代中期，美國的一些大學開始設立有關課程，但當時的課程名稱並不叫數據結構。1968年美國唐.歐.克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本演算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。從20世紀60年代末到70年代初，出現了大型程序，軟體也相對獨立，結構程序設計成為程序設計方法學的主要內容，人們越來越重視數據結構。從70年代中期到80年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展並未終結，一方面，面向各專門領域中特殊問題的數據結構得到研究和發展，如多維圖形數據結構等；另一方面，從抽象數據類型和面向對象的觀點來討論數據結構已成為一種新的趨勢，越來越被人們所重視。

⑹ 數據結構與演算法分析：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版)》需具有一些中級程序設計知識，還需要離散數學的一些背景知識。

⑺ 數據結構與演算法分析 —— 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）。

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

⑻ 什麼是數據結構和演算法分析在編程里起到什麼作用

編程是為了解決問題，這些問題並表都是數值計算，其所處理的數據並不都是數值，但計算機所能處理的最終是0和1的二進制串，所以需要把問題中的數據用計算機能處理的方式來表示，這就需要數據結構。

簡單的說，數據結構是數據在計算機中的表示方式，有邏輯結構和物理結構之分，如邏輯上同樣的隊列，物理上可以是順序存儲，也可以是鏈式存儲。

通俗的講，演算法就是解決問題的方法，比如同樣的排序，可以用冒泡排序、插入排序等，不同的演算法可以達到相同的目標，但是效率可能有所不同。