數據結構事前分析估演算法

『壹』 數據結構考試重點

第一章 數據結構基本概念
1、基本概念：理解什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量

第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現

第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示

第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法

第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法

第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法

第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法

第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算

第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算

第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算

『貳』 張永的數據結構與演算法與嚴蔚敏數據結構區別

摘要 一.演算法

『叄』 求數據結構的分析方法

這個得靠自己。旁人無法指導。好好努力，對自己有點信心，堅持就是勝利

『肆』 快數據結構的重點是什麼，各位大哥大姐，有學過數據結構的幫個忙吧，感謝萬分！

重點中的重點是樹，特別是樹中的二叉樹，其相關的演算法最好掌握，還有其他章節的主要是棧，隊列，串裡面的主要是串的模式匹配，基本就這些

『伍』 數據結構與演算法分析

本文出自：

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年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展並未終結，一方面，面向各專門領域中特殊問題的數據結構得到研究和發展，如多維圖形數據結構等；另一方面，從抽象數據類型和面向對象的觀點來討論數據結構已成為一種新的趨勢，越來越被人們所重視。

『陸』 數據結構的問題 求步驟和思路

1 學習方法

因為要准備這個話題， 所以我認真的思考了我的學習方法， 但是我覺得基本上我就是上課前看看書、上課時認真聽課、 下課以後復習復習、當然還有做作業時很認真的去做。根本談不上什麼好方法， 不過我還是有一些話要送給大家。

我能行！

個人覺得這句話非常重要，不知道大家是怎樣看待數據結構這門課的， 有多少人覺得數據結構很難呢看我知道還是有一些同學這樣覺得的， 有時候我跟我的朋友講要怎樣學，講了一大堆以後， 他就向我抱怨：我以前c＋＋都沒有學好， 數據結構更學不好了， 這哪跟哪的話啊，數據結構與c＋＋沒有什麼關系，我想假如抱有這樣的心態， 自己就不相信自己， 那是不可能學好的， 然後那些覺得數據結構很難的同學， 我想他們應該會很看重數據結構的吧， 然後就一天到晚捧著一本數據結構， 這樣不會覺得很累嗎看而且因為覺得很難， 就容易不相信自己， 學的效率也不會很好， 個人認為數據結構很好學， 很容易學， 或許這有點妄自菲薄吧， 但是因為我覺得很容易， 當然就會覺得自己沒問題， 學得很輕松， 效果也還可以。大家都是從高考走過來的， 應該知道心態的重要性吧， 兩種不同的心態， 完全就是兩種不同的效果。 學了這么久數據結構了， 我們到底在學些什麼呢看 不知道大家有沒有想過， 那現在我們現在來歸納一下我們學習的內容吧， 其實學到現在我們也就學了幾種普通的數據結構， 象二叉樹， 樹， 圖，還有排序的問題， 前面的線性表和字元串也就是一些概念， 當然還有一個很重要的KMP演算法， 然後在每種數據結構中我們也就是學到了若干處理的演算法， 我想真正數起來也就是幾十個演算法吧。 學習數據結構也就是要掌握這幾十種演算法， 多簡單。至於如何掌握每個演算法呢， 我想就是多看看書， 重要的是能夠理解。

我能獨自完成作業！

這里我的定義和老師的不同， 老師是鼓勵大家討論的， 不過我發現還是有一些同學就是先問好別人演算法，然後再自己寫， 雖然這個不算抄襲作業， 但自己基本上沒有一個思考問題的過程， 雖然要理解演算法也會要思考很多， 但是因為沒有自己獨立的思考過程， 要自己寫程序、 寫演算法的時候根本寫不出來， 所以我想如果真的想學好數據結構的話， 最好是能夠自己思考問題， 不要剛想了一會就覺得做不出來， 然後就去問其他人。其實老師給我們的作業還是基於我們的水平的， 我絕對相信我們自己能夠獨自想出演算法， 雖有可能會比較長時間吧， 但是這樣肯定會比問其他人學到更多的東西。當然我並不是說不要問同學， 有時候就是腦筋轉不過來，一問別人就懂了， 當然問了別人不能只是我知道了這個演算法， 還應該去想如何思考才能得到這個演算法，這樣水平會提高很多。

多實驗！

這個就沒有太多理由了， 我一直覺得編程是一門熟練科學， 多編程，水平肯定會提高， 最重要的是能夠養成一種感覺，就是對程序對演算法的敏感， 為什麼那些牛人看一個演算法一下子就看懂了看而自己要看很久才能弄懂， 而且弄懂了過了一陣子又忘記了看其實這個是因為牛人們以前看的程序很多， 編得也很多， 所以他們有了那種感覺，所以我覺得大家應該多看程序， 多寫程序， 培養自己的感覺。

2 復習和考試的技巧

我想大家應該都有這樣的感覺，就是覺得自己什麼都掌握了， 但是在考試的時候就是會犯暈， 有時候一出考場就知道錯在哪個了， 然後考完以後一對答案，發現其實考得很簡單， 應該都是自己會做的， 這個就是與自己的復習和考試的技巧有關系了。

首先就是復習， 前面已經說過其實我們學的演算法也就是幾十個， 那麼我們的任務也就是理解這幾十個演算法， 復習也就是要加深你的理解。如何理解演算法， 然後理解到什麼程度呢看 是能默出整個演算法嗎看其實不是這樣的， 數據結構的考試有它的特點， 考過期中考試了， 大家應該都發現數據結構其實不要求你把整個演算法背出來， 它注重考察你的理解， 那麼怎麼考察呢看其實也就是兩種方式吧， 一種就是用實例， 就是給你一個例子， 要你用某個演算法運行出結果， 我想這個期末考試的時候仍然會有很多這樣的題目， 比如排序那塊就很好出這樣的題目，要復習這種題目我覺得很簡單，就是每個演算法都自己用例子去實踐一下， 以不變應萬變，我期中復習的時候就是這樣去做的， 而且考試之前我就覺得那個並查集的題目就很有可能會考， 於是就自己出了幾個例子，做了一下。另外一種考察方式就是演算法填空和演算法改錯， 可能有一些同學覺得這種題目很難， 其實我們首先可以確定這兩種題目肯定是與書上演算法有關系的， 只要理解了書上的演算法就可以了，有人覺得看完書以後什麼都懂了， 而且要默也默得出來， 其實不是這樣的，演算法改錯和填空主要是考察的細微處， 雖然你覺得你默得出來， 那是能夠默出演算法的主體部分， 很多細微的地方你就會很容易忽略。我想大家考過期中考以後應該都有這種感覺吧看那要怎樣解決這種問題呢看 我覺得有兩種方法， 一種就是自己去編程實現， 這種方法比較有意義，還能夠提高編程水平， 另外一種就是用實例分析演算法的每句話， 我認為這種方法是最有效的。

然後還有一種題目， 就是最後的寫演算法的題目， 我覺得這種題目還是很好解決的， 只要是能夠自己做出作業的， 基本上都會很容易做出來，這也是為什麼我前面覺得平時做作業應該自己獨立思考的原因，同時做這種題目千萬要小心， 尤其是題目簡單的時候， 那肯定會有一些小地方要考慮清楚，一不小心就會被扣掉很多分， 這樣很不值。

我覺得考試的時候沒有太多要講的， 只要復習好了， 考試的時候細心一點就可以了， 然後就是做一個題目開始就要盡量保證正確，如果覺得留在那裡等後面做完了再來檢查，這樣錯誤還是很有可能檢查不出來， 我期中考試的時候就基本上沒有檢查， 因為我做每個題目都是確保正確， 用的時間也挺多的， 然後也覺得沒有檢查的必要了。

一個學生學習數據結構的體會（轉）
讀《數據結構（C語言版）》（1）

今天開始認真讀這本清華版的數據結構，嚴蔚敏和吳偉民編著。也許你會奇怪我為什麼會選擇這本C語言描述的數據結構書，現在的數據結構不都用面向對象語言描述嗎看其實這本書不是我選的，而是我參加的機試指定的參考書。不過對於本書選用的語言，我倒有自己的看法。用C語言描述顯然有很多不便，但是在一個充斥著用OO描述數據結構的世界裡，從OO中抽身出來用C看待數據結構的思想，也許更能看清數據結構的本質。

好了，言歸正傳。在今天這第一篇文章里，我來探討一下數據結構的基本概念。作者一開篇就歸納了計算機解題的一般步驟：逗首先要從具體問題抽象出一個適當的數學模型，然後設計一個解此數學模型的演算法，最後編出程序，進行測試、調試直至得到最終解答。地我把它再進一步歸納一下，就是：抽象數學模型——設計演算法——編寫程序。這個思路非常重要，除了一些非常簡單的問題，所有的程序設計都應該遵循這三個基本步驟。我們平時寫程序常犯的錯誤是忽略第一個或第二個步驟，或者更甚者，前兩個都忽略。

在設計數學模型的過程中，實際上就引出了數據結構的概念。本書中作者給出的定義是：逗簡單來說，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。地國內的教材為了語言上的嚴謹常常把話說得很難懂。請大家注意這句話里的這幾個關鍵詞：1）非數值計算，這說明了數據結構這門學科的應用范圍，如果你想解一個線性方程組，大概很難直接找到合適的數據結構；2）操作對象，也就是問題中的數據及其表示的形式；3）關系，即數據間的關系；4）操作，即針對數據的操作。

把以上的定義用公式寫出來，就是

Data_Structure = (D, S)

其中D是數據元素的有限集，S是D上關系的有限集。所以在設計數據結構時，首要的任務就是找出要操作的數據，其次是挖掘出數據間的關系。這兩步完成以後，數據的邏輯結構就定下來了。其中數據間的結構有以下幾種：

集合，這和數學中的集合概念是一致的；
線性結構，即數據元素之間一對一的關系；
樹形結構，即數據元素之間一對多的關系；
圖狀結構或網狀結構，即數據元素之間多對多的關系。
然而只有邏輯結構是不夠的，程序要能夠運行，必須把數據的邏輯結構在計算機中表示出來，也就是設計物理結構。大多數高級語言都對數據的物理結構有較好支持，如各種數據類型。作者在解釋數據類型的概念時說到：逗引入數據類型的目的，從硬體的角度看，是作為解釋計算機內存中信息含義的一種手段，而對使用數據類型的用戶來說，實現了信息的隱蔽，即將一切用戶不必了解的細節都封裝在類型中。地這個概括非常精闢，從中可以看出以後的OOP只是在更高層次上對信息的封裝和隱蔽。

對數據類型進一步擴展，作者引出了抽象數據類型的概念。抽象數據類型（ADT）是指一個數學模型以及定義在該模型上的一組操作。在引入抽象數據類型後，使邏輯結構更加獨立，從而讓程序員可以更加專注於邏輯結構的設計。把抽象數據類型用公式表示出來，就是(D, S, P)，其中D是數據對象，S是D上的關系集，P是對D的基本操作集。如果計算機解題一定要遵循一個通用的模式的話，上面這個式子就給出了答案。

讀《數據結構（C語言版）》（2）

本節談一談演算法分析和大O估演算法（big-O notation）。演算法效率的度量一般採用事前分析估算的方法，通常的做法是，逗從演算法中選取一種對於所研究的問題（或演算法類型）來說是基本操作的原操作，以該基本操作重復執行的次數作為演算法的時間量度地。談到這里時，作者引出了大O估演算法。

在本書中，作者對大O估演算法的介紹顯得有些草率。一開始就冒出一個式子T(n) = O(n3)，然後在本頁最底下用小字介紹了所謂的逗"O"的形式定義地：若f(n)是正整數n的一個函數，則xn=O(f(n))表示存在一個正的常數M，使得當n≥n0時都滿足|xn|≤M|f(n)|。也許是我數學基礎太差，總之看到這個定義時我一頭霧水。不知道為什麼作者沒有花一點篇幅介紹大O估演算法的由來和定義。我google了一下，發現了這樣的介紹：

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Note: As an example, n2 + 3n + 4 is O(n2), since n2 + 3n + 4 < 2n2 for all n > 10. Strictly speaking, 3n + 4 is O(n2), too, but big-O notation is often misused to mean equal to rather than less than. The notion of "equal to" is expressed by Θ(n).

The importance of this measure can be seen in trying to decide whether an algorithm is adequate, but may just need a better implementation, or the algorithm will always be too slow on a big enough input. For instance, quicksort, which is O(n log n) on average, running on a small desktop computer can beat bubble sort, which is O(n2), running on a supercomputer if there are a lot of numbers to sort. To sort 1,000,000 numbers, the quicksort takes 20,000,000 steps on average, while the bubble sort takes 1,000,000,000,000 steps!

Any measure of execution must implicitly or explicitly refer to some computation model. Usually this is some notion of the limiting factor. For one problem or machine, the number of floating point multiplications may be the limiting factor, while for another, it may be the number of messages passed across a network. Other measures which may be important are compares, item moves, disk accesses, memory used, or elapsed ("wall clock") time.

（以上介紹來自：Paul E. Black, "big-O notation", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.）

另外，這個帖子也討論了演算法的時間復雜度估計，說得非常通俗易懂。

讀《數據結構（C語言版）》（3）

【問題描述】

設計一個可進行復數運算的演示程序。

【基本要求】

實現下列六種基本運算：

由輸入的實部和虛部生成一個復數；
兩個復數求和；
兩個復數求差；
兩個復數求積；
從已知復數中分離出實部；
從已知復數中分離出虛部。
運算結果以相應的復數或實數的表示形式顯示。
（全文見附件）

『柒』 數據結構中評價演算法的兩個重要指標是什麼

數據結構中評價演算法的兩個重要指標是時間復雜度和空間復雜度。

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

1、時間復雜度：

演算法的時間復雜度是指執行演算法所需要的計算工作量。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做。

2、空間復雜度：

演算法的空間復雜度是指演算法需要消耗的內存空間。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

(7)數據結構事前分析估演算法擴展閱讀：

評估演算法效率的方法：

1、事後統計方法

這種方法主要是通過設計好的測試程序和數據，利用計算機計時器對不同演算法編制的程序的運行時間進行比較，從而確定演算法效率的高低。

2、事前分析估算方法

在計算機程序編寫前，依據統計方法對演算法進行估算。經過總結，可以發現一個高級語言編寫的程序在計算機上運行時所消耗的時間取決於下列因素：演算法採用的策略、編譯產生的代碼質量、問題的輸入規模、機器執行指令的速度。

參考資料來源：網路-演算法