資料結構的介紹
1.資料的分類：
1.資料項：資料的最小單位，具有原子性
2.資料元素：資料的基本單位，由若干個資料項組成，計算機通常將其當成一個整體處理
3.資料物件：是由性質相同的資料源的集合，是資料的子集
4.資料：描述客觀事物的數值、字符以及能輸入機器且能被處理的各種符號集合
2.資料結構：是帶有結構特性的資料元素的集合，它研究的是資料的邏輯結構和資料的物理結構以及它們之間的相互關系，
并對這種結構定義相適應的運算，設計出相應的演算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構型別，
資料結構=邏輯結構+物理結構+操作
邏輯結構：線性結構(線性表，堆疊佇列，串和陣列)，非線性結構(集合，樹，圖)
物理結構：順序存盤，鏈式存盤，索引存盤，散列存盤
操作：檢索，排序，插入，洗掉，修改等
3.邏輯結構和物理結構
1.邏輯結構：資料元素之間的邏輯關系，與實作無關
1.集合結構：數學集合，具有：確定性，唯一性，無序性
2.線性結構：有且只有一個開始結點和一個終端結點，并且每個結點最多只有一個前驅結點，最多只有一個后繼結點
3.非線性結構：一個結點元素可能對應多個直接前驅和多個直接后繼
線性結構是一對一的關系，集合無關系，樹為一對多的關系，圖為多對多的關系
主要為線性結構和樹結構
2.物理結構(存盤結構)：資料的存盤結構主要包括資料元素本身的存盤以及資料元素之間關系表示，是資料的邏輯結構在計算機中的表示，
1.順序存盤：把邏輯上相鄰的節點存盤在物理位置上相鄰的存盤單元中，結點之間的邏輯關系由存盤單元的鄰接關系來體現，
由此得到的存盤結構為順序存盤結構，通常順序存盤結構是借助于計算機程式設計語言（例如C/C++）的陣列來描述的，
（資料元素的存盤對應于一塊連續的存盤空間，資料元素之間的前驅和后續關系通過資料元素，在存盤器中的相對位置來反映）
優點：
1、節省存盤空間，因為分配給資料的存盤單元全用存放結點的資料（不考慮c/c++語言中陣列需指定大小的情況），結點之間的邏輯關系沒有占用額外的存盤空間，
2、采用這種方法時，可實作對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存盤地址，
缺點：
1、插入和洗掉操作需要移動元素，效率較低，
2、必須提前分配固定數量的空間，如果存盤元素少，可能導致空閑浪費，
2.鏈式存盤：資料元素的存盤對應的是不連續的存盤空間，每個存盤節點對應一個需要存盤的資料元素，每個結點是由資料域和指標域組成，
元素之間的邏輯關系通過存盤節點之間的鏈接關系反映出來，邏輯上相鄰的節點物理上不必相鄰，
缺點：
1、比順序存盤結構的存盤密度小 (每個節點都由資料域和指標域組成，所以相同空間內假設全存滿的話順序比鏈式存盤更多)，
2、查找結點時鏈式存盤要比順序存盤慢，
優點：
1、插入、洗掉靈活 (不必移動節點，只要改變節點中的指標)，
2、有元素才會分配結點空間，不會有閑置的結點，
3.索引存盤：除建立存盤結點資訊外，還建立附加的索引表來標識結點的地址
4.散列存盤：根據結點的關鍵字直接計算出該結點的存盤地址 HashSet HashMap
注：同一邏輯結構可以對應多種存盤結構
同樣的運算，在不同的存盤結構中，其實作程序是不同的
演算法的介紹
演算法：演算法是指令的集合，是為了解決特定問題而規定的一系列操作，它是明確定義的可計算程序，以一個資料集合作為輸入，并產生一個資料集合作為輸出，
特性：輸入性，輸出性，可行性，有窮性，確定性，
復雜度：評價演算法的優劣依據(時間復雜度和空間復雜度）
1.時間復雜度：執行演算法所需要的計算作業量
一個演算法花費的時間與演算法中陳述句的執行次數成正比例，哪個演算法中陳述句執行次數多，它花費時間就多，
一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，表示為T(n)，n表示問題的規模
但有時我們想知道它變化時呈現什么規律，想知道問題的規模，而不是具體的次數，此時引入時間復雜度，
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函式，用T(n)表示，
若有某個輔助函式f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函式，
記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度，
或者說：時間復雜度就是時間頻度去掉低階項和首項常數，
注：時間頻度與時間復雜度是不同的，時間頻度不同但時間復雜度可能相同，
例：某兩個演算法的時間頻度是 T(n)= 100000n^2+10n+6 T(n) = 10n^2+10n+6 T(n) = n^2 但是時間復雜度都是 T（n） = O（n2）
最壞時間復雜度和平均時間復雜度
1.最壞情況下的時間復雜度稱最壞時間復雜度，一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度，
這樣做的原因是：最壞情況下的時間復雜度是演算法在任何輸入實體上運行時間的上界，這就保證了演算法的運行時間不會比任何更長，
在最壞情況下的時間復雜度為T(n)=O(n)，它表示對于任何輸入實體,該演算法的運行時間不可能大于O(n)，
2.平均時間復雜度是指所有可能的輸入實體均以等概率出現的情況下，演算法的期望運行時間，
第一，難計算
第二，有很多演算法的平均情況和最差情況的復雜度是一樣的，
時間復雜度的計算
根本沒有必要計算時間頻度，即使計算處理還要忽略常量、低次冪和最高次冪的系數，所以可以采用如下簡單方法：
⑴ 找出演算法中的基本陳述句； 演算法中執行次數最多的那條陳述句就是基本陳述句，通常是最內層回圈的回圈體，
⑵ 計算基本陳述句的執行次數的數量級；只需計算基本陳述句執行次數的數量級，這就意味著只要保證基本陳述句執行次數的函式中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數，
這樣能夠簡化演算法分析，并且使注意力集中在最重要的一點上：增長率，
⑶ 用大Ο記號表示演算法的時間性能， 將基本陳述句執行次數的數量級放入大Ο記號中，
常用時間復雜度的數量級：常數階O(1) ，對數階O(log2n)，線性階O(n)，線性對數階O(n*log2n)，平方階O(n2) ，立方階O(n3)......
例：
時間復雜度為O(1)，
int count=0;
時間復雜度為O(log2 n)
int n=8, count=0;
for (int i=1; i<=n; i*=2)
count++;
時間復雜度為O(n)，
int n=8, count=0;
for (int i=1; i<=n; i++)
count++;
時間復雜度為O(n2)
int n=8, count=0;
for (int i=1; i<=100n; i++)
for (int j=1; j<=10n; j++)
count++;
時間復雜度為O(nlog2n)
int n=8, count=0;
for (int i=1; i<=n; i*=2)
for (int j=1; j<=n; j++)
count++;
時間復雜度為O(n2)
int n=8, count=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=i; j++)
count++;
2.空間復雜度：執行這個演算法所需要的記憶體空間
演算法的存盤量包括:
1．程式本身所占空間
2．輸入資料所占空間
3．輔助變數所占空間
輸入資料所占空間只取決于問題本身，和演算法無關，則只需要分析除輸入和程式之外的輔助變數所占額外空間，
空間復雜度是對一個演算法在運行程序中臨時占用的存盤空間大小的量度，一般也作為問題規模n的函式，以數量級形式給出，記作：S(n) = O(g(n))
空間復雜度分析1：
int fun(int n){
int i，j，k，s;
s=0;
for (i=0;i<=n;i++)
for (j=0;j<=i;j++)
for (k=0;k<=j;k++)
s++;
return(s);
}
由于演算法中臨時變數的個數與問題規模n無關，所以空間復雜度均為S(n)=O(1)，
空間復雜度分析2：
void fun(int a[]，int n，int k)
//陣列a共有n個元素
{ int i;
if (k==n-1)
for (i=0;i<n;i++)
printf(“%d\n”，a[i]); //執行n次
else
{ for (i=k;i<n;i++)
a[i]=a[i]+i*i; //執行n-k次
fun(a，n，k+1);
}
}
此屬于遞回演算法，每次呼叫本身都要分配空間，fun(a,n,0)的空間復雜度為O(n)，
注意：
1.空間復雜度相比時間復雜度分析要少
2.對于遞回演算法來說，代碼一般都比較簡短，演算法本身所占用的存盤空間較少，但運行時需要占用較多的臨時作業單元；
若寫成非遞回演算法，代碼一般可能比較長，演算法本身占用的存盤空間較多，但運行時將可能需要較少的存盤單元，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144278.html
標籤：其他