一、什麼是資料結構

1、用計算機解決一個具體問題的步驟

（1）分析問題，確定資料模型。

（2）設計相應的演算法。

（3）編寫程式，執行並除錯程式直至得到正確的結果。

2、需要從資料入手來分析並得到解決問題的方法

（1）結構化資料：

資料：是描述客觀事物的數、字元以及所有能輸入到計算機中並被計算機程式處理的符號的集合。

資料元素：是資料的基本單位（例如，A班中的每個學生記錄都是一個數據元素），也就是說資料元素是組成資料的、有一定意義的基本單位，在計算機中通常作為整體處理

資料項：是具有獨立含義的資料最小單位，也稱為成員或域（例如，A班中每個資料元素即學生記錄是由學號、姓名、性別和班號等資料項組成）。

（2）資料物件

資料物件是性質相同的有限個數據元素的集合，它是資料的一個子集。

如大寫字母資料物件是集合C={'A'，'B'，'C'，…，'Z'}；1～100的整數資料物件是集合N={1，2，…，100}。

注：預設情況下，資料結構中的資料都指的是資料物件。

（3）資料結構

資料結構是指所涉及的資料元素以及資料元素之間的關係，可以看作是相互之間存在著特定關係的資料元素的集合。可時把資料結構看成是帶結構的資料元素的集合。

（4）資料元素之間的關係 結構,現實世界的結構是紛繁複雜的

（5）一個數據結構的幾個方面：

資料元素之間的邏輯關係：資料的邏輯結構。

資料元素及其關係在計算機儲存器中的儲存方式：資料的儲存結構（或物理結構）。

施加在該資料上的操作：資料運算。

二、資料的邏輯結構

資料的邏輯結構是面向使用者的，它反映資料元素之間的邏輯關係而不是物理關係。

資料的邏輯結構是獨立於計算機的。

（1）由於資料邏輯結構是面向使用者的，可以採用表格、圖等使用者容易理解的形式表示。

（2）二元組

為了更通用地描述資料的邏輯結構，通常採用二元組表示資料的邏輯結構，一個二元組如下：

B=(D，R)

其中，B是一種邏輯資料結構，D是資料元素的集合，在D上資料元素之間可能存在多種關係，R是所有關係的集合。即：

D={di | 0≤i≤n-1，n≥0}

R={rj | 1≤j≤m，m≥0}

例：R={rj | 1≤j≤m，m≥0}

R中的某個關係rj（1≤j≤m）是序偶（將兩個元素 x,y 有順序地放在一起構成一個組合(x,y)稱為序偶）的集合。

對於rj中的任一序偶<x，y>（x，y∈D），把x叫做序偶的第一元素，把y叫做序偶的第二元素，又稱序偶的第一元素為第二元素的前驅元素，稱第二元素為第一元素的後繼元素。如在<x，y>的序偶中，x為y的前驅元素，而y為x的後繼元素。

若某個元素沒有前驅元素，則稱該元素為開始元素；若某個元素沒有後繼元素，則稱該元素為終端元素。

對於對稱序偶，即滿足這樣的條件：若<x，y>∈r（r∈R），則<y，x>∈r（x，y∈D），可用圓括號代替尖括號，即(x，y)∈r。

（3）集合

集合：結構中資料元素之間除了"同屬於一個集合"的關係外，沒有其他關係，與數學中的集合概念相同。

（4）線性結構

線性結構：若結構是非空的，則有且僅有一個開始元素和終端元素，並且所有元素最多隻有一個前驅元素和一個後繼元素。

（5）樹形結構

樹形結構：若結構是非空的，則有且僅有一個元素為開始元素（也稱為根結點），可以有多個終端元素，每個元素有零個或多個後繼元素，除開始元素外每個元素有且僅有一個前驅元素。

（6）圖形結構

圖形結構：若結構是非空的，則每個元素可以有多個前驅元素和多個後繼元素。

三、資料的儲存結構

（1）資料在計算機儲存器中的儲存方式就是儲存結構。它是面向程式設計師的。

設計儲存結構的這種對映應滿足兩個要求：

儲存所有元素、儲存資料元素間的關係

（2）在軟體開發中，人們設計了各種儲存結構。歸納為4種基本的儲存結構。

順序儲存結構、鏈式儲存結構、索引儲存結構、雜湊（雜湊）儲存結構

練1：如下圖，利用擅長的語言編寫學生類。

該儲存稱為順序儲存結構，結構的特性是：

所有元素存放在一片地址連續的儲存單元中。

邏輯上相鄰的元素在物理位置上也是相鄰的，所以不需要額外空間表示元素之間的邏輯關係。

練2：

如下圖，利用擅長的語言編寫學生類。

該儲存稱為鏈式儲存結構，結構的特性是：

資料元素存放在任意的儲存單元中，這組儲存單元可以是連續的，也可以是不連續的。

透過指標域來反映資料元素的邏輯關係。

四、資料的運算

（1）將資料存放在計算機中的目的是為了實現一種或多種運算。

運算包括功能描述（或運算功能）和功能實現（或運算實現）。

前者是基於邏輯結構的，是使用者定義的，是抽象的。後者是基於儲存結構的，是程式設計師用計算機語言或偽碼錶示的，是詳細的過程，其核心是設計實現某一運算功能的處理步驟，即演算法設計。

例如，對於高等數學成績表這種資料結構，可以進行一系列的運算：

（2）同一運算，在不同儲存結構中的實現過程是不同的。

練習：查詢序號為i的學生分數，利用自己擅長的語言完成

其本身就是運算的功能描述。但在順序儲存結構和鏈式儲存結構中的實現過程不同的。

注：

同一邏輯結構可以對應多種儲存結構。

同樣的運算，在不同的儲存結構中，其實現過程是不同的。

五、資料型別

（1）資料型別是一組性質相同的值的集合和定義在此集合上的一組操作的總稱

（2）資料結構是指計算機處理的資料元素的組織形式和相互關係，而資料型別是某種程式設計語言中已實現的資料結構。

（3）在程式設計語言提供的資料型別支援下，就可以根據從問題中抽象出來的各種資料模型，逐步構造出描述這些資料模型的各種新的資料結構。

（4）抽象資料型別（ADT）

指的是從求解問題的數學模型中抽象出來的資料邏輯結構和運算（抽象運算），而不考慮計算機的具體實現。

抽象資料型別 = 邏輯結構 ＋ 抽象運算