一、數(shù)據(jù)結構概念
1. 數(shù)據(jù)類型
（1）原子類型：其值不可再分的數(shù)據(jù)類型。
（2）結構類型：其值可以再分解成若干成分的數(shù)據(jù)類型。
（3）抽象數(shù)據(jù)類型：一個數(shù)學模型及定義在該數(shù)據(jù)模型上的一組操作。
2. 數(shù)據(jù)結構
數(shù)據(jù)結構是一組或多組存在特定關系的數(shù)據(jù)元素的集合。
（1）數(shù)據(jù)的邏輯結構
數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。
集合：結構中的數(shù)據(jù)元素除了同屬一個集合外，沒有任何關系。
線性結構：結構中的數(shù)據(jù)元素只存在一對一的關系。
樹形結構：結構中的數(shù)據(jù)元素存在一對多的關系。
網(wǎng)狀結構：結構中的數(shù)據(jù)元素存在多對多的關系。
（2）數(shù)據(jù)的存儲結構
存儲結構是指數(shù)據(jù)結構在計算機中的表示（映像、物理結構），包括數(shù)據(jù)元素的表示和關系的表示。
順序存儲：把邏輯上相鄰的元素放在物理位置也相鄰的存儲單元中，元素的關系可以由存儲單元的鄰接關系來體現(xiàn)，如數(shù)組。
優(yōu)點：可以通過索引直接訪問任何位置的元素，不需要從頭遍歷，且每個元素占用最少的存儲空間，不會有指針或鏈接信息占用額外空間。
缺點：只能使用相鄰的一整塊空間，會產(chǎn)生外部碎片。
鏈式存儲：存儲元素時借助指示元素位置的指針來表示元素之間的邏輯關系，不需要存儲單元物理位置相鄰，如List。
優(yōu)點：充分利用所有存儲單元，不會出現(xiàn)碎片。
缺點：每個元素存儲指針占用額外空間，且必須順序存取。
索引存儲：在存儲元素時附加索引表，索引項形式為 [關鍵字，地址]，常用于數(shù)據(jù)庫或文件系統(tǒng)。
優(yōu)點：檢索速度快。
缺點：索引表占用額外空間，增刪數(shù)據(jù)需要額外花時間修改索引表。
散列存儲：根據(jù)元素的關鍵詞找出元素的存儲地址（哈希存儲），如哈希表。
優(yōu)點：增刪查操作快。
缺點：哈希表占用額外的空間，有可能需要花時間處理哈希沖突。
二、算法
1. 算法特征
（1）有窮性：算法總在執(zhí)行有窮步之后結束，每一步都在有窮時間內(nèi)完成。
（2）確定性：算法每條指令有確切的含義，對于相同的輸入只能得出相同的輸出。
（3）可行性：算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次實現(xiàn)。
（4）輸入：算法有零個或多個輸入。
（5）輸出：算法有零個或多個輸出。
2. 算法效率的度量
（1）時間復雜度：算法中基本運算的執(zhí)行次數(shù)的數(shù)量級作為該算法的時間復雜度。
時間復雜度表示算法執(zhí)行所需的時間，它描述了算法的運行時間與輸入數(shù)據(jù)規(guī)模之間的關系。時間復雜度通常用大O表示法（Big O notation）來表示，形式為O(f(n))，其中f(n)是輸入數(shù)據(jù)規(guī)模n的函數(shù)。
常見的時間復雜度：
O(1)：常數(shù)時間復雜度，表示算法的執(zhí)行時間與輸入數(shù)據(jù)規(guī)模無關。
O(n)：線性時間復雜度，表示算法的執(zhí)行時間與輸入數(shù)據(jù)規(guī)模成正比。
O(n^2)：平方時間復雜度，表示算法的執(zhí)行時間與輸入數(shù)據(jù)規(guī)模的平方成正比。
O(log n)：對數(shù)時間復雜度，表示算法的執(zhí)行時間與輸入數(shù)據(jù)規(guī)模的對數(shù)成正比。
O(n log n)：線性對數(shù)時間復雜度，表示算法的執(zhí)行時間與輸入數(shù)據(jù)規(guī)模乘以其對數(shù)成正比。
（2）空間復雜度：該算法所需的存儲空間。
空間復雜度表示算法執(zhí)行所需的內(nèi)存空間，它描述了算法的存儲空間與輸入數(shù)據(jù)規(guī)模之間的關系?？臻g復雜度也通常用大O表示法來表示，形式為O(f(n))，其中f(n)是輸入數(shù)據(jù)規(guī)模n的函數(shù)。
常見的空間復雜度：
O(1)：常數(shù)空間復雜度，表示算法的存儲空間與輸入數(shù)據(jù)規(guī)模無關。
O(n)：線性空間復雜度，表示算法的存儲空間與輸入數(shù)據(jù)規(guī)模成正比。
O(n^2)：平方空間復雜度，表示算法的存儲空間與輸入數(shù)據(jù)規(guī)模的平方成正比
