1.研究方向

計算機主要用于數值計算時，一般要經過如下幾個步驟：

在此程序中尋求數學模型的實質是分析問題，從中提取操作的物件，并找出這些操作物件之間的關系，然后用數學語言加以描述，即建立相應的數學方程，例如:

用計算機進行全球天氣預報時，就需要求解一組球面坐標系下的二階橢圓偏微分方程
預測人口增長情況的數學模型為常微分方程

求解這些數學方程的演算法是計算數學研究的范疇，如高斯消元法、差分法、有限元法等演算法，資料結構主要研究非數值計算問題，非數值計算問題無法用數學方程建立數學模型.

資料結構是一門研究非數值計算程式設計中的操作物件，以及這些物件之間的關系和操作的學科，資料結構的研究不僅涉及計算機硬體（特別是編碼理論、存盤裝置和存取方法等）的研究范圍，而且和計算機軟體的研究有著密切的關系，無論是編譯程式還是作業系統都涉及資料元素在存盤器中的分配問題，在研究資訊檢索時也必須考慮如何組織資料，以使查找和存取資料元素更為方便，因此，可以認為資料結構是介于數學、計算機硬體和軟體三者之間的一門核心課程，

隨著大型程式和大規模檔案系統的出現，很多人認為程式設計的實質就是對所處理的問題選擇一種好的資料結構，并在此結構基礎上施加一種好的演算法，著名科學家Wirth教授的《演算法+資料結構＝程式》正是這種觀點的集中體現，

2.基本概念和術語

資料(Data)： 是客觀事物的符號表示，是所有能輸入到計算機中并被計算機程式處理的符號的總稱，如數學計算中用到的整數和實數，文本編輯中用到的字串，多媒體程式處理的圖形、影像、聲音及影片等通過特殊編碼定義后的資料，

資料元素(Data Element)： 是資料的基本單位，在計算機中通常作為一個整體進行考慮和處理，在有些情況下，資料元素也稱為元素、記錄等，資料元素用于完整地描述一個物件，如前一節示例中的一名學生記錄，樹中棋盤的一個格局（狀態），以及圖中的一個頂點等，

資料項(Data Item) ：是組成資料元素的、有獨立含義的、不可分割的最小單位，例如，學生基本資訊表中的學號、姓名、性別等都是資料項，

資料物件(Data Object)： 是性質相同的資料元素的集合，是資料的一個子集，例如：整數資料物件是集合N= {O, 士1' 士2, …}, 字母字符資料物件是集合C= {'A','B', …，'Z','a','b', …，'z'}, 學生基本資訊表也可以是一個資料物件，由此可以看出，不論資料元素集合是無限集（如整數集），或是有限集（如字母字符集），還是由多個資料項組成的復合資料元素（如學生表）的集合，只要集合內元素的性質均相同，都可稱之為一個資料物件，

3.資料結構

資料結構(Data Structure) ：是相互之間存在一種或多種特定關系的資料元素的集合，換句話說，資料結構是帶”結構＂的資料元素的集合， “結構” 就是指資料元素之間存在的關系，

資料結構包括邏輯結構和存盤結構兩個層次，

3.1 邏輯結構

資料的邏輯結構是從邏輯關系上描述資料，它與資料的存盤無關，是獨立于計算機的，因此，
資料的邏輯結構可以看作是從具體問題抽象出來的數學模型，資料的邏輯結構有兩個要素：一是資料元素；二是關系，資料元素的含義如前所述，關系是指資料元素間的邏輯關系，根據資料元素之間關系的不同特性，通常有四類基本結構，如圖1.3所示，它們的復雜程度依次遞進，

下面四種結構中所舉的示例是以某班級學生作為資料物件（資料元素是學生的學籍檔案記
錄），來分別考察資料元素之間的關系，
(1) 集合結構
資料元素之間除了“屬于同一集合” 的關系外，別無其他關系，例如，確定一名學生是否為
班級成員，只需將班級看做一個集合結構，

(2) 線性結構
資料元素之間存在一對一的關系，例如，將學生資訊資料按照其入學報到的時間先后順序進
行排列，將組成一個線性結構，

(3) 樹結構
資料元素之間存在一對多的關系，例如，在班級的管理體系中，班長管理多個組長，每位組
長管理多名組員，從而構成樹形結構，

(4) 圖結構或網狀結構
資料元素之間存在多對多的關系，例如，多位同學之間的朋友關系，任何兩位同學都可以是
朋友，從而構成圖狀結構或網狀結構，
其中集合結構、樹結構和圖結構都屬于非線性結構，
線性結構包括線性表（典型的線性結構，如例1.1中的學生基本資訊表）、堆疊和佇列（具有特
殊限制的線性表，資料操作只能在表的一端或兩端進行）、字串（也是特殊的線性表，其特殊性
表現在它的資料元素僅由一個字符組成）、陣列（是線性表的推廣，它的資料元素是一個線性表）、廣義表（也是線性表的推廣，它的資料元素是一個線性表，但不同構，即或者是單元素，或者是線性表），非線性結構包括樹（具有多個分支的層次結構）和二叉樹（具有兩個分支的層次結構）、有向圖（一種圖結構，邊是頂點的有序對）和無向圖（另一種圖結構，邊是頂點的無序對），

3.2 存盤結構

資料物件在計算機中的存盤表示稱為資料的存盤結構，也稱為物理結構，把資料物件存盤到
計算機時，通常要求既要存盤各資料元素的資料，又要存盤資料元素之間的邏輯關系，資料元素
在計算機內用一個結點來表示，資料元素在計算機中有兩種基本的存盤結構，分別是順序存盤結
構和鏈式存盤結構，

(1)順序存盤結構
順序存盤結構是借助元素在存盤器中的相對位置來表示資料元素之間的邏輯關系，通常借助
程式設計語言的陣列型別來描述，

對于前面的“學生基本資訊表”，假定每個結點（學生記錄）占用50 個存盤單元，資料從0
號單元開始由低地址向高地址方向存盤，對應的順序存盤結構如表1.2所示，

(2) 鏈式存盤結構
順序存盤結構要求所有的元素依次存放在一片連續的存盤空間中，而鏈式存盤結構，無需占
用一整塊存盤空間，但為了表示結點之間的關系，需要給每個結點附加指標欄位，用于存放后繼
元素的存盤地址，所以鏈式存盤結構通常借助于程式設計語言的指標型別來描述，
假定給前面的“學生基本資訊表” 中的每個結點附加一個“下一個結點地址＂，即后繼指標欄位，用于存放后繼結點的首地址，則可得到如表1.3所示的鏈式存盤結構，從表中可以看出，每個結點占用兩個連續的存盤單元，一個存放結點的資訊，另一個存放后繼結點的首地址，

3.3 資料型別和抽象資料型別

資料型別是一個值的集合和定義在這個值集上的一組操作的總稱，例如，C語言中的整型變址，其值集為某個區間上的整數（區間大小依賴于不同的機器），定義在其上的操作為加、減、乘、除和取模等算術運算；而實型變數也有自己的取值范圍和相應運算，比如取模運算是不能用于實型變數的，程式設計語言允許用戶直接使用的資料型別由具體語言決定，資料型別反映了程式設計語言的資料描述和處理能力，

抽象資料型別(Abstract Data Type, ADT) 一般指由用戶定義的、表示應用問題的數學模型，以及定義在這個模型上的一組操作的總稱，具體包括三部分：資料物件、資料物件上關系的集合以及對資料物件的基本操作的集合，說白了在C++中就是struct和class，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294713.html

標籤：其他

上一篇：資料結構順序表/ 鏈表oj 曲四