数据结构简单学习笔记
原文链接：https://blog.csdn.net/qq_39355828/article/details/110842561 (opens new window)
# 1.栈在括号匹配中的应用：
//括号匹配问题
bool bracketCheck(char str[],int length)
{
SqStack S;
InitStack(S
for(int i=0;i<length;i++)
{
if(str[i]='('||str[i]='['||str[i]='{')
{
Push(S,str[i]);
}
else{
char topElem;
Pop(S,toElem);
if(str[i]==')'&&toElem!='(')
return false;
if(str[i]==']'&&toElem!='[')
return false;
if(str[i]=='}'&&toElem!='{')
return false;}
}
return StackEmpty(S);//检索完全部括号，则说明匹配成功
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 2.栈在表达式求值中的应用
操作数，运算符，界限符
波兰式和逆波兰式
后缀表达式的手写计算方法，从左向右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行相应运算，
# 3.栈在函数调用中的应用
将原始问题转化为属性相同，但规模比较小的问题。递归算法存在复杂计算。队列可用于图的广度优先遍历。
# 4.矩阵的压缩存储
二维数组的存储方式：行优先，列优先
b[i][j]=LOC+((i*N+j)*sizeof(ElemType);
# 5.串
串的长度，定义。
字串：任意个来内需的字符组成的子序列
串：顺序存储，链式存储，
int Index(SString S,SString T)
{
int i=1,n=Strlength(S),m=Strlength(T);
SString sub;
while(i<n-m+1)
{
Sub(sub,S,i,m);//从S中找出长度和T等长的字符串，存储在sub中，并不断向下移动
if(StrCompare(sub,T)!=0) i++;//比较字符串，查找不对，则继续向下
else return i;//返回字串在主串中的位置
}
return 0；
}
/*---------------------------------------------------------------------*/
#define MAXLEN 255
typedef struct
{
char ch[MAXLEN];//静态数组，系统自动回收
int length;
}SString;
typedef struct
{
char *ch;
int length;
}HString;//动态数组实现，需要自己手动free回收
HString S;
S.ch=(char *)malloc(MAXLEN*sizeof(char));
S.length=0;
//求子串,从某个位置开始截取特定长度字符串。
bool SubString(SString &Sub,SString S,int pos,int len)
{
if(pos+len-1>S.length)
return false;
for(int i=pos;i<pos+len;i++)
{
Sub.ch[i-pos+1]=S.ch[i];
Sub.length=len;
return true;
}
}
//比较两个字符大小
int StrCompare(SString S,SString T)
{
for(i=1；i<=S.length&&i<T.length;i++)
{
if(S.ch[i]!=T.ch[i])
{
return S.ch[i]-T.ch[i];
}
}
return S.length-T.length;
}
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
串的模式匹配
1.朴素模板匹配方法（算法复杂度O（m））
int Index(SString S,SString T)
{
int i=1;
}
int Index(SString S,SString T)
{
int k=1;
int i=k.j=1;
while(i<=S.length&&j<T.length)
{
if(S.ch[i]==T.ch[i])
{
i++;
j++;
}
else
{
k++;
i=k;
j=1;
}
}
if(j>T.length)
return K;
else
return 0;
}
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
2.KMP算法
# 6.树
树的度，孩子个数最大的个数。
先序遍历，中序遍历，后序遍历
线索二叉树
若无左子树，左指针指向前驱结点
若无右子树，则将右指针指向后继结点
# 6.1二叉排序树
左子树<根节点<右子树 中序遍历序列是一个递增的有序数列
查找：先查找根节点，如果比根节点小，则查找左子树，比根节点大，则查找右子树
插入：小于根节点，插入左子树，大于根节点，插入右子树。等于根节点时不进行插入
建立：读入元素，建立根节点，二叉树为空，则将其作为根节点，大于二叉树，插入右子树，反之，左节点。等于根节点，不进行插入。
删除：叶节点可直接删除，如果只有一颗子树，则让z的子树成为z父节点的子树，代替z节点。如果有两颗子树，则让z的中序序列直接后继代替z，并删去直接后继节点。（因为中序序列是递增序列）
查找效率：ASL取决于树的高度
/*遍历，*/
BSTNode *BST_Search(BoTriTree T,ElemType e,BSTNode *&p)
{
p=NULL;
while(T!=NULL&&key!=T->data)
{
p=T;
if(key<T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;
}
/*插入*/
int BST_Insert(BiTriTree &T,KeyType k)
{
if(T==NULL)
{ T=(BiTriTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;}
else if(k==T->key)
return 0;
else if(key>T->key)
return BST_Insert(T->rchild,k);
else if(key<T->key)
return BST_Insert(T->lchild,k);
}
/*构造二叉排序树*/
void Create_BST(BiTriTree &T,KeyType k[],int n)//第二个参数 保存所有插入的数组
{
T==NULL；
int i=0;
while(i<n)
{
BST_Insert(T,k[i]);
i++;
}
}
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
# 6.2平衡二叉树
左子树高度等于右子树高度
平衡因子：左子树高度-右子树高度
如何计算高度为h的最小平衡二叉树的节点N0。
void Judge_AVL(BiTree bt,int &balance,int &h)
{
int bl=0,br=0,h1=0,hr=0;
int(bl==NULL)
{
h=0;
balance=1;
}
else if(bt->lchild==NULL&&bt->rchild==NULL)
{
h=1;
balance=1;
}
else
{
Judge_AVL(bt->lchild,bl,hl);
Judge_AVL(bt->rchild,br,hr);
if(hl>hr)
h=hl+1;
else
h=hr+1;
if(abs(hl-hr)<2&&bl==1&&br==1)
balance=1;
else
balance=0;
}
}
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
平衡二叉树的插入
LL平衡旋转（右单旋转）
右旋操作：将A的左孩子B代替A，将A结点称为B的右子树根结点，而B的原右子树则作为A的左子树。
RR平衡旋转（左单旋转）
将A的左孩子结点B代替A，将A结点称为B的左子树根节点，而B的原左子树作为A的右子树
LR平衡旋转（再结点A的左孩子的右子树插入新节点）
# 6.3哈夫曼树
带权路径长度：带权路径最小的二叉树
（1）将n个结点作为n颗树仅含有一个根节点的二叉树，构成森林F
（2）生成一个新的结点，并从F中找出根节点权值最小的两棵树作为左右子树，且新节点的权值为两棵子树根结点之和
（3）从F中删除这两棵树。并将新生成的树加入F中
(4) 重复2，3步骤，直到F中只有一棵树为止
哈夫曼树用于编码：对于一个字符串序列，用二进制表示字符
前缀相同
# 7.图结构
顶点集合和边的集合：
任意两个顶点都是连通的，则是连通图。
# 7.1图的生成-——邻接矩阵法
#include<iostream>
#define MAXVEX 10/*最大顶点数*/
#define INFINITY 65656/*表示权值无穷*/
using namespace std;
typedef int EdgeType;
typedef char VertexType;
typedef struct
{
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numNodes,numEdges;//图中当前顶点和边数
}MGraph;
/*建立无向图的邻接矩阵表示*/
void CreateMGraph(MGraph *Gp)
{
int i,j,k,w;
cout<<"请输入顶点数和边数（空格分隔）："<<endl;
cin>>Gp->numNodes>>Gp->numEdges;
cout<<"请输入顶点信息"<<endl;
for(i=0;i<Gp->numNodes;i++) //输入顶点
cin>> Gp->vexs[i];
for(i=0;i<Gp->numNodes;i++) //初始化邻接矩阵
{
for(j=0;j<Gp->numNodes;j++)
{
if(i==j)
Gp->arc[i][j]=0;//顶点没有到自己的边
else
Gp->arc[i][j]=INFINITY;//初始化边为无穷
}
}
/*输入边的上下标和权值*/
for(k=0;k<Gp->numEdges;k++)
{
cout<<"请输入"<<Gp->numEdges<<"个边(Vi,Vj)的上标、下标和权值w(空格分隔)"<<endl;
cin>>i>>j>>w;
Gp->arc[i][j]=w;
Gp->arc[j][i]=Gp->arc[i][j];//对称矩阵
}
}
int main(void)
{
MGraph MG;
CreateMGraph(&MG);
return 0;
}
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
# 7.2图的生成-——十字链表法
# 7.3图的遍历
深度优先：二叉树前序遍历
广度优先：队列操作
# 9.静态查找和动态查找
平衡二叉树：
散列表查找步骤：1.当存储记录时，通过散列函数计算出记录的散列地址
当查找纪录时，通过同样是散列函数计算记录的散列地址，并按此散列地址访问该记录
散列表 一对一查找效率高
直接定值法：
f(key)=a∗key+b f(key)=a*key+b f(key)=a∗key+b
数字分析法：
平方取中法：关键字平方之后，取若干位数字作为散列地址
折叠法：关键字从左到有分割成位数相等的及部分，然后将这几部分叠加求和
初留余数法：关键字对key 求余数
# 10.排序算法
堆排序：