数据结构与算法分析-PPT

1第一章

绪论教学内容：1.1数据结构的原则1.2抽象数据类型和数据结构1.3问题、算法和程序学习要求： 理解、掌握算法的基本概念和简单的算法分析、数据和数据结构的基本概念、数据的逻辑结构和存储结构的基本概念及其性质和两种结构之间的关系。12引言

二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。23计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。34

在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。451.1数据结构的原则数据结构：一类数据的表示及其相关操作学习数据结构的必要性 计算机功能强大更复杂的问题 更复杂的问题更大的计算量 工作越复杂越偏离人们的日常经验故：必须有一种数据结构来组织各种复杂的数据。 任何一种数据项集合都必须具备查询、排序、修改的功能，如果选择一个好的数据结构和算法将会对程序的运行时间产生巨大的影响。5一、为什么要学习数据结构？1、什么是程序、软件？

N.沃思（NiklausWirth)教授提出：程序=算法+数据结构67程序的主要目标是存储信息和检索信息,而基础是信息表示.

程序设计核心目标：（１）设计一种容易理解、编码和调试的算法（软件工程原理）（２）设计一种能有效利用计算机资源的算法（数据结构和算法）程序简明清晰（简洁）7程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）82、电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。9（1）数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。10（2）非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述1112例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表1213例2人机对奕问题树……..……..…...…...…...…...1314例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图14例4:电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。15例5:田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。16例6：田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M跳高跳远标枪铅球200M100M1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。17（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米A B CDE F（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。解法如下：18姓名项目1项目2项目3丁一ABE马二CD

张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛19总结： 求解非数值计算的问题主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。20二、数据结构课程的形成和发展：形成阶段：

60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：

数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。

70年代后期，我国高校陆续开设该课程。21《数据结构课程》所处的地位：22231.2抽象数据类型和数据结构

一、名词解释类型：是一组值的集合。如：整数数据项：一条信息或其值属于某种类型的一条记录。如：学生记录里的姓名项数据类型：一种类型和定义在该类型上的一组操作。如整型变量是整数数据类型的一个成员，而加法是定义在整数类型上的一种操作2324抽象数据类型(ADT)：指数据结构作为一个软件组件的实现每个ADT的操作由它的输入和输出定义每个ADT的操作细节是封装的数据结构：是ADT的实现与ADT联系的操作都是由一个成员函数来实现“数据结构”常指计算机内存中的数据“文件结构”常指外存储器中数据的组织2425二、什么是数据结构？

基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图2526逻辑形式与物理形式数据项包括逻辑与物理形式逻辑形式是由ADT给出的数据项的定义物理形式是数据结构中对数据项的实现数据类型（*.h）ADT:类型操作数据项:

逻辑形式数据项:

物理形式数据结构:(class)存储空间子程序2627数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系2728元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储28291536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素114001346

元素4∧

…….

……..

…….1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h2930

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：302、数据结构的定义定义1----

数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。3132数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科323、数据结构的三个方面的含义：逻辑结构---数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算（算法）33（1）逻辑结构---线性结构----

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串非线性结构----

一个结点可能有多个直接前趋和直接后继。例如：树、图、多维数组、广义表等。34（2）存储结构存储结构两方面的内容：数据元素自身值的表示（数据域）该结点与其它结点关系的域（链域）四种基本的存储方法：顺序存储方法（结构）链接存储方法（链式存储结构）索引存储方法散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。35逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。3637选择数据结构：（学生信息管理系统）分析问题，以确定任何算法均会遇到的资源限制确定必须支持的基本操作，并度量每种操作所受的资源限制。选择最接近这些开销的数据结构效率：如果能在所要求的资源限制(resourceconstraint)内将问题解决好，则称该算法是有效率(efficient)的。代价：解决一个问题所耗费的关键资源(如时间、空间)。选择数据结构要考虑的三个问题：1、开始时是将所有数据项都插入数据结构还是与其他操作混合在一起插入2、数据项能否删除3、所有数据项是否按某一个已经定义好的顺序排列，是否允许查找特定的数据项3738代价与效益每一个数据结构都与代价与效益联系在一起很难说一种算法在所有情况下都比其他算法好一个数据结构必须要求：空间存储数据项时间执行单个操作程序设计工作每一个问题都有可利用空间和时间的限制只有对问题特性进行仔细分析后才能得到解决问题的最好的数据结构银行例子：开户：几分钟交易：几秒钟销户：月末（更长时间）3839学习的目的对每个数据结构加强对存在代价与效益的观念掌握常用的数据结构——将常用的数据结构放入你的工具包理解怎样去衡量一个数据结构或程序的代价——评价标准39401.3问题、算法和程序问题：需要完成的任务一组输入必有一组相应的输出问题的定义应包括对任何行为可行方案所需资源的限制4041问题问题函数函数是输入(定义域domain)和输出(值域range)的一种映射关系函数的输入可是一个值或一个实例这些值组成的输入称为函数的参数对于一个给定的输入，函数每次计算所得的输出应必然相同4142算法和程序算法：解决一个问题的方法或过程.处方对于一个问题的算法给定一输入，必然会转化为一个输出输入输出的映射一个问题可用多种算法来解决算法的属性：正确性具体步骤确定性有限性可终止性程序：用某种程序设计语言对一种算法的实现42算法的概念和描述：一、算法的概念：

所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。431.算法----求解一个特定任务的指令的有限序列。

例7.求a[0]..a[n-1]中n个数的平均值(假定n>0)。

floataverage(floata[],intn){inti；floats=0.0；//累加器赋初值

for(i=0；i<n；i++)

s=s+a[i]；//a[i]累加到s中

s=s/n；//计算平均值

printf(“ave=%f”,s)；//输出

return(s)；//返回

}其中：a,n为输入量；s为输出量。442.算法的5个特征(1)有穷性：在有限步(或有限时间)之后算法终止。例8.{i=0；s=0；

while(i<=10)s+=i；

i++；//使i趋于10

}45(2)确定性：无二义性。例9：{x=5；y=10；

z=x+++y；

printf(“%d,%d,%d”,x,y,z)；

}x+++y解释为：x+(++y)？还是(x++)+y？例:intx=0;表达式：x+++x++的值46(3)可行性：可以在计算机上实现。for(i=1,s=0；i<1000000000000；++i)

s++；？？？(4)输入：有0或多个输入量。(5)输出：至少有一个输出量。473.算法设计要求

(1)正确性

a.无语法错误；

b.对n组输入产生正确结果；

c.对特殊输入产生正确结果；

d.对所有输入产生正确结果。

(2)可读性：“算法主要是为了人的阅读与交流”。

(3)健壮性

scanf(“%d”,&x)；y/=x；？？？

(4)高效与低存储量48下列描述不符合算法的什么特征和要求？例10

voidsuanfa1()

{inti,s=0；

for(i=0；i>=0；i++)//死循环

s++；//不能终止

}49例11

floatsuanfa2()

{intx,y；

scanf(“%d”,&x)；

y=sqrt(x)；//当x<0时,出错

return(y)；

}5051算法的描述工具：（1）自然语言；（2）程序设计语言；（3）流程图（框图）；（4）伪语言；是一种包括高级程序设计语言的三种基本结构（顺序、选择、循环）和自然语言成分的“面向读者”的语言。5152算法的描述工具：（5）likeC++或likeC

介于伪码语言和程序设计语言之间的一种表示形式。保留了C++或语言的精华；不拘泥与C++或C语言的语法细节；同时在C中也添加了一些C++的成分。特点：便于理解、阅读；能方便的转换成C++或C语言。目的：便于简明扼要的描述算法；突出算法的思路。52算法描述举例

问题：设一维数组a[0..n-1]中已有n个整数,其中n为个常数,试设计算法:求a[]中的最大值。

算法基本思想:

1.maxai=a[0]；

2.i=1；

3.若i<=n-1,则：

3.1若a[i]>maxai,则maxai=a[i]；

3.2i++；

3.3转3

4.maxai为最大值。53Ｃ函数(算法)//求数组a中n个元素的最大值inta_maxint(inta[],intn){intj,maxai=a[0]；//最大值的初值

for(j=1；j<=n-1；j++)

if(a[j]>maxai)//比较元素大小

maxai＝a[j]；//新的最大值

printf("maxai＝%d\n",maxai)；//输出

returnmaxai；}54二、一个算法必须满足以下五个准则：（1）有穷性---执行了有限条指令后一定要终止。（2）确定性（无二义）---算法的每一步操作都必须有确切定义，不得有任何歧义性。55（3）可（能）行性---算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。（4）输入数据---一个算法有n（n>=0)个初始数据的输入。（5）输出数据---一个算法有一个或多个与输入有某种关系的有效信息的输出。思考：算法与程序有何区别？56例12一个不是算法的例子(1)begin(2)n<=0(3)n=n+1(4)repeat(3)(5)end例13一个不超过100次计数的算法(1)begin(2)n<=0(3)n=n+1(4)ifn=100do(5),elserepeat(3)(5)outputn(6)end57三、算法的描述和实现

描述---可采用条列式步骤、流程图、伪码（PseudoCode）、程序语句等。实现---必须借助程序设计语言提供的数据类型及其运算。

本课的描述---采用类C++语言。5859例14：运用伪码编写：顺序查找某一特定值的算法。ProcedureS_Search(data,keyvalue)设I为1；

while(){if(欲查找值等于data[I])

printf(“找到数据”)；

elseif(I>数据个数)

printf(“未能找到数据”)；

I++；}59四、算法的简单分析1算法的评价准则（首先，算法必须是“正确”的）（1）执行算法所耗费的时间（效率要高）。（2）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。（3）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。6061算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量

A.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣6162B.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适6263时间复杂度：基本操作重复执行的次数的阶数T(n)=o(f(n))空间复杂度：s(n)=o(f(n))例15：N×N矩阵相乘for(i=1;i<=n;i++)//n+1for(j=1;j<=n;j++)//n(n+1){c[i][j]=0;//n*n for(k=1;k<=n;k++)//n*n(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n*n*n}632算法的简单分析：1、程序正确性的四个层面：（1）不含语法错误（2）程序对于n组输入数据能够得出满足规格说明要求的结果。（3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。（4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。642、算法效率的度量（1）程序运行所耗费的时间(由下列因素决定)：

算法所选用的策略

问题的规模

书写程序所采用的语言

编译程序所产生的机器代码的质量

机器执行指令的速度一个算法耗费的时间=算法中每条语句的执行时间之和。若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。65算法的时间复杂度----

算法(或程序)中基本操作(或语句)重复执行的次数的总和。

设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)；时间复杂度记作T(n),有：

T(n)=O(f(n))

例16{ints；

scanf(“%d”,&s)；

s++；

printf(“%d”,s)；

}

其中：语句频度为：f(n)=f(1)=3

时间复杂度为：T(n)=O(f(n))=O(3)=O(1）

O(1)称成为常量阶/常量数量级66例17分析下面的算法voidsum(inta[],intn){ints=0,i；//1次

for(i=0；i<n；i++)//n次(严格为2*(n+1)次）

s=s+a[i]；//n次

printf(“%d”,s)；//1次

}其中：语句频度为：f(n)=1+n+n+1

时间复杂度为：T(n)=O(f(n))=O(2n+2)=O(n）

O(n)称成为线性阶/线性数量级67例18分析下面的算法1.voidsum(intm,intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=m；i++)//m次

4.{for(j=1；j<=n；j++)//m*n次

5.s++；//m*n次

6.printf(“%d”,s)；//m次

7.}8.}

其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1

当m=n时,f(n)=2n2+2n+1T(n)=O(f(n))=O(2n2+2n+1)=O(n2)O(n2)

称成为平方阶/平方数量级68例19分析下面的算法；当n=5,指出输出结果1.voidsum(intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=n；i++)//n次

4.{for(j=1；j<=i；j++)//?次

5.s++；//?次

6.printf(“%d”,s)；//n次

7.}8.}

其中：第4行的次数为1+2+...+n=n(1+n)/2

第5行的次数为1+2+...+n=n(1+n)/2

f(n)=1+n+n(n+1)+n=n2+3n+1T(n)=O(f(n))=O(n2）

O(n2）称成为平方阶/平方数量级6970例20：求解：S=1!+2!+…..+n!算法1：

longsum_of_fac(intn){longs=0,t,i,j;for(i=1;i<=n;i++)//n次

{t=1;//n次

for(j=1;j<=i;j++)//n*(n+1)/2次

t*=i;//n*(n+1)/2次

s+=t;//n次

}return(s);//1次

}f(n)=n+n+n*(n+1)/2+n*(n+1)/2+n+1=n2+4n+1T(n)=O(f(n))=O(n2)求i!7071例20(续）：求解：S=1!+2!+…..+n!算法2：

longsum_of_fac(intn){longs=0,t,i;t=1;//1次

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

{t*=i;//n次

s+=t;//n次

}return(s);//1次

}f(n)=1+n+n+n+n+1=3n+2T(n)=O(f(n))=O(n)求i!7172Voidmain(){intnum,fn,fn1,fn2,i;scanf(“%d”,&num);if(num<=1)printf(“Fibonacciof%d=1\n”,num);else{fn2=0;fn1=1;for(i=2;i<=num;i++){fn=fn1+fn2;fn2=fn1; fn1=fn;}printf(“Fibonacciof%d=%d\n”,num,fn);}}讨论：当num<=1时，执行4个指令，执行次数为4；当num>1时，执行3+2+1+num+3*(num-1)+(num-1)+1=5*num+3个指令，执行次数为5*num+372（2）问题的规模（size