第二章 線性結(jié)構(gòu)

2.1 線性表（list）

• 數(shù)據(jù)對(duì)象集：線性表是n（≥0）個(gè)元素構(gòu)成的有序序列（）

• 操作集：線性表L

  1. 初始化空
  2. 根據(jù)位序k查找值
  3. 查找元素x第一次出現(xiàn)的位置
  4. 刪除指定位序的元素
  5. 返回線性表長(zhǎng)度

• 主要操作代碼實(shí)現(xiàn)(順序存儲(chǔ))

  • 初始化

  • 查找

  • 插入

  • 刪除

• 鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

  • 初始化

  • 查找

  • 插入

  • 刪除

• 廣義表

  • 線性表的一種推廣，在線性表中，n個(gè)基本元素都是基本的單元素；但是在廣義表中，元素不僅可以是單元素也可以是另一個(gè)廣義表。
    • 問(wèn)題：有時(shí)候一個(gè)域是一個(gè)不能分解的單元，也有可能是一個(gè)指針。
    • C語(yǔ)言中可以用union解決，union可以把不同類(lèi)型的數(shù)據(jù)組合在一起，不同類(lèi)型的類(lèi)型共用一處空間，另外再使用標(biāo)記去區(qū)分。

• 多重鏈表

  • 多重鏈表中節(jié)點(diǎn)可能同時(shí)隸屬于多個(gè)鏈

    • 多重鏈表中節(jié)點(diǎn)的指針域會(huì)有多個(gè)，但是一個(gè)鏈表包含多個(gè)指針不一定是多重鏈表（比如雙向鏈表，但其實(shí)該鏈表串聯(lián)起來(lái)的鏈表實(shí)際上是同一個(gè)，只不過(guò)是指向了鏈表的不同方向。）

  • 用途：

    • 樹(shù)和圖等相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都可以采用多重鏈表的方式實(shí)現(xiàn)存儲(chǔ)。

    • 栗子1：矩陣存儲(chǔ)

    • 用二維數(shù)組方式存儲(chǔ)

    • 缺點(diǎn)：數(shù)組大小需要事先確定，稀疏矩陣會(huì)造成大量空間浪費(fèi)

    • 方法

    • 結(jié)點(diǎn)數(shù)據(jù)域：行坐標(biāo)Row、列坐標(biāo)Col、數(shù)值Value

    • 結(jié)點(diǎn)指針域：行指針（Right）、列指針（Down）、入口節(jié)點(diǎn)Term項(xiàng)

      
      
      多重鏈表.png
      
      
      多重鏈表存儲(chǔ)節(jié)點(diǎn)統(tǒng)一表示.png

2.2 堆棧（Stack）

• 堆棧是一種線性結(jié)構(gòu)，也是一個(gè)特殊的線性表
• 常見(jiàn)用途：函數(shù)調(diào)用、遞歸、（表達(dá)式求值）、深度優(yōu)先搜索、回溯算法

栗子2：算數(shù)表達(dá)式求值

• 兩類(lèi)對(duì)象
  • 運(yùn)算數(shù)
  • 運(yùn)算符號(hào)
• 不同運(yùn)算符號(hào)優(yōu)先級(jí)不一樣
• 前綴、中綴、后綴表達(dá)式
  • 后綴表達(dá)式求值策略：從左向右掃描，逐個(gè)處理運(yùn)算數(shù)和運(yùn)算符號(hào)
    • 要求：1 順序存儲(chǔ)結(jié)構(gòu)（存儲(chǔ)運(yùn)算數(shù)） 2 返回最后存儲(chǔ)兩個(gè)運(yùn)算數(shù)

• 堆棧：具有一定操作約束的線性表
  • 只能在一端（棧頂，Top）做插入、刪除
  • 插入數(shù)據(jù)：入棧（Pus）
  • 刪除數(shù)據(jù)：出棧（Remove）
  • 后入先出：LIFO
• 堆棧抽象數(shù)據(jù)類(lèi)型描述
  • 數(shù)據(jù)對(duì)象集：一個(gè)由0個(gè)或者多個(gè)元素的有窮線性表
  • 操作集：長(zhǎng)度為MaxSize的堆棧SStack,堆棧元素itemElementType
    1. 初始化（生成空堆棧，最大長(zhǎng)度為MaxSize）
    2. 判斷滿(mǎn)棧
    3. 插入
    4. 判斷空棧
    5. 刪除
• 棧的順序存儲(chǔ)實(shí)現(xiàn)
  • 棧的順序結(jié)構(gòu)通常是由一個(gè)一維數(shù)組和一個(gè)記錄棧頂元素位置的變量組成

• 堆棧的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
  • 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)際上是一個(gè)單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進(jìn)行。

2.3 隊(duì)列(Queue)

• 隊(duì)列也是一種受限的線性表

• 插入和刪除操作：只能在一端插入，而在另一端刪除。

• 先入先出：FIFO

• 隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)

  • 用一維數(shù)組和一個(gè)記錄隊(duì)列頭元素位置的變量front以及記錄隊(duì)尾位置的變量rear組成
  • 循環(huán)隊(duì)列，形成一個(gè)環(huán)
  • 循環(huán)隊(duì)列.png

• 鏈?zhǔn)酱鎯?chǔ)

  • 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以用單鏈表實(shí)現(xiàn)。插入和刪除操作分別在鏈表兩頭，front要做刪除操作，在表頭。rear做插入操作，在表尾。