|
我們使用的計算機絕大多數都是馮·諾依曼體系，其理論基礎就是”存儲程序“概念。數據和操作數據的指令都需要先存儲到地址線性表示的內存單元中。數據的一般操作有”增、查、刪、改、遍歷“等，數據存儲需要”存得進、取得出”，需要考慮時間和空間效率，所以要“存數值、存聯(lián)系”，數據的存儲不僅需要保存數據本身，還需要考慮保存數據本身的邏輯關系。 程序要處理的數據有數值類或非數值類兩種類型。數值類處理的是純數值性的信息，如科學和工程計算。數值類數據的關系一般用數學公式或方程來描述。而非數值類問題的數據及數據間的相應關系一般無法用數學公式或方程來描述，如排序問題、檢索問題，需要另外設計數據的描述方法和相應的算法來處理。 所以，用計算機解決實際問題，需要對解決的問題進行分析，提煉出問題的兩個要素：信息和功能。（數據描述和數據處理的步驟描述，也就是數據結構和算法）。 分析問題中的已知信息，提煉數據和數據之間的聯(lián)系（數據的邏輯結構），選用合適的存儲方式（數據的存儲結構）將邏輯結構（數據元素和邏輯關系）存到計算機中，然后在存儲結構之上按照自頂向下逐步細化的方法給出算法。這就是程序設計思維的一般過程。 上圖中，程序設計將算法”翻譯“成相應命令語句及處理形成代碼。
下表是一般編程的解題步驟與從軟件工程角度看這些步驟的對應關系。
1 數據類型與抽象數據類型計算機對數據的處理，就如同工廠對“物料”的處理一樣，物料如同數據，工藝如同算法。一般來說，按照“存儲程序”概念，數據需要保存到“一格一格”的內存單元中，根據數據種類、數量的多少、數據元素的復雜程度，對應的數據結構和復雜度也會有所區(qū)別。如果數據量少，數據元素聯(lián)系簡單，則用簡單的基本數據類型如變量、數組即可描述需要處理的數據，用簡單的一些表達式即可描述算法。如果數據量大，數據元素聯(lián)系復雜（普通數學方程無法描述），則需要定義或選擇復雜的數據結構（抽象數據類型），如棧、樹、圖等，以及復雜的算法。 1.1 數據類型（data type)是一組性質相同的值的集合和定義在集合上的一級操作的總稱。 1.2 抽象數據類型（Abstract Data Type，ADT）指的是用戶進行軟件系統(tǒng)設計時從問題的數學模型中抽象出來的邏輯數據結構和邏輯數據結構上的運算，而不考慮計算機的具體存儲結構和運算的具體實現(xiàn)算法。抽象數據類型中的數據對象和數據運算的聲明與數據對象的表示和數據運算的實現(xiàn)相互分離。 一個具體問題的抽象數據類型的定義通常采用簡潔、嚴謹的文字描述，一般包括數據對象（即數據元素的集合）、數據元素關系和基本運算三方面的內容。其基本格式可描述如下：
(Data和Relation一般可以用結構體或類數據成員定義，Operation一般可以用函數（數據結構算法）或類成員函數定義。) 如，線性表的抽象數據類型：
2 數據元素及聯(lián)系（邏輯結構）現(xiàn)實世界是復雜的，抽象后的數據也有線性、非線性、集合的邏輯關系，而計算機內部的存儲單元地址只是線性關系，所以數據元素邏輯關系與實際存儲的映射會形成不同的數據結構和算法，會有不同的時間和空間效率。 數據結構的含義包括三個方面－數據的邏輯結構、數據的存儲結構以及數據的運算（如增、查、刪、改）。數據的邏輯結構體現(xiàn)在數據的聯(lián)系，數據的存儲是數據在計算機中的體現(xiàn)。 3 數據存儲（存儲結構）3.1 順序存儲結構 Sequential storage strcture 是采用一組連續(xù)的存儲單元存放所有的數據元素，也就是說，所有數據元素在存儲器中占有一整塊存儲空間，而且兩個邏輯上相鄰的元素在存儲器中的存儲位置也相鄰。因此，數據元素之間的邏輯關系由存儲單元地址間的關系隱含表示，即順序存儲結構將數據的邏輯結構直接映射到存儲結構。 順序存儲結構的主要優(yōu)點是存儲效率高，因為分配給數據的存儲單元全用于存放數據元素，元素之間的邏輯關系沒有占用額外的存儲空間；另外，在采用這種存儲方法時可實現(xiàn)對元素的隨機存儲，即每個元素對應一個邏輯序號，由該序號可以直接計算出對應元素的存儲地址，從而獲取元素值。順序存儲結構的主要缺點是不便于數據修改，對元素的插入或刪除操作可能需要移動一系列的元素。 3.2 鏈式存儲結構 Linked storage structure 在鏈式存儲結構中，每個邏輯元素用一個內存結點存儲，每個結點是單獨分配的，所有的結點地址不一定是連續(xù)的，所以無須占用一整塊存儲空間。為了表示元素之間的邏輯關系，給每個結點附加指針域，用于存放相鄰結點的存儲地址，也就是通過指針域將所有結點鏈接起來，這就是鏈式存儲結構名稱的由來。 3.3 順序存儲與鏈式存儲二者優(yōu)、缺點對比
3.4 索引存儲結構 Indexed storage structure 索引存儲結構是指在存儲數據元素信息的同時還建立附加的索引表。存儲所有數據元素信息的表稱為主數據表，其中每個數據元素有一個關鍵字和對應的存儲地址。索引表中的每一項稱為索引項，索引項的一般形式為“關鍵字，地址”，其中“關鍵字”唯一標識一個元素，“地址”對應該關鍵字的元素在主數據表中的存儲地址。通常，索引表中的所有索引項是按關鍵字有序排列的。 在按關鍵字查找時，首先在索引表中利用關鍵字的有序性快速查找到該關鍵字的地址，然后通過該地址在主數據表中找到對應的元素。 索引存儲結構的優(yōu)點是查找效率高。缺點是需要建立索引表，從而增加了空間開銷。 3.5 哈希（或散列）存儲結構 Hashed storage structure 哈希存儲結構的基本思想是根據元素的關鍵字通過哈希（或散列）函數直接算出一個值，并將這個值作為該元素的存儲地址。 哈希存儲結構的優(yōu)點是查找速度快，只要給出待查元素的關鍵字就可立即計算出該元素的存儲地址。與前3種存儲方法不同的是，哈希存儲方法只存儲元素的數據，不存儲元素之間的邏輯關系。哈希存儲結構一般只適合要求對數據能夠進行快速查找和插入的場合。 4 數據運算（增、查、刪、改）數據運算是指對數據實施的操作。每種數據結構都有一組相應的運算，最常用的運算有檢索、插入、刪除、更新和排序等。數據運算最終需要在對應的存儲結構上用算法實現(xiàn)，所以數據運算分為運算定義和運算實現(xiàn)兩個層面。 5 數據結構具體類型5.1 線性表包括順序表和鏈表兩種類型。 5.2 棧：操作都在表的一端(棧頂，top)進行，按先入(插入)后出(刪除)的方式管理的線性表；棧相對于線性表來說，不需要考慮數組的下標增減等細節(jié)，而直接使用對棧的Push和Pop操作。如回退操作、遞歸調用、函數調用等可以方便地用到這種受限的線性表結構。 5.3 隊列：一端插入(隊尾)一端刪除(隊頭)的線性表。
5.4 樹結構：反映一種層次的縱向關系，如計算機文件系統(tǒng)的目錄結構。其存儲的數據邏輯關系是每一個結點都有1個或0個雙親（parent）結點，n個或0個子（child）結點。樹結構的基本操作包括：構造、插入、刪除、遍歷、深度、查找等。堆通常是一個可以被看做一棵樹（完全二叉樹）的數組對象。 5.5 廣義表：包含子結構的線性結構，是線性表的推廣，但是一種非線性結構類型。 5.6 圖結構：數據結構中的圖不是幾何平面中的圖的概念，而是拓撲意義上的圖。通常平面幾何或立體幾何研究的對象是點、線、面之間的位置關系以及它們的度量性質。拓撲學研究幾何圖形在連續(xù)變形下保持不變的性質。如地鐵線路圖就是應用了拓撲學的原理。通常在平面幾何中，把平面上的一個圖形搬到另一個圖形上，如果完全重合，那么這兩個圖形叫做全等形。但在拓撲學中，無論圖的大小或者形狀怎么變化，只要其中點和線的數量不變，它們就是等價圖。 圖是一種比線性表和樹形結構更為復雜的非線性數據結構，圖對結點的前驅和后繼個數不加限制，各數據元素之間的關系可以是任意的，描述的是“多對多”的關系。在數據結構中，考慮的是圖在計算機中的存儲和操作。 圖是由頂點和邊構成，除了要存儲結點的信息，還要存儲邊的信息。另外，圖有無向圖、有序圖、加權圖等、
6 算法在分析處理的問題、確定的需要的數據結構、完成了數據的存儲之后，接下來的事情就是對數據的加工處理了，對問題求解進行精確描述，也就是算法。 不同的問題有不同的解決方法，同一個問題也可能會有多種算法可供選擇。 算法有5個特征。
算法的實現(xiàn)由函數完成。算法設計的一般步驟是：
常用算法：遞推法、遞歸法、窮舉法、貪心算法、分治法、動態(tài)規(guī)劃法、迭代法、分支界限法。 算法可大致分為基本算法、數據結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數值分析、加密算法、排序算法、檢索算法、隨機化算法、并行算法，厄米變形模型，隨機森林算法。 7 數據處理（數據結構和算法）綜述實際問題中數據的處理，一是根據問題中的信息，抽象出信息中的數據與聯(lián)系，并根據問題的功能要求及數據量的大小，選用合適的存儲結構；二是根據功能要求劃分模塊分別處理；三是測試和調試
如，求一個數的階乘n! 5.1 問題分析：可以先選擇一個數值不太大，又不是特殊點的值，如n=5來設計算法的實現(xiàn)。 5.2 測試樣例設計：
5.3 函數接口及功能描述：
5.4 代碼實現(xiàn)
5.5 測試結果
|
|
|
