數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、（存儲）物理結(jié)構(gòu)和數(shù)據(jù)的運算三個部分。常見的數(shù)據(jù)結(jié)構(gòu)有：隊列，樹，堆，數(shù)組，棧，鏈表，涂，散列表等。
第一節(jié)：數(shù)據(jù)結(jié)構(gòu)概述
數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，并確保經(jīng)過這些運算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。
1.1 概念術(shù)語
（1）數(shù)據(jù)（Data）是能被計算機處理的符號或符號集合，含義廣泛，可理解為“原材料”。如字符、圖片、音視頻等。
（2）數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位。例如一張學生統(tǒng)計表。
（3）數(shù)據(jù)項（data item）組成數(shù)據(jù)元素的最小單位。例如一張學生統(tǒng)計表，有編號、姓名、性別、籍貫等數(shù)據(jù)項。
（4）數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如正整數(shù)N={1，2，3，····}。
（5）數(shù)據(jù)結(jié)構(gòu)（data structure）是數(shù)據(jù)的組織形式，數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素集合。
（6）數(shù)據(jù)類型（data type）是按照數(shù)據(jù)值的不同進行劃分的可操作性。在C語言中還可以分為原子類型和結(jié)構(gòu)類型。原字類型是不可以再分解的基本類型，包括整型、實型、字符型等。結(jié)構(gòu)類型是由若干個類型組合而成，是可以再分解的。
下圖展示出他們之間的關(guān)系：
1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)（logical structure）是指在數(shù)據(jù)中數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)元素之間存在不同的邏輯關(guān)系構(gòu)成了以下4種結(jié)構(gòu)類型。
（1）集合結(jié)構(gòu)：集合的數(shù)據(jù)元素沒有其他關(guān)系，僅僅是因為他們擠在一個被稱作“集合”的盒子里。
（2）線性結(jié)構(gòu)：線性的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對一的，并且是一種先后的次序，就像a-b-c-d-e-f-g·····被一根線穿連起來。
（3）樹形結(jié)構(gòu)：樹形的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對多的，這就像公司的部門級別，董事長-CEO\CTO-技術(shù)部\人事部\市場部.....。
（4）圖結(jié)構(gòu)：圖的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是多對多的。就是我們常見的各大城市的鐵路圖，一個城市有很多線路連接不同城市。
1.3 數(shù)據(jù)的存儲（物理）結(jié)構(gòu)
存儲結(jié)構(gòu)（storage structure）也稱為物理結(jié)構(gòu)（physical structure），指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式。數(shù)據(jù)的存儲結(jié)構(gòu)一般可以反映數(shù)據(jù)元素之間的邏輯關(guān)系。分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。
（1）順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在一組存儲地址連續(xù)的存儲單元里，其數(shù)據(jù)元素間的邏輯關(guān)系和物理關(guān)系是一致的。
（2）鏈式存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。
1.4 抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型（abstract data type，ADT）是描述具有某種邏輯關(guān)系的數(shù)據(jù)模型，并對在數(shù)學模型上進行的一組操作。抽象數(shù)據(jù)類型描述的是一組邏輯上的特性，與在計算機內(nèi)部表示無關(guān)，計算機中的整數(shù)數(shù)據(jù)類型是一個抽象數(shù)據(jù)類型，不同處理器可能實現(xiàn)方法不同，但其邏輯特性相同，即加、減、乘、除等運算是一致的?！俺橄蟆钡囊馑际菙?shù)據(jù)類型的數(shù)學抽象特性而不是指它們的實現(xiàn)方法。抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計中的問題分解、抽象、信息隱藏等特性，可以把現(xiàn)實中的大問題分解為多個規(guī)模小且容易處理的小問題，然后建立起一個能被計算機處理的數(shù)據(jù)，并把每個功能模塊的實現(xiàn)細節(jié)作為一個獨立的單元，從而使具體實現(xiàn)過程隱藏起來。就類似建一棟房子，分成若干個小任務(wù)，如地皮規(guī)劃、圖紙設(shè)計、施工、裝修等，整個過程與抽象數(shù)據(jù)類型中的問題分解類似。而搬磚人不需要了解圖紙設(shè)計如何，設(shè)計圖紙人員不需要了解施工的地基、砌墻的具體細節(jié)，裝修工人不用關(guān)系圖紙和搬磚過程，這就是抽象類型中的信息隱藏。
抽象數(shù)據(jù)類型的概念可能讓初學者不太容易理解。例如線性表的抽象數(shù)據(jù)類型的描述數(shù)據(jù)對象集合：線性表的數(shù)據(jù)對象集合為{a1,a2,a3,····,an},每個元素的類型均為DataType。其中，除了第一個元素a1外，每一個元素有且只有一個直接前驅(qū)元素；除了最后一個元素an外，每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的。
1.5算法
算法（algorithm）是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為有限的操作序列。在數(shù)據(jù)類型建立起來之后，就要對這些數(shù)據(jù)類型進行操作，建立起運算的集合即程序。運算的建立、方法好壞直接決定著計算機程序原型效率的高低。
（1）數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系
兩者既有聯(lián)系又有區(qū)別。聯(lián)系是程序=算法+數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的基礎(chǔ)，算法總是要依賴某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。區(qū)別是數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)等一些基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基本上解決實際問題。算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是這些思想的基礎(chǔ)。
（2）算法的五大特性
有窮性，是指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不是出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。
確定性，是指算法執(zhí)行的每一步驟在一定條件下只有一條執(zhí)行路徑，也就是相同輸入只能有一個唯一的輸出結(jié)果。
可行性，是指算法每一步驟都必須可行，能夠通過有限的執(zhí)行次數(shù)完成。
輸入，是指算法具有零個或多個輸入。
輸出，是指算法至少有一個或多個輸出。
（3）算法設(shè)計要求
正確性，是指算法在執(zhí)行結(jié)束后得到的結(jié)果是正確的。
可讀性，是指算法的設(shè)計讓人方便易于看懂。
健壯性，是指算法在任何輸入情況下不應(yīng)出現(xiàn)崩潰的特性。
時間效率?高和儲存量量低，是指算法運行花費的時間大小和運行所使用的內(nèi)存的高低。
1.6時間復雜度
在進行算法分析時，語句總是執(zhí)行次數(shù) T(n) 是關(guān)于問題規(guī)模 n 的函數(shù)。進而分析次數(shù)T(n)隨規(guī)模n的變化情況并確定T(n)的數(shù)量級。算法的時間復雜度就是算法的時間度量，記作T(n) = O（f（n））。它表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f（n）的增長率相同，稱作算法的漸進時間復雜度，簡稱為時間復雜度。其中，f（n）是問題規(guī)模n的某個函數(shù)。
算法的時間復雜度是衡量一個算法好壞的重要指標。一般情況下，隨著規(guī)模n的增大，次數(shù)T(n)的增長較慢的算法為最優(yōu)算法。常見時間復雜度從小到大依次排列：O(1) < O(log2n) < O(n) < O(n2）<O(n3) ····<O(n!)
時間復雜度的計算方法
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，那么我們就去掉于這個項相乘的常數(shù)。比如3n^2 我們?nèi)?n^2
讓我們看一下代碼：
/* 1\. 常數(shù)階時間復雜度計算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
intsum =0; //執(zhí)行1次
sum = (1+n)*n/2; //執(zhí)行1次
printf("testSum1:%d\n",sum);//執(zhí)行1次
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
inti,sum =0; //執(zhí)行1次
for(i =1; i <= n; i++) { //執(zhí)行n+1次
sum += i; //執(zhí)行n次
}
printf("testSum3:%d\n",sum); //執(zhí)行1次
}
//x=x+1; 執(zhí)行n*n次 ->O(n^2)
void add3(int x,int n){
for(inti =0; i< n; i++) {
for(intj =0; j < n ; j++) {
x=x+1;
}
}
}
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
intcount =1; //執(zhí)行1次
//n = 10
while(count < n) {
count = count *2;
}
}
1.7 空間復雜度
空間復雜度（space complexity）作為算法所需存儲空間的量度，記做S(n) = O (f(n))。其中，n為問題的規(guī)模；f（n）為語句關(guān)于n的所占存儲空間的函數(shù)。
一般情況下，一個程序在機器上運行時，除了需要存儲程序本身的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要存儲對數(shù)據(jù)操作的存儲單位。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，這樣只需要分析該算法在實現(xiàn)時所需的輔助單元即可。若算法執(zhí)行時所需的輔助空間相對于輸入數(shù)據(jù)量而言是個常量，則稱此算法為原地工作，空間復雜度為O(1)。
int n=5;
int a[10]={1,2,3,4,5,6,7,8,9,10};
//算法實現(xiàn)(1)
int temp;
for(int i=0;i <n/2;i++)
{
temp=a[I];
a[i]=a[n-i-1];
a[n-i-1]=temp;
}
以上例子只需要用到輔助空間temp，所以空間復雜度為O(1)
int b[10]={0};
for(inti=0;i<n;i++)
{
b[i]=a[n-i-1];
}
for(inti=0;i<n;i++)
{
a[i]=b[I];
}
這個例子中需要用到b(n）的輔助空間，所以空間復雜度為O(n)
