数据结构与算法基础

内容提要

• 数组与矩阵
• 线性表
• 广义表
• 树与二叉树
• 图
• 排序与查找
• 算法基础及常见的算法

数组

1. 数组类型：存储地址计算
2. 一维数组a[n]：a[i]的存储地址为：a+i*len
3. 二维数组a[m][n]：

• a[i][j]的存储地址（按行存储）为：a+(i*n+j)*len
• a[i][j]的存储地址（按列存储）为：a+(j*n+i)*len

稀疏矩阵

例题

设有如下所示的三角矩阵A[0..8,1..8]，将该三角矩阵的非零元素（即行下标不小于列下标的所有元素）按行优先压缩存储在数组M[1..m]中，则元素A[i,j](0<=i，j<=i)存储在数组M的（A）中。

数据结构的定义

1.数据结构的概念

2.数据逻辑结构

线性结构

非线性结构（树形结构：无环路，图：有环路）

线性表的定义

1、线性表的概念

（a1,a2,...,a3)

2、线性表常见的两种存储结构

顺序存储结构（顺序表）

链式存储结构（链表）

线性表

顺序表

链表

• 单链表
• 循环链表
• 双向链表

链表的基本操作

• 单链表删除结点
• 单链表插入结点
• 双向链表删除结点
• 双向链表插入结点

线性表-顺序存储与链式存储对比

线性表-队列与栈

例题

输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如下图所示，若有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出序列（D）

A:e4,e3,e2,e1

B:e4,e2,e1.e3

C:e4,e3,e1,e2

D:e4,e2,e3,e1

广义表

广义表是n个表元素组成的有限序列,是线性表的推广。

通常用递归的形式进行定义，记做:LS (a0，a1，....，an)。

注:其中LS是表名，ai是表元素，它可以是表(称做子表),也可以是数据元素(称为原子)。其中n是广义表的长度(也就是最外层包含的元素个数),n=0的广义表为空表;而递归定义的重数就是广义表的深度,直观地说，就是定义中所含括号的重数(原子的深度为0，空表的深度为1)。

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

若有:LS1=(a,(b,c),(d,e))head(LS1)=atail(LS1)=((b,c)，(d,e))

例1,有广义表LS1=(a,(b,c),(d,e)),则其长度为?深度为?

答案：长度为3，深度为2.

例2,有广义表LS1= (a,(b,c)，(d,e))),要将其中的b字母取出,操作就为?

答案：head（head（tail（LS1）））

树与二叉树

• 结点的度
• 树的度
• 叶子结点
• 分支结点
• 内部结点
• 父结点
• 子结点
• 兄弟结点
• 层次

树与二叉树

二叉树的重要特性:

1. 在二叉树的第i层上最多有2^i-1个结点(i>=1);
2. 深度为k的二叉树最多有2k -1个结点(k>=1);
3. 对任何棵二叉树,如果其叶子结点数为n0,度为2的结点数为n2 ,则n0=n2+1。
4. 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到log2nJ+1层，每层从左到右)，则对任一结点i(1<=i<=n)，有:

• *如果i=1,则结点i无父结点，是二叉树的根;如果i>1 ,则父结点是【i/2】;
• *如果2i>n,则结点为i叶子结点，无左子结点;否则，其左子结点是结点2i;
• *如果2i+1>n,则结点无右子叶点，否则,其右子结点是结点2i+1。

树与二叉树遍历

1. 前序遍历 12457836
2. 中序遍历 42785136
3. 后序遍历 48752631
4. 层次遍历 12345678

树与二叉树-反向构造二叉树

由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树。

树与二叉树-树转二叉树

• 孩子结点-左子树结点
• 兄弟结点-右孩子结点

树与二叉树-查找二叉树

• 二叉排序树
• 左孩子小于根
• 右孩子大于根

插入结点:

①若该键值结点已存在,则不再插入，如: 48;

②若查找二叉树为空树,则以新结点为查找叉树;

③将要插入结点键值与插入后父结点键值比较,就能确定新结点是父结点的左子结点，还是右子结点。

删除结点:

①若待删除结点是叶子结点，则直接删除;

②若待删除结点只有一个子结点,则将这个子结点与待删除结点的父结点直接连接，如: 56 ;

③若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s ,用结点s的值代替结点p的值,然后删除节点s ,节点s必属于上述①，②情况之一,如89。

树与二叉树-最优二叉树（哈夫曼树）

（在多媒体的压缩方式经常使用：无损压缩）

需要了解的基本概念：

• 树的路径长度
• 权
• 带权路径长度
• 树的带权路径长度(树的代价）

例题：假如有一组权值5，29，7，8，14，23，3，11请尝试构造哈夫曼树。

树与二叉树-线索二叉树

• 为什么要有线索二叉树
• 线索二叉树的概念
• 线索二叉树的表示
• 如何将二叉树转化为线索二叉树

树与二叉树-平衡二叉树

• 平衡二叉树的提出原因
• 平衡二叉树的定义（
• 任意结点的左右子树深度相差不超过1
• 每结点的平衡度只能为-1、0或1）
• 平衡树的建立过程
• 动态调平衡问题

例题：对数列{1，5，7，9，8，39，73，88}构造序列二叉树，可以构造出多颗形式不同的排序二叉树。

图-基本概念

完全图

• 在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图（complete graph）

• 在有向图中，若每对顶点之间都有两条有向边相互连接，则称该图为完全图。

图的存储-邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Rij定义为：

图的存储-邻接表

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

图-图的遍历

图-拓扑排序

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

上图的拓扑序列有：02143567，01243657，02143657，01243567

图的最小生成树-普里姆算法

算法基础-算法的特性

• 有穷性：执行有穷步之后结束
• 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清。
• 输入（>=0)
• 输出 (>=1)
• 有效性：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0,b/a就无效。

算法基础-算法的复杂度

时间复杂度：

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

如果存在两个常数c和m ,对于所有的n ,当n>=m时有f(n)<=cg(n) ,则有f(n)=O(g(n))。也就是说,随着n的增大,f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n^3+2n^2+n ,则T(n)=O(n^3). 常见的对算法执行所需时间的度量:O(1)<0(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<0(2^n)

空间复杂度:

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

查找-顺序查找

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

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

查找-二分查找

二分法查找的基本思想是:(设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。●若R[mid].key=k,则查找成功,算法结束。

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

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

例题：

请给出在含有12个元素的有序表{1，4，10，16，17，18，23，29，33，40，50，51}中二分查找关键字17的过程。

查找-折半查找

折半查找在查找成功时关键字的比较次数最多为[log2n]=1次。

折半查找的时间复杂度为O（log2n）。

查找-散列表

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

查找-散列表冲突的解决方法

开放定址法是指当构造散列表发生冲突时,使用某种探测手段，产生-个探测的散列地址序列,并且逐个查找此地址中是否存储了数据元素,如果没有,则称该散列地址开放,并将关键字存入,否则继续查找下-个地址。只要散列表足够大,总能找到空的散列地址将数据元素存入。

• 线性探测法
• 伪随机数法

例:记录关键码为(3，8, 12, 17,9),取m=10(存储空间为10),p=5,散列函数h =key%p。

排序

1、排序的概念

• 稳定与不稳定排序
• 内排序与外排序

2、排序方法分类

• 插入类排序
• （直接插入排序
• 希尔排序）
• 交换类排序
• （冒泡排序
• 快速排序）
• 选择类排序
• （简单选择排序
• 推排序）
• 归并排序
• 基数排序

排序-直接插入排序

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

排序-希尔排序

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

排序-直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换......依次类推，直到所有记录排完为止。

排序-推排序的概念

（最复杂的一种）

设有n个元素的序列{K1，K2，...，Kn}，当且仅当满足下述关系之一时，称之为推。

（1）ki<=k2i且ki<=k2i+1;

（2）ki>=k2i且ki>=k2i+1;

其中(1)称为小顶堆，（2）称为大顶堆

排序-堆排序

堆排序的基本思想为:先将序列建立堆,然后输出堆顶元素,再将剩下的序列建立堆,然后再输出堆顶元素,依此类推,直到所有元素均输出为止,此时元素输出的序列就是一个有序序列。

堆排序的算法步骤如下(以大顶堆为例):

(1)初始时将顺序表R[1..n]中元素建立为一个大顶堆,堆顶位于R[1]待序区为R[1..n].(2)循环执行步骤3 ~步骤4 ,共n-1次。(3)假设为第次运行,则待序区为R[1..n-i+1],将堆顶元素R[1]与待序区尾元素R[n-i+1]交换,此时顶点元素被输出,新的待序区为R[1..n-i]。(4)待序区对应的堆已经被破坏,将之重新调整为大顶堆。

例题：

假设有数组A={1，3，4，5，7，2，6，8，0}，初建推过程如下：

例题

将顺序表R{80，60，16，50，45，10，15，30，40，20}进行堆排序。

排序-冒泡排序

冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。

排序-快速排序

快速排序采用的是分治法,其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题,然后再将这些子问题的解组合成原问题的解。

快速排序通常包括两个步骤:

第一步，在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录都分成两组,第1组都小于该数,第2组都大于该数,如图所示。第二步，采用相同的方法对左、右两组分别进行排序,直到所有记录都排到相应的位置为止。 

排序-归并排序

归并也称为合并,是将两个或两个以上的有序子表合并成-个新的有序表。若将两个有序表合并成个有序表,则称为二路合并。合并的过程是:比较A[i]和A[j]的排序码大小,若A[i]的排序码小于等于A[j]的排序码,则将第一个有序表中的元素A[i]复制到R[k]中,并令i和k分别加1;如此循环下去,直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。

排序-基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

排序

更多软考自查在我的主页“文章”中可以查看！！！