?2016-2026 Matools All rights reserved,
粵ICP備17059708號
數(shù)據(jù)結(jié)構(gòu)小白入門
數(shù)據(jù)結(jié)構(gòu)指一組相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,
當(dāng)我們需要在計算機中存儲這些數(shù)據(jù)時,還涉及到數(shù)據(jù)的,組織方式,在計算機中的存儲方式,以及定義在該數(shù)據(jù)上的一組操作;
* 一組數(shù)據(jù)相互之間有某種關(guān)系
* 組織方式
* 存儲方式
* 以及可對其進行的一組操作 理解:
我們學(xué)習(xí)的最終目的是要在計算機中存儲一組數(shù)據(jù),但是不得不先考慮數(shù)據(jù)的組織方式,在計算機中的存儲方式,以及可以對這些數(shù)據(jù)進行的一組操作
,當(dāng)然了既然是一組數(shù)據(jù)必然表明了這寫數(shù)據(jù)之間是存在想換的關(guān)聯(lián)關(guān)系的;關(guān)系可能還會有多種;
例如:
一組數(shù)據(jù):12345
組織方式:從小到大
存儲方式:可使用線性存儲結(jié)構(gòu)
操作:要取出最大的一個
數(shù)據(jù)結(jié)構(gòu)研究方向
問題:
* 機外處理
* 處理要求
建模:
* 邏輯結(jié)構(gòu)
* 基本運算
實現(xiàn):
* 存儲結(jié)構(gòu)
* 算法
基本術(shù)語
數(shù)據(jù)(Data):
? 所有能被計算機處理的符號的集合
數(shù)據(jù)元素(DataElement):
? 是數(shù)據(jù)集合中的一個 個體,即數(shù)據(jù)的基本單位
數(shù)據(jù)項(DataItem):
? 數(shù)據(jù)元素常?？煞譃槿舾蓚€數(shù)據(jù)項,數(shù)據(jù)項是數(shù)據(jù)具有意義的最小單位
組織數(shù)據(jù)的三個層次:
數(shù)據(jù)(表)->數(shù)據(jù)元素(行)->數(shù)據(jù)項(字段)
實際問題中的數(shù)據(jù)成為原始數(shù)據(jù)
邏輯結(jié)構(gòu)(LogicalStructure)
? 數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系,如從小到大/一對一/一對多
物理結(jié)構(gòu)(PhysicalStructure)
? 也會叫做存儲結(jié)構(gòu),指數(shù)據(jù)在計算機內(nèi)的表示,邏輯結(jié)構(gòu)在計算機中的具體實現(xiàn)
邏輯結(jié)構(gòu)
常見的邏輯結(jié)構(gòu)如下:
集合:
數(shù)據(jù)元素屬于同一個集合,表示為R{}; 數(shù)據(jù)之間不存在特定關(guān)系
組織結(jié)構(gòu)松散,任意兩節(jié)點之間都沒有鄰接關(guān)系
線性:
除了起始節(jié)點d1和終端階段dn外,每個節(jié)點都有一個前驅(qū)和一個后繼,表示為R={d1,d2...dn},數(shù)據(jù)之間存在前后順序關(guān)系
各節(jié)點按邏輯關(guān)系排列,形成一條'鏈'
樹狀:
每個元素最多有一個前驅(qū),可以有多個后繼,表示為(D,{R}),就像一個樹干長了多個樹枝
具備分支,層次特性,上層節(jié)點可以和下層多個節(jié)點相鄰接,但是下層節(jié)點只能和一個上層節(jié)點鄰接
圖狀:
任何兩個元素之間都可以相鄰接,表示為(D,{R})
注意:
邏輯結(jié)構(gòu)
*
與元素本身的形式,內(nèi)容,無關(guān)
*
元素的相對位置,無關(guān)
*
與包含的節(jié)點個數(shù),無關(guān)
存儲結(jié)構(gòu)
存儲結(jié)構(gòu)由 存儲節(jié)點(每個存儲節(jié)點存放一個數(shù)據(jù)元素) 和 節(jié)點之間的邏輯關(guān)系共同組成
反過來說,一個完整的存儲結(jié)構(gòu)必須可以存儲數(shù)據(jù)元素,以及元素之間的邏輯關(guān)系
存儲結(jié)構(gòu)分類 (缺圖)
*
順序存儲
使用索引(相對起始位置)來表示數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)被存儲在一組連續(xù)的存儲單元中
特點:
* 需預(yù)先分配長度,
* 插入和刪除慢,需要移動其他元素
* 存取數(shù)據(jù)快捷,屬于隨機存儲結(jié)構(gòu)(可通過索引直接訪問任意位置數(shù)據(jù))
*
鏈?zhǔn)酱鎯?br>
借助元素地址指針表示數(shù)據(jù)的邏輯結(jié)構(gòu),每個元素都會包含指向下一個元素的指針
這種結(jié)構(gòu)需要在節(jié)點上附加一個指針項,指出后繼節(jié)點的位置,即每個節(jié)點存儲單元包含兩個部分:[數(shù)據(jù)項,指針項]
特點:
* 動態(tài)分配內(nèi)容,不需要預(yù)先分配內(nèi)存
* 插入刪除快捷,不需要移動其他元素
* 非隨機存取結(jié)構(gòu)(獲取數(shù)據(jù)必須遍歷前面的所有節(jié)點)
*
索引存儲(Map是否屬于索引結(jié)構(gòu) 很疑惑?)
借助索引表來指示數(shù)據(jù)元素的存儲位置
索引表中包含了所有數(shù)據(jù)元素的地址,查詢索引表能夠快速的定位到需要的數(shù)據(jù)
特點:
* 索引是一份獨立于實際存放數(shù)據(jù),的數(shù)據(jù)結(jié)構(gòu)(就像書的目錄都在正文前面)
* 索引需要占用額外的存儲空間
* 當(dāng)實際數(shù)據(jù)發(fā)生改變時需要重建索引
* 查詢數(shù)據(jù)快
* 插入修改,刪除慢
*
散列存儲(哈希表)
通過散列函數(shù)計算得出元素的位置
特點:
* 在散列函數(shù)不變時,相同數(shù)據(jù)會得出相同的位置
* 存入順序和取出順序通常不一致
* 無法完成隨機存取(指定獲取某個元素)
順序和鏈?zhǔn)绞亲罨镜囊彩亲畛Ｓ玫拇鎯Y(jié)構(gòu),需要重點掌握,包括各自的優(yōu)缺點,使用場景等
鏈?zhǔn)酱鎯Y(jié)構(gòu)可實現(xiàn)樹結(jié)構(gòu)(邏輯結(jié)構(gòu))
運算
運算指的是某種邏輯結(jié)構(gòu)上可以進行的操作;
運算分為兩類:
*
加工型運算
會改變原邏輯結(jié)構(gòu)的內(nèi)容,順序,個數(shù)等的操作
*
引用型運行
與加工型運算相反
常見運算:
建立,查找,讀取,插入,刪除
加工型:建立,插入,刪除
引用型:讀取,查找
算法
算法字面意思,計算方法;
算法規(guī)定了求解給定類型問題所需的所有處理步驟以及執(zhí)行順序
,使得問題能在有限時間內(nèi)機械的求解,一個算法就是對特定問題求解步驟的一種描述,再具體一點,算法是一段有窮的指令序列;算法必須能使用某種語言描述;
例如:
計算1到5的和
,這個需求,如何來實現(xiàn),第一步做什么,第二步做什么,整個計算步驟和執(zhí)行順序統(tǒng)稱為算法,如果最終能夠在有限的步驟下求出正確的和,那這就是一個合格的算法;
算法的特點:
*
有窮性
算法必須在執(zhí)行有窮步后結(jié)束
*
確定性
算法的每一個步驟都必須是明確定義的,
*
可行性
算法中的每一步都是可以通過已實現(xiàn)的操作來完成的
*
輸入
一個算法具備0或多個輸入
*
輸出
一個算法有一個或多個輸出,它們與輸入有著特定的關(guān)系
算法與程序的區(qū)別,算法只是一種描述,可以使用任何語言,但是通常不能直接被計算機運行,而程序則是算法的具體實現(xiàn),使用某種計算機語言;
算法設(shè)計應(yīng)滿足的要求
*
正確性:對于合法的輸入產(chǎn)生符合要求的輸出
*
易讀性:算法應(yīng)該盡可能易讀,便于交流,這也是保證正確性的前提(注釋可提高易讀性)
*
健壯性:當(dāng)輸入非法數(shù)據(jù)時,算法可作出適當(dāng)反應(yīng)而不至于崩潰(例如輸出錯誤原因);
*
時空性:指的是算法的時間復(fù)雜度和空間復(fù)雜度,算法分析主要也是分析算法的時間復(fù)雜度和空間復(fù)雜的,其目的是提高算法的效率;
算法分析
解決同一問題的算法可能有多種,我們希望從中選出最優(yōu)的算法,效率高的,占用空間小的,為此我們就需要對算法進行評估和分析;
通常評估算法根據(jù)兩個度量
*
時間復(fù)雜度:算法運行完成所需的總步數(shù)(標(biāo)準(zhǔn)操作),通常是問題規(guī)模的函數(shù)
*
空間復(fù)雜度:算法執(zhí)行時所占用的存儲空間,通常是問題規(guī)模的函數(shù)
確定算法的計算量
* 合理選擇一種或幾種操作作為'標(biāo)準(zhǔn)操作',無特殊說明默認以賦值操作作為標(biāo)準(zhǔn)操作;
* 確定算法共執(zhí)行多少次標(biāo)準(zhǔn)操作,并將此次數(shù)規(guī)定為算法的計算量
* 以算法在所有時輸入下的計算量最大值作為算法的最壞情況時間復(fù)雜度
* 以算法在所有時輸入下的計算量最小值作為算法的最好情況時間復(fù)雜度
* 以算法在所有時輸入下的計算量平均值作為算法的平均情況時間復(fù)雜度
* 最壞/平均情況時間復(fù)雜度都可作為時間復(fù)雜度,通常以最壞情況衡量;
注意:時間復(fù)雜度通常以量級來衡量,也就是說不需要精確的計算到底執(zhí)行了幾步,而是得出其計算量的數(shù)量級即可,并忽略常數(shù),因為當(dāng)數(shù)量級足夠大時,常數(shù)對于計算量的影響可以忽略不計;
如: (n-1)(n-2) 數(shù)量級為 n^2
時間復(fù)雜度使用大O表示,如O(1)
案例:
1.
void aFunction(){ int c = 10 + 20; int d = c * c; printf(d); }
上列算法若以賦值運算作為標(biāo)準(zhǔn)操作,則該算法的計算量為2,其時間復(fù)雜度記為O(1),為什么是O(1)呢,是因為2是一個常數(shù),常數(shù)對于函數(shù)的增長影響并不大,所以計算量為常數(shù)時表示為O(1),按照這種方式,即使計算量為2000,同樣記為O(1),稱為
常數(shù)
2.
void bFunction(int n){ for(int i = 0;i < n;i++){ // n int c = 2 * i;// 1 int d
= 3 * i;// 2 } }
此時函數(shù)的循環(huán)次數(shù)由未知數(shù)n來決定,循環(huán)體內(nèi)計算量為2,當(dāng)n是一個自然數(shù)時,函數(shù)的計算量等于(n)(2),此時時間復(fù)雜度為O(n),無論用常數(shù)2
對n進行加減乘除對于n的指數(shù)都沒有影響,當(dāng)n足夠大時,內(nèi)部的2次計算量可以忽略,所以記為O(n),稱為線性階
更粗陋的度量方法是函數(shù)體包含一層循環(huán)時記為O(n)
3.
void bFunction(int n){ for(int i = 0;i < n;i++){ for(int j = 0;j < i;j++){ } }
}
外層循環(huán)次數(shù)為n,內(nèi)層循環(huán)次數(shù)隨著n的增長而增長且最大值為n-1次,那么整個函數(shù)的計算量為(n)(n-1),常數(shù)可以忽略,所以時間復(fù)雜度記為O(n^2)
,稱為平方階
粗陋的方法是有兩層嵌套循環(huán),且循環(huán)次數(shù)都隨著n的增長而增長,所以是O(n^2),以此類推,但是要注意下面這種情況
4.
void bFunction(int n){ for(int i = 0;i < n;i++){ for(int j = 0;j < 3;j++){ } }
}
此時內(nèi)層循環(huán)的循環(huán)次數(shù)是固定(常數(shù))所以不會影響計算量的數(shù)量級,時間復(fù)雜度記為O(n)
5.
void bFunction(int n){ for(int i = 3;i < n;){ i *= 3; } }
此時函循環(huán)次數(shù)會隨著3循環(huán)體中的常數(shù)3的的變化而變化,我們可以用對數(shù)來表示,
假設(shè)循環(huán)次數(shù)為s,循環(huán)條件可表示為 s = 3^s < n;(即i本身為3,其次冪會不斷的增長,但結(jié)果要小于n)
當(dāng)然這里有個條件是i的初值必須和每次乘等的值相同,形成次冪的增長;
用對數(shù)表示為s = log3n,時間復(fù)雜度記為O(log3n),常數(shù)可以忽略,所以最后是O(logn)稱之為對數(shù)階
對數(shù)階的數(shù)量級小于線性階,因為若n的值相同,對數(shù)階計算量必然小于線性階
6.
void bFunction(int n){ for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){
for(int k = 0;k < n;k++){ } } } }
上述算法時間復(fù)雜度為O(n^3),3為常數(shù),對應(yīng)著循環(huán)的嵌套層數(shù);也可以用O(n^C)表示,稱為多項式階
7.
void bFunction(int n){ int num = 2; for(int i = 0;i < n;){ //O(n) num *= 2; }
for (int j = 0;j<num;j++){ //O(n) } }
上述函數(shù)輸入的參數(shù)n將作為循環(huán)次數(shù)的指數(shù),假設(shè)循環(huán)次數(shù)為s, s = 2^n,那么時間復(fù)雜度為O(2^n),
稱之為指數(shù)階,可記為O(C^n)
8.
void bFunction(int n) { for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ } }
for(int i=0;i<n;i++){ } }
對于順序運行的算法,總時間復(fù)雜度等于算法中最大時間復(fù)雜度,即O(n^2)
9.
void bFunction(int n) { if(n % 2 ==0){ for(int i=0;i<n;i++){ for(int
j=0;j<n;j++){ } } }else{ for(int i=0;i<n;i++){ } } }
對于具備分支結(jié)構(gòu)的算法,總時間復(fù)雜度等于算法中時間復(fù)雜度最大路徑的復(fù)雜度,即O(n^2)
時間復(fù)雜度大小順序
常數(shù) < 對數(shù)階 < 線性階 < 平方階 < 多項式階 < 指數(shù)階
O(1) < O(logn) < O(n) < O(n^2) < O(n^C) < O(C^n)
優(yōu)劣:
通常具有常數(shù)階復(fù)雜度的算法是好的算法
具有指數(shù)階復(fù)雜度的算法是差的算法
個人觀點,若有錯誤敬請指出,謝謝!
熱門工具 換一換