数据结构与算法第一二部分

数据结构与算法第一二部分1第1页，课件共68页，创作于2023年2月课程内容及教学概述第一部分基础知识第一章算法在计算中的作用第二章算法入门第三章函数的增长第四章递归式第五章概率分析和随机算法第二部分排序和顺序统计学第六章堆排序第七章快速排序第八章线性时间排序第九章中位数和顺序统计学

第2页，课件共68页，创作于2023年2月课程内容及教学概述第三部分数据结构第十章基本数据结构第十一章散列表第十二章二叉查找树第十三章红黑树第十四章数据结构的扩展第四部分高级设计和分析技术第十五章动态规划第十六章贪心算法第十七章平摊分析第3页，课件共68页，创作于2023年2月课程内容及教学概述第五部分高级数据结构第十八章B树第十九章二项堆第二十章斐波那契堆第二十一章用于不相交集合的数据结构第六部分图算法第二十二章图的基本算法第二十三章最小生成树第二十四章单源最短路径第二十五章各对顶点之间的最短路径第4页，课件共68页，创作于2023年2月第一部分基础知识第一章算法在计算中的作用第二章算法入门第三章函数的增长第四章递归式第五章概率分析和随机算法这部分内容主要介绍算法设计和分析问题，算法的表达方法、后面要用到的一些设计策略以及许多基本思想第5页，课件共68页，创作于2023年2月第一章算法在计算中的作用内容提要1.1算法1.2作为一种技术的算法什么是算法？研究算法的目的？第6页，课件共68页，创作于2023年2月第一章算法在计算中的作用1.1算法简单来说，算法（algorithm)就是定义良好的计算过程，取一个或一组值作为输入，并产生一个或一组输出。也就是，算法是一系列的计算步骤，用来将输入数据转换成数出结果。第7页，课件共68页，创作于2023年2月1.1算法例如，排序问题描述如下。输入：由n个数据构成的序列<a1,a2,…,an>.输出：对输入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.排序是基本的操作，有许多好的算法。排序算法的衡量因素很多，涉及到：数据的项数、已经排好的程度、对数据项取值可能的限制、存储设备的类型（内存、磁盘、磁带）等第8页，课件共68页，创作于2023年2月1.1算法算法的正确性：如果一个算法对每个输入都能得到正确的结果，并停止，则称为是正确的。不正确的算法对某些输入来说，可能不会停止，或得到的不是预期的结果。有时，如果算法的错误率可以得到控制的话，有时也是有用的。算法的描述：自然语言、计算机语言等。要求：算法的规格说明必须提供关于代码运行的计算过程的精确描述。第9页，课件共68页，创作于2023年2月1.1算法算法可以解决哪些类型的问题？举例互联网信息：管理、操作、检索、搜索引擎。互联网中的路由选择电子商务：信用卡号、密码、银行结单等的私密性与欺诈检测。欺诈检测物流配送第10页，课件共68页，创作于2023年2月1.1算法应用举例生物信息学领域：人类基因项目的目标是：找出人类DNA中的所有100000种基因，确定构成人类DNA的30亿种化学基对的各种序列，储存在数据库中，并开发出用于分析的工具。

------每一步骤都需要复杂的算法。制造业：稀有资源的分配。。。。。第11页，课件共68页，创作于2023年2月1.1算法各领域的例子形式上存在较大差异，但其底层所涉及到的支撑技术具有许多共性。许多有趣算法的两个共同特征：有很多候选的解决方案，其中大多数都不是所需要的。找到真正需要的解决方案往往不容易。有实际的应用。最短路径：运输公司成本；互联网中：路由节点数据结构算法必然涉及到数据结构：数据的组织方式。不同特性和应用场合。算法设计和分析技术面临新的问题时所需要的技术第12页，课件共68页，创作于2023年2月1.1算法关于NP完全问题-----有趣的问题：迄今为止，没有找出NP完全问题的有效解法，但也没有人能证明NP完全问题的有效解法是不存在的。如果NP问题中的任何一个问题存在有效算法，则该集合中其他所有问题都存在有效算法。有几个NP完全问题类似于（但又不完全同于）一些有着已知有效算法的问题，对一个陈述的一点小小改动，就会对其一直最佳算法的效率带来很大的变化。来自于实践，有了解或研究的必要。避免不必要的徒劳。例如：配货车的最短路径规划问题----旅行商问题。第13页，课件共68页，创作于2023年2月1.2作为一种技术的算法由于计算机的计算速度、存储空间总是有一定的局限，因此，研究性能更好的算法成为与研究高性能硬件类似的技术。例：幻方问题（纵横图）将1～n２放在n＊n（n为奇数）的方阵中，使得任意一行任意一列以及两条对角线上的所有元素之和均相等。如n=5时的方阵如下图所示。15８１241716147５232220136432119121092251811第14页，课件共68页，创作于2023年2月这一问题如果采用试探的方法，在ｎ值较大时，将难以求出，因为可能的状态数是ｎ２！个。经典的构造方法如下：将数1放在第一行的中间元素，然后往左上的位置上放入下一个数。若左上的位置已有数，则将其放入该数的下一行中的同一列的位置上。若已是最左或最上面位置上的元素，则其下一个位置的寻找方法是：将方阵卷成一个纸筒，然后依此再按同样的方向再找下一个位置，直到n×n个元素全部放入为止。1.2作为一种技术的算法15８１241716147５232220136432119121092251811第15页，课件共68页，创作于2023年2月1.2作为一种技术的算法ｎ＝５时的求解过程如下：１２

３

４

５

６

７８９１０１１１２１３１４１５１６１７１８１９２０２１２２２３２４２５第16页，课件共68页，创作于2023年2月第二章算法入门内容提要插入排序算法分析算法设计第17页，课件共68页，创作于2023年2月2.1插入排序先从插入排序算法开始排序问题描述如下。输入：由n个数据构成的序列<a1,a2,…,an>.输出：对输入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.插入排序的基本思想：将待排序表看作是左右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。类似于打牌时摸牌的过程，逐渐将抓到的牌插入到合适的位置上。

第18页，课件共68页，创作于2023年2月2.1插入排序伪代码如下：voidinsert_sort(elementtypeA[n+1]){for(i=2;i<=n;i++)//i表示待插入元素的下标

{temp=A［i］;//临时保存待插入元素，以腾出A［i］的空间

j=i-1;//j指示当前空位置的前一个元素

while(j>=1&&A［j］.key>temp.key)//搜索插入位置并腾空位

{A［j+1］=A［j］;j=j-1;}A［j+1］=temp;//插入元素

}}第19页，课件共68页，创作于2023年2月2.1插入排序求解过程简述循环不变式A12345n…………a1a2a3a4a5an

TempX第20页，课件共68页，创作于2023年2月2.1插入排序循环不变式与正确性证明证明3个性质：初始化：循环的第一轮迭代开始前，应该是正确的。保持：如果在循环的某次迭代之前是正确的，则在下一次迭代开始前，也应该保持正确。终止：当循环结束时，不变式给了一个有用的性质，有助于表明算法是正确的。前两个性质成立时，就能保障循环不变式再循环的每一轮迭代开始前都是正确的。

------与数学归纳法类似。证明过程：类似于归纳法初始化的证明。保持的证明。终止的证明。第21页，课件共68页，创作于2023年2月2.2算法分析算法分析就是对算法所需要的资源进行预测。资源涉及到：时间开销内存硬件资源通信带宽严格来说，需要对相关资源建模，以准确描述。例如，关于RAM、时间、硬件等的模型。然而，准确的描述是困难的。所用的数学模型，如组合数学、概率论等构建困难。指令的执行时间如果太精细要求，也是困难的。资源、数据的规模等都存在较大差异。第22页，课件共68页，创作于2023年2月2.2算法分析插入算法的分析voidinsert_sort(elementtypeA[n+1]){for(i=2;i<=n;i++){temp=A［i］;j=i-1;while(j>=1&&A［j］.key>temp.key){A［j+1］=A［j］;j=j-1;}A［j+1］=temp;}}n次n-1次n-1次n-1次各次循环次数和n-1次第23页，课件共68页，创作于2023年2月2.2算法分析空间性能:需要一个记录的辅助存储空间。时间性能:与数据表初始状态有关

最好（有序）最坏（逆序）平均

比较：

n-1(n+2)(n-1)/2O(n2)

移动：

2(n-1)(n+4)(n-1)/2因而适用于基本有序，规模小的数据第24页，课件共68页，创作于2023年2月2.3算法设计算法设计涉及到多种技术例如：增量式方法，插入排序就是采用的这种方法：先排好数组A[1..i-1],然后再将A[i]插入其中，以构成新的有序子数组。还有多种算法设计技术，例如：分治法动态规划法贪心法等。第25页，课件共68页，创作于2023年2月2.3.1分治法分治法(divide-and-conquer)许多问题的求解技术可以这样进行：原问题可以分解为若干子问题分别进行求解，适当综合子问题的解，可以得到原问题的解。其中，在许多情况下，各子问题得求解方法与原问题的求解方法类似，因而可以采用递归技术来实现。例如：二分查找方法快速排序算法第26页，课件共68页，创作于2023年2月2.3.1分治法分治法在每一层递归上都有3个步骤：分解（Devide)：将原问题分解成一系列子问题；求解（Conquer):递归地求解各子问题，若子问题“足够小”（递归出口），则直接求解。合并（combine)：合并子问题的解，以求解原问题的解。例如，归并排序（mergesort）的操作：分解：分解数组为两个n/2规模的数组；求解：对两个子序列分别采用归并排序进行求解；合并：合并两个已排序子序列，得到排序结果。其它例子：二分查找方法，快速排序算法第27页，课件共68页，创作于2023年2月2.3.1分治法归并排序（mergesort）的操作分析：关键操作是合并：为此，引入一个函数Merge(A,p,q,r),其功能是：合并已排序子序列A[p..q]和A[q+1..r]，得到已排序子序列A[p..r]。

merge(A,p,q,r){len1=p-q+1;len2=q-r;for(i=1;i<=lenq;i++)L[i]=A[p+i-1];//复制到另外的数组中

for(i=1;i<=len2;i++)R[i]=A[q+i];i1=1;i2=1;L[len+1]=∞;R[len2]=∞;//设置监视哨

for(k=p;k<=r;k++)if(L[i1]<=R[i2]){A[k]=L[i1];k++;i1++;}else{A[k]=L[i2];k++;i2++;}}第28页，课件共68页，创作于2023年2月2.3.2分治法分析正确性证明：

初始化：第一轮之前，即k=p时，是正确的。

保持：证明每一轮迭代正确。(之前正确，之后也正确)终止：最后一轮正确。第29页，课件共68页，创作于2023年2月2.3.2分治法分析性能分析：时间性能：分解：不费时间求解：2T（n/2）合并：O(n)

2T（n/2）+O(n)=>整个排序：分析可参见树形描述，可知为O(nlogn)空间性能：不能就地归并，一倍的辅助制空间ABCGFDajara1a2apa3alapE第30页，课件共68页，创作于2023年2月第三章函数的增长时间函数的描述:对给定的函数g(n),用O(g(n)表示函数集合：

O(g(n)={f(n)|存在常数c1,c2和n0,使得对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n)}

可以表示为f(n)=O(g(n)第31页，课件共68页，创作于2023年2月第四章递归式当算法递归调用时，运行时间通常可以用递归式来表示。例如Merge_sort算法的时间函数T(n)：

O(1)n=1T(n)=2T（n/2）+O(n)n>1

解为O(nlogn)

如何求解？代换法，递归树方法，主方法第32页，课件共68页，创作于2023年2月4.1代换法代换法求解的两个步骤：（1）猜测解的形式（2）用数学归纳法找出使得解真正有效的常数只能用于容易猜测的情形。例，确定递归式2T（n/2）+n的解为此，先猜测T(n)=O(nlogn),

然后证明T(n)<=cnlogn(c是某个常数）先假设：对n/2成立，即T(n/2)<=cn/2log(n/2),

则T(n)=2T（n/2）+n<=2(cn/2log(n/2))+n<=cnlog(n/2)+n=cnlogn-cnlog2+n<=cnlogn

问题：取决于猜测第33页，课件共68页，创作于2023年2月4.2递归树方法归并排序算法分析时，用到了递归树描述。每个节点代表：递归函数调用集合中的一个子问题的代价。将每一层内的代价相加，得到一层的代价；各层的代价和，构成总代价。更适合于分治法求解算法的分析描述。第34页，课件共68页，创作于2023年2月4.2递归树方法T(n)=3T(n/4)=cn2的求解示例cn2T(n/4)T(n)(a)(b)T(n/4)T(n/4)cn2c(n/4)2T(n/16)c(n/4)2c(n/4)2T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)T(n/16)(c)cn23/16c(n/4)29T(n/16)第35页，课件共68页，创作于2023年2月4.3主方法主方法（mastermethod)主方法给出求解如下形式的递归式方法：

T(n)=aT(n/b)+f(n)

其中，a>=1,b>1是常数

f(n)是渐近正的函数。描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。每个子问题的求解时间为T(n/b)，划分和合并的时间为f(n).第36页，课件共68页，创作于2023年2月第二部分排序和顺序统计学

排序是软件设计中最常见的运算之一，因而成为算法分析与设计中最常用的讨论对象。已经提出了许多排序算法。按照所用到的基本方法，可概括为：插入排序、交换排序、选择排序、归并排序、基数排序等。排序——将数据表（a1,a2,……，an）调整为按关键字从小（大）到大（小）排列的过程。排序问题描述如下。输入：由n个数据构成的序列<a1,a2,…,an>.输出：对输入序列的排序<a’1,a’2,…,a’n>，使得a’1≤a’2≤…≤a’n.第37页，课件共68页，创作于2023年2月第六章堆排序堆排序：利用堆进行的排序。属于选择排序一类。定义：称n个元素组成的序列(a1,a2,…，an)

为堆，当且仅当满足下面关系。（其中ki是元素ai的关键字）

（1）ki≤k2i;ki≤k2i+1(2i≤n；2i+1≤n)

或 （2）ki≥k2i;

ki≥k2i+1 (2i≤n；2i+1≤n)如果将此序列对应到编号的完全二叉树，

a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…第38页，课件共68页，创作于2023年2月第六章堆排序如果将此序列对应到编号的完全二叉树，则堆的定义可用完全二叉树中的有关术语解释为：每一结点均不大于(或不小于）其左、右孩子结点的值。若序列(a1,a2,…,an)是堆，则堆顶(完全二叉树的根)必为序列中的最小或最大值。将根最大的堆称为大根堆，根最小的堆称为小根堆.a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…ai≥a2i;ai≥

a2i+1第39页，课件共68页，创作于2023年2月第六章堆排序—堆示例1009080706065553050103020405065758090大根堆小根堆第40页，课件共68页，创作于2023年2月第六章堆排序—堆示例例：判断下面数据是否是堆：(5,23,16,68,64,72,71,73,45,79,90,81,75,94,97)解：对应的二叉树形式如下：52316686472717345799081759497123456789101112131415不是堆！第41页，课件共68页，创作于2023年2月第六章堆排序堆排序思想（约定进行增排序，因而采用大根堆）如果初始序列是堆，则可通过反复执行如下操作而最终得到一个有序序列：筛选过程即输出根：即将根（第一个元素）与当前子序列中的最后一个元素交换。调整堆：将输出根之后的子序列调整为堆。如果初始序列不是堆，则首先要将其先建成堆，然后再按（1）的方式来实现。第42页，课件共68页，创作于2023年2月第六章堆排序由此可知，实现堆排序需要解决两个问题：（1）如何由一个无序序列建成一个堆？（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？问题（2）的解决方法是：在输出堆顶元素之后，以堆中最后一个元素替代之，此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。我们称自堆顶至叶子的调整过程为“筛选”。问题1的解决方法是：从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第⌞n/2⌟个元素，由此“筛选”只需从第⌞n/2⌟个元素开始。第43页，课件共68页，创作于2023年2月1009080706065553050100509050输出根：100705090第六章堆排序第44页，课件共68页，创作于2023年2月第六章堆排序907080506065553050100308030输出根：1006530909080第45页，课件共68页，创作于2023年2月第六章堆排序voidsift(elementtypeA[],intn,intk,intm)//对数组中下标为1～n中的元素中的序号不大于m的以k为根的子序列调整{x=A[k];finished=FALSE；

i=k;j=2*i;//i指示空位，j先指向左孩子结点

while(j<=m&&!finished){if(j<m&&A[j].key<A[j+1].key)j=j+1;//让j指向左右孩子中的最大者

if(x.key>=A[j].key)finished=TRUE;//根最大

else{A[i]=A[j];//大的孩子结点值上移

i=j;j=2*j;}//继续往下筛选

}A[i]=x;}第46页，课件共68页，创作于2023年2月如何由一个无序序列建成一个堆？通过反复调用筛选操作来实现。建堆过程要从下往上逐棵子树地进行筛选，即根的下标按照从n/2到1的次序将各子树调整为堆。第六章堆排序第47页，课件共68页，创作于2023年2月第六章堆排序例：由初始序列（12,15,30,80,100,46,78,33,90,86,64,55,120,230,45）建大根堆1215308010046783390866455120230452345678910111213141512307812046908023030783010015861523012120125512建成的堆：(230,100,120,90,86,55,78,33,80,15,64,12,46,30,45)

第48页，课件共68页，创作于2023年2月第六章堆排序voidheap_sort(elementtypeA[],intn){for(i=n/2;i>=1,i--)sift(A,i,n);//建初始堆

for(i=n;i>=2;i--){A[i]<==>A[1];//输出根

sift(A,1,i-1);//调整子序列为堆

}}算法正确性证明：初始化：保持：终止：第49页，课件共68页，创作于2023年2月第六章堆排序算法时间复杂度分析：

voidsift(elementtypeA[],intn,intk,intm)//对数组中下标为1～n中的元素中的序号不大于m的以k为根的子序列调整{x=A[k];finished=FALSE；

i=k;j=2*i;//i指示空位，j先指向左孩子结点

while(j<=m&&!finished){if(j<m&&A[j].key<A[j+1].key)j=j+1;//让j指向左右孩子中的最大者

if(x.key>=A[j].key)finished=TRUE;//根最大

else{A[i]=A[j];//大的孩子结点值上移

i=j;j=2*j;}//继续往下筛选

}A[i]=x;}

O(nlog2n)a1a2a3a7a6a5a8a9a4a11a10a13a1212345678910111213…第50页，课件共68页，创作于2023年2月第七章快速排序基本思想：分治法

将数据表划分为左右两部分，其中：左边的所有元素都小于右边的所有元素；然后，对左右两部分分别进行快速排序。划分方法：选定一个参考点（中间元素），所有元素与之相比较，小的放左边，大的放右边。第51页，课件共68页，创作于2023年2月第七章快速排序具体划分方法：选择第一个元素作为中间元素。划分：(1)先保存该元素的值到其它位置，腾出其空间。(2)从后往前搜索一个比中间数小的元素，并将其放置到前面的这个空位上。(3)从前往后搜索一个比中间数大的元素，并将其放置到后面的这个位置上。重复(2)，(3)，直到两边搜索的空位重合时为止，此时将中间元素放在该空位中。第52页，课件共68页，创作于2023年2月用快速排序算法对数据表从小到大进行排序。

A=(12,5,4,19,25,1,34,7,10,23,8,5)第七章快速排序解：(125419251347102385)5x=12

12

5419

8

25

2310

134

7

()()

71

548

105()()12

19

232534()

4515

7

810()()()12

252319()341

4

55

87101219

252334()()第53页，课件共68页，创作于2023年2月第七章快速排序voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//对数组A中下标为s～t的子表进行划分{x=A[s];//保存中间元素，腾出空位

i=s;j=t;while(i!=j){while(i<j&&A[j].key>x.key)j--;if(i<j){A[i]=A[j];i=i+1;}while(i<j&&A[i].key<x.key)i++;if(i<j){A[j]=A[i];j=j-1;}}A[i]=x;*cutpoint=i;}第54页，课件共68页，创作于2023年2月第七章快速排序//对数组A中下标从s到t的元素组成的子表快速排序voidQuick_sort(elementtypeA[n],ints,intt){if(s<t){partition(A,s,t,*i);//划分

Quicksort(A,s,*i-1);//对前面子表快速排序

Quicksort(A,*i+1,t);//对后面子表快速排序

}}第55页，课件共68页，创作于2023年2月第七章快速排序时间复杂度分析：（可先画出其递归树，再分析）一般情况(每次等分子表):因此，T(n)=2T（n/2）+O(n)=>整个排序：分析可参见树形描述，可知为O(nlogn)O(nlog2n)（a1a2a3an

）表长为n（a1’a2’)x(a3’an’）表长为n/2（）（）（）（）（）每个表长为1nn/2n/2---n---n---nlogn…第56页，课件共68页，创作于2023年2月第七章快速排序最坏情况（每次划分的结果是1：k-1）：T(n)=T（n-1）+c(n)T(n)=O(n2)快速排序的平均时间接近于最佳时间，例如，即使是每次的划分是9：1。T(n)=T（9n/10）+T(n/10)+c(n)仍是O(nlogn)数量级的。

nn/1081n/100---cn---cn---cnLog10/9n…1log10n9n/10第57页，课件共68页，创作于2023年2月第七章快速排序正确性证明：初始化：保持：终止：voidpartition(elementtypeA[n],ints,intt,int*cutpoint)//对数组A中下标为s～t的子表进行划分{x=A[s];//保存中间元素，腾出空位

i=s;j=t;while(i!=j){while(i<j&&A[j].key>x.key)j--;if(i<j){A[i]=A[j];i=i+1;}while(i<j&&A[i].key<x.key)i++;if(i<j){A[j]=A[i];j=j-1;}}A[i]=x;*cutpoint=i;}第58页，课件共68页，创作于2023年2月第八章线性时间排序8.1排序算法时间下界前述排序算法都是比较排序：元素间的次序基于元素间的比较时间复杂度下界为O(nlgn).排序性能分析的决策树模型以3个元素的比较为例第59页，课件共68页，创作于2023年2月8.1排序算法时间下界以3个元素的比较为例内部节点：对应一个比较操作分支：对应一次比较的一种情况叶子节点：对应一个排列1：2≤>2：31：3(1,2,3)1：3(2,1,3)2：3(1,3,2)(3,1,2)(