数据结构与算法1

算法的基本概念

算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。也不等于计算方法。

算法的基本特征：

• 确定性，算法中的每一步骤都必须有明确的定义，不允许有多义性；
• 有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；
• 可行性，算法原则上能够精确地执行；

算法地组成要素：一个算法由数据对象的运算和操作以及其控制结构这两部分组成。

算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。

算法的基本控制结构：顺序，选择，循环 。

算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。

算法的复杂度

算法效率的度量——算法的复杂度：时间复杂度和空间复杂度。

算法时间复杂度：指执行算法所需要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。

算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。

空间复杂度和时间复杂度并不相关。

数据结构的基本概念

数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。

数据元素：数据元素是数据的基本单位。

数据对象：数据对象是性质相同的数据元素的集合。

数据结构：是指由某一些数据对象中所有数据成员之间的关系组成的集合。

逻辑结构和存储结构

数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。

数据的存储结构也称为数据的物理结构，是数据在计算机中的物理结构，是数据在计算机中的存放方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。

数据结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对立。

常见的存储结构有：顺序，链表，索引等。采用不同的存储结构其数据处理的效率是不同的。

线性结构和非线性结构

线性结构的条件（一个非空数据结构）：1.有且只有一个根结点；2.每一个结点最多有一个前驱，也最多有一个后继。

非线性结构：不满足线性结构条件的数据结构。

栈、队列、双向链表是线性结构，树、二叉树为非线性结构。

线性表及其顺序表存储结构

线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录；有多个记录构成的线性表称为文件

非空线性表的结构特征：

1. 有且只有一个根节点a₁，它无前驱；
2. 有且只有一个终端结点a_n，它无后继；
3. 除根节点于终端结点外，其他所有结点有且只有一个前驱，也有且只有一个后继。

结点个数n称为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：

• 线性表中所有元素所占的存储空间是连续的；
• 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR（a1），每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存放地址为：ADR(ai)=ADR（a1）+（i - 1）k 即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。

顺序表的插入运算

​ 在一般情况下，要在第 i ( 1 ≤ i ≤ n) 个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n - i + 1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。

可以归纳为三个步骤：

1. 把原来第n个节点至第i个节点依次往后移一个元素位置。
2. 把新节点放在第i个位置上。
3. 修正线性表的节点个数。

​ 一般情况下，在第 i ( 1 ≤ i ≤ n )个元素之前插入一个元素时，需将第 i 个元素之后(包括第i个元素）的所有元素向后移动一个位置。
如果要在第1个位置处插入一个新元素，则需要移动表中所有的元素。
线性表的插入运算，其时间主要花费在节点的移动上，所需移动节点的次数不仅与表的长度有关，而且与插入的位置有关。

顺序表的插入运算

​ 在一般情况下，要在第 i（1≤ i ≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第 i 个元素之间共 n - i + 1 个元素依次向后移动一个位置，移动结束后，第 i 个位置就被空出，然后将新元素插入到第 i 项。插入结束后，线性表的长度就增加了1。

可以归纳为三个步骤：

1. 把原来第n个节点至第 i 个节点依次往后移一个元素位置。
2. 把新节点放在第 i 个位置上。
3. 修正线性表的节点个数。

一般情况下，在第 i（1≤ i ≤n）个元素之前插入一个元素时，需将第 i个元素之后(包括第 i 个元素）的所有元素向后移动一个位置。
如果要在第1个位置处插入一个新元素，则需要移动表中所有的元素。
线性表的插入运算，其时间主要花费在节点的移动上，所需移动节点的次数不仅与表的长度有关，而且与插入的位置有关。

顺序表的删除运算

​ 在一般情况下，要删除第 i（1≤ i ≤n）个元素时，则要从第 i + 1个元素开始，直到第n个元素之间共 i - 1个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。

可以归纳为两个步骤：

1. 把第i个元素之后（不包括第 i 个元素）的n - i个元素依次前移一个位置。
2. 修正线性表的节点个数。

​ 显然，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动线性表中的元素。如果要删除第1个元素，则需要移动表中所有的元素。

​ 在一般情况下，如果删除第i（1≤ i ≤n）个元素，则原来第 i 个元素之后的所有元素都必须依次往前移动一个位置。

​ 由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。但这种顺序存储方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。

栈和队列

什么是栈

栈实际上也是线性表，只不过是一种特殊的线性表。

栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。
即：栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此也可以看出栈具有记忆作用。

通常用指针top来指示栈顶的位置，用指针bottom指向栈底。

栈的顺序存储及其运算

​ 与一般的线性表一样，在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）。

在栈的顺序存储空间S（1:m）中，S（bottom）通常为栈底元素（在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。

栈的基本运算有三种：入栈，退栈与读栈顶元素。

入栈运算

入栈运算是指在栈顶位置插入一个新元素。操作过程如下：

1. 首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（“上溢”错误），算法结束。
2. 然后将栈顶指针进1（即top加1）。
3. 最后将新元素x插入栈顶指针指向的位置。

退栈运算

退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：

1. 首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（“下溢”错误），算法结束。
2. 然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
3. 最后将栈顶指针退1（即top减1）。

读栈顶元素

读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：

1. 首先判断栈顶指针是否为0.如果是，则说明栈空，读不到栈顶元素，算法结束。
2. 然后将栈顶元素赋给一个指定的变量。

这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。

队列及其基本运算

什么是队列

队列也是一种特殊的线性表。

队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。
显然，在这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表。

往队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。入队运算只涉及队尾指针（rear）的变化，而退队运算只涉及排头指针（front）的变化。

与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。

循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

所谓的循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

在循环队列中，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

循环队列主要有两种基本运算：入队运算与退队运算。

每进行一次入队运算，队尾指针就进1。当队尾指针rear=m+1时，则置rear=1。
每进行一次退队运算，排头指针就进1。当排头指针front=m+1时，则置front=1。

当循环队列满或空时都有front=rear，不能确定队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需要增加一个标志s，s值的定义如下：

s=0 表示队列空
s=1 表示队列非空

• 队列空的条件：s=0；
• 队列满的条件：s=1且front=rear。

入队运算

入队运算是指在循环队列的队尾加入一个新的元素。操作过程如下：

1. 首先判断循环队列是否满。当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算（“上溢”错误），算法结束。
2. 然后将队尾指针进1（rear=rear+1），并当rear=m+1时置rear=1。
3. 最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。

退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：

1. 首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算（“下溢”错误），算法结束。
2. 然后将排头指针进1（front=front+1），并当front=m+1时置front=1。
3. 再将排头指针指向的元素赋给指定的变量。
4. 最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（s=0）。

树的基本概念

树是一种非线性结构，是n个结点的有限集。当n=0 时为空树，n>0时为非空树。

结点的度：结点所拥有的子树的个数。

叶子结点：度为0的结点。

分支结点：除叶子结点以外的结点。

结点的层次：根结点在第一层，同一层上左右结点的子结点在下一层。

树的深度：所处层次最大的那个结点的层次。

树的度：树中所有结点的度的最大值。

二叉树及其基本性质

二叉树的概念：二叉树是一种特殊的树形结构，每个结点最多只有两棵子树，且有左右之分不能互换，因此，二叉树有五种不同的形态，见教材12页。

二叉树的性质：

1. 在二叉树的第k层上，最多有2k-1(k≥1)个结点。
2. 深度为m的二叉树最多有2m-1个结点。
3. 在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。
4. 具有n个结点的二叉树，其深度不小于[log2n]+1,其中[log2n]表示为log2n的整数部分。

满二叉树与完全二叉树

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m－1个结点。

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

满二叉树是完全二叉树，而完全二叉树一般不是满二叉树。

完全二叉树的性质：

1. 具有n个结点的完全二叉树的深度为[log2n]+1。
2. 完全二叉树中度为1的结点数为0或1。

二叉树的遍历

前序遍历（中左右）：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

中序遍历（左中右）：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历（左右中）：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

例如：前序遍历：ABCDFHEG。

则 中序遍历：BAFHDCGE。

​ 后序遍历：BHFDGECA。

顺序查找

顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。

在下列两种情况下也只能采用顺序查找：

（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。

（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。

排序

1、交换排序

（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为 n(n－1)/2。

（2）快速排序法 ，在最坏的情况下，快速排序需要比较次数为 n(n－1)/2。

2、插入类排序法：

（1）简单插入排序法，最坏情况需要 n(n-1)/2次比较；

（2）希尔排序法，最坏情况需要O(n1.5)次比较。（大写O是算法复杂度的表示方法）

3、选择类排序法：

（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；

（2）堆排序法，最坏情况需要O(nlog2n)次比较。

相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。