文章目錄

• ​​資料結構三要素/邏輯結構和實體存儲結構/線性表與順序表連結清單/隊列與循環隊列​​

• ​​資料結構的内容(三要素)（outline)​​

• ​​關聯​​

• ​​邏輯結構​​

• ​​邏輯結構小結​​

• ​​實體結構(存儲結構)​​
• ​​線性表​​
• ​​循環隊列的長度​​

• ​​循環隊列滿判斷​​

資料結構三要素/邏輯結構和實體存儲結構/線性表與順序表連結清單/隊列與循環隊列

資料結構的内容(三要素)（outline)

• 邏輯結構
• 存儲結構
• 資料運算

關聯

• 資料的邏輯結構和存儲結構密不可分

• 另外,邏輯結構獨立于存儲結構;而存儲結建構立在邏輯結構上思考
• 對于一種資料存儲結構而言，必定有包括它的邏輯結構，
• 某一種邏輯結構在計算機語言中映射其存儲結構
• 相比于某一種邏輯結構和某一種資料結構,存儲結構關乎代碼結構,是更具體的

• 在計算機語言編寫代碼上就可以看出
• 給定一種資料結構

• 算法的設計取決于邏輯結構的標明
• 算法的實作取決于實體結構的采用

邏輯結構

• 指資料元素之間的邏輯關系,從邏輯關系上描述資料
• 它于資料的存儲結構無關,是獨立于計算機的
• 邏輯結構分為

• 線性結構(三大類)

• 一般線性表

• 它的實作方式(存儲方式)可以是

• 順序存儲,此時稱為​

  ​順序表​

  ​(存儲結構上順序表的方式是基于一片連續的實體位址)
• 鍊式存儲,此時稱為​

  ​連結清單​

  ​(存儲結構上連結清單并不連續)

• 但是,實作​

  ​連結清單​

  ​的存儲結構可以是順序存儲結構
• 不僅僅是鍊式存儲才能實作連結清單(隻是說,線性表的鍊式存儲實作的一定是連結清單)
• (比如靜态連結清單,基于資料組實作連結清單)

• (操作)受限線性表

• stack
• queue
• string

• 線性表的推廣

• array

• 線性結構經常可以由順序存儲結構實作，也可以由鍊式存儲實作

• 非線性結構

• 集合
• 樹形結構

• 一般樹
• 二叉樹

• 圖狀結構

• 有向圖
• 無向圖

邏輯結構小結

• 通過上面的分析可以知道,下面這些都還是屬于邏輯結構的範疇:

• 線性結構

• 線性表

• 棧
• 隊列

• ⛔注意,如果一個"名字"可以展現出存儲結構,那麼一般就認為他是具體的資料結構(預設包含了資料運算)

• 順序表:線性表的順序存儲
• 單連結清單:線性表的鍊式存儲
• 哈希表:非線性結構的散列存儲
• 循環隊列:線性結構邏輯結構(隊列)的順序存儲

• 非線性結構

• 集合
• 樹

• 二叉樹
• 一般樹

• 圖

• 有向圖
• 無線圖

實體結構(存儲結構)

• 資料結構在計算機中的表示
• 包括一下方面:

• 資料元素的表示
• 關系表示（存儲資料是，通常不僅僅存儲各資料元素的值，還要存儲資料元素之間的關系）

• 比如前驅、後繼

• 用計算機語言實作的邏輯結構(依賴于計算機語言)

• 具體的存儲結構主要有:

• 順序存儲

• 順序存儲也可以用來實作線性結構和非線性結構(比如:樹/圖)

• 鍊式存儲

• 注意，鍊式存儲設計的時候，各個不同結點的存儲空間可以不連續
• 但是結點内的存儲單元位址必須連續

• 索引
• 散列

線性表

• 棧,隊列,循環隊列這幾種資料結構都屬于線性表(邏輯結構)的範疇

• 它們既可以通過順序存儲來實作也可以通過鍊式存儲來實作

• 以隊列為例

• 隊列的順序存儲實作的可以稱為順序隊列

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SequentialQueue      

• 順序存儲的隊列基本缺點在于空間配置設定上不容易把握,(比如容易發生溢出或者空間使用率低下)
• 是以,基于順序存儲結構的這一缺點,改進出來​

  ​循環隊列​

  ​(任然基于順序存儲結構)實作的

• 循環隊列可以一定程度提高空間使用率以及降低溢出的發生
• 但是在鍊式存儲中,​

  ​循環隊列​

  ​就顯得多餘,應為鍊式存儲的靈活性,基本不用考慮溢出問題
• 而且對于操作受限的線性表而言,基本操作隻允許在端(隊列是兩端,棧隻有一端)操作,沒有随機通路棧内或者隊列内的某個元素的需求,鍊式存儲往往更加合适用來實作這類邏輯結構

• 隊列的鍊式存儲實作可以稱為鍊隊列

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;      

循環隊列的長度

• 我們設循環隊列的長度(隊列中存在的元素數量(實際有效長度))
• 為了友善計算,我們為循環隊列打了兩重下标,第二重開始的下标是虛拟的

• 第二重下标是第一重下标加上MaxSize後得到的(本例中MaxSize=8)

• 并且,隊列頭指針F總是沿着順時針的方向追趕隊尾指針R
• 我們允許R取得第二重下标,而F隻允許取第一重下标中的值

• 這樣,隊列的元素數量(實際長度)就可以表示為:

• 而實際上,我們知道隊列的元素長度是不會超過;
• 恰好地,我們有一種運算(取模運算),

• 為了同一表達式,我們限制R的值隻可以在第二重下标中取得,并把此時的值記為()

循環隊列滿判斷

• 判斷隊列滿的方案有多種

• 犧牲掉一個位置來判斷​

  ​隊滿​

  ​

• 具體的判空條件為​

  ​(Q.rear+1)%MaxSize==Q.front​

  ​

• 之是以這裡要用,
• 這種情況下,這超過了數組下标的範圍
• 不可能超過數組的下标範圍,這樣及時滿足隊滿條件,也無法做出正确判斷!

• 在隊列的資料類型中設定​

  ​size​

  ​成員來表示隊列元素個數
• 或者設定​

  ​tag​

  ​​成員來區分​

  ​Q.front==Q.rear​

  ​是隊滿還是隊空