第 01 章 基本概念
數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作的一門學科
四類基本數(shù)據(jù)結(jié)構(gòu)：集合巧号，線性煤裙，樹混驰，圖
數(shù)據(jù)類型：一組性質(zhì)相同的值的集合以及這個集合上的操作的一組總稱
抽象數(shù)據(jù)類型：指一個數(shù)學模型以及定義在該模型上的一組操作
算法：對特定問題求解步驟的一種描述盛末，指令的有限序列
算法的五個特性：有窮性唁奢，確定性甚负，可行性柬焕，0個或多個輸入，1個或多個輸出
算法的設計要求：正確性梭域，可讀性斑举，健壯性，高效率病涨，低存儲
時間復雜度的計算：只考慮基本操作（可以這么理解：最深那一層括號中的語句都屬于基本操作）富玷，即基本操作的重復次數(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)點：隨機存取
- 缺點：插入或刪除元素不方便
-
鏈式：用一組物理位置任意的存儲單元來存儲
- 優(yōu)點：插入或刪除元素很方便
- 缺點：非隨機存取
本章涉及到的一些存儲結(jié)構(gòu)
// 順序存儲結(jié)構(gòu)
typedef struct {
ElemType *elem; // 數(shù)組
int length; // 有效長度
int listSize; // 分配的空間
} SqList;
// 鏈式存儲結(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個或多個字符組成的有限序列
串相等：兩個串長度相等且各個對應位置的字符都相等
子串：由串中任意個連續(xù)的字符組成的子序列
kmp算法：next數(shù)組要解決的時當模式串失配的時候当悔，該指向的位置
next數(shù)組的求法
nextval數(shù)組的求法
第 05 章 數(shù)組和廣義表
數(shù)組：具有相同類型的數(shù)據(jù)元素的集合
兩種順序存儲方式：
- 以行序為主序（按一行一行的順序存）
- 以列序為主序（按一列一列的順序存）
稀疏矩陣：在m x n的矩陣中有t個非零元素傅瞻，令 L = t/(m x n)，當L <=0.05時稱為稀疏矩陣
- 三元組順序表
- 十字鏈表
廣義表：n個元素的有限序列盲憎，每一個元素可能是原子嗅骄，也可能是一個子表
- 表頭：第一個元素就是表頭，可以是原子饼疙，也可以是子表
- 表尾：除表頭之外的其他元素組成的表
- 長度：最外層所包含元素的個數(shù)
- 深度：該廣義表展開后括號的重數(shù)溺森，深度可以理解為有多少組括號。
- 原子深度為0窑眯，空表深度為1
- 遞歸表的深度是無窮值屏积，長度是有限值
本章涉及到的一些存儲結(jié)構(gòu)：
// 稀疏矩陣的三元組順序存儲結(jié)構(gòu)
typedef struct {
int i, j; // 該非零元素的下標
Element e;
} Triple;
typedef struct {
Triple data[MAX_SIZE + 1]; // 下標為0的空間不用
int mu, nu, tu; // 行數(shù)，列數(shù)伸但，非零元素個數(shù)
} TSMatrix;
// 廣義表的首尾鏈表表示法
typedef enum {
ATOM, LIST
} ELemtag;
typedef struct GLNode {
Elemtag tag; // 標志域肾请，用于區(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; // 標志域
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ū)別就是二叉樹嚴格區(qū)分左右却妨，這是二叉樹與樹的主要區(qū)別）
- 二叉樹中不存在度大于2的結(jié)點
- 子樹有左右之分
- 滿二叉樹，一顆深度為k的且有2^k -1個結(jié)點的二叉樹
- 完全二叉樹括眠，這顆深度為k的二叉樹與同樣深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應上時彪标，稱為完全二叉樹（完全二叉樹是路徑長度最短的二叉樹）
-
關于二叉樹的性質(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é)點的下標
}PTree;
// 帶雙親的孩子鏈表表示法
typedef struct CTNode { // 鏈表結(jié)點
int child; // 孩子的下標
struct CTNode *next;
} *ChildPtr;
typedef struct { // 結(jié)點
int parent; // 雙親的下標
TElemType data;
ChildPtr firstChild; // 指向第一個孩子的指針
} CTBox;
typedef struct { // 樹結(jié)構(gòu)
CTBox nodes[MAX_TREE_SIZE];
int n, r; // n是結(jié)點數(shù)爆办，r是根結(jié)點的下標
} 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)：與邊或弧相關的數(shù)
網(wǎng)：帶權(quán)的圖
子圖：頂點和邊各自的子集
在無向圖或者有向圖中挑格，邊的數(shù)目總和 = 度的總和/2
連通：如果說從頂點a到頂點b有路徑，則稱a和b是連通的
連通圖：圖中任意兩個頂點都是連通的
連通圖至少有n-1條邊沾歪，當邊的數(shù)目小于n-1漂彤，則此圖一定是非連通圖
強連通圖：任意兩個頂點都連通的有向圖
生成樹：所有頂點均由邊連接在一起但不存在回路的圖
- 頂點個數(shù)與圖的頂點個數(shù)相同
- 生成樹的圖的極小連通子圖
- 一個有n個頂點的連通圖的生成樹有n-1條邊
圖的各種存儲結(jié)構(gòu)：
-
鄰接矩陣：使用兩個數(shù)組，一個一維數(shù)組存儲頂點形象灾搏，另外一個二維數(shù)組存儲邊或弧的關系
- 有向圖中行的1的個數(shù)是頂點的出度挫望，列的1的個數(shù)是頂點的入度
- 無向圖中頂點的度是行或列中的1的個數(shù)
- 鄰接表，類似樹的孩子鏈表表示法狂窑，有向圖的又分為鄰接表（找出度易）和逆鏈接表（找入度易）
- 十字鏈表媳板，僅適用于有向圖
不知道什么時候記錄的：
在無向圖中，表結(jié)點的個數(shù)是邊的個數(shù)的2倍
有向圖中泉哈，表結(jié)點的個數(shù)是邊的個數(shù)
圖的遍歷：
- 深度優(yōu)先遍歷：當前訪問的頂點有未被訪問的鄰接頂點蛉幸，則選其一訪問，重復不斷丛晦，反之則退回到上一個頂點（連通圖的深度優(yōu)先遍歷類似于樹的先根遍歷）
- 廣度優(yōu)先遍歷：從某一頂點出發(fā)奕纫，訪問其所有的鄰接頂點，然后按次序再訪問其所有的鄰接頂點（一層一層的掃描烫沙，類似樹的層序遍歷）
最小生成樹：在一個無向網(wǎng)中匹层，使得各邊權(quán)數(shù)之和最小的那棵生成樹
構(gòu)造最小生成樹的兩個算法：
- 普里姆算法：從某個頂點開始，逐個找個各頂點最小權(quán)值的邊
- 克魯斯卡爾算法锌蓄，依次加入最小的連通分量升筏，但是不能形成環(huán)
最短路徑問題：
- 從某個源點到其余頂點的最短路徑問題：迪杰斯特拉算法：在求出的最短路徑的基礎上求出其他結(jié)點的最短路徑
- 每對頂點間的最短路徑問題，佛洛伊德算法：逐步試著在原直接路徑中增加中間頂點瘸爽，若加入后路徑變短您访，則修改之
有向無環(huán)圖：有向圖中不存在環(huán)，簡稱DAG圖
AOV網(wǎng)：用DAG圖表示一個工程蝶糯，頂點表示活動
拓撲排序：找到做事的先后順序
- 在有向圖中選一個沒有前驅(qū)（即入度為0）的頂點并輸出之
- 從圖中刪除該頂點和所有以它為尾的弧
- 重復上面兩部洋只，直到全部頂點均已輸出，或者當圖中不存在無前驅(qū)的頂點為止
AOE網(wǎng)：頂點表示事件，弧表示活動识虚，弧的權(quán)表示活動持續(xù)時間
- 關鍵路徑：路徑長度最長的路徑
- 關鍵活動：最遲開始時間和最早開始時間相等的活動
- 關鍵事件：最遲開始時間和最早開始時間相等的事件
第 09 章 查找
靜態(tài)查找：只查找
- 順序查找
- 折半查找-針對有序表
- 索引查找-分塊有序（但是塊內(nèi)是無序的）
動態(tài)查找：查找后插入或者刪除
- 二叉排序樹：左子樹的值比根小肢扯，右子樹的值比根大，中序遍歷二叉排序樹可得到一個關鍵字的有序序列
- 二叉排序樹的刪除：
- 被刪除結(jié)點為葉子結(jié)點担锤，那就直接刪除就行
- 若被刪除結(jié)點只有左子樹蔚晨，則用左孩子替代，若只有右子樹肛循，則用右孩子替代
- 左右子樹都非空铭腕，用被刪除結(jié)點的中序直接前驅(qū)替代，或者用中序直接后繼替代多糠，或者用左子樹直接替代
散列表累舷，Hash Table，又稱為哈希表夹孔，特點：數(shù)據(jù)元素的關鍵字與其存儲地址直接相關被盈，關鍵字通過哈希函數(shù)（散列函數(shù)）確定存儲地址
- 同義詞：不同關鍵字通過散列函數(shù)映射到同一個值
- 沖突：通過散列函數(shù)確定的位置存放了其他元素
解決沖突：鏈地址法
第 10 章 排序
內(nèi)部排序：待排序的所有記錄全部放置在內(nèi)存中
外部排序：待排序的記錄個數(shù)太多，需要使用到外存
