基本介紹
- 中文名：套用數據結構
- 外文名：application data structure
- 涉及學科：計算機等
- 套用領域：CAD、資料庫等
- 縮寫：ADS
- 對象：數據結構
數據結構,背景,概念,數據結構的設計,分析步驟,建立數據結構,存儲結構,設計,套用數據結構解決表達式中括弧匹配問題,抽象數據的邏輯結構,選用存儲數據的物理結構,算法描述,套用數據結構,為設計資料的數據描述提供依據,適合套用軟體,為數據檢索提供條件,為數據通信提供條件,
數據結構
背景
計算機處理的信息和數據不僅包括數字，而且包括字元、表格、圖形、圖像、聲音、動畫等複雜問題，這些信息不只是簡單、孤立的數據，而是存在某些關係的數據。獨立的數據往往是毫無意義的，只有將它們組織在一起才能賦予它們確切的含義。如何組織、處理這些信息，就是數據結構的基本問題。數據結構就是指數據之間的結構層次關係。例如，給定二個點的坐標，計算機可以將它們連成一個三角形.也可以過這三個點作一個圓或畫一段圓弧。但是，如果事先並沒有確定這三個點之間的繪圖關係，亦即如何組織利用這三個點進行畫線、畫圓或畫圓弧，那么計算機就不能完成相應的動作。只有當點的坐標和繪圖關係確定之後，計算機才能畫出我們所希望的圖形。因此，數據及其結構層次關係在計算機中的表達，是影響套用軟體成敗及效率高低的關鍵。
概念
數據的邏輯結構大致上可以分為線性結構和非線性結構。線性結構的數據元素之間存在一對一的關係，其特點是除了開頭和最後一個節點外，其他的任意一個節點都只有一個直接前驅節點後後繼節點。線性結構主要包括有線性表、棧和佇列。樹、集合、圖都是非線性結構，其中樹形結構模擬層次，圖形結構模擬對稱和非對稱關係。研究數據結構是程式設計的需要，是為了使得程式設計更加的健壯、高效，使得程式的開發更加的方便。
數據結構的設計
套用數據結構解決生活中的問題的首要前提是研究套用什麼數據結構解決生活中的問題。
分析步驟
其分析步驟為:
- 首先分析任務中的操作對象，即找出任務中涉及到的數據，從中總結和抽象出操作對象，並且分析操作對象之間的邏輯關係;
- 其次根據任務中對操作對象的操作，研究套用何種存儲方式來存儲數據才能高效的執行程式並且占用較小的存儲空間。
- 選擇數據結構的接口要最接近軟體的需求。通常當有多個滿足需要的接口數據結構實現時，可以根據比較他們的接口操作的運行時間以及數據結構消耗的空間來進行選擇，有的時候時間和空間可以相互轉換，比如可以用空間來交換操作的效率;
- 最後在物理存儲方式的基礎上設計正確的算法實現操作，完成任務。
建立數據結構
生活中所要處理的數據之間可以抽象出來不同的邏輯關係，建立不同的數據結構，但是針對實際問題要從中選取能夠準確描述問題的基本特性並且易於實現的邏輯結構。
例如：八枚硬幣中其中有一枚硬幣是較為輕的，要求用一個天平將這枚輕的硬幣判斷出來，判斷的過程採用將硬幣分析兩組或者三組，分別使用天平比較的方式來判斷。這一判斷過程可以用一個樹形圖來表示，所以可以將該問題抽象為判定樹，構建樹形結構。
存儲結構
根據選定的數據結構可以用不同的存儲結構來實現。不同類型的數據結構常用的存儲結構為順序存儲結構、鏈式存儲結構、散列存儲結構及索引存儲結構。不同的存儲結構具有不同的特點，大致上存在的差異在存儲空間和運算效率兩個方面。例如線性表的順序存儲結構與鏈式存儲結構在存儲空間上來對比，鏈式存儲結構顯然要多占用一部分存儲空間。從運算效率上來對比，如果線性表需要進行大量的插入和刪除操作的話，那么鏈式存儲結構從執行效率上來講要占有優勢。而如果線性表要反覆進行查詢操作的話，順序存儲結構具備隨機讀寫的特點，就比較適合這種情況。
設計
確定數據的邏輯關係與存儲結構的情況下，可以設計出不同的算法來實現套用。設計的算法應該是正確的算法。正確的算法的含義是:能夠解決實際問題，輸入的所有可能的合法的輸入都能產生預期的正確的結果;能夠在有窮的步驟內執行完程式;能夠用最簡短的語句最高效的完成任務。
套用數據結構解決表達式中括弧匹配問題
抽象數據的邏輯結構
在此問題中操作對象為表達式的括弧，括弧的匹配的表達式都具有這樣的特點:在從左至右掃描表達式的過程中，最先掃描到的右括弧必定與之前最後掃描到的左括弧相匹配。根據這特點及棧的先進後出的特點可以將表達式抽象成棧，表達式中的左、右括弧為棧中的數據元素。並且該邏輯結構具有出棧及入棧的操作能夠滿足任務的需求。
選用存儲數據的物理結構
順序棧占用存儲空間小，不浪費空間，同時進棧與出棧操作程式執行效率高。所以解決該問題可採用順序存儲結構實現棧。順序棧的特點是:用一組連續的空間存放自棧底到棧頂的數據元素。數據元素之間存線上性關係，第一個入棧的數據元素稱為棧底元素，最後一個入棧的數據元素稱為棧頂元素，用指針TOP標誌。順序棧的基本操作包括:創建一個空棧、判斷棧是否為滿、判斷棧是否為空、得出棧的長度、入棧、出棧、返回棧頂元素。如圖1所示:
圖1
順序棧入棧操作的實現步驟為:
判斷如果棧己滿，返回false，不允許入棧
- 若棧不滿，將棧頂指針top+ 1
- 數據element存入top所指的空間中
- 操作成功返回true
順序棧出棧操作的實現步驟為:
- 判斷順序棧狀態，如果棧己空，不允許出棧
- 若棧不空，取出棧頂指針top所指的內容
- 棧頂指針top-1，指向下一個元素
- 返回出棧數據
算法描述
關於括弧匹配的操作是這樣進行的:
(1)將輸入的表達式按序存入數組，掃描整個數組，遇到左括弧都進行棧
(2)遇到右括弧
①先進行判空，若是空棧，則一個右括弧入棧後一定是不匹配的
②如果判空後不是空棧，那么就把棧里的括弧彈出並與遇到的第一個右括弧進行匹配判斷，若匹配則繼續執行步驟1. 2，若不匹配則整個表達式也不匹配。
(3)當進行完上面得操作後，如果棧不為空，那就說明肯定還有括弧留在棧中，那一定就是不匹配了。若整個表達式掃描完畢，棧也為空，則說明表達式中括弧匹配。
套用數據結構
以上所講的數據結構在計算機輔助機械設計系統中的套用主要有下列幾個方面:
為設計資料的數據描述提供依據
從嚴格意義上來講，應用程式中對任何一個變數的定義、對任何一個數據檔案的存取都涉及到數據結構的問題。定義數據結構應遵循的一個基本原則是:數據結構簡單、邏輯關係明確清晰、便於操作、存取速度快、運行效率高、占用存儲空間少。對簡單意義的變數一般可以用常量、單變數來定義；對較為複雜的數據一般可以用一維數組、多維數組、結構變數或指針來定義。
適合套用軟體
適合套用軟體作業中對設計模型作實時修改的需要。如增加、刪除、修改記錄等。應根據實際情況，對線性結構的數據和非線性結構的數據構造不同的數據結構，以便於提高數據操作的效率。順序存儲結構和鏈式存儲結構各有優缺點，它們適合於不同的場合，因而選用時應權衡考慮。
為數據檢索提供條件
在設計中常常需要根據設計對象的某些特徵、屬性來檢索一些數據以供設計之用，為此就必須利用數據結構來提供條件。如一部機器可能由很多個零件組成，套用軟體作業中可能需要根據零件的名稱、材料、標準件或非標準件等條件進行檢索。這就需要很好地定義零件信息的數據結構以便檢索。
為數據通信提供條件
如為網路機械設計、數據交換及共享數據資源提供條件。智慧型化、集成化和網路化是CAD發展的趨勢。這些都涉.及到大量數據的通信和交換。只有嚴密、高效的數據結構才能保證計算機輔助機械設計技術的健康發展。
