一竹习、數(shù)據(jù)結(jié)構緒論
- 邏輯結(jié)構與物理結(jié)構
- 邏輯結(jié)構：集合指孤、線性（一對一）瘩绒、樹（一對多）猴抹、圖（多對多）
- 物理結(jié)構：順序存儲結(jié)構、鏈式儲存結(jié)構
- 抽象數(shù)據(jù)類型 （Abstract Data Type,ADT）：是指一個數(shù)學模型及定義在該模型上的一組操作
標準格式
ADT 抽象數(shù)據(jù)類型名
Date 數(shù)據(jù)元素之間的邏輯定義
Operation
操作1
初始條件
操作結(jié)果描述
操作2
......
操作3
......
endADT
二锁荔、算法
- 算法特性：輸入輸出蟀给、確定性、又窮性阳堕、可行性
- 算法要求：正確性跋理、健壯性、可讀性恬总、時間效率高和存儲量低
- 算法時間復雜度
- 推導大O階方法
1.用常數(shù)1取代運行時間中所有加法常數(shù)
2.在修改后的運行函數(shù)中前普，只保留最高位
3.如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)
得到的結(jié)果是大O階
- 推導大O階方法
三越驻、線性表
- 定義：零個或多個數(shù)據(jù)元素的有限序列
- 抽象數(shù)據(jù)結(jié)構
ADT 線性表
Data ：
線性表的數(shù)據(jù)對象集合為{a1汁政，a2道偷，......，an}记劈，每個元素的類型均為DataType勺鸦。其中，除第一個元素a1外目木，每一個元素有且只有一個直接前驅(qū)元素换途，除了最后一個元素an外每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關系是一對一的關系刽射。
Operation：
InitList(&l)
操作結(jié)果：構造一個空的線性表L
DestroyList(&l)
初始條件：線性表已存在
操作結(jié)果：銷毀線性表L
ClearList(&l)
初始條件：線性表已存在
操作結(jié)果：置線性表L為空表
ListEmpty(L)
初始條件：線性表已存在
操作結(jié)果：若線性表L為空表军拟，則返回TRUE，否則返回FALSE
ListLenght(L)
初始條件：線性表已存在
操作結(jié)果：返回線性表L數(shù)據(jù)元素個數(shù)
GetElem(L,i,&e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結(jié)果：用e返回線性表L中第i個數(shù)據(jù)元素的值
locatElem(L,e,comare())
初始條件：線性表已存在,comare()是數(shù)據(jù)元素判定函數(shù)
操作結(jié)果：返回線性表L中第1個與e滿足關系comare()的數(shù)據(jù)元素的位序
PriorElem(L,cur_e,&pre_e)
初始條件：線性表已存在
操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素誓禁，且不是第一個懈息，則用pre_e返回它的前驅(qū)，否則操作失敗摹恰，pre_e無定義
NextElem(L,cur_e,&)
初始條件：線性表已存在
操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素辫继，且不是第最后一個，則用next_e返回它的后繼俗慈，否則操作失敗姑宽，next_e無定義
ListInsert(&L,i,e)
初始條件：線性表已存在（1≤i≤ListLenght(L)+1）
操作結(jié)果：在線性表L中第i個數(shù)據(jù)元素之前插入新元素e，L長度加1
ListDelete(&L,i,&e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結(jié)果：刪除線性表L中第i個數(shù)據(jù)元素闺阱，用e返回其值际看，L長度減1
ListTraverse(L,visit())
初始條件：線性表已存在
操作結(jié)果：依次對線性表L的每個數(shù)據(jù)元素調(diào)用visit()函數(shù)淑玫，一旦visit()失敗芳杏，則操作失敗}ADT List
- 順序儲存結(jié)構代碼
#define MAXSIZE 20
typedef int ElemType栓撞；
typedef struct{
ElemType data[MAXSIZE];
int length;
}SqList;
單鏈表、靜態(tài)鏈表救拉、循環(huán)鏈表难审、雙向鏈表
- 單鏈表
- 單鏈表儲存結(jié)構代碼
typedef struct node{
ElemType data；
struct Node *next亿絮；
} Node告喊；
typedef struct Node *LinkList；
- 靜態(tài)鏈表（早期沒有指針派昧，用數(shù)組代替指針）
- 靜態(tài)鏈表的儲存結(jié)構代碼
#define MAXSIZE 1000
typedef struct{
Elemtype data黔姜；
int cur；/游標/
}Component,StaticLinkList[MAXSIZE];
靜態(tài)鏈表
頭指針存放備用鏈表（后面空閑空間）第一個節(jié)點下標
數(shù)組最后一個元素的cur用來存放頭結(jié)點（第一個插入元素的下標）
循環(huán)鏈表
將單鏈表中的終端結(jié)點的指針端由空指針改為指向頭結(jié)點蒂萎，鏈表就形成了一個環(huán)-
雙向鏈表
- 雙向鏈表的儲存結(jié)構代碼
typedef Struct DulNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode next;
}DulNode,DuLinkList;
- 雙向鏈表的儲存結(jié)構代碼
四秆吵、棧與隊列
棧
- 棧的定義：限定僅在表尾進行插入和刪除操作的線性表
- 棧的抽象數(shù)據(jù)類型
ADT 棧（stack）
Data ：
同線性表
Operation：
InitStack（*S）
初始化操作，建立一個空棧*S
DestroyStack（*S）
若棧存在五慈，則銷毀它
ClearStack（*S）
將棧清空
StackEmpty（*S）
若棧為空纳寂，則返回true主穗，反之返回false
GetTop（S，*e）
若棧存在且非空毙芜，用e返回棧頂元素
Push（*S忽媒，e）
若棧存在，插入新元素e到棧S中并成為棧頂元素
Pop（S腋粥，e）
刪除棧S中棧頂元素晦雨，并用e返回其值
StackLengh（S）
返回棧S的元素個數(shù)
endADT
- 棧的順序存儲結(jié)構
typedef int SElemType；
typedef struct{
SElemtype data[MAXSIZE];
int top;
}SqStack隘冲； - 兩棧共享空間
typedef struct{
SElemType data[MAXSIZE];
int top1;
int top2;
}sqDoubleStack闹瞧；
判斷是否滿棧
top1+1==top2
-
棧的鏈式存儲結(jié)構
typedef struct StackNode{
SElemType data;
struct StackNode next;
}StackNode,LinkStackPtr;typedef struct LinkStack{ LinkStack top; int count; }LinkStack； 棧的應用：
四則運算表達式求值：后綴表示法(逆波蘭表示法)展辞。
隊列
- 隊列的定義：只允許在一端進行插入操作奥邮，而在另一端進行刪除操作的線性表
- 隊列的抽象數(shù)據(jù)類型
ADT 隊列（Queue）
Data ：
同線性表
Operation：
InitQueue（*Q）
初始化操作，建立一個空隊列*Q
DestroyQueue（*Q）
若隊列存在罗珍，則銷毀它
ClearQueue（*S）
將隊列清空
QueueEmpty（*Q）
若隊列為空漠烧，則返回true，反之返回false
GetHead（Q靡砌，*e）
若隊列存在且非空，用e返回隊頭元素
EnQueue（*Q珊楼，e）
若隊列Q存在通殃，插入新元素e到隊列Q中并成為隊尾元素
DeQueue（Q，e）
刪除隊列Q中隊頭元素厕宗，并用e返回其值
QueueLengh（Q）
返回隊列Q的元素個數(shù)
endADT
- 循環(huán)隊列
- 定義：隊列頭尾相接
- 循環(huán)隊列順序存儲結(jié)構
typedef int QElemType画舌；
typedef struct{
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
隊列滿的條件是
######（rear+1）%QueueSize == front
- 隊列的鏈式儲存結(jié)構
typedef int QElemType；
typedef struct QNode{
QElemType data已慢；
struct QNde next曲聂；
}QNode,QueuePtr;
typedef struct{
QueuePtr font,rear;
}LinkQueue；
五佑惠、串
- 串的定義：串是由零個或多個字符組成的有限序列朋腋，又名叫字符串
- 串的抽象數(shù)據(jù)結(jié)構
ADT 串（string）
Data
串中元素僅由一個字符組成，相鄰元素具有前驅(qū)和后繼關系
Operation
StrAssign( &T, chars )
初始條件：chars是字符串常量膜楷。
操作結(jié)果：生成一個其值等于chars的串T旭咽。
StrCopy( &T, S )
初始條件：串S存在。
操作結(jié)果：由串S復制得串T赌厅。
StrEmpty( S )
初始條件：串S存在穷绵。
操作結(jié)果：若S為空串，則返回TRUE特愿，否則返回FALSE仲墨。 StrCompare( S, T )
初始條件：串S和T存在勾缭。
操作結(jié)果：若S>T，則返回值>0目养；若S=T俩由，則返回值=0；若S<T混稽，則返回值<0采驻。
StrLength( S )
初始條件：串S存在。
操作結(jié)果：返回S的元素個數(shù)匈勋，稱為串的長度礼旅。
ClearString( &S )
初始條件：串S存在。
操作結(jié)果：將S清為空串洽洁。
Concat( &T, S1, S2 )
初始條件：串S1和S2存在痘系。
操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。
SubString( &Sub, S, pos, len )
初始條件：串S存在饿自，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
操作結(jié)果：用Sub返回串S的第pos個字符起長度為len的子串汰翠。
Index( S, T, pos )
初始條件：串S和T存在，T是非空串昭雌，1≤pos≤StrLength(S)复唤。
操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置烛卧；否則函數(shù)值為0佛纫。
Replace( &S, T, V )
初始條件：串S，T和V存在总放，T是非空串呈宇。
操作結(jié)果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。 ######StrInsert( &S, pos, T )
初始條件：串S和T存在局雄，1≤pos≤StrLength(S)+1甥啄。
操作結(jié)果：在串S的第pos個字符之前插入串T。
StrDelete( &S, pos, len )
初始條件：串S存在炬搭，1≤pos≤StrLength(S)-len+1蜈漓。
操作結(jié)果：從串S中刪除第pos個字符起長度為len的子串。
DestroyString( &S )
初始條件：串S存在尚蝌。
操作結(jié)果：串S被銷毀迎变。
}
endADT
- 串的匹配
- 樸素匹配算法
一個一個匹配 - kmp模式匹配算法
算法思想：利用已經(jīng)匹配過的數(shù)據(jù)，創(chuàng)建一個next數(shù)組飘言。避免重復遍歷
難點：理解next數(shù)組
六衣形、樹
樹的定義
樹是n個結(jié)點的有限集。n=0時稱為空樹。在任何一棵非空樹：
（1）有且僅有一個特定的稱為根的結(jié)點
（2）當n>1時谆吴，其余結(jié)點可分為m（m>0）個互不相交的有限集t1倒源、t2、......句狼、tm笋熬，其中每一個集合本身又是一棵樹，并且稱為根的子樹-
結(jié)點的度：結(jié)點擁有的子樹數(shù)腻菇，度為零的稱為葉節(jié)點（終端結(jié)點）
樹的度是節(jié)點的度的最大值
結(jié)點的層次從根開始定義胳螟，根為第一層，樹中結(jié)點的最大層次稱為樹的深度（高度）
樹的抽象數(shù)據(jù)類型
ADT 樹（tree）
Data
樹是由一個根節(jié)點和若干棵子樹構成筹吐。樹中結(jié)點具有相同數(shù)據(jù)類型及層次關系糖耸。
Operation
endADT
- 樹的存儲結(jié)構
雙親表示法
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode{
TElemType data；
int parent丘薛；
}PTNode嘉竟；
typedef struct
{
PTNode nodes[MAX_TREE_SIZE];
int r,n;/根的位置和結(jié)點數(shù)/
}PTree;-
孩子表示法
#define MAX_TREE_SIZE 100 typedef int ElemType; typedef struct CTNode{ int child； struct CTNode *next洋侨； }*ChildPtr舍扰； typedef struct { TElemType data； ChildPtr firstchild希坚； }CTBox; typedef struct { CTbox nodes[MAX_TREE_SIZE]; int r,n; }CTree;
線性表儲存結(jié)點元素边苹，孩子鏈表的孩子結(jié)點 child是數(shù)據(jù)域，儲存某結(jié)點在表頭數(shù)組中的下標裁僧。next是指針域勾给，用來存儲指向某結(jié)點的下一個孩子的指針
孩子兄弟表示法
typedef int ElemType;
typedef struct CSNode{
TElemType data；
struct CSNode firstchild锅知，rightsib；
}CSNode脓钾，*CSTree售睹；-
二叉樹
定義
是n個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹）可训，或者由一個跟結(jié)點和兩棵互不相交的昌妹、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。-
存儲結(jié)構
- 順序儲存結(jié)構
從根節(jié)點開始遍歷二叉樹握截，遇到?jīng)]有則置空 - 二叉鏈表
typedef struct BiTNode{
TElemType data飞崖；
struct BiTNode lchild，rchild谨胞；
} BiTNode固歪，*BiTree；
- 順序儲存結(jié)構
-
遍歷二叉樹
- 定義：從根節(jié)點出發(fā)，按照一定的次序依次訪問二叉樹中所有結(jié)點牢裳，使得每個結(jié)點被訪問依次且僅被訪問依次
- 前序遍歷
根左右
* 中序遍歷
>左根右
* 后序遍歷
>左右根
-
線索二叉樹
- 定義：二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化
- 二叉樹的線索存儲結(jié)構
typedef enum{Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode lchild,rchild;
PointerTag LTag;
PointerTag RTag;
} BiThrNode,*BiThrTree; - 中序遍歷線索化
void InThreading(BiThrTree p）
{
if(p) {
InThreading(p->lchild);//左子樹線索化
if(!p->lchild){
p->LTag=Thread;
p->lchild=pre;}//前驅(qū)線索
if(!pre->rchild){
pre->RTag=Thread;
pre->rchild=p;}//后續(xù)線索
pre=p; //保持pre指向p的前驅(qū)
InThreading(p->rchild);//右子樹線索化
}
}//InThreading
因為此時p結(jié)點的后繼還沒有訪問到逢防，因此只能對它的前驅(qū)界限pre的右指針rchild做判斷，if（蒲讯！pre->rchild）表示如果為空忘朝，則p就是pre的后繼，于是pre->rchild=p判帮，并且設置pre->RTag=Thread,完成后繼結(jié)點的線索化
- 赫夫曼樹
- 定義 帶權路徑長度wpl最小的二叉樹稱為赫夫曼樹（最優(yōu)二叉樹）
- 算法描述
七局嘁、圖
- 圖的定義
- 圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E),其中晦墙，G表示一個圖悦昵，V是圖G中頂點的集合，E是圖G中邊的集合
- 有向邊（毁送础）：頂點vi到vj有方向旱捧，則稱這條邊為有向邊
- 簡單圖：不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)踩麦，則為簡單圖
- 無向（有向）完全圖：任意兩個頂點之間都存在邊
- 權：與圖的邊或弧相關的數(shù)
- 網(wǎng)：帶權的圖
- 回路（環(huán)）：第一個頂點到最后一個頂點相同的路徑
- 簡單路徑：頂點不重復出現(xiàn)的路徑
- 連通圖：圖中任意兩個頂點都是連通的
- 連通分量：無向圖中的極大連通子圖
- 強連通圖：在有向圖中枚赡，對于每一對vi，vj從vi到vj和從vj到vi都存在路徑谓谦，則稱G是強連通圖贫橙。有向圖中的極大連通子圖稱做有向圖的強連通分量。
- 圖的抽象數(shù)據(jù)結(jié)構
ADT 圖（Graph）
Data
頂點的有窮非空集合和邊的集合
Operation
endADT
- 圖的儲存結(jié)構
- 鄰接矩陣
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFINITY 65355
typedef struct{
VertexType vexs[MAXVEX];/頂點數(shù)組/
EdegeType arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
}MGraph; - 鄰接表
- 鄰接矩陣
與上一章的孩子表示法思路相同
typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode{
int adjvex反粥； /*鄰接點域卢肃，存儲該頂點的對應下標*/
EdgeType weight；/*存儲權值*/
struct EdgeNode *next;
}EdgeNode才顿；
typedef struct VertexNode{
VertexType data莫湘；
EdgeNode firstedge；
}VertexNode,AdjList[MAXVEX];
typedef struct{
AdjList adjList;
int numVertexes,numEdges;
}GraphAdjList;
* 邊集數(shù)組
![邊集數(shù)組]XO.png](http://upload-images.jianshu.io/upload_images/1318539-703d9b755b44bc94.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
* 十字鏈表
【data郑气、firstin幅垮、firstout】【tailvex、headvex尾组、headlink忙芒、taillink】
容易求得頂點的出度和入度
-
鄰接多重表
邊表結(jié)點結(jié)構
- 圖的遍歷
- 深度優(yōu)先遍歷
從圖中某個頂點v出發(fā)，訪問此頂點讳侨，然后從v的未被訪問的鄰接點出發(fā)呵萨，深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到（鄰接表） - 廣度優(yōu)先遍歷
類似于樹的前序遍歷（隊列）
- 深度優(yōu)先遍歷
- 最小生成樹
- （普里姆）prim算法
- （克魯斯卡爾）kruskal算法
- 最短路徑
- （地杰斯特拉）dijkstr算法
- （弗洛伊德）floyd算法
- 拓撲排序
八跨跨、查找
- 順序表查找
- 有序表查找
- 有序查找
- 斐波那契查找
- 插值查找
- 線性索引查找
- 稠密查找
- 到排查找
- 分塊索引
- 二叉排序樹
- 平衡二叉樹
- 多路查找樹（B樹）
- 散列表查找（哈希表）概述
- 散列函數(shù)構造方法
- 處理散列沖突方法
- 散列表的查找實現(xiàn)
九潮峦、排序
- 冒泡排序
- 簡單選擇排序
- 直接插入排序
- 希爾排序
- 堆排序
- 歸并排序
- 快速排序
