数据结构的基本考点,给自己做备忘,老是学了忘忘了学
有一个很不错的网站,可以演示各种数据结构运行的过程
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
1.链表的倒数第K个查找
1 | void search(LinkList &L, ElemType k){ |
2.手写遍历算法
- 递归先序遍历
1
2
3
4
5
6
7void preOrder(BiTree T){
if(T != null){
visit(T);
preOrder(T->lchild);
preOrder(T->rchild);
}
} - 非递归先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void preOrder(BiTree T){
InitStack(S);
BiTree p = T;
while(p||isEmpty(s))
{
if(p){
push(S, p);
visit(p);
p = p->lchild;
}
else{
pop(S, p);
p = p->rchild;
}
}
} - 层次遍历
1 | void levelOrder(BiTree T){ |
3.字符串匹配算法
普通匹配
kmp算法
4.逆波兰表达式
中缀表达式转成后缀表达式(如(a+b)*(c+d)
转换为 ab+cd+*
)
转换规则:当前字符为变量或者数字,则存入后缀表达式;如果是运算符op,op比操作符栈顶优先级高则压入,否则将栈中操作符不断弹出,直到op的优先级高于栈顶。
5.二叉搜索树
它或者是一棵空树;或者是具有下列性质的二叉树:若左子树不空,则左子树上所有结点的值均小于它的根结点的值;若右子树不空,则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树。若子树为空,查找不成功。
可以显著的改进查找的效率,查找一个数据的了路径最长不超过树的深度。
1 | //递归实现 |
6.平衡二叉搜索树(红黑树)
就是若一棵二叉树的每个左右节点的高度差最多相差1,此二叉树即是平衡二叉树。把二叉树的每个节点的左子树减去右子树定义为该节点的平衡因子。二叉平衡树的平衡因子只能是1、0或者-1。
在二叉搜索树的插入和删除运算中,采用平衡树的优点是:使树的结构较好,从而提高查找运算的速度。缺点是:是插入和删除运算变得复杂化,从而降低了他们的运算速度。
7.散列
- 散列函数
- 平方取中法
- 除留余数法
- 折叠法
- 数字分析法
- 解决冲突
- 开放定址法
- 拉链法
7.排序算法
插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
交换排序
- 起泡排序
- 快速排序
选择排序
- 直接选择排序
- 堆排序
- 竞标赛排序
归并排序
- 归并
- 迭代归并
基数排序