當(dāng)前位置：首頁 > 嵌入式培訓(xùn) > 嵌入式學(xué)習(xí) > 學(xué)習(xí)筆記 > 數(shù)據(jù)結(jié)構(gòu)基本知識點總結(jié)，比較全面
數(shù)據(jù)結(jié)構(gòu)基本知識點總結(jié)，比較全面
時間：2018-08-21 來源：未知
基本概念
1、數(shù)據(jù)：即信息的載體，能夠輸入到計算機(jī)當(dāng)中，能被計算機(jī)識別，存儲和處理的符號的總稱。
2、數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，又稱之為記錄。3、數(shù)據(jù)項：數(shù)據(jù)元素是由多個數(shù)據(jù)項組成的。4、結(jié)構(gòu)：
邏輯結(jié)構(gòu)：
集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了同屬于一個集合外，沒有其他任何關(guān)系線性結(jié)構(gòu)：數(shù)據(jù)元素具有一對一的關(guān)系⭐
樹形結(jié)構(gòu)：數(shù)據(jù)元素具有一對多的關(guān)系
圖形結(jié)構(gòu)：數(shù)據(jù)元素具有多對多的關(guān)系
存儲結(jié)構(gòu)(物理結(jié)構(gòu))：
順序存儲結(jié)構(gòu)：數(shù)據(jù)元素存儲在連續(xù)分配的地址空間當(dāng)中
鏈?zhǔn)酱鎯Y(jié)構(gòu)：數(shù)據(jù)元素可以存儲在任意合法的地址空間當(dāng)中，地址空間可以連續(xù)也可以不連續(xù)
索引存儲結(jié)構(gòu)：存儲數(shù)據(jù)元素的同時，建立附加的索引表
散列存儲結(jié)構(gòu)(哈希)：根據(jù)key值和特定的函數(shù)計算出他的存儲位置(效率最
高)⭐
5、算法： 解決特定問題的步驟的描述
基本特性： 輸入，輸出，有窮型，確定性可行性
設(shè)計要求： 正確性，可讀性，健壯性，時間效率高，存儲量低
時間復(fù)雜度： 隨著輸入規(guī)模n的增加，算法的執(zhí)行時間的增長率和算法執(zhí)行次數(shù)的增長率保持一致，我們成為算法的漸進(jìn)時間復(fù)雜度，簡稱為算法的時間復(fù)雜度。
大O推導(dǎo)： 使用常數(shù)1去替代表達(dá)式中的常數(shù)項;在修改后的表達(dá)式中，只保留最高階次項;如果最高階次項存在且不為1，我們?nèi)サ糇罡唠A次項的系數(shù)。
冒泡排序的大O推導(dǎo)為：平方級。線性表： 數(shù)據(jù)元素具有線性結(jié)構(gòu)(一對一)
順序表： 線性表的順序存儲結(jié)構(gòu)1、數(shù)據(jù)：即信息的載體，能夠輸入到計算機(jī)當(dāng)中，能被計算機(jī)識別，存儲和處理的符號的總稱。2、數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，又稱之為記錄。3、數(shù)據(jù)項：數(shù)據(jù)元素是由多個數(shù)據(jù)項組成的。
4、結(jié)構(gòu)：
邏輯結(jié)構(gòu)：
集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了同屬于一個集合外，沒有其他任何關(guān)系
線性結(jié)構(gòu)：數(shù)據(jù)元素具有一對一的關(guān)系⭐
樹形結(jié)構(gòu)：數(shù)據(jù)元素具有一對多的關(guān)系
圖形結(jié)構(gòu)：數(shù)據(jù)元素具有多對多的關(guān)系
存儲結(jié)構(gòu)(物理結(jié)構(gòu))：
順序存儲結(jié)構(gòu)：數(shù)據(jù)元素存儲在連續(xù)分配的地址空間當(dāng)中
鏈?zhǔn)酱鎯Y(jié)構(gòu)：數(shù)據(jù)元素可以存儲在任意合法的地址空間當(dāng)中，地址空間可以連續(xù)也可以不連續(xù)
索引存儲結(jié)構(gòu)：存儲數(shù)據(jù)元素的同時，建立附加的索引表
散列存儲結(jié)構(gòu)(哈希)：根據(jù)key值和特定的函數(shù)計算出他的存儲位置(效率最
高)⭐
5、算法： 解決特定問題的步驟的描述
基本特性： 輸入，輸出，有窮型，確定性可行性
設(shè)計要求： 正確性，可讀性，健壯性，時間效率高，存儲量低
時間復(fù)雜度： 隨著輸入規(guī)模n的增加，算法的執(zhí)行時間的增長率和算法執(zhí)行次數(shù)的增長率保持一致，我們成為算法的漸進(jìn)時間復(fù)雜度，簡稱為算法的時間復(fù)雜度。
空間復(fù)雜度：程序最大一次使用的空間大小
大O推導(dǎo)： 使用常數(shù)1去替代表達(dá)式中的常數(shù)項;在修改后的表達(dá)式中，只保留最高階次項;如果最高階次項存在且不為1，我們?nèi)サ糇罡唠A次項的系數(shù)。
冒泡排序的大O推導(dǎo)為：平方級。線性表： 數(shù)據(jù)元素具有線性結(jié)構(gòu)(一對一)順序表： 線性表的順序存儲結(jié)構(gòu)
