高级程序员-数据结构

1 数据结构 1.1 数据结构与抽象数据类型 数据类型 是一个“值”的集合和定义在此集合上的 “一组操作” 的总称。 对程序员而言，各种语言中的“整数”类型都是相同的，因为它们的数学特性相同。 整数是数据元素的序列。 -maxint, …, -2, -1, 0, 1, 2, …, +maxint 抽象数据类型(ADT) 是指一个数学模型以及定义在该数学模型上的一组操作。 三个要素: 数据对象、数据关系、基本操作 1.2 逻辑结构、存储结构综述 逻辑结构是用来描述数据元素之间的逻辑关系。 包括如下 1、 线性结构 “一对一”(序列) 的关系 (线性表，栈，队列，串，数组，广义表) 2、 非线性结构 包括 树型结构――“一对多”的关系。如：(二叉树，树，森林) 图状结构――“多对多”的关系。如：(图，网) 3、 集合结构 “同属一个数据对象”的关系。如：(查找表，文件) 存储结构反应了逻辑结构在存储器中的映象 按“关系”() 的表示方法不同而分: 1、 顺序结构 ⎯⎯ 以数据元素在存储器中的一个固定的相对位置表示数据元素之间的关系。 2、 链式结构 ⎯⎯ 以“指针”表示数据元素的“前驱”或“后继”。 1.2.1 线性结构 线性表的结构特点 ⎯⎯ 数据元素的序列 两种存储结构 1、 顺序表 2、 链表――(单链表、双链表、循环链表)(静态链表) www.ccidedu.com 1.2.1.1 顺序表： 实现随机存取; 插入或删除需要移动元素; 链表: 只能进行顺序存取; 插入或删除时只需要修改指针; 不需要预分配存储空间; 顺序表适于应用在不常进行修改操作，表中元素相对稳定的场合; 链表适于应用在修改操作 频繁，事先无法估计最大表长的场合。 以下为顺序表常用操作： 1、 查询 i=0; while ( i=i; j-- ) va.elem[j]=va.elem[j-1]; va.elem[i]=x; va.length++; 3、 删除 for ( j=i; jnext; while ( p!=NULL && p->data!=x ) p=p->next; 2、 插入 s=new LNode; s->next=p->next; p->next=s; 3、 删除 q=p->next; p->next=q->next; delete(q); www.ccidedu.com www.ccidedu.com 1.2.1.2 有序表： 数据元素之间存在可“比较” 的关系，且每个元素必“≤”(或 “≥”)起后继元素。 对有序表进行的操作必须维护结构的“有序”关系，如不能随意插入等。因此查询的结 果同时得到插入的位置 对顺序表来说 i=0; while ( inext && p->next->data <= x ) p=p->next; 1.2.1.3 栈 栈是后进先出的线性结构 假设依次进栈的序列为: 1，2，…，n， 依次出栈的序列为: p1, p2, …, pn 则不可能出现下列情况: pi > pk > pj ( i < j < k ) 如: 1 4 5 2 6 3 ，2 1 6 4 3 5 等 1.2.1.4 队列 链队列的结构示意图如下： … 空队列的结构示意图如下： ∧a1 aQ.front ∧Q.front Q.rear ∧Q.front Q.rear ∧Q.front Q.rear www.ccidedu.com 1.2.1.5 数组 n_Array = ( D, R) R = { R1, R2, …, Rn } Ri 属线性关系 或者 n 维数组是 n-1 维数组的线性表 数组只有对数据元素进行“存取”的操作，而没有“插入”与“删除”的操作， 结构一旦建立，其维数与每一维的上下界均不变，因此数组只有顺序存储结构，不需要 链式存储表示。 但由于数组的逻辑结构是“多维”的，而计算机的存储结构是一维的，因此数组的存储表 示需要建立一个从多维到一维的映象关系。 以“行(序)”为主(序) (或称“低”下标优先) a0,0 a0,1 a0,2 a1,0 a1,1 a1,2a0,0 a0,1 a0,2 a1,0 a1,1 a1,2 L LOC( i, j ) = LOC( 0,0 ) + ( b2×i＋j )×L 称为基地址或基址。 www.ccidedu.com 以“列(序)”为主(序) (或称“高”下标优先) a0,1a0,0 a1,0 a1,1 a0,2 a1,2a0,0 a0,1 a0,2 a1,0 a1,1 a1,2 L LOC( i, j ) = LOC( 0,0 ) + ( b1×j＋i )×L 称为基地址或基址。 其中，b1 为行的数目，( 即第一维的下标为 0..b1-1 ) b2 为列的数目，(即第二维的下标为 0..b2-1 ) 低下标优先即为从最右下标开始:： 如: A[3][2][4] 的存储次序为: (0,0,0), (0,0,1), (0,0,2), (0,0,3), (0,1,0), …, (0,1,3), …, (1,0,0), …, (1,1,0), …, (1,1,3), (2,0,0), …, (2,1,3) 高下标优先即为从最左下标开始 则 A[3][2][4] 的存储次序为: (0,0,0), (1,0,0), (2,0,0), (0,1,0), …, (2,1,0), (0,0,1) …, (0,1,1), …, (0,0,2), …, (2,1,2), (0,0,3), …, (2,1,3) 推广到一般情况，可得到 n 维数组数据元素存储位置(以行序为主序)的映象关系: 1 2 1 ( , , , ) (0,0, ,0) n n i i i LOC j j j LOC c j = = +∑L L 其中 cn = L，ci-1 = bi ×ci , 1 < i ≤ n 称为 n 维数组的映象函数， 数组元素的存储位置是其下标的线性函数。 1.2.1.6 广义表 ⎯⎯ 递归定义的线性结构 LS = ( α1, α2, ⋅⋅⋅, αn ) 其中：αi 或为原子 或为广义表 ( 称为 LS 的子表 ) 例如: A = ( ) F = ( d, A, (e) ) D = ( (a, (b,c)), F ) C = ( A, D, F ) B = ( a, B ) = ( a, ( a, ( a, ⋅⋅⋅ , ) ) ) 广义表 的结构特点: 1) 广义表中的数据元素按一定次序排列; 2) 广义表的长度定义为最外层包含元素个数; 3) 广义表的深度定义为所含括弧的重数; “空表”的深度为 1; “原子”的深度为 0 。 4) 广义表可以共享; 5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。 6) 任何一个非空广义表 LS = ( α1, α2, …, αn) 均可分解为 表头 Head( LS ) = α1 和 表尾 Tail( LS ) = ( α2, …, αn ) 两部分 例如: D = ( E, F ) = ((a, (b, c))，F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) 1.2.2 非线性结构 1.2.3 排序 排序是将无序的记录序列调整为有序记录序列的一种操作。一般情况下，排序的定义为: 假设含有 n 个记录的序列为：{ R1，R2，…，Rn } 它们的关键字相应为 { K1，K2，…，Kn } 需确定序号 1, 2, …, n 的一种排列 p1，p2，…，pn， 使其相应的关键字满足非递减（或非递增）的关系： 1 2 np p p K K K≤ ≤ ≤L www.ccidedu.com www.ccidedu.com 即使上列记录序列重新排列为按关键字有序的序列 1 2 np p p R R R⊆ ⊆ ⊆L 若待排序记录中的关键字 Ki(i=1，2，…，n) 都 不相同，则排序的结果是唯一的； 若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。 假设排序前的记录序列为 R1, …, Ri, … …, Rj, …, Rn (其中 Ki = Kj) 若在排序后的序列为 1 np i j p R R R R⊆ ⊆ ⊆ ⊆ ⊆ ⊆L L L 则称所用的排序方法是稳定的；反之，若为 1 np j i p R R R R⊆ ⊆ ⊆ ⊆ ⊆ ⊆L L L 则称所用的排序方法是不稳定的。 排序分为内部排序和外部排序两种。 内部排序指的是排序进行的过程中不使用计算机外部存储器。 它是一个逐步扩大记录的“有序序列”区域长度的过程。 外部排序指的是排序过程中需要对外存进行访问 1.2.3.1 直接插入排序 插入排序的基本思想是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。 有序序列R[1..i-1] 实现一趟插入排序的步骤为: 1) 在 R[1..i-1] 中查找 R[i] 的插入位置，即确定 j (0≤j＜i) 使得 R[1..j].key≤R[i].key＜ R[j+1..i-1].key 2) 将 R[j+1..i-1] 中的记录后移一个位置; R[ 无序序列 R[i..n] 有序序列R[1..i] R[ 一趟直接插入排序 无序序列 R[i+1..n]R[ 3) 将 R[i] 插入到 j+1 的位置。 void InsertSort(int data[], int n) { // 对数组元素 data[1..n] 进行直接插入排序 int i, j; for (i=2; i<=n; ++i) if (data[i] < data[i-1]) { data[0] = data[i]; // 复制为哨兵 data[i] = data[i-1]; for (j=i-2; data[0]=low; --j) data[j+1] = data[j]; // 记录后移 data[low] = data[0]; // 插入到正确位置 } } // InsertSort 折半插入排序的时间复杂度为 O(n2) 1.2.3.3 表插入排序 为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。 利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将 每个记录都调整到它们所应该在的位置上。 表插入排序的过程如下: 1. 构造一个只含一个记录的有序链表; 2. 从 i=2 起，将记录逐个插入该有序链表; www.ccidedu.com 3. 根据指针值所指将记录序列调整为一个有序序列; 1.2.3.4 希尔排序 希尔排序的基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时 再进行直接插入排序。 例如， 16 25 12 30 47 11 23 36 9 18 31 第一趟“增量为 5”的插入排序之后得到 11 23 12 9 18 16 25 36 30 47 31 第二趟“增量为 3”的插入排序之后得到 9 18 12 11 23 16 25 31 30 47 36 第三趟“增量为 1”的插入排序之后得到 9 11 12 16 18 23 25 30 31 36 47 从例子的排序过程可见， 由于希尔排序在前几趟的排序过程中，关键字较大的记录是“跳跃式”地往后移动， 同时使得在进行最后一趟插入排序之前序列中记录的关键字已基本有序，只需作少量关键字 比较和移动记录， 由此减少了整个排序过程中所需进行的“比较”和“移动”的次数。 希尔排序的时间复杂度和所取增量序列相关，例如有人证明得到，当增量序列为 2^(t-k-1)(k = 0, 1, …, t-1)时，希尔排序的时间复杂度为 O(n3/2)。 www.ccidedu.com 1.2.3.5 起泡排序 基本思想为：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。 一般情况下，起泡排序需进行 n-1 趟，但若第 i 趟起泡过程中，没有进行任何记录的交换， 则表明区段 R[1..n-i+1]中的记录已经按关键字从小到大有序排列，起泡排序已经完成，可见 排序结束的条件是 (i=1) 或者 (第 i 趟的起泡中没有进行记录交换)。 因此和直接插入相似，起泡排序过程中进行的“比较”和“移动”操作的次数取决于待 排记录序列的状态，在待排记录处于“正序”时取最小值，此时只需进行一趟起泡排序，反 之，在待排记录处于“逆序”时取最大值，此时需进行 n-1 趟起泡 待排记录序列状态 “比较” 次数 “移动”次数 正序 n-1 0 逆序 n(n-1)/2 3n(n-1)/2 起泡排序的时间复杂度为 O(n2)。 一般情况下，每经过每一趟起泡，待排记录序列的上界 i 减 1。但实际上，有的时候起泡 的上界可以缩减不止 1 个记录的位置， www.ccidedu.com void BubbleSort( int data[], int n ){ // 对数组元素 data[1..n] 进行起泡排序 i = n; while (i > 1) { // i>1 表明上一趟曾进行过记录的交换 lastExchangeIndex = 1; for (j = 1; j < i; j++){ if (data[j+1] < data[j] { temp=data[j]; data[j]=data[j+1]；data[j+1]=temp; lastExchangeIndex = j; // 记下进行交换的记录的位置 }//if }//for i = lastExchangeIndex; // 一趟起泡后仍处于无序状态的最后一个记录的位置 }// while }// BubbleSort 1.2.3.6 快速排序 起泡排序是通过一趟“起泡”选定关键字最大的记录，所有剩余关键字均小于它的记录 继续进行排序。 快速排序则是通过一趟排序选定一个关键字介于“中间”的记录，从而使剩余记录可以 分成两个子序列分别继续排序。 www.ccidedu.com 枢轴可取待排序列中的任何一个记录，但为方便起见，通常取序列中第一个记录 R[s]为枢 轴，以它的关键字作为划分的依据。 但如果 R[s] 是关键字最小或最大的记录，则一次划分蜕化为一趟起泡。 为避免之，通常取 R[s]、R[(s+t)/2] 及 R[t] 三者关键字中取中间值的记录为枢轴。⎯⎯ 三 者取中 ,可以推证，快速排序的平均时间复杂度为 O(nlogn)，在三者取中的前提下，对随机 的关键字序列，快速排序是目前被认为是最好的排序方法。如果借用起泡排序中设置记录“交 换与否”的布尔变量的作法，快速排序也适用于已经有序的记录序列。 1.2.3.7 简单选择排序 选择排序的基本思想是，在待排区段的记录序列中选出关键字最大或最小的记录，并将它移 动到法定位置。 第 i (i=1,2,…,n-1) 趟的简单选择排序 (序列中前 i-1 个记录的关键字均小于后 n-i+1 个记 录的关键字) 的操作为，在后 n-i+1 个记录中选出关键字最小的记录，并将它和第 i 个记 录进行互换。 简单选择排序的时间复杂度为 O(n2)。 无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相同，均为 1 1 ( 1( ) 2 n i n nn i − = −− =∑ ) www.ccidedu.com 而“移动”次数在待排序列为“正序”时达最小为 0，在“逆序”时达最大为 3(n-1)。除表 插入之外，简单选择排序所需移动记录是所有简单排序方法中最少。 简单选择排序方法本身是稳定的。 1.2.3.8 堆排序 利用“堆”的特性进行排序的方法称为“堆排序”。 若含 n 个元素的序列 {k1, k2, …, kn} 满足下列关系则称作“小顶堆”或“大顶堆”: 2 2 2 1 2 1 ni 1, 2, , 2 i i i i i i i i k k k k k k k k+ + ≤ ≥⎧ ⎧ ⎢ ⎥= ⎨ ⎨ ⎢ ⎥≤ ≥ ⎣ ⎦L或 “堆顶”元素即为序列中的“最小值”或“最大值”。 ⎩ ⎩ 堆排序的基本思想为:首先将待排记录序列建为“堆”，在输出堆顶记录之后，重新将序列中 的剩余记录调整为“堆”，并输出堆顶记录，如此反复执行，直至序列中只剩一个记录为止。 可见“堆排序”也是一种选择类的排序方法，每一趟从记录的无序序列中选出一个关键字最 大或最小的记录。 它的特点是，在第一趟选最大或最小关键字记录时先“建堆”，从而减少之后选择次大或次 小关键字等一系列记录时所需的比较和移动次数。 可以证明，堆排序的时间复杂度为 O(nlogn)。 和选择排序雷同，无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于“最好” 或“最坏”的状态。 1.3 性能分析 1.3.1 时间性能分析 1. 平均的时间性能 时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序 时间复杂度为 O(n2 直接插入排序、起泡排序和简单选择排序 )： 时间复杂度为 O(n): 基数排序 2. 当待排记录序列按关键字顺序有序时 直接插入排序和起泡排序能达到 O(n)的时间复杂度; 快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 4. 在三种时间复杂度为 O(n2)的简单排序方法中，以直接插入排序为最优，通常可将它与 其它排序方法，如快速排序等混合应用。 5. 当记录中的其它数据项所占空间比关键字大得多时，尚需考虑排序过程中移动记录所需 时间，在简单选择排序和“链表”的排序过程中记录的移动次数最少。 1.3.2 空间性能分析 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序以及希尔排序的空间 复杂度均为 O(1)； 2. 快速排序的平均空间复杂度为 O(logn)，此为递归工作栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n); 4. 链式基数排序需附设指针数组和队列首尾指针，则空间复杂度为 O(n+rd)。 1.3.3 排序方法的稳定性能 1. “稳定的”排序方法是指，对于两个关键字相同的记录，排序过程不改变它们在排序之前 的相对位置; 2. 快速排序、堆排序和希尔排序是不稳定的排序方法。 3. “稳定性”仅由排序方法本身所采用的策略决定，不应根据“算法”的描述形式来判别。 4. 对于不稳定的排序方法，只要能举出一个实例说明即可。 例如 : 对 { 4, 3, 4, 2 } 进行快速排序， 得到 { 2, 3, 4, 4 } 5. 对单关键字记录序列进行排序时，不需要考虑所选排序方法的稳定性，对多关键字的记 录序列进行 LSD策略排序时，必须采用稳定的排序方法。 1.4 时间复杂度 和算法执行时间相关的因素： 1、 算法选用的策略 2、 问题的规模 3、 编写程序的语言 4、 编译程序产生的机器代码的质量 5、 计算机执行指令的速度 一个特定算法的 “运行工作量” 的大小，只依赖于问题的规模（通常用整数量 n 表示）， 或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记 作： T (n) = O(f(n)) 称 T (n) 为算法的(渐近) 时间复杂度 www.ccidedu.com 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法 中重复执行的次数 作为算法运行时间的衡量准则。 “基本操作” 指的是，该操作重复执行次数和算法的运行时间成正比。 举例来看 例一 两个矩阵相乘 void mult(int a[], int b[], int& c[] int n) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=0; i