簡介
- 參考書籍：
- 數(shù)據(jù)結(jié)構(gòu) Java語言描述第二版
- 大話數(shù)據(jù)結(jié)構(gòu)
- 參考資料
- 算法可視化工具
- 學(xué)習(xí)的內(nèi)容
- 時(shí)間復(fù)雜度
- 線性表的學(xué)習(xí)
- 棧與隊(duì)列學(xué)習(xí)
- 串與數(shù)組
- 樹與二叉樹的學(xué)習(xí)
- 圖的學(xué)習(xí)
- 排序
- 查找
一忍啤、基本概念和術(shù)語
1. 數(shù)據(jù)(Data)
- 數(shù)據(jù)是信息的載體膝但，是對客觀事物的符號(hào)表示，能夠被計(jì)算機(jī)程序識(shí)別，儲(chǔ)存鲫骗、加工和處理
- 數(shù)據(jù)還包括圖像聲音等非數(shù)值數(shù)據(jù)
2. 數(shù)據(jù)元素（Data Element）
- 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素薇缅、結(jié)點(diǎn)瞬矩、頂點(diǎn)、記錄炼杖。
3. 數(shù)據(jù)項(xiàng)（Data Item）
- 一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段灭返、域、屬性）組成坤邪。
- 數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位熙含。
4. 數(shù)據(jù)對象（Data Object）
- 是相同數(shù)據(jù)元素組成的集合
5. 數(shù)據(jù)結(jié)構(gòu)（Data Structure）
一、含義：數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系艇纺，即數(shù)據(jù)的組織形式怎静。
二邮弹、數(shù)據(jù)結(jié)構(gòu)包括內(nèi)容
- 數(shù)據(jù)邏輯結(jié)構(gòu)(Logical Structure)
- 定義：
- 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)蚓聘，獨(dú)立于計(jì)算機(jī)腌乡。
- 邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。
- 數(shù)據(jù)的邏輯結(jié)構(gòu)是各個(gè)數(shù)據(jù)元素之間的邏輯關(guān)系
- 分類
- 線性結(jié)構(gòu)
- 非線性結(jié)構(gòu)
- 集合
- 樹形結(jié)構(gòu)
- 圖形結(jié)構(gòu)
- 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（Storage Structure）
- 定義：
- 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示或粮，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（Storage Structure）导饲；
- 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱為映象），它依賴于計(jì)算機(jī)語言氯材。
- 對機(jī)器語言而言渣锦，存儲(chǔ)結(jié)構(gòu)是具體的。一般氢哮，只在高級(jí)語言的層次上討論存儲(chǔ)結(jié)構(gòu)袋毙。
- 儲(chǔ)存方式：
- 順序儲(chǔ)存方式
- 鏈?zhǔn)絻?chǔ)存方式
- 索引儲(chǔ)存方式
- 散列儲(chǔ)存（哈希儲(chǔ)存）方式
- 數(shù)據(jù)的操作
- 定義：
- 數(shù)據(jù)操作就是對數(shù)據(jù)進(jìn)行某種方法的處理，也稱數(shù)據(jù)運(yùn)算
- 數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上冗尤，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合听盖。
- 最常用的檢索、插入裂七、刪除皆看、更新、排序等運(yùn)算實(shí)際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作背零。
二腰吟、算法與算法分析
1. 算法：
- 定義： 對特殊問題進(jìn)行求解步驟的一種描述
- 性質(zhì)：
- 有窮性
- 有限性
- 有效性
- 輸入
- 輸出
- 目標(biāo)：
- 正確性
- 可讀性
- 健壯性
- 高效性(時(shí)間和空間)
- 時(shí)間復(fù)雜度分析
- 算法執(zhí)行時(shí)間： 指令序列(i)的執(zhí)行次數(shù)和 * 指令序列(i)執(zhí)行時(shí)間
- 空間復(fù)雜度分析
- 表示：S(n) = O(f(n))
- 固定空間需求(Fix space requiremnet): 程序代碼、常量徙瓶、變量所占空間毛雇，與處理問題規(guī)模無關(guān)
- 可變空間需求(Variable space requirement): 輸入數(shù)據(jù)元素和程序運(yùn)行所占的空間，與處理問題規(guī)模相關(guān)
