《數(shù)據(jù)結(jié)構(gòu)》筆記

第 01 章 基本概念

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的一門學(xué)科

四類基本數(shù)據(jù)結(jié)構(gòu)：集合，線性，樹，圖

數(shù)據(jù)類型：一組性質(zhì)相同的值的集合以及這個集合上的操作的一組總稱

抽象數(shù)據(jù)類型：指一個數(shù)學(xué)模型以及定義在該模型上的一組操作

算法：對特定問題求解步驟的一種描述，指令的有限序列

算法的五個特性：有窮性，確定性，可行性，0個或多個輸入，1個或多個輸出

算法的設(shè)計要求：正確性，可讀性，健壯性，高效率，低存儲

時間復(fù)雜度的計算：只考慮基本操作（可以這么理解：最深那一層括號中的語句都屬于基本操作），即基本操作的重復(fù)次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，記作：T(n) = O(f(n))

頻度：基本操作的執(zhí)行次數(shù)

加工型操作：會修改元素

引用型操作：只用不改

第 02 章 線性表

線性表：n個數(shù)據(jù)元素的有限序列

4個唯一：

  • 存在唯一一個被稱作“第一個”的數(shù)據(jù)元素
  • 存在唯一一個被稱作“最后一個”的數(shù)據(jù)元素
  • 除第一個之外的數(shù)據(jù)元素均只有一個前驅(qū)
  • 除最后一個之外的數(shù)據(jù)元素均只有一個后繼

存儲方式

  • 順序：用一組地址連續(xù)的存儲單元依次存儲
    • 優(yōu)點：隨機存取
    • 缺點：插入或刪除元素不方便
  • 鏈?zhǔn)剑河靡唤M物理位置任意的存儲單元來存儲
    • 優(yōu)點：插入或刪除元素很方便
    • 缺點：非隨機存取

本章涉及到的一些存儲結(jié)構(gòu)

// 順序存儲結(jié)構(gòu)
typedef struct {
    ElemType *elem; // 數(shù)組
    int length; // 有效長度
    int listSize; // 分配的空間
} SqList;

// 鏈?zhǔn)酱鎯Y(jié)構(gòu)
typedef struct LNode {
    ElemType data; // 數(shù)據(jù)域
    struct LNode *next; // 指針域
} LNode,*LinkList; // LinkList是指向單鏈表的指針，由此唯一確定一個單鏈表

第 03 章 棧與隊列

棧：限定在表尾進行插入或刪除操作的線性表，后進后出

這里的表尾即是棧頂，表頭是棧底

隊列：限定在表的一端插入，另一端刪除的線性表，先進先出

插入的一端稱為隊尾，刪除的一端稱為隊頭

本章涉及到的一些存儲結(jié)構(gòu)：

// 順序棧的存儲結(jié)構(gòu)
typedef struct {
    SElemType *base; // 棧底指針
    SElemType *top; // 棧頂指針，靈魂所在
    int stackSize; // 分配的空間
} SqStack;

// 鏈棧的存儲結(jié)構(gòu)
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct LinkStack {
    LinkStackPtr top;
    int count;
} LinkStack;

// 循環(huán)隊列
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;

// 鏈隊列的存儲結(jié)構(gòu)
typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 隊頭
    QueuePtr rear; // 隊尾
} LinkQueue;

第 04 章 串

串：0個或多個字符組成的有限序列

串相等：兩個串長度相等且各個對應(yīng)位置的字符都相等

子串：由串中任意個連續(xù)的字符組成的子序列

kmp算法：next數(shù)組要解決的時當(dāng)模式串失配的時候，該指向的位置

next數(shù)組的求法

nextval數(shù)組的求法

第 05 章 數(shù)組和廣義表

數(shù)組：具有相同類型的數(shù)據(jù)元素的集合

兩種順序存儲方式：

  • 以行序為主序（按一行一行的順序存）
  • 以列序為主序（按一列一列的順序存）

稀疏矩陣：在m x n的矩陣中有t個非零元素，令 L = t/(m x n)，當(dāng)L <=0.05時稱為稀疏矩陣

  • 三元組順序表
  • 十字鏈表

廣義表：n個元素的有限序列，每一個元素可能是原子，也可能是一個子表

  • 表頭：第一個元素就是表頭，可以是原子，也可以是子表
  • 表尾：除表頭之外的其他元素組成的表
  • 長度：最外層所包含元素的個數(shù)
  • 深度：該廣義表展開后括號的重數(shù)，深度可以理解為有多少組括號。
    • 原子深度為0，空表深度為1
    • 遞歸表的深度是無窮值，長度是有限值

本章涉及到的一些存儲結(jié)構(gòu)：

// 稀疏矩陣的三元組順序存儲結(jié)構(gòu)
typedef struct {
    int i, j; // 該非零元素的下標(biāo)
    Element e;
} Triple;
typedef struct {
    Triple data[MAX_SIZE + 1]; // 下標(biāo)為0的空間不用
    int mu, nu, tu; // 行數(shù)，列數(shù)，非零元素個數(shù)
} TSMatrix;

// 廣義表的首尾鏈表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    Elemtag tag; // 標(biāo)志域，用于區(qū)分元素結(jié)點和表結(jié)點 
    union { // 元素結(jié)點和表結(jié)點的聯(lián)合部分 
      Atomtype atom; // atom 是原子結(jié)點的值域 
      struct {
          struct GLNode *hp, *tp; // hp和tp分別指向表頭和表尾 
      }ptr; // ptr是表結(jié)點的指針域
    };
  }*GList;                           

// 廣義表的孩子兄弟鏈表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    ELemtag tag; // 標(biāo)志域
    union {
        AtomType atom; // 原子結(jié)點的值域
        struct GLNode *hp; // 表結(jié)點的指針
    };
    struct GLNode *tp;// 指向兄弟結(jié)點
} *GList;

第 06 章 樹和二叉樹

  • 樹：n個結(jié)點的有限集，n=0 稱為空樹，若n>0，則有且僅有一個“根”，其余為根的子樹
  • 度：結(jié)點擁有的子樹數(shù)量（樹的度是樹內(nèi)各結(jié)點的度的最大值）
  • 二叉樹：由一個根結(jié)點及左子樹和右子樹組成（與樹的區(qū)別就是二叉樹嚴(yán)格區(qū)分左右，這是二叉樹與樹的主要區(qū)別）
    • 二叉樹中不存在度大于2的結(jié)點
    • 子樹有左右之分
  • 滿二叉樹，一顆深度為k的且有2^k -1個結(jié)點的二叉樹
  • 完全二叉樹，這顆深度為k的二叉樹與同樣深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)上時，稱為完全二叉樹（完全二叉樹是路徑長度最短的二叉樹）
  • 關(guān)于二叉樹的性質(zhì)：
    • 性質(zhì)1：在二叉樹的第i層上至多有 2^(i-1)個結(jié)點
    • 性質(zhì)2：深度為k的二叉樹至多有2^k -1個結(jié)點
    • 性質(zhì)3：對任何一棵二叉樹T，如果其葉子數(shù)為n，度為2的結(jié)點樹為m，則 n = m + 1
    • 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為log2n + 1
    • 性質(zhì)6：在n個結(jié)點的二叉鏈表中有n+1個空指針域

遍歷二叉樹：巡訪二叉樹中的結(jié)點，使得每一個結(jié)點均被訪問且僅被訪問過一次

  • 先序：根，左，右
  • 中序：左，根，右
  • 后序：左，右，根

線索二叉樹：根據(jù)遍歷二叉樹的方法，使用結(jié)點的空閑位置，指出前驅(qū)結(jié)點或后綴結(jié)點，實質(zhì)是在遍歷的過程中用線索取代空指針

中序前驅(qū)左孩找右，中序后繼右孩找左

哈夫曼樹：帶權(quán)路徑長度最短的二叉樹

  • 包含n個葉子結(jié)點的哈夫曼樹中共有2n-1個結(jié)點
  • 哈夫曼樹中的結(jié)點的度或為0或為2

本章涉及到的一些存儲結(jié)構(gòu)：

// 二叉樹的存儲結(jié)構(gòu)
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子
} BiTNode, *BiTree;

// 樹的雙親表示法
typedef struct PTNode {
    TElemType data;
    int parent; // 雙親位置
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r,n; // n是結(jié)點數(shù)，r是根結(jié)點的下標(biāo)
}PTree;

// 帶雙親的孩子鏈表表示法
typedef struct CTNode { // 鏈表結(jié)點
    int child; // 孩子的下標(biāo)
    struct CTNode *next;
} *ChildPtr;
typedef struct { // 結(jié)點
    int parent; // 雙親的下標(biāo)
    TElemType data;
    ChildPtr firstChild; // 指向第一個孩子的指針
} CTBox;
typedef struct { // 樹結(jié)構(gòu)
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; // n是結(jié)點數(shù)，r是根結(jié)點的下標(biāo)
} CTree;

// 孩子兄弟表示法
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild,*nextsibling; // 第一個孩子，兄弟結(jié)點
}CSNode,*CSTree;

第 07 章 圖

圖是由頂點的有窮非空集合和頂點之間邊的集合組成的

邊：無向圖中的連線

弧：有向圖中的連線

無向完全圖：任意兩頂點都存在邊的無向圖，含有n個頂點的無向完全圖有n(n-1)/2條邊

有向完全圖：任意兩頂點都存在方向互為相反的兩條弧，有n個頂點的有向完全圖有n(n-1)條邊

權(quán)：與邊或弧相關(guān)的數(shù)

網(wǎng)：帶權(quán)的圖

子圖：頂點和邊各自的子集

在無向圖或者有向圖中，邊的數(shù)目總和 = 度的總和/2

連通：如果說從頂點a到頂點b有路徑，則稱a和b是連通的

連通圖：圖中任意兩個頂點都是連通的

連通圖至少有n-1條邊，當(dāng)邊的數(shù)目小于n-1，則此圖一定是非連通圖

強連通圖：任意兩個頂點都連通的有向圖

生成樹：所有頂點均由邊連接在一起但不存在回路的圖

  • 頂點個數(shù)與圖的頂點個數(shù)相同
  • 生成樹的圖的極小連通子圖
  • 一個有n個頂點的連通圖的生成樹有n-1條邊

圖的各種存儲結(jié)構(gòu)：

  • 鄰接矩陣：使用兩個數(shù)組，一個一維數(shù)組存儲頂點形象，另外一個二維數(shù)組存儲邊或弧的關(guān)系
    • 有向圖中行的1的個數(shù)是頂點的出度，列的1的個數(shù)是頂點的入度
    • 無向圖中頂點的度是行或列中的1的個數(shù)
  • 鄰接表，類似樹的孩子鏈表表示法，有向圖的又分為鄰接表（找出度易）和逆鏈接表（找入度易）
  • 十字鏈表，僅適用于有向圖

不知道什么時候記錄的：

在無向圖中，表結(jié)點的個數(shù)是邊的個數(shù)的2倍

有向圖中，表結(jié)點的個數(shù)是邊的個數(shù)

圖的遍歷：

  • 深度優(yōu)先遍歷：當(dāng)前訪問的頂點有未被訪問的鄰接頂點，則選其一訪問，重復(fù)不斷，反之則退回到上一個頂點（連通圖的深度優(yōu)先遍歷類似于樹的先根遍歷）
  • 廣度優(yōu)先遍歷：從某一頂點出發(fā)，訪問其所有的鄰接頂點，然后按次序再訪問其所有的鄰接頂點（一層一層的掃描，類似樹的層序遍歷）

最小生成樹：在一個無向網(wǎng)中，使得各邊權(quán)數(shù)之和最小的那棵生成樹

構(gòu)造最小生成樹的兩個算法：

  • 普里姆算法：從某個頂點開始，逐個找個各頂點最小權(quán)值的邊
  • 克魯斯卡爾算法，依次加入最小的連通分量，但是不能形成環(huán)

最短路徑問題：

  • 從某個源點到其余頂點的最短路徑問題：迪杰斯特拉算法：在求出的最短路徑的基礎(chǔ)上求出其他結(jié)點的最短路徑
  • 每對頂點間的最短路徑問題，佛洛伊德算法：逐步試著在原直接路徑中增加中間頂點，若加入后路徑變短，則修改之

有向無環(huán)圖：有向圖中不存在環(huán)，簡稱DAG圖

AOV網(wǎng)：用DAG圖表示一個工程，頂點表示活動

拓撲排序：找到做事的先后順序

  1. 在有向圖中選一個沒有前驅(qū)（即入度為0）的頂點并輸出之
  2. 從圖中刪除該頂點和所有以它為尾的弧
  3. 重復(fù)上面兩部，直到全部頂點均已輸出，或者當(dāng)圖中不存在無前驅(qū)的頂點為止

AOE網(wǎng)：頂點表示事件，弧表示活動，弧的權(quán)表示活動持續(xù)時間

  • 關(guān)鍵路徑：路徑長度最長的路徑
  • 關(guān)鍵活動：最遲開始時間和最早開始時間相等的活動
  • 關(guān)鍵事件：最遲開始時間和最早開始時間相等的事件

第 09 章 查找

靜態(tài)查找：只查找

  • 順序查找
  • 折半查找-針對有序表
  • 索引查找-分塊有序（但是塊內(nèi)是無序的）

動態(tài)查找：查找后插入或者刪除

  • 二叉排序樹：左子樹的值比根小，右子樹的值比根大，中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列
  • 二叉排序樹的刪除：
    • 被刪除結(jié)點為葉子結(jié)點，那就直接刪除就行
    • 若被刪除結(jié)點只有左子樹，則用左孩子替代，若只有右子樹，則用右孩子替代
    • 左右子樹都非空，用被刪除結(jié)點的中序直接前驅(qū)替代，或者用中序直接后繼替代，或者用左子樹直接替代

散列表，Hash Table，又稱為哈希表，特點：數(shù)據(jù)元素的關(guān)鍵字與其存儲地址直接相關(guān)，關(guān)鍵字通過哈希函數(shù)（散列函數(shù)）確定存儲地址

  • 同義詞：不同關(guān)鍵字通過散列函數(shù)映射到同一個值
  • 沖突：通過散列函數(shù)確定的位置存放了其他元素

解決沖突：鏈地址法

第 10 章 排序

內(nèi)部排序：待排序的所有記錄全部放置在內(nèi)存中

外部排序：待排序的記錄個數(shù)太多，需要使用到外存

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容