数据结构与算法基础

2022-03-02 本文已影响0人小飞5

数组

一维数组a[n] a[i]的存储地址为a+i*len

二维数组a[m][n] a[i][j]的存储地址按行存储为：a+(i*n+j)*len

a[i][j]的存储地址按列存储为：a+(j*m+i)*len

稀疏矩阵

在考试中可以使用代入法来快速选择

数据结构的定义

数据结构的概念：

从逻辑上可以分为线性结构和非线性结构，非线性结构可以分为树和图

树和图树不包含闭环

线性表的定义

线性表可以分为顺序表和链表

顺序存储与链式存储对比

队列和栈

队列的基本原则是先进先出

栈则是先进后出

广义表

广义表是由n个表元素组成的有限序列，是线性表的推广，通常用递归的形式进行定义记作 $LS=(a_{0},a_{1},...,a_{n})$

注：LS是表名， $a_{i}$ 是表元素，它可以是表，也可以是数据元素，其中n是广义表的长度，n=0的广义表为空表

基本运算：取表头head(Ls)和取表尾tail(Ls)

树与二叉树

基本概念

节点的度指当前节点拥有子节点的数量

树的度表示所有节点含有最高的子元素的节点

叶子节点表示最后一层节点（没有子节点）

分支节点含有分支的节点

内部节点非叶子节点和非根节点

子节点和父节点是一个相对的概念

兄弟节点属于用一个父节点

满二叉树与完全二叉树

满二叉树指整棵树没有缺失的节点

完全二叉树是指除最底一层，上面的层次都是满的

二叉树遍历

层次遍历：按二叉树的层次依次遍历

前序遍历：先访问根节点再访问左右节点

中序遍历：先访问左子树然后访问根节点最后访问右节点

后序遍历：先访问左子树在访问右子树最后访问根节点

查找二叉树

树的左节点小于根节点，右节点大于根节点这种树成为查找(排序)二叉树方便查询比对

最优二叉树(哈夫曼树)

用于哈夫曼编码，能够让原始信息的编码长度变得更短

图

基本概念

图的存储-邻接矩阵

用一个n阶方阵来存放图中个结点的关联信息其矩阵元素 $R_{ij}$ 定义为

图的存储-邻接表

首先把每隔定点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针

图的遍历

拓扑排序

我们把用有向边表示活动之间开始的先后关系，这种有向图称为用顶点表示活动网络

算法基础

算法的特性

算法的复杂度

时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入的渐进时间复杂度在数量上估计一个算法的执行时间。定义如下

如果存在两个常数c和m，对于所有的n，当n $\geq$ m时有 $f(n)\leq cg(n)$ 则有 $f(n)=O(g(n))$ 。也就是说，随着n的增大，f(n)渐进地不大于g(n)

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

顺序查找

顺序查找的思想：将查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功，否则，则查找失败

查找成功时，顺序查找的平均查找长度为（等概率情况下）：

$ASL=\sum_{i=1}^nP_{i} \times (n-i+1)=\frac{1+2+L+n}{n} =\frac{n+1}{2}$

二分查找法（需要先将表变成有序表）

二分查找法的基本意思：（设R[low,...,high]是当前的查找区）

(1)确定该区间的中点位置：mid=[(low+high)/2];

(2)将待查的k值与R[mid].key比较，若相等，则查找成功饼返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下

·若R[mid].key>k,则由表的有序性可知R[mid,...,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,...,mid-1]中。因此，新查找区间是左子表R[low,...,high]，其中high=mid-1

·若R[mid].key<k,则要查找的k必在mid的右子表R[mid+1,...,high]中，则新的查找区间是右子表R[low,...,high],其中low=mid+1

·若[mid].key=k，则查找成功，算法结束

(3)下一次查找是针对新的查找区间进行，重复步骤(1)和(2).

(4)在查找过程中,low逐步增加,而high逐步减少。如果high<low，则查找失败，算法结束

散列表

散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0...n-1](n<<m)中，这个区间就称为散列表，散列查找使用的转换函数称为散列函数

排序

直接插入排序：当插入第i个记录时， $R_{1} ,R_{2} ,...,R_{i-1}$ 均已排好序，因此，将第i个记录 $R_{i}$ 依次与 $R_{i-1} ,...,R_{2} ,R_{1}$ 进行比较，找到合适的位置插入。它简单明了，但速度很慢

希尔排序：先取一个小于n的整数 $d_{1}$ 作为第一个增量，把文件的全部记录分成 $d_{1}$ 个组。所有距离为 $d_{1}$ 的倍数的记录放在同一个组中。先在各组内进行直接插入排序，然后，取第二个增量 $d_{2} <d_{1}$ 重复上述的分组和排序，直至所取的增量 $d_{t} =1(d_{t} <d_{t-1} <O<d_{2} <d_{1} )$ ,即所有记录放在同一组中进行直接插入排序为止，该方法实际上是一种分组插入方法。