什么是資料結構？

資料結構是研究非數值計算的程式設計中計算機的操作物件以及它們之間的關系和操作的學科，

一、資料結構的研究內容及基本概念和基本術語

掌握資料、資料元素、抽象資料型別、資料結構、資料的邏輯結構與存盤結構等概念，

• 資料：是客觀事物的符號表示，是所有能輸入到計算機中并被計算機處理的符號的總稱， 例如一個學生資訊大全的所有資訊稱為資料，

• 資料元素:是資料的基本單位，它通常被看作一個整體進行考慮與處理，有時稱為結點、頂點或記錄等， 例如：一個學生的所有資訊稱為資料元素，

• 資料項：是組成資料元素的、有獨立含義的、不可分割的最小單位， 例如：一個學生的學號稱為資料項，

• 資料物件：是性質相同的資料元素的集合，是資料的子集， 例如：{‘A’、‘B’、‘C’}稱為資料物件，

• 資料結構：是相互之間存在一種或多種關系的資料元素的集合，換句話說，資料結構是帶“結構”的資料元素的集合，“結構”是資料元素之間存在的關系，

• 邏輯結構：資料的邏輯結構是從邏輯關系上描述資料，它與資料的存盤無關，是獨立于計算機的，并且可以看作是具體問題抽象出來的數學模型，

• 存盤結構：資料物件在計算機中的存盤表示稱為資料的存盤結構，也稱為物理結構，存盤結構分為順序結構和鏈式結構，

（1) 順序結構：順序存盤結構借助元素在存盤器中的相對位置來表示資料元素之間的邏輯關系，在存盤器中需要連續的存盤空間，

（2）鏈式結構：鏈式存盤結構無需占用連續的存盤空間，但是為了表示資料元素之間的關系，需要給每個資料元素附加地址欄位，用于存放后繼元素的存盤地址，優點：不會占用太大的記憶體空間，缺點：查找資訊不方便，耗時長，

• 按某種邏輯關系組織起來的一批資料（或稱帶結構的資料元素的集合）應用計算機語言并按一定的存盤表示方式把它們存盤在計算機的存盤器中，并在其上定義了一個運算的集合，資料結構包含三個方面的內容，即資料的邏輯結構，資料的存盤結構和對資料進行的運算（操作），

• 三方面的關系：
  （1）資料的邏輯結構獨立于計算機中，是資料本身所固有的，
  （2）存盤結構是邏輯結構在計算機存盤器的映像，必須依賴于計算機，（因為既要存盤各資料元素的資料，又要資料元素之間的邏輯關系），
  （3）運算是指所施加的一組操作的總稱，
  

• 邏輯結構的形式定義是一個二元組：Data-Structure=（D，S），其中D是資料元素的有限集，S是D上關系的有限集，
  注：D上的關系S可以用序偶來表示：<x,y>（x，y屬于D），x元素為y元素的直接前驅，y元素為x元素的直接后繼，

資料型別

• 資料型別指的是一個值的集合和定義在這個值集上的一組操作的總稱，
• 型別明顯地規定了資料的取值范圍、存盤方式以及允許進行的計算，這些我們在學習C語言中都能夠體會的到，
  資料結構的主要運算（基本操作演算法）包括：建立、消除、洗掉、插入、訪問、修改、排序、查找，而書上總結的只有查找、插入、修改、洗掉，

抽象資料型別（ADT）

• 抽象資料型別指的是一個由用戶定義、表示數學應用問題的數學模型，以及定義在這個模型上的一組操作的總稱，
• 抽象資料型別的形式定義分為三部分：資料物件（D）、資料物件上關系的集合（S）以及對資料物件的基本操作的集合（P），

ADT抽象資料型別名{
    資料物件：<資料物件的定義>
    資料關系：<資料關系的定義>
    基本操作：<基本操作的定義>
} ADT抽象資料型別名

下面就給出復數的存盤表示和相應的操作的具體實作程序，也可以參考書上用結構體的程序實作，

ADT complex{
資料物件：D={real, image | real∈實數, image∈實數} 
資料關系：R={<real,image>} 
基本操作：
    InitComplex(&C)
    操作結果：構造一個復數，
    GetReal(C, &real)
    初始條件：復數C存在，
    操作結果：用real回傳復數C的實部，
    GetImage(C, &image)
    初始條件：復數C存在，
    操作結果：用image回傳復數C的虛部，
    OutputComplex(C)
    初始條件：復數C存在，
    操作結果：輸出復數C的值，
    Add(C1,C2,&C)
    初始條件：復數C1,C2存在，
    操作結果：用復數C回傳復數C1,C2的和，
    Sub(C1,C2,&C)
    初始條件：復數C1,C2存在，
    操作結果：用復數C回傳復數C1,C2的差，
}ADT Complex

二、演算法、時間復雜度、空間復雜度

演算法

是為了解決某類問題而規定的一個有限長的操作序列，

• 演算法必須要有以下5個特性：
  （1）有窮性：有限步后要能結束，不能死回圈，
  （2）確定性：每條指令有確切含義，相同的輸入有相同的結果，不會產生二義性，
  （3）可行性：每個操作都能經過有限次基本運算完成，
  （4）輸入：演算法可以沒有輸入，
  （5）輸出：演算法一定有輸出，

• 評價演算法準則：
  （1）正確性：能夠得到問題正確的解
  （2）可讀性：便于人對演算法的理解
  （3）健壯性：對于非法資料能給出處理
  （4）高效率低存盤：執行速度快，消耗空間少，這兩者是矛盾的，需要平衡，

• 演算法效率度量
  度量程式執行時間有兩種方法，一是事后統計，即將演算法撰寫為程式，在計算機上運行得到運行的時間，但執行時間與計算機性能有關，容易掩蓋演算法本身的優劣，所以通常使用事前估演算法，

時間復雜度

演算法執行時間=一次簡單操作時間*執行次數，由于一次簡單操作時間受計算機性能影響，所以衡量演算法效率，主要看執行次數多少，并且我們不需要求出精確次數，而只需要求出某個函式f(n)，使得當n充分大時，時間增長率與f(n)增長率相同，即T(n) = O( f(n) ) ，計算時間復雜度主要分為兩個步驟：先分析哪條陳述句是陳述句頻度最大的陳述句，再計算回圈執行多少次求出時間復雜度，

熟記不同時間復雜度的大小關系：

時間復雜度運算我們需要掌握兩條法則：

加法法則：

乘法法則：

因為一個演算法的平均時間復雜度難以確定，因此，通常只討論演算法在最壞情況下（即取回圈次數最多）的時間復雜度，即分析在最壞情況下，演算法執行時間的上界，

求下列程式的時間復雜度：

例題：

void fun(int n)
{
	int i =1;
	while(i<=n)
	{
		i = i*2;
	}
}

回圈看似執行n次，但因為回圈變數每次都*2，回圈執行x次后，i最后可以看為2的x次方，2的x次方<=n,則能計算出x為log2的n次，所以時間復雜度為f(n)=O(log2的n次），

例題：（立方階）

for(i=1;i<=n;i++)
	for(j=1;j<=i;j++)
		for(k=1;k<=j;k++)
			x++;

這條程式的陳述句頻度最深的毫無疑問是x++，我們觀察嵌套最深的for回圈的條件，k從1到j，則執行了j次，第二層回圈中，j從1到i，則要算出1到i等引數列的和，即2分之i(i+1),最外層回圈中i從1到n，回圈n次，算出1到n的和代入到第二層結果的i中，則結果能夠算出最終結果，參考書本14頁最上方，

空間復雜度

該演算法所耗費的存盤空間，這個空間指的是額外的輔助空間，

這里第一章只重點考察時間復雜度，計算空間復雜度相對簡單，看書上例題即可，在此處不再說明，

總結

因為第一章涉及概念與術語比較多，一定要盡力地去背誦，去了解資料結構的大致內容，此后作者還會持續更新對《資料結構》后面知識的知識梳理，請持續關注，如果本篇文章讓您對資料結構的入門有幫助，麻煩點個贊謝謝！