数据结构是指数据的存储结构，是带有结构特性的数据元素的集合。精心选择的数据结构可以带来更好的运行或者存储效率。数据结构是计算机科学与技术专业、软件工程专业甚至于其它电气信息类专业的重要专业基础课程，在 408 计算机学科专业基础综合考试中占有 45 分。以下为我在学习和实战练习过程中所做的笔记，可供参考。
一、基本概念
C/C++语言基础
数据类型：
- 结构型
int a[maxSize];
- 指针型
int *a;
- 链表结点
1
2
3
4
5
| typedef struct Node
{
int data;
struct Node *next;
}Node;
|
- 二叉树结点
1
2
3
4
5
6
| typedef struct BTNode
{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
|
- 动态申请数组空间
1
2
| int *p;
p=(int *)malloc(n * sizeof(int));
|
函数：
- 函数参数的引用型定义
1
2
3
4
5
6
| int a=0;
void f(int &x)
{
++x;
}
f(a);
|
- 数组作参数的引用型定义
1
| void f(int x[][maxSize], int n){···;}
|
算法的时间复杂度和空间复杂度
时间复杂度：
- $T(n)=O(f(n)中增长最快的项的系数)$
- 将最坏的情况作为算法时间复杂度的度量
- $O(1)≤O(\log{2}\left(n\right)≤O(n)≤O(n\log{2}\left(n\right)≤O(n^2)≤O(2^n)$（常对幂指阶）
- 取最深层循环内的语句所描述的操作为基本操作，由循环基本执行的次数为规模n，计算函数 $f(n)$
空间复杂度：算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间大小，空间复杂度 = 函数递归调用的深度。
数据结构基本概念
数据是对客观事物的符号表示，数据元素是数据的基本单位，数据对象是性质相同的数据元素的集合。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合
- 数据的逻辑结构是对数据之间关系的描述，分为线性结构（一个数据元素的次序集合）和非线性结构（树、图）
- 数据的存储（物理）结构是数据的逻辑结构在计算机中的表示（映像），包括数据元素的表示和关系的表示
数据元素之间的关系：顺序映像和非顺序映像
数据结构中常用储存方法：顺序存储（数组）、链式存储（指针）、索引存储 <关键字, 地址>、散列存储（根据结点的关键字通过散列函数直接计算出该结点的存储地址）
算法的基本概念
算法的特性：有穷性、确定性、输入、输出、可行性
算法的设计目标：正确性、可读性、健壮性、高效率和低存储量需求
二、线性表
线性表的基本概念
线性表是具有相同特性数据元素的一个有限序列，长度 $n≥0$
线性表只有一个表头元素，一个表尾元素，除表头表尾元素外其他元素只有一个直接前驱和一个直接后继（有序性）
顺序表：随机访问特性、要求占用连续的存储空间、做插入操作要移动多个元素
链表：不支持随机访问、结点的存储空间利用率稍低、支持存储空间的动态分配
头指针指向链表的第一个结点、头结点指向带头结点链表的第一个结点
单链表、双链表、循环单链表、循环双链表、静态链表（数据元素分量+指针分量）
线性表的结构体定义
顺序表
1
2
3
4
5
| typedef struct
{
int data[maxSize];
int length;
}Sqlist;
|
单链表
1
2
3
4
5
6
7
| typedef struct LNode
{
int data;
struct LNode *next;
}LNode
LNode *A = (LNode*)malloc(sizeof(LNode));
|
双链表
1
2
3
4
5
6
| typedef struct DLNode
{
int data;
struct DLNode *prior;
struct DLNode *next;
}DLNode;
|
顺序表的操作
插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int ListInsert(SeqList *L,int i,ElemType *e){
int k；
if(L->length==MAXSIZE)
return ERROR;
if（i<1 || i>L->length+1)
return ERROR;
if(i<=L->length)
{
for(k=L->length-1；k>=i-1；k--)
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
L->length++;
return OK;
}
|
删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int ListDelete(SqList *L,int i,ElemType *e){
int k;
if (L->length==0)
return ERROR;
if(i<1|| i>L->length)
return ERROR;
*e=L->data[i-1];
if(i<L->1ength)
{
for（k=i；k<L->length;k++)
L->data[k-1]=L->data[k];
}
L->length--；
return OK;
}
|
查找元素
1
2
3
4
5
6
7
8
| int findElem (Sqlist L, int e)
{
int i;
for (i=0; i<L.length; ++i)
if (e==L.data[i])
return i;
return -1;
}
|
求指定位置元素
1
2
3
4
5
| int getElem(Sqlist L, int p, int &e)
if(p<0||p>L.length-1)
return 0;
e=L.data[p];
return 1;
|
单链表的操作
尾插法建立链表C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void createlistR(LNode *&C, int a[], int n)
{
LNode *s, *r;
int i;
C=(LNode *)malloc(sizeof(LNode));
C->next=NULL;
r=C;
for (i=0; i<n; ++i)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=a[i];
r->next=s;
r=r->next;
}
r->next=NULL;
}
|
归并成递减的单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| void merge (LNode *A, LNode *B, LNode *C)
{
LNode *p=A->next;
LNode *q=B->next;
LNode *s;
C=A;
C->next=NULL;
free(B);
while(p!=NULL&&q!=NULL)
{
if(p->data<=q->data)
{
s=p;p->next;
s->next=C->next;
C-next=s;
}
else
{
s=q;q=q->next;
s->next=C->next;
C->next=s;
}
}
while(p!=NULL)
{
s=p;
p=p->next;
s->next=C->next;
C->next=s;
}
while(q!=NULL)
{
s=q;
q=q->next;
s->next=C->next;
C->next=s;
}
}
|
单链表获取元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int GetElem(LinkList L,int i,ElemType *e){
int j=1;
LinkList p;
p=L->next;
while(p && j<i)
{
p=p->next；
++j;
}
if(!p || j > i)
return ERROR;
*e = p->data;
return OK;
}
|
单链表插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int ListInsert(LinkList *L,int i,ElemType e)
{
int j=1；
LinkList p,s;
p=*L；
while (p && j<i)
{
p=p->next;
++j；
}
if (!p || j>i)
return ERROR;
s=(LinkList *) malloc (sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
|
双链表的操作
尾插法建立双链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void createDlistR(DLNode *&L, int a[], int n)
{
DLNode *s, *r;
int i;
L=(DLNode *)malloc(sizeof(DLNode));
L->prior=NULL;
L->next=NULL;
r=L;
for (i=0; i<n; ++i)
{
s=(DLNode *)malloc(sizeof(DLNode));
s->data=a[i];
r->next=s;
s->prior=r;
r=s;
}
r->next=NULL;
}
|
双链表寻找结点
1
2
3
4
5
6
7
8
9
10
11
| DLNoded* findNode(DLNode *C, int x)
{
DLNode *p=C->next;
while(p!=NULL)
{
if(p->data==x)
break;
p=p->next;
}
return p;
}
|
双链表插入结点
1
2
3
4
| s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
|
双链表删除结点
1
2
3
| p->prior->next = p->next;
p->next->prior = p->prior;
free(p)
|
链表的逆置
1
2
3
4
5
6
7
8
9
| ListNode* reverseList(ListNode head)
{
if(head == NULL || head->next == NULL)
return head;
ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newhead;
}
|
循环链表的操作
逆置循环链表
- 只交换节点中的数据成员 data，其他的前后指针不变
1
2
3
4
5
6
7
8
9
10
11
| void Reverse ()
{
LinkList * begin = _head;
LinkList * end = _tail;
while (begin != end && begin->_prev != end)
{
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}
}
|
删除顺序表中值在 min 和 max 之间的数
- 对顺序表进行遍历查找介于 min 与 max 之间的数然后进行删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void Delete(Seqlist *L,int min,int max)
{
int i=0,n=0;
while(i<L->length)
{
if(L->elem[i]>=min && L->elem[i]<=max)
n++;
else
L->elem[i-n]=L->elem[i];
i++;
}
L->length -= n;
if(L->length==0)
printf("the sqlist ie empty/n");
}
|
三、栈和队列
栈和队列的基本概念
栈是一种只能在一端进行插入或删除操作的线性表（FILO），栈顶（Top）动态变化，栈底固定不变
队列为仅允许在表的一端进行插入，在表的另一端进行删除的线性表（FIFO），队头（Front）可进行删除，队尾（Rear）可进行插入
栈和队列的结构体定义
顺序栈的定义
1
2
3
4
5
| typedef struct
{
int data[maxSize];
int top;
} SqStack;
|
链栈结点的定义
1
2
3
4
5
| typedef struct LNode
{
int data;
struct LNode *next;
} LNode;
|
顺序队列的定义
1
2
3
4
5
6
| typedef struct
{
int data[maxSize];
int front;
int rear;
} SqQueue;
|
链队结点的定义
1
2
3
4
5
| typedef struct QNode
{
int data;
struct QNode *next;
} QNode;
|
链队类型的定义
1
2
3
4
5
| typedef struct
{
QNode *front;
QNode *rear;
} LiQueue;
|
顺序栈
栈空状态：st.top==-1
栈满状态：st.top==maxSize-1
非法状态：栈满后继续入站上溢，栈空继续出栈下溢
定义一个栈并初始化：int stack[maxSize]; int top==-1
进栈：先移动指针再进栈
1
2
3
4
5
6
7
8
| int push(SqStack &st,int x)
{
if(st.top==maxSize-1)
return 0;
++(st.top);
st.data[st.top]=x;
return 1;
}
|
出栈：先取出元素，再移动指针
1
2
3
4
5
6
7
8
| int pop(SqStack &st,int &x)
{
if(st.stop==-1)
return 0;
x = st.data[st.top];
--(st.top);
return 1;
}
|
链栈
栈空状态：lst->next==NULL
不存在栈满状态
进栈：头插法建立链表中的插入操作
p->next=lst->next; lst->next=p;
出栈：单链表的删除操作，出栈元素保存在 x 中
p-lst->next; x=p->data; lst->next=p->next; free(p);
循环队列
解决假溢出：front=(front+1)%maxSize
队空状态：qu.rear==qu.front
队满状态：(qu.rear+1)%maxSize==qu.front
初始化队列：队首和队尾指针重合，并且指向0
进队算法
1
2
3
4
5
6
7
8
| int enQueue(SqQueue qu)
{
if((qu.rear+1)%maxSize==qu.front)
return 0
qu.rear=(qu.rear+1)%maxSize;
qu.data[qu.rear]=x;
return 1;
}
|
出队算法
1
2
3
4
5
6
7
8
| int denQueue(SqQueue &qu, int &x)
{
if(qu.rear==qu.front)
return 0;
qu.front=((qu.front+1)%maxSize)
x=qu.data[qu.front];
return 1;
}
|
链队（尽量避免使用）
队空状态：lqu->rear==NULL 或者 lqu->front==NULL
不存在队满状态
初始化链队
1
2
3
4
5
| void initQueue(LiQueue *&lqu)
{
lqu=(LiQueue*)malloc(sizeof(LiQueue));
lqu->front=lqu->rear=NULL;
}
|
进队操作：lqu->rear->next=p; lqu->rear=p;
出队操作：p=lqu->front; lqu->front=p->next; x=p->data; free(p);
用队列实现栈
入栈：push(x)，除栈顶元素：pop() — 移，获取栈顶元素：top() ，返回栈是否为空：empty()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
void push(int x)
{
q1.push(x);
}
int pop()
{
int length1 = q1size();
for(int i-0; i< length1- 1; i++)
{
q2.push(q1.front());
q1. pop();
}
data= q1.front()
int length2= q2size():
for(int j=0;j< length2; j++)
{
q1.push(q2.front());
q2.pop();
}
return data;
}
int top()
int length1 = q1.size();
int data;
for (int i=0; i< length1- 1; i++)
{
q2.push(q1.front());
q1.pop();
}
data= q1.front();
return data;
}
bool empty()
{
if(q1.empty()&&q2.empty())
return true;
else
return false;
}
|
四、串
串数据类型的定义
串是限定了元素为字符的线性表，char str[]="abcdef";
空格串不是空串
串赋值：对数组中的每个元素进行逐一赋值操作
strassign(str,"cur input");
取串长度
串比较操作
1
2
3
4
5
6
7
| int strcompare(Str s1, Str s2)
{
for(int i=0;i<s1.length&&i<s2.length;++i)
if(s1.ch[i]!=s2.ch[i])
return s1.ch[i]-s2.ch[i];
return s1.length - s2.length;
}
|
串的模式匹配算法
KMP 算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| void getnext(str substr, int next[])
{
int i=1, j=0;
next[1]=0;
while (i<substr.length)
{
if (j==0||substr.ch[i]==substr.ch[j])
{
++i, ++j;
next[i]=j;
}
else
j=next[j];
}
}
int KMP (Str str, Str substr, int next[])
{
int i=j=1;
while(i<=str.length&&j<=substr.length)
{
if (j==0||str.ch[i]==substr.ch[j])
++i, ++j;
else
j=next[ j];
if (j>substr.length)
return i-substr.length;
else
return 0;
}
}
|
五、矩阵与广义表
矩阵
矩阵的转置
1
2
3
4
5
6
| void trsmat(int A[][maxSize],int B[][maxSize],int m, int n)
{
for (int i = 0;i < m;++i)
for (int j = 0;j < n;++j)
B[j][i] = A[i][j];
}
|
矩阵相加
1
2
3
4
5
6
| void addmat(int C[][maxSize],int A[][maxSize],int B[][maxSize],int m, int n)
{
for (int i = 0;i < m;++i)
for (int j = 0;j < n;++j)
C[i][j] = A[i][j] + B[i][j];
}
|
矩阵相乘
1
2
3
4
5
6
7
8
9
10
| void amutmat(int C[][maxSize],int A[][maxSize],int B[][maxSize],int m, int n,int k)
{
for (int i = 0;i < m;++i)
for (int j = 0;j < k;++j)
{
C[i][j] = 0;
for int(h = 0;h < n;++h)
C[i][j] += A[i][j] * B[i][j];
}
}
|
相同的元素或者零元素在矩阵中分布存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵
广义表
表元素可以是原子或者广义表的一种线性表的扩展结构
广义表可以是递归定义的，长度为表最上层元素的个数，深度为表中括号的最大的层数
当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾
原子结点有两个域：标志域和数据域
广义表结点有三个域：标志域，头指针域与尾指针域
六、树
树的基本概念
树是一种非线性的数据结构，是若干个结点的集合，由唯一的根和若干个互不相交的子树组成
- 结点不仅包含数据元素，并且包含指向子树的分支
- 结点的度是结点拥有的子树个数或者分支个数，树的度是树中各结点度的最大值
- 树的高度是树中结点的最大层次，根结点的高度为树的高度
树的双亲存储结构：int tree[maxSize]
树的链式存储结构
二叉树的概念和性质
二叉树的定义
- 每个结点最多只有两颗子树，即二叉树中的结点的度只能为0、1、2
- 子树有左右顺序之分，不能颠倒
满二叉树：在一颗二叉树中，如果所有的分支节点都有左、右孩子节点，并且叶子节点都集中在二叉树的最下一层
完全二叉树由满二叉树从右至左、从上之下挨个删除结点得到的
二叉树的主要性质
- 非空二叉树上叶子结点数等于双分支结点数加1，$n_0=n_2+1$
- 在二叉树的第 $i$ 层上最多有 $2^{i-1}$个节点，$(i>=1)$
- 二叉树中如果深度为 $k$，那么最多有 $2^{k-1}$ 个节点，$(k>=1)$
若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
- 若 i=1，则该结点是二叉树的根，无双亲，否则编号为 $\lfloor i/2\rfloor$ 的结点为其双亲结点（向下取整）
- 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点
- 若 2i+1>n，则该结点无右孩子，否则，编号为2i+1 的结点为其右孩子结点
- Catalan()：给定 n 个结点，能够成 $h\left( n\right) =\dfrac{C_{2n}^{n}}{n+1}$ 棵不同的二叉树
- 在完全二叉树中，具有n个节点的完全二叉树的深度为 $\lfloor log2n\rfloor+1$
二叉树的顺序存储结构最适用于完全二叉树
二叉树的链式存储结构
1
2
3
4
5
6
| typedef struct BTNode
{
char data;
struct BTNoode* lchild;
struct BTNode* rchild;
} BTNode;
|
二叉树的遍历算法
先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
void PreTraverseTree2(BitNode * root)
{
StackNode* S;
BitNode* p;
S = NULL;
p = root;
S = InitStack(S);
if (NULL == p)
{
printf("树为空！\n");
return;
}
while (p || !StackEmpty(S))
{
if (p)
{
StackPush(S, p);
printf("%c ", p->data);
p = p->lchild ;
}
else
{
StackPop(S, p);
p = p->rchild;
}
}
free(S);
}
void preOrder(BiTNode *root)
{
if (root)
{
printf("%d ", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
void InOrderTraverseTree2(BitNode* root)
{
StackNode* S;
BitNode* p;
S = NULL;
p = root;
S = InitStack(S);
if (NULL == p) {
printf("树为空！\n") ;
return;
}
while (p || !StackEmpty(S)) {
if (p)
{
StackPush(S, p);
p = p->lchild;
}
else
{
StackPop(S, p);
printf("%c ", p->data);
p = p->rchild;
}
}
free(S);
}
void inOrder(BiTNode* root)
{
if (root)
{
inOrder(root->lchild);
printf("%d ", root->data);
inOrder(root->rchild);
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
void LastTraverseTree2(BiTNode* root)
{
StackNode* S; BiTNode* cur, * pre;
S = NULL; S = InitStack(S);
if (NULL == root)
{
printf("树为空！\n");
return;
}
pre = NULL; cur = NULL;
StackPush(S, T);
while (!StackEmpty(S))
{
cur = NULL;
StackGetTop(S, cur);
if ((cur->lchild == NULL && cur->rchild == NULL) ||
(pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
{
printf("%c ", cur->data);
pre = cur;
StackPop(S, cur);
}
else
{
if (cur->rchild != NULL)
StackPush(S, cur->rchild);
if (cur->lchild != NULL)
StackPush(S, cur->lchild);
}
}
free(S);
}
void postOrder(BiTNode* root)
{
if (root)
{
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d ", root->data);
}
}
|
层次遍历：自上而下，自左向右
- 首先，将二叉树的祖先节点入队列
- 然后循环执行以下步骤，直到队列为空：节点出队列进行相应操作，该节点如果有左孩子节点，左孩子节点入队列，该节点如果有右孩子节点，右孩子节点入队
1
2
3
4
5
6
7
8
9
10
11
12
13
| void LayerOrder(BiTreeNode* head)
{
LQueue Q;
Initiate_Queue(&Q);
BiTreeNode* p;
if (head != NULL) AppendQueue(&Q, head);
while (QueueNotEmpty(&Q)) {
p = QueueDelete(&Q);
cout << p->data << " ";
if (p->LChild != NULL) AppendQueue(&Q, p->LChild);
if (p->RChild != NULL) AppendQueue(&Q, p->RChild);
}
}
|
哈夫曼树和哈夫曼编码
哈夫曼树又叫做最优二叉树，它的特点是带权路径最短
- 树的路径长度是指从根到每个节点的路径长度之和
- 带权路径长度是从该节点到根节之间的路径长度乘以结点的权值
- 树的带权路径长度（WPL）是指树中所有叶子节点的带权路径长度之和
求哈夫曼树的带权路径长度：WPL = 第 i 个节点的权值+ 第i个节点的长度
1
2
3
4
5
6
7
8
9
10
11
12
| ElemType WeightPathLength(struct BTreeNode* FBT, int len)
{
if (FBT == NULL)
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)
return FBT->data * len;
else
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
|
哈夫曼树的构造方法：根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)
{
int k1 = -1, k2;
for (j = 0; j < n; j++)
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;
b[k2] = NULL;
}
free(b);
return q;
}
|
哈夫曼编码
- 每个字符对应一个二进制编码，采用不等长编码方式，构造哈夫曼树
- 将每个字符的出现频率作为字符结点的权值赋予叶子结点，每个分支结点的左右分支分别用0和1编码
- 从树根结点到每个叶子结点的路径上所经分支的0、1编码序列等于该叶子结点的二进制编码
- 哈夫曼编码产生的是最短前缀码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void HuffManCoding(struct BTreeNode* FBT, int len)
{
static int a[10];
if (FBT != NULL)
{
if (FBT->left == NULL && FBT->right == NULL)
{
int i;
printf("结点权值为%d的编码：", FBT->data);
for (i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
else
{
a[len] = 0;
HuffManCoding(FBT->left, len + 1);
a[len] = 1;
HuffManCoding(FBT->right, len + 1);
}
}
}
|
七、图
图的基本概念
图由结点的有穷集合的 V 和边的集合 E 组成（G(V,E)）
图是按照无方向和有方向分为无向图和有向图，无向边用 $(v_i,v_j)$ 表示，有向边用 $$ 表示
路径长度：路径上边或者弧的数目
顶点的度：顶点关联边的数目
- 有向图中：方向指向顶点的边为入度；方向背向顶点的边为出度
- 在有向图中，顶点的度就是两者之和
- 在无向图中，任意两个顶点是相通的就是连通图，它的极大连通子图为连通分量
- 在向图中，任意两个顶点间互相都存在路径的就是强连通图，它的极大强连通子图为强连通分量
图的存储结构
邻接矩阵
- 图的顺序存储结构
- 用两个数组保存数据：一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息
- 无向图中邻接矩阵是个对称矩阵
- 0表示无边，1表示有边
- 顶点的度是行内数组之和，有向图中各行之和是出度，各列之和是入度
- 邻接矩阵对于边数相对顶点较少的图，就是对存储空间极大的浪费
1
2
3
4
5
6
7
8
9
10
11
| typedef struct
{
int no;
char info;
} VertexType;
typedef struct
{
int edges[maxSize][maxSize];
int n,e;
VertexType vex[maxSize];
} MGragh;
|
邻接表
- 数组和链表相结合的存储方法，图的链式存储结构
- 图中顶点用一个一维数组存储
- 图中每个顶点 $V_i$ 的所有邻接点构成一个线性表
- 顶点表的各个结点由 data 和 Firstedge 两个域表示
- data 是数据域，存储顶点信息
- firstedge 是指针域，指向边表的第一个结点，即顶点的第一个邻接点
- 边表结点由 adjvex 和 next 两个域组成
- adjvex 是邻接点域，存储某顶点的邻接点在顶点表中坐标
- next 存储边表中下一个结点指针
- 有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| typedef struct ArcNode
{
int adnex;
struct ArcNode * nextarc;
int info;
} ArcNode;
typedef struct
{
char data;
ArcNode* firstarc;
}VNode;
typedef struct
{
VNode adjlist[maxSize];
int n, e;
} AGraph;
|
十字链表
- 在邻接表中针对有向图，分为邻接表和逆邻接表，导致无法从一个表中获取图的入读和出度的情况，有人提出了十字链表
- 定点表
- firstin：入边表头指针，指向顶点入边表的第一个结点
- firstout：出边表头指针，指向顶点出边表第一个结点
- 边表
- tailvex 是指弧起点在顶点表的下标，headvex 弧终点在顶点表的下标
- headlink 入边表指针域，指向终点相同的下一条边
- taillink 是指边表指针域，指向起点相同的下一条边
邻接多重表
- ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标
- ilink 指向依附项点 ivex 的下一条边
- jlink 指向依附顶点 jvex 的下一条边
图的遍历算法
深度优先遍历（DFS，Depth First Search）
- 首先从图中某个顶点 $v_0$ 出发，访问此顶点，然后依次从 $v_0$ 相邻的顶点出发 深度优先遍历，直至图中所有与 $v_0$ 路径相通的顶点都被访问了
- 若此时尚有顶点未被访问， 则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问
- 深度优先遍历是一个递归的过程，这种遍历过程类似树的先序遍历，均是先访问节点，再从该节点出发继续向下遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool visited[Max_Vex];
void DFSTraverse(Graph G)
{
for (v = 0;v < G.vexnum;++v)
visited[v] = false;
for (v = 0;v < G.vexnum;++v)
if (!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v)
{
visit(v);
visited[v] = true;
for (w = FirstNeighbor(G, v);w >= 0;w = NextNeighbor(G, v, w))
if (!visited[w])
DFS(G, w);
}
|
广度优先遍历（BFS，Breadth First Search）
- 首先从图的某个顶点 $v_0$ 出发，访问了 $v_0$ 之后，依次访问与 $v_0$ 相邻的未被访 问的顶点
- 然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完
- BFS 遍历的方式类似于树的层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| bool visited[Max_Vex];
void BFSTraverse(Graph G)
{
for (i = 0;i < G.vexnum;++i)
visited[v] = false;
InitQueue(Q);
for (v = 0;v < G.vexnum;++v)
if (!visited[v])
BFS(G, v);
}
void BFS(Graph G, int v)
{
visit(v);
visited[v] = true;
while (!isEmpty(Q))
{
DeQueue(Q, v);
for (w = FirstNeighbor(G, v);w >= 0;w = NextNeighbor(G, v, w))
if (!visited[w])
{
visit(w);
visited[w] = true;
EnQueue(Q, w)
}
}
}
|
最小生成树
Prim 算法
- 从图中仼意取出一个顶点，把它当成一棵树，然后从与这棵树相接的边中选取一条最短（权值最小）的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树
- 然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连顶点并入当前树中，得到一棵有3个顶点的树
- 以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树
1
2
3
4
5
6
7
8
9
10
11
| void prim (G,T)
{
T = ∅;
U = {w};
while ((V - U) != ∅ )
{
设 (u，v) 是使 u∈U 与 v∈ (V-U)，且权值最小的边;
T = T∪ (u，v);
U = U∪ {v};
}
}
|
Kruskal 算法
- 将图中边按照权值从小到大排序，然后从最小边开始扫描各边，并检测当前边是否为候选边，即是否该边的并入会构成回路，如不构成回路，则将该边并入当前生成树中，直到所有边都被检测完为止
- Kruskal 算法的时间复杂度主要由选取的排序算法决定，排序算法所处理数据的规模由图的边数e 决定，与顶点数无关，因此克鲁斯卡尔算法适用于稀疏图
- 普里姆算法和克鲁斯卡尔算法都是针对于无向图的
- 判断是否产生回路要用到并查集，并查集中保存了一棵或者几棵树
- 通过树中一个结点，可以找到其双亲结点，进而找到根结点（可以快速地将两个含有很多元素的集合并为一个，两个集合就是并査集中的两棵树，只需找到其中一棵树的根，然后将其作为另一棵树中任何个结点的孩子结点即可，可以方便地判断两个元素是否属于同一个集合
- 通过这两个元素所在的结点找到它们的根结点，如果它们有相同的根，则说明它们属于同一个集合，否则属于不同集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void kruskal（V，T）
{
T = V;
numS = n;
while (numS > 1)
{
从 E 中取出权值最小的边（v,u）;
if（v 和 u 属于 T 中不同的连通分量）
{
T = T∪（u，v）;
numS--;
}
}
}
|
最短路径
Dijkstra 算法
- 通常用于求图中某一顶点到其余各顶点的最短路径
- 设 G=(V,E) 是一个带权有向图，把图中顶点集合 V 分成两组
- 第一组为已求出最短路径的顶点集合（用 S 表示，初始时 S 中只有一个源点，,以后每求得一条最短路径就将求得的顶点加入到集合 S 中，直到全部顶点都加入到 S 中）
- 第二组为其余未确定最短路径的顶点集合（用 U 表示），按最短路径长度的递增次序依次把第二组的顶点加入 S 中，在加入的过程中，总保持从源点 V 到 S 中各顶点的最短路径长度不大于从源点 V 到 U 中任何顶点的最短路径长度
Dijkstra 算法步骤
- 初始时，S 只包含源点，即 S＝{v}，v 的距离为 0，U 包含除 v 外的其他顶点，即:U={其 余顶点}，若 v 与 U 中顶点 u 有边，则正常有权值，若 u 不是 v 的出边邻接点，则 权值为 $∞$
- 从 U 中选取一个距离 v 最小的顶点 k，把 k 加入 S 中（该选定的距离就是 v 到 k 的最短路 径长度）
- 以 k 为新考虑的中间点，修改 U 中各顶点的距离值：若从源点 v 到顶点 u 的距离（经过顶点 k）比原来距离（不经过顶点 k）短，则修改顶点 u 的距离值，修改后的距离值为 v 到 k 的距离加上 k 到 u 的距离
- 重复步骤 b 和 c 直到所有顶点都包含在 S 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| void Dijkstra(int v0)
{
bool S[MAXNUM];
int n=MAXNUM;
for(int i=1; i<=n; ++i)
{
dist[i] = A[v0][i];
S[i] = false;
if(dist[i] == MAXINT)
prev[i] = -1;
else
prev[i] = v0;
}
dist[v0] = 0;
S[v0] = true;
for(int i=2; i<=n; i++)
{
int mindist = MAXINT;
int u = v0;
for(int j=1; j<=n; ++j)
if((!S[j]) && dist[j]<mindist)
{
u = j;
mindist = dist[j];
}
S[u] = true;
for(int j=1; j<=n; j++)
if((!S[j]) && A[u][j]<MAXINT)
{
if(dist[u] + A[u][j] < dist[j])
{
dist[j] = dist[u] + A[u][j];
prev[j] = u;
}
}
}
}
|
Floyd 算法
- Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包
- Floyd-Warshall 算法的时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$
- Floyd 算法是一个经典的动态规划算法，目标是寻找从点 i 到点 j 的最短路径，假设 Dis(i,j) 为节点 u 到节点 v 的最短路径的距离
- 对于每一个节点 k，检查 Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，证明从 i 到 k 再到 j 的路径比 i 直接到j的路径短，便设置 Dis(i,j) = Dis(i,k) + Dis(k,j)，这样当遍历完所有节点 k，Dis(i,j) 中记录的便是 i 到 j 的最短路径的距离
Floyd 算法步骤
- 从任意一条单边路径开始，所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大
- 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短，如果是更新它
1
2
3
4
5
| for (k = 1;k <= n;k++)
for (i = 1;i <= n;i++)
for (j = 1;j <= n;j++)
if (a[i][j] > a[i][k] + a[k][j])
a[i][j] = a[i][k] + a[k][j];
|
拓扑排序
对一个有向无环图 G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若存在由 u 到 v 的路径，则在拓扑排序序列中一定是 u 出现在 v 的前边
- 从 DAG 图中选择一个没有前驱的节点并输出
- 从图中删除该节点和所有以它为起点的有向边
- 重复上两步直到当前的 DAG 图为空或不存在无前驱的顶点为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| bool topologicalSort(Graph GL)
{
EdgeNode* e;
int top = 0;
int count = 0;
int* stack;
stack = (int*)malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
if (0 == GL->adjList[i].in)
stack[++top] = i;
while (top != 0)
{
gettop = stack[top--];
printf("%d -> ", GL->adjList[gettop].data);
count++;
for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
k = e->adjvex;
if (!(--GL->adjList[k].in))
stack[++top] = k;
}
}
if (count < GL->numVertexes) return false;
else return true;
}
|
八、排序
排序的基本概念
排序：将原本无序的序列重新排列成有序序列的过程，这个序列中的每一项可能是单独的数据元素，也可能是一条记录
记录由多个数据元素组成的，既可以按照记录的主关键字排序（主关键字唯一标识一条记录），也可以按照记录的次关键字排序
稳定性：当待排序序列中有两个或两个以上相同的关键字时，排序前和排序后这些关键字的相对位置，如果没有发生变化就是稳定的，否则就是不稳定的
排序算法的分类
- 插入类的排序：直接插入、折半插入、希尔排序
- 交换类的排序：冒泡排序、快速排序
- 选择类的排序：简单选择、堆选择
- 归并类的排序：二路归并
- 基数类的排序：多关键字排序
插入类的排序
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
| void InsertSort(int* h, size_t len)
{
if(h==NULL) return;
if(len<=1) return;
int i,j;
for(i=1;i<len;++i)
for(j=i;j>0;--j)
if(h[j]<h[j-1]) Swap(h[j],h[j-1]);
else break;
return;
}
|
希尔排序
- 缩小增量排序：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序
- 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
1
2
3
4
5
6
7
8
9
10
11
12
| void ShellSort(int* h, size_t len)
{
if(h==NULL) return;
if(len<=1) return;
for(int div=len/2;div>=1;div/=2)
for(int k=0;k<div;++k)
for(int i=div+k;i<len;i+=div)
for(int j=i;j>k;j-=div)
if(h[j]<h[j-div]) Swap(h[j],h[j-div]);
else break;
return;
}
|
交换类的排序
快速排序
1
2
3
4
5
6
7
8
9
| void QuickSort(SeqList R，int low，int high)
{
int pivotpos；
if (low < high) {
pivotpos = Partition(R，low，high)；
QuickSort(R，low，pivo t pos-1)；
QuickSort(R，pivotp o s+1，high)；
}
}
|
冒泡排序
- 通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置
1
2
3
4
5
6
7
8
9
10
11
| void BubbleSort(int* h, size_t len)
{
if(h==NULL) return;
if(len<=1) return;
for(int i=0;i<len-1;++i)
for(int j=0;j<len-1-i;++j)
if(h[j]>h[j+1])
Swap(h[j],h[j+1]);
return;
}
|
选择类的排序
选择排序
- 初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列，然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
- 每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void SelectionSort(int* h, size_t len)
{
if(h==NULL) return;
if(len<=1) return;
int minindex,i,j;
for(i=0;i<len-1;++i)
{
minindex=i;
for(j=i+1;j<len;++j)
{
if(h[j]<h[minindex]) minindex=j;
}
Swap(h[i],h[minindex]);
}
return;
}
|
堆排序
- 堆实际上是一棵完全二叉树，堆的每一个父节点都大于（或小于）其子节点，堆的每个左子树和右子树也是一个堆
- 最大堆（大顶堆）：堆的每个父节点都大于其孩子节点；最小堆（小顶堆）：堆的每个父节点都小于其孩子节点
- 堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共 n 个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第 n-1 个元素。所以，如果需要升序，就建一个大堆，需要降序，就建一个小堆
1
2
3
4
5
6
7
8
9
10
11
12
| void HeapSort(SeqIAst R)
{
int i；
BuildHeap(R)；
for (i = n;i > 1； i -)
{
R[0] = R[1];
R[1] = R[i];
R[i] = R[0];
Heapify(R，1 ，i-1);
}
}
|
二路归并排序
MERGE-SORT：利用归并的思想实现的排序方法，采用经典的分治（divide-and-conquer）策略
递归拆分子序列，将两个已经有序的子序列合并成一个有序序列
1
2
3
4
5
6
7
8
9
10
| void MergeSortDC(SeqList R，int low，int high)
{
int mid；
if(low<high){
mid=(low+high)/2；
MergeSortDC(R，low，mid);
MergeSortDC(R，mid+1，high)；
Merge(R，low，mid，high)；
}
}
|
基数排序
不需要比较关键字的大小，根据关键字中各位的值，通过对排序的N个元素进行若干趟分配与收集来实现排序的
时间复杂度为 $O\left( d\left( n+r_{d}\right) \right)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| int GetMaxDight(int* h, int len)
{
if(h==NULL) return 0;
if(len<1) return 0;
int max=h[0];
for(int i=1;i<len;++i)
{
if(h[i]>max) max=h[i];
}
int digit=1;
while(max/10!=0)
{
max/=10;
++digit;
}
return digit;
}
int GetReminder(int value,int digit)
{
int div=1;
for(int i=1;i<digit;++i)
div*=10;
return value/div%10;
}
void RadixSort_LSD(int* h, int len)
{
if(h==NULL) return;
if(len<=1) return;
int digit=GetMaxDight(h,len);
int count[10]={0};
int *tmp=(int*)calloc(len,sizeof(int));
for(int d=1;d<=digit;++d)
{
memset(count,0,sizeof(count));
for(int i=0;i<len;++i)
{
count[GetReminder(h[i],d)]++;
}
for(int i=1;i<10;++i)
{
count[i]+=count[i-1];
}
for(int i=len-1;i>=0;--i)
{
int r=GetReminder(h[i],d);
int index=count[r];
tmp[index-1]=h[i];
count[r]--;
}
memcpy(h,tmp,len*sizeof(int));
}
free(tmp);
}
void RadixSort_LSD_Reverse(int* h, int len)
{
if(h==NULL) return;
if(len<=1) return;
int digit=GetMaxDight(h,len);
int count[10]={0};
int *tmp=(int*)calloc(len,sizeof(int));
for(int d=1;d<=digit;++d)
{
memset(count,0,sizeof(count));
for(int i=0;i<len;++i)
{
count[GetReminder(h[i],d)]++;
}
for(int i=8;i>=0;--i)
{
count[i]+=count[i+1];
}
for(int i=len-1;i>=0;--i)
{
int r=GetReminder(h[i],d);
int index=count[r];
tmp[index-1]=h[i];
count[r]--;
}
memcpy(h,tmp,len*sizeof(int));
}
free(tmp);
}
|
排序知识点总结
快速排序、希尔排序、归并排序、堆排序的平均时间复杂度都是 $O\left( n\log _{2}n\right)$，其他都是 $O(n^2)$
快速排序的空间复杂度为 $O\left( \log {2}n\right)$，归并排序的空间复杂度为 $O\left( n\right)$，基数排序的空间复杂度为 $O\left( r{d}\right)$，其他都是 $O(1)$
快速排序、希尔排序、简单选择排序、堆排序是不稳定的，其他都是稳定的
交换类和选择类的排序，经过一趟排序能够保证一个关键字到达最终位置
简单选择排序和折半插入排序的关键字比较次数和原始序列无关
交换类的排序趟数和原始序列有关
直接插入按顺序查找的方式，而折半插入按折半查找的方式排序
借助于比较进行排序的算法在最坏情况下的时间复杂度至少为 $O\left( n\log _{2}n\right)$
九、查找
查找的基本概念
给定一个值 K，在含有 n 个记录的表中找出关键字等于 K 的记录叫查找，记录即为关键字
通常把查找过程中对关键字的平均比较次数（也称平均查找长度）作为衡量一个查找算法优劣的标准
平均查找长度 $ASL=\sum ^{n}{i=1}p{i}\times c_{i}$
- $p{i}$ 为查找第 i 个记录的概率，$c{i}$ 为找到第 i 个记录所需要进行比较的次数（查找长度）
顺序查找
- 用待查找的关键字和给定序列中的各元素的关键字从左到右（或从右到左）依次进行比较，直到成功或失败
- 存储结构通常是顺序结构，也可是链式结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
int SeqSearch(SSTable S, DataType x)
{
int i = 0;
while (i > s.length & S.list[i].key != x.key)
i++;
if (s.list[i].key == x.key)
return i + 1;
return 0;
}
int SeqSearch2(SSTable S, DataType x)
{
int i = S.length;
s.list[o].key = x.key;
while (s.list[i].key != x.key)
i--;
return i;
}
Node* Search(Lnode* head, int key)
{
LNode* p = head->next;
while (p != NUll)
{
if (P->data == key)
return p;
p = p->next;
}
return NULL;
}
|
二分查找
- 要求线性表是有序的
- 在给定序列是有序表的前提下，将表中间位置处的关键字和查找关键字比较，相 等则查找成功
- 否则从中间位置将表分成前后两个子表，如果中间位置处的关键字大于 查找关键字，则进一步查找前子表，否则查找后子表
- 重复以上过程，直到找到满足条件的记录，此时查找成功，或直到子表不存在为止，表示查找失败
1
2
3
4
5
6
7
8
9
10
11
12
| int BSearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid == key])
return mid;
else if (arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
|
二叉排序树（BST）
二叉排序树要么是空树,要么是满足下列要求的树
- 若它的左子树不空，则左子树上所有的关键字的值均小于根节点关键字值
- 若它的右子树不空，则右子树上所有的关键字的值均大于根节点关键字值
- 左右子树又各是一棵二叉排序树
Binary Search Tree 又被叫做二叉搜索树 or 二叉查找树
在对某个关键字进行查找的时候，首先和二叉排序树的根节点进行比较，若相等则査找成功
由于二叉排序树本身的性质，若该关键字小于根节点值，则再与其左子树进行比较,否则和其右子树进行比较，直到找到与之相等的节点，则查找成功
若待比较的位置来到空指针处，则表示査找失败，返回失败的标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
BTNode* BSTSearch(BTNode* p, int key) {
while (p != NULL) {
if (key == p->key)
return p;
else if (key < p->key)
p = p->lChild;
else
p = p->rChild;
}
return NULL;
}
BTNode* BSTSearch2(BTNode* p, int key) {
if (p == NULL)
return NULL;
else{
if (key == p->key)
return p;
else if (key < p->key)
return BSTSearch2(p->lChild, key);
else
return BSTSearch2(p->rChild, key);
}
}
|
平衡二叉树（AVL 树）
平衡二叉树是一种特殊的二叉排序树，其左右子树都是平衡二叉树且左右子树高度之差的绝对值不超过1
一个节点的平衡因子为其左子树的高度减去右子树的高度，对于平衡二叉树，树中所有结点的平衡因子取值只可能是-1、0、1
若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，则首先要找出插入新节点后失去平衡的最小子树，然后再调整这颗子树使之成为平衡子树
当失去平衡的最小子树被调整为平衡子树后，无需调整原有其他所有的不平衡子树
最小不平衡子树：是以距离插入结点最近且以平衡因子绝对值大于1的结点作为跟的子树，又称为失去平衡的最小子树
散列表
Hash：根据给定的关键字来计算出关键字在表中的地址
Hash table（哈希表）：是根据关键码值（Key value）而直接进行访问的数据结构，=通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫做散列表
给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希表，函数 f(key) 为哈希函数
键（key）：又称为关键字。唯一的标示要存储的数据，可以是数据本身或者数据的一部分
槽（slot/bucket）：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器
哈希函数（hash function）：将 key 映射 map 到数据应该存放的槽 slot 所在位置的函数
哈希冲突（hash collision）：哈希函数将两个不同的键映射到同一个索引的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int h1(int x){
return (x%5);
}
int h2(char* x){
int i,sum;
for(sum=0, i=0; x[i] != '\0'; i++)
sum += (int)x[i];
return (sum%5);
}
int ELFhash(char*key)
{
unsigned long h=0;
while(*key)
{
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if(g)
h ^= g >> 24;
h &= ~g;
}
return h % MOD;
}
|
散列表的性能分析（查找成功时的平均查找长度）：找到表中已有表项的平均次数
装填因子是关键字个数和表长度的比值
十、常用算法补充
动态规划算法
- 处理多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态
- 这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）
- 动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for (j = 1; j <= m; j = j + 1)
xn[j] = 初始值;
for (i = n - 1; i > = 1; i = i - 1)
for (j = 1; j >= f(i); j = j + 1)
xi[j] = j = max{ g(xi - 1[j1:j2]), ...... , g(xi - 1[jk:jk + 1]) };
t = g(x1[j1:j2]);
print(x1[j1]);
for (i = 2; i <= n - 1; i = i + 1)
{
t = t - xi - 1[ji];
for (j = 1; j >= f(i); j = j + 1)
if (t = xi[ji])
break;
}
|
贪心算法
- 在对问题求解时，总是做出在当前看来是最好的选择，局部最优解
- 整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的
- 贪心算法建立哈夫曼树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include <bits/stdc++.h>
using namespace std;
typedef struct BTreeNode
{
int data;
struct BTreeNode* left;
struct BTreeNode* right;
}btreenode;
btreenode *CreateHuffman(int a[],int n)
{
int i;
btreenode *s[n+1], *ss;
for(int i = 0;i<n;i++){
s[i] = new btreenode;
s[i]->data = a[i];
s[i]->left = s[i]->right = NULL;
}
for(int i = 1;i<n;i++){
int k = -1,t;
for(int j = 0;j<n;j++){
if(s[j]&&k==-1){
k = j;
continue;
}
if(s[j]){
t = j;
break;
}
}
for(int i = t;i<n;i++){
if(s[i]){
if(s[i]->data<s[k]->data){
t = k;
k = i;
}
else if(s[i]->data<s[t]->data){
t = i;
}
else{
;
}
}
}
ss = new btreenode;
ss->data = s[k]->data+s[t]->data;
ss->left = s[k];
ss->right = s[t];
s[k] = ss;
s[t] = NULL;
}
free(s);
return ss;
}
int WeightPathLength(btreenode* FBT, int len){
if(!FBT){
return 0;
}
else{
if(FBT->left ==NULL&&FBT->right ==NULL)
return FBT->data*len;
else{
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
void HuffManCoding(btreenode* FBT, int len){
static int a[20];
if(FBT){
if(FBT->left == NULL&&FBT->right == NULL){
printf("结点权值为%d的编码:",FBT->data);
for(int i = 0;i<len;i++){
printf("%d",a[i]);
}
printf("\n") ;
}
else{
a[len] = 0;
HuffManCoding(FBT->left,len+1);
a[len] = 1;
HuffManCoding(FBT->right,len+1);
}
}
}
int main(){
btreenode *s;
int n;
printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n：");
while(true){
scanf("%d",&n);
if(n>0){
break;
}
else{
printf("-------输入不合法,请重新输入!!\n");
}
}
int *a = (int *)malloc(n *sizeof(int));
printf("从键盘输入%d个整数作为权值:",n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
s = CreateHuffman(a,n);
printf("哈夫曼树的带权路径长度：");
printf("%d\n", WeightPathLength(s, 0));
printf("树中每个叶子结点的哈夫曼编码：\n");
HuffManCoding(s,0);
return 0;
}
|