3.2 数据结构基础
按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就成为一个数据结构。
数据结构研究的内容如下：
（1）数据的逻辑结构：按照某种逻辑关系将数据组织好，即逻辑结构。
（1）数据的逻辑结构：按照某种逻辑关系将数据组织好，即逻辑结构。
（2）数据的存储结构：将数据及数据之间的关系存储到存储区域中，即存储结构。
（3）数据的运算：在这些数据上定义一个基本运算的集合。
3.2.1 基本概念
数据（Data）
数据是信息的载体。
数据元素是数据的基本单位。
一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构（Data Structure）
数据结构指的是数据之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：
（1）数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；
数据的逻辑结构有两大类：
①线性结构
②非线性结构
（2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）。
数据的存储结构可用以下四种基本存储方法得到：
①顺序存储方法
该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
②链接存储方法
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure），通常借助于程序语言的指针类型描述。
③索引存储方法
该方法通常在储存结点信息的同时，还建立附加的索引表。
④散列存储方法
该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。
（3）数据的运算，即对数据施加的操作。
3.2.2 线性表
（1）基本概念
一个线性表由有限个类型相同的数据元素组成。在这有限个数据元素中，数据元素构成一个有序的序列，除了第一个和最后一个元素外，每一个元素都有唯一的前驱元素和唯一的后继元素。
（2）顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
(3)顺序表的运算
在线性表的顺序存储结构下，可以对线性表进行各种处理。
3.2.3 栈及其基本运算
（1）栈的定义
栈是一种运算受限的线性表。
（2）栈的顺序存储及其运算
栈的顺序存储利用一组地址连续的存储单元依次存放栈中的各个数据元素，又可称为顺序栈。为了方便操作，通常设一个标记top标出栈顶元素所在的位置。
栈的基本运算有三种：入栈、退栈与读栈顶元素。
3.2.4 队列及其基本运算
(1)队列的定义
队列（queue）是一种先进先出（first in first out，FIFO）的线性表。它只允许在表的一端（队尾/rear）插入元素，而在另一端（队头/front）删除元素。插入操作称为入队或进队，删除操作称为出队或离队。队列示意图如下：
①允许删除的一端称为队头（Front）。
②允许插入的一端称为队尾（Rear）。
③当队列中没有元素时称为空队列。
④队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
（2）循环队列及其运算
所谓循环队列，就是将队列存储空间的最后一个位置连接到第一个位置，形成逻辑上环状间，供队列循环使用。
3.2.5 线性链表
线性链表是具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据元素，逻辑上相邻的元素在物理上不要求也相邻，不能随机存取。一般用结点描述：
结点(表示数据元素)=数据域(数据元素的映像)+指针域(指示后继元素存储位置)
在线性表的链接存储中，为了方便在表头插入和删除结点的操作，经常在表头结点（存储第一个元素的结点）的前面增加一个结点，称之为头结点。这样原来的表头指针由指向第一个元素的结点改为指向头结点，头结点的数据域为空，头结点的指针域指向第一个元素的结点。如果整个链表的存取必须从头指针开始，线性链表有三种：
（1）单链表：每个节点有一个指针域，有一个头指针h而尾指针，表中最后一个节点的指针域是空的，其结构简单，但查找需要从头开始，所以查找效率不高。
（2）循环链表：每个节点有一个指针域，有一个头指针h和一个尾指针r，表中最后一个结点的指针域不是空的，尾指针指向表的第一个结点，它可以形成环形结构，可显著提高查找效率。
（3）双向链表：每个结点有两个指针域，一个指向直接前驱，一个指向直接后继，它形成双向结构，从某结点出发，既可以向前查找又可以向后查找，所以双向链表进一步提高查找效率。
3.2.6 树与二叉树
树是一种很常见的非线性的数据结构，称为树形结构，简称树。树形结构就像自然界的一棵树的构造一样，有一个根和若干个树枝和树叶。根或主干是第一层的，从主干长出的分枝是第二层的，一层一层直到最后，末端的没有分支的结点叫做叶子，所以树形结构是一个层次结构。
（1）树的定义
树是n(n>=0)个结点的有限集D和D上定义了关系H的一个数据结构，记作T{D,H}，它满足以下条件：
l 有且仅有一个结点没有前驱（父结点），该结点称为树的根；
l 除根外，其余的每个结点都有且仅有一个前驱；
l 树中的每一个结点都构成一个以它为根的树。
（2）二叉树的定义
二叉树是一棵有序树，它的任一结点至多只有两个孩子，分别叫做左孩子和右孩子。根的左孩子L和右孩子R也是二叉树，称为根的左子树和右子树。
二叉树的两个特殊形态：
①满二叉树：
如果一棵深度为K的二叉树，共有2K-1个结点，即任意第I层有2I-1的结点，称为满二叉树。
②完全二叉树：
如果一棵二叉树最多只有最下层但不是叶结点的度数可以小于2，并且最下层的结点如果只有一个孩子，它必须是左孩子，则称此二叉树为完全二叉树。
（3）二叉树的性质
二叉树具有以下重要性质：
性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。
性质2深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
（4）二叉树的遍历
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。根据对根结点访问先后顺序，二叉树的遍历操作发生位置命名：前（根）序遍历、中（根）序遍历和后（根）序遍历。若二叉树非空，具体遍历算法如下：
①中（根）序遍历的递归算法定义：
l 中序遍历左子树；
l 访问根结点；
l 中序遍历右子树。
②前（根）序遍历的递归算法定义：
l 访问根结点；
l 前序遍历左子树；
l 前序遍历右子树。
③后（根）序遍历得递归算法定义：
l 后序遍历左子树；
l 遍历右子树；
l 后序访问根结点。
3.2.7 查找技术
所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。
（1）顺序查找
顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到(即查找成功)；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(即查找失败)。
（2）二分查找
二分法查找(又称对分查找)只适用于顺序存储的有序表。在此所说的有序表是指当中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。
设有序线性表的长度为n，被查元素为x，则对分查找的方法如下：
将x与线性表的中间项进行比较；
若中间项的值等于x，则说明查到，查找结束；
若x小于中间项的值，则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找；
若x大于中间项的值，则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找；
这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。
动态演示：
3.2.8 排序
排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。本节主要介绍一些常用的排序方法。
1.简单选择排序
（1）基本思想
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
简单选择排序的示例：
（2）运行过程
第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。
（3）视频讲解
算法动态演示：
2.冒泡排序
冒泡排序（Bubble Sort）是一种典型的交换排序算法，通过交换数据元素的位置进行排序。
（1）基本思想
冒泡排序的基本思想就是：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。
（2）运行过程
冒泡排序算法的运作如下：
①比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
③针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
④持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。
（3）视频讲解
算法动态演示：
3、插入排序
我们玩扑克时抓牌的过程，通常我们用右手抓牌，每抓一张牌，就放到左手上，每抓下一张牌后，会把这张牌依次与左手上的牌比较，并把它插入到一个合适的位置（通常按照牌面大小）。
上述的过程即为插入排序的过程，插入排序原理很简单，将一组数据分成两组，分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及了元素的移动。
（1）视频讲解
算法动态演示：
4.希尔排序
希尔排序是1959年由D.L.Shell提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序。
希尔排序是对插入排序的一种改进，它的核心思想是将待排序数组中任意间隔为h的元素都变为有序的，这样的数组叫做h有序数组。比如数组[5,3,2,8,6,4,7,9,5],我们可以看到a[0]、a[3]、a[6]是有序的，a[1]、a[4]、a[7]是有序的，a[2]、a[5]、a[8]是有序的，因此这个数组是一个h有序数组（h=3）。根据h有序数组的定义，我们可以知道，当h=1时，相应的h有序数组就是一个已经排序完毕的数组了。
希尔排序的大致过程如下：把待排序数组分割为若干子序列（一个子序列中的元素在原数组中间隔为h，即中间隔了h-1个元素），然后对每个子序列分别进行插入排序。然后再逐渐减小h，重复以上过程，直至h变为足够小时，再对整体进行一次插入排序。由于h足够小时，待排序数组的逆序数已经很小，所以再进行一次希尔排序是很快的。希尔排序通常要比插入排序更加高效。
算法动态演示：
5.选择排序
假如我们现在按身高升序排队，选择排序是这样一种排队的方法，让目前队头的人依次与其后的每个人进行比较，比较后较矮的那个人继续与后面的人进行比较，这样第一趟比较下来，就能够找到最矮的人，然后把这个最矮的人和当前队头的人交换一下位置。然后第二趟比较，让第二名依次与后面比较，可以找到第二矮的人，然后让第二矮的人和当前队列第二名交换位置，依此类推，一共进行n-1趟比较后，就能完成整个排队过程。
6.堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
（1）基本思想：
堆的定义如下：具有n个元素的序列（k1,k2,...,kn)，当且仅当满足下列条件时称之为堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：
①大顶堆序列：（96,83,27,38,11,09)
②小顶堆序列：（12，36，24，85，47，30，53，91）
初始时把要排序的n个数的序列看作一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。因此，实现堆排序需解决两个问题：
①如何将n个待排序的数建成堆；
②输出堆顶元素后，怎样调整剩余n-1个元素，使其成为一个新堆。
算法动态演示：
