1數(shù)據(jù)結(jié)構(gòu)緒論

概念和術(shù)語：

• 數(shù)據(jù)：是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合。數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值類型，還包括字符及聲音、圖像、視頻等非數(shù)值類型。
• 數(shù)據(jù)元素：是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理。比如在人類中，人就是數(shù)據(jù)元素
• 數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。人都有姓名、生日、性別等相同的數(shù)據(jù)項(xiàng)
• 數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。
• 數(shù)據(jù)結(jié)構(gòu)： 結(jié)構(gòu)是指各個(gè)組成部分相互搭配和排列的方式。結(jié)構(gòu)就是關(guān)系，比如分子結(jié)構(gòu)，就是說組成分子的原子之間的排列方式

邏輯結(jié)構(gòu)：

• 集合結(jié)構(gòu)
• 線性結(jié)構(gòu)
• 樹形結(jié)構(gòu)
• 圖形結(jié)構(gòu)

image.png

2 算法

算法效率的度量方法：

• 事前分析估算方法：大O時(shí)間復(fù)雜度分析
• 事后統(tǒng)計(jì)方法：批量數(shù)據(jù)測試

常見的時(shí)間復(fù)雜度：

• 常數(shù)階 O(n)
• 對(duì)數(shù)階 O(logn)
• 線性階 O(n)
• 常數(shù)對(duì)數(shù)階（n * logn）
• 平方階 O(n^2)
• O(2^n)
• O(n!)
• O(n^n)

3 線性表

image.png

4 棧與隊(duì)列

• 順序棧
• 兩棧共享存儲(chǔ)空間
• 鏈棧

棧的應(yīng)用：

• 遞歸
• 四則運(yùn)算表達(dá)式求值
  • 后綴表達(dá)式
  • 中綴表達(dá)式