数据结构与算法 课件 第1章 数据结构概述

第1章数据结构概述数据结构课程主要讨论数据的表示（数据的结构）和数据处理的基本方法（算法）。要想成为一个优秀的程序设计人员，至少需要以下三个条件：①

能够熟练地选择和设计各种数据结构和算法。

②至少要能够熟练地掌握一门程序设计语言。

③熟知所涉及的相关应用领域的知识。1【本章重点】①数据结构及相关概念；②数据的逻辑结构和存储结构，二者的关系；③算法及特性；④算法的时间复杂度和空间复杂度的概念。2【本章难点】①抽象数据类型的理解和使用；②描述算法的工具；③算法的时间复杂度分析与计算。3【本章内容】数据结构的基本概念算法习题141.1数据结构的基本概念软件开发的三个阶段（1）分析阶段：对问题进行分析，抽象出数据模型，形成求解问题的基本思路，确定解决问题的方案；（2）设计阶段：将数据以及数据之间的关系存储到计算机的内存中，设计数据处理的算法；（3）实现阶段：将算法转换为用某种程序设计语言编写的程序，并进行测试、修改，直到得到问题的解答。5关于数据结构的基本术语数据是信息的载体，它是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例如，一个代数方程的求解程序中所用的数据是整数和实数；一个编译程序或文本编辑程序中所使用的数据是字符串。随着计算机应用领域的扩大，数据的含义更为广泛，如图像、声音等都可以通过编码而属于数据的范畴。数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。数据项是具有独立含义的，不可再分割的最小标识单位。一个数据元素可以由若干个数据项组成，6数据结构（DataStructure）是数据元素之间的相互关系，即数据的组织形式。一般来说，数据结构所研究的主要内容包括以下三个方面：（1）数据的逻辑结构——数据元素之间的逻辑关系。（2）数据的存储结构——数据元素及其关系在计算机中的存储方式，数据的存储结构又称为数据的物理结构。（3）数据的运算——对数据施加的操作，即数据的运算。7数据的逻辑结构（1）集合：数据元素之间只是“属于同一集合”的关系。（2）线性结构：数据元素之间存在“一对一”的前后顺序关系，除第一个元素和最后一个元素之外，其余元素都有唯一的一个直接前驱元素和唯一的一个直接后继元素。（3）树形结构：数据元素之间存在“一对多”的层次关系，除最顶层的元素之外，其余元素都有若干个直接给后继元素。（4）图结构：数据元素之间存在“多对多”的任意关系，每个元素都有若干个直接前驱元素和若干个直接后继元素。8数据的存储结构（1）顺序存储结构

元素之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于程序语言的数组（又称为向量）来描述的。

该方法主要应用于线性数据结构，非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。（2）链式存储结构

通过元素存储地址的指针表示数据元素之间的逻辑关系，即逻辑上相邻的元素在物理位置上不一定相邻。通常要借助于程序语言的指针类型来描述它。（3）索引存储结构

在存储数据元素的同时，还需要有索引表，索引表中的每一项称为索引项，其一般形式是（关键字，地址），关键字是能够唯一标识一个元素的那些数据项。（4）散列存储结构

根据数据元素的关键字计算出该元素的存储地址。又称为计算寻址的方式。91.2算法算法的定义

算法是对特定问题求解步骤的描述，是指令的有限序列。算法的性质（1）输入性：0至多个输入。（2）输出性：1至多个输出。（3）有穷性:对于合法的输入值，算法在执行有穷步之后结束。（4）确定性:对于相同的输入执行相同的路径，即对于相同的输入只能得出相同的输出。（5）可行性:用于描述算法的操作都是足够基本的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。10（1）自然语言

优点：容易理解；缺点：不够严谨，容易出现二义性。（2）流程图

优点：直观易懂；缺点：严密性不如程序设计语言，灵活性不如自然语言。（3）程序设计语言

优点：描述算法能够由计算机执行；缺点：抽象性差，设计者在设计算法时过于受到程序设计语言的语法规则限制，往往忽视了算法的正确性和逻辑性。（4）伪代码

伪代码是介于自然语言和高级语言之间的方法，例如用类C语言来描述算法。优点：重点给出算法的逻辑，并且不受语言的语法规则限制。【例】（P8）用伪代码描述求两个正整数的最大公约数。11描述算法的工具对算法的评价标准

通常从正确性、易读性、健壮性和高效性等四个方面评价算法的质量。算法的高效性

算法的高效性包括时间特性和空间特性。时间特性是指执行算法所需要的计算时间长短。空间特性则是执行算法所需要的辅助存储空间大小。（1）算法时间特性的分析

一个算法所需的计算时间，应当是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数（称为频度）与该语句执行一次所需时间的乘积。

我们通过算法的时间复杂度来衡量算法的时间特性。12算法时间复杂度的计算【例1.2】求两个n阶方阵的乘积C＝A×B，其算法如下：＃definen自然数voidMatrixmlt(intA[n][n],intB[n][n],intC[n][n]){ inti,j,k;

语句频度

for(i=0;i<n;i++) //语句①

n+1

for(j=0；j<n;j++){ //语句②

n(n+1)

C[i][j]=0; //语句③

n2

for(k=0;k<n;k++)//语句④

n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j];//语句⑤

n3 }}

算法中所有语句的频度之和为T(n)=2n3+3n2+2n+1。算法的语句频度之和T(n)是矩阵阶数n的函数，n是算法求解方阵乘积问题的规模。13

一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的时间复杂度记为T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，f(n)一般是算法中频度最大的语句频度。例如，算法Matrixmlt的时间复杂度是T(n)=O(n3)，这里的f(n)=n3是该算法中语句⑤的频度。由此可见，当有循环嵌套时，算法的时间复杂度是由最内层语句的频度f(n)决定的。

计算算法的时间复杂度要考虑问题的规模。14【例1.3】交换a和b的值。temp=a;a=b;b=temp;

以上三条单个语句的频度都为1，该算法的执行时间是一个与问题规模n无关的常数，时间复杂度记作T(n)=O(1)。事实上，只要算法的执行时间不随着问题的规模增加而增长，即使算法中有成百上千条语句，其时间复杂度也只是O(1)。15【例】在一维数组A[n]中顺序查找值为k的元素，顺序查找算法如下：intFind(intA[],intn,intk){ for(i=0;i<n;i++) if(A[i]==k)break; returni;}

算法从A[0]开始查找，如果A[0]的值就等于k，那么比较一次就查找到了，这是最好情况；如果A[n-1]的值等于k，则需要比较n次才能查找到，这是最坏情况；平均情况下需要比较(n+1)/2次。

计算算法的时间复杂度要考虑最坏情况。1617【例1.4】判断n是否为素数。voidprime(intn){ inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素数",n);

elseprintf("%d不是素数",n);}设语句i++；的频度为f(n)，由i<sqrt(n)可知f(n)<sqrt(n)。时间复杂度应考虑最坏的情况，所以18【例1.5】变量计数。 i=1；1 while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤log2n，取最大值f(n)=log2n，T(n)=O(f(n))=O(log2n)常见的时间复杂度按数量级递增排列：常量阶O(1)<对数阶O(log2n)<线性阶O(n)<线性对数阶O(nlog2n)<平方阶O(n2)<立方阶O(n3)<…<k次方阶O(nk)<指数阶O(2n)算法的空间复杂度算法的空间复杂度是指在算法执行过程中所需要的辅助存储空间数量。辅助存储空间是除算法本身和输入输出数据所占存储空间之外，算法运行时临时开辟的存储空间，记为：S(n)=O(f(n))

其中n为问题的规模，分析方法与算法的时间复杂度类似。19算法的易读性

一个高质量的算法除了正确和运行效率高之外，还对算法的易读性有一定的要求。算法的易读性主要体现在算法的结构、代码的书写格式以及注释等方面。（1）算法的结构

解决某个较为复杂问题的算法通常也是由一个个模块组成的，而每个模块的功能相对独立。尽可能做到高内聚、低耦合。（