数据结构与算法

第1页，共54页，2023年，2月20日，星期五算法（Algorithm）定义定义：

Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.

算法是规则的有限集合，是为解决特定问题而规定的一系列操作。

2第2页，共54页，2023年，2月20日，星期五算法、语言、程序的关系1.算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。2.语言：描述算法的工具，算法可用自然语言、框图或高级程序设计语言进行描述。3.程序：是算法在计算机中的实现，会受到语言和计算机系统的限制。3第3页，共54页，2023年，2月20日，星期五举例:编写一个程序，输入任意自然数N，计算其阶乘。设计思想算法程序4第4页，共54页，2023年，2月20日，星期五设计思想输入一个自然数N，计算1*2*3*……*N，输出其结果。5第5页，共54页，2023年，2月20日，星期五算法：定义三个整型变量S、I、N输入N的值分别给S、I赋初值，S←1，I←1若I的值小于等于N，执行第5步；否则执行第8步S←S*II←I+1返回第4步输出结果S结束6第6页，共54页，2023年，2月20日，星期五程序（选用VisualBasic语言编程）：PrivateSubCmdOk_Click()N=Val(TxtInput.Text)S=1I=1WHILEI<=NS=S*II=I+1WENDLblResult.Caption=Str(N)&”的阶乘：”&Str(S)EndSub演示7第7页，共54页，2023年，2月20日，星期五算法的特性3.有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2.确定性：算法中的每一个步骤必须有确定含义，无二义性。4.输入：有多个或0个输入5.输出：至少有一个或多个输出。1.可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算执行有限次而完成。

8第8页，共54页，2023年，2月20日，星期五算法的基本要素

算法中对数据的运算和操作

算术运算、逻辑运算、关系运算、数据传输

算法的控制结构顺序结构、选择结构、循环结构9第9页，共54页，2023年，2月20日，星期五算法设计的基本方法列举法归纳法递推递归：直接递归、间接递归减半递推回溯10第10页，共54页，2023年，2月20日，星期五算法的正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；11第11页，共54页，2023年，2月20日，星期五可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。健壮性

当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。12第12页，共54页，2023年，2月20日，星期五高效率与低存储量需求

通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。13第13页，共54页，2023年，2月20日，星期五对算法作性能评价

评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。

有关数量关系计算

14第14页，共54页，2023年，2月20日，星期五有关数量关系计算

数量关系评价体现在时间——时间复杂度数量关系评价体现在空间——空间复杂度关于算法执行时间语句频度

算法的时间复杂度数据结构中常用的时间复杂度频率计数

最坏时间复杂度

算法的空间复杂度

15第15页，共54页，2023年，2月20日，星期五关于算法执行时间定义：

一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。分析：

不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中基本运算的执行次数做出估计，从中得到算法执行时间的信息。16第16页，共54页，2023年，2月20日，星期五语句频度

定义： 语句频度是指该语句在一个算法中重复执行的次数。例如：算法语句对应的语句频度

1输入N12S=113I=114WHILEI<=Nn+15S=S*In6I=I+1n7WENDn8输出Str(S)1

总执行次数：Tn=4n+517第17页，共54页，2023年，2月20日，星期五算法的时间复杂度

一个特定算法的工作量的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))

称T(n)为算法的(渐近)时间复杂度，简称时间复杂度。一般情况下，随n的增大，算法执行时间的增长较慢的算法为最优算法。18第18页，共54页，2023年，2月20日，星期五例如给出X=X+1作为基本运算（1）x=x+1；时间复杂度为O(1)，称为常量阶；（2）for(i=1;i<=n;i++)x=x+1;时间复杂度为O(n)，称为线性阶；（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;时间复杂度为O(n2),

称为平方阶。19第19页，共54页，2023年，2月20日，星期五常用的时间复杂度频率计数

数据结构中常用的时间复杂度频率计数有7个:O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型20第20页，共54页，2023年，2月20日，星期五intSeqSearch（RecordListl,KeyTypek）/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/{l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return（i）;}605846352825221815126123456789101121第21页，共54页，2023年，2月20日，星期五（1）平均性态：平均时间复杂度P5A(n)=i=1nPiCi＝n1i=1nCi＝n1i=1n(n-i+1)=21(n+1)例：查找算法时间复杂度:

O(n)平均时间复杂度:

A(n)=(n+1)/222第22页，共54页，2023年，2月20日，星期五（2）最坏情况复杂性：最坏时间复杂度

P6定义：讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。如无特殊说明，所讨论的各算法的时间复杂度均指最坏情况下的时间复杂度。最坏时间复杂度:

W(n)=n+123第23页，共54页，2023年，2月20日，星期五voidbubble(inta[],intlength){将a中整数数组重新排序，达到递增有序}inti=0,j,temp;intchange;do{ change=false; for(j=1;j<length-i;j++) if(a[j]>a[j+1])

{temp=a[j];a[j]=a[j+1];a[j+1]=temp;change=true;} i=i+1;}while(i<length||change==true)}例如冒泡排序算法时间复杂度:

O(n2)24第24页，共54页，2023年，2月20日，星期五例两个矩阵相乘voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)25第25页，共54页，2023年，2月20日，星期五例选择排序voidselect_sort(int&a[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。

}//select_sort基本操作:

比较(数据元素)操作j=i;//

选择第i个最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}时间复杂度:

O(n2)26第26页，共54页，2023年，2月20日，星期五例：voidcmatrix(inta[][],intM,intN,intd)for(inti=0;i<M;i++)for(intj=0;j<N;j++)a[i][j]*=d;}算法的时间复杂度：O（M*N）27第27页，共54页，2023年，2月20日，星期五算法的空间复杂度

定义：

用空间复杂度作为算法所需存储空间的量度，记做：S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。28第28页，共54页，2023年，2月20日，星期五算法的存储量包括:1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间

若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。

若所需存储量依赖于特定的输入，则通常按最坏情况考虑。29第29页，共54页，2023年，2月20日，星期五1.2数据结构的基本概念（定义）数据结构的相关名词：数据数据元素数据集合数据处理数据结构30第30页，共54页，2023年，2月20日，星期五数据（Data）定义：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。31第31页，共54页，2023年，2月20日，星期五数据元素（DataElement）定义：

在数据处理中，每一个需要处理的对象都可以抽象成数据元素。简单情况下：18、11、35、23、16…春、夏、秋、冬父亲、儿子、女儿32第32页，共54页，2023年，2月20日，星期五复杂情况下

一个数据元素由一个或多个数据项组成，数据项是有独立含义的最小单位。在计算机中通常作为一个整体进行考虑和处理。例如：..................北京1983.11河北女

赵虹玲101住

址

出生年月

籍

贯性

别

姓

名

学

号

数据元素数据项例如：一次借书、一次球赛等33第33页，共54页，2023年，2月20日，星期五数据集合

具有某种公共特性的数据元素的集合。如：季节名集合、家庭成员集合、整数集合、学生集合、某运动场“比赛”集合等数据处理

对数据集合中的各元素以各种方式进行的运算，包括插入、删除、查找、更改等运算。34第34页，共54页，2023年，2月20日，星期五数据集合中各数据元素之间所固有的逻辑关系，即逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。主要目的：提高效率（时间、空间）数据结构主要研究的问题35第35页，共54页，2023年，2月20日，星期五6058463528252218151261234567891011利用有序表进行对分查找：6018625283522581512461234567891011利用无序表进行顺序查找：36第36页，共54页，2023年，2月20日，星期五数据结构（DataStructure）

一般情况下：

数据结构是指在具有相同特征的数据元素的集合中，各数据元素之间存在某种特定关系。这种关系反映了该集合中的数据元素所固有的一种结构，即数据的组织形式。例如表结构：..................北京1983.11河北女

赵虹玲101住

址

出生年月

籍

贯性

别

姓

名

学

号

37第37页，共54页，2023年，2月20日，星期五数据结构（DataStructure）树型结构图结构1254338第38页，共54页，2023年，2月20日，星期五数据结构的内容

逻辑结构

存储结构

运算集合

39第39页，共54页，2023年，2月20日，星期五1.数据的逻辑结构定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。形式化描述：

B=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。根据数据元素之间关系的不同特性，通常分为四类基本的结构

集合结构、线性结构、树型结构、图状结构。40第40页，共54页，2023年，2月20日，星期五集合结构定义：

结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

集合例如：41第41页，共54页，2023年，2月20日，星期五线性结构定义： 结构中的数据元素之间存在着一对一的线性关系。

例如：线性表42第42页，共54页，2023年，2月20日，星期五树型结构定义：

结构中的数据元素之间存在着一对多的层次关系。

例如：

树43第43页，共54页，2023年，2月20日，星期五图状结构或网状结构

定义： 结构中的数据元素之间存在着多对多的任意关系。例如：

图44第44页，共54页，2023年，2月20日，星期五综上所述，数据的逻辑结构可概括为：线性结构——线性表、栈、队、数组逻辑结构非线性结构——树、图逻辑结构45第45页，共54页，2023年，2月20日，星期五逻辑结构的二元组表示B=（D,R）例1.5(P12)例1.6(P12)例1.7(P12)46第46页，共54页，2023年，2月20日，星期五m*n的矩阵是一个线性数据结构Am×n=a12a12┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amn47第47页，共54页，2023年，2月20日，星期五Am×n=a12a12┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnA=（12┅

j

┅n)我们可以把矩阵看成一个线性表：A=(12…

j…n)，其中j（1≤j≤n）本身也是一个线性表，称为列向量。矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j,…,amj)48第48页，共54页，2023年，2月20日，星期五Am×n=a12a12…a1j

…a1na21a22…a2j

…a2n┇┇ai1ai2…aij

…ain┇┇am1am2…amj

…amnB‖12┇i┇m我们还可以将数组Am×n看成另外一个线性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一个线性表，称为行向量，即：I=（