数据结构（第2版）（C语言实现）绪论.pptx

;;;;1.1数据结构的基本概念;抽象数据类型(ADTs:AbstractDataTypes);抽象数据类型可以用以下的三元组来表示：

ADT=（数据对象，数据对象之间的关系，在数据对象上的操作）

;例如，线性表的抽象数据类型描述如下：

ADTList

{

数据对象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

数据关系：R={ai-1,ai|ai-1，ai∈D，i=2，3，…，n}

基本操作：

InitList(L)

初始条件：表L不存在。

操作结果：构造一个空的线性表。

ClearList(L)

初始条件：表L已存在。

操作结果：表L被置为空。

ListLength(L)

初始条件：表L已存在。

操作结果：返回线性表L的元素个数。

…

}ADTList;1.3数据的逻辑结构与存储结构;1.3数据的逻辑结构和存储结构;1.4算法的特性和算法的描述;1.4算法的特性和算法的描述;1.5算法;1.4算法的特性和算法的描述;1.4.3算法的描述

算法的描述方式有多种：自然语言、伪代码（或称为类语言）、程序流程图及程序设计语言（如C语言）。

例如，求两个正整数m和n的最大公约数的算法可用以下几种方式描述。;1.4算法的特性和算法的描述;1.5算法;1.5算法;1.4算法的特性和算法的描述;1.5.1算法设计的四个目标

一个好的算法应该具备以下目标：

1．算法的正确性

算法的正确性（correctness）是指算法至少应该包括对于输入、输出和加工处理无歧义性的描述，能正确反映问题的需求，且能够得到问题的正确答案。;通常算法的正确性应包括以下4个层次：a.算法对应的程序没有语法错误；b.对于几组输入数据能得到满足规格要求的结果；c.对于精心选择的典型的、苛刻的带有刁难性的几组输入数据能得到满足规格要求的结果；d.对于一切合法的输入都能得产生满足要求的结果。;2．可读性

算法主要是为了人们方便阅读和交流，其次才是计算机执行。可读性（readability）好有助于人们对算法的理解，晦涩难懂的程序往往隐含错误不易被发现，难以调试和修改。;3．健壮性（robustness）

当输入数据不合法时，算法也能做出反应或进行处理，而不会产生异常或莫名其妙的输出结果。例如，求一元二次方程根ax2+bx+c=0的???法，需要考虑多种情况，先判断b2-4ac的正负，如果为正数，则该方程有两个不同的实根；如果为负，表明该方程无实根；如果为零，表明该方程只有一个实根；如果a=0，则该方程又变成了一元一次方程，此时若b=0，还要处理除数为零的情况。如果输入的a、b、c不是数值型，还要提示用户输入错误。;4．高效率和低存储量

效率指的是算法的执行时间。对于同一个问题如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指算法在执行过程中需要的最大存储空间。效率与低存储量需求都与问题的规模有关，求100个人的平均分与求1000个人的平均分所花的执行时间和运行空间显然有一定差别。设计算法时应尽量选择高效率和低存储量需求的算法。;1.5.2算法效率评价

算法执行时间需通过依据该算法编制的程序在计算机上的

运行时所耗费的时间来度量，而度量一个算法在计算机上的执

行时间通常有两种方法：

1．事后统计方法

这种方法有两个缺陷：一是必须依据算法事先编制好程

序，这通常需要花费大量的时间与精力；二是时间的长短依赖

计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。

因此，人们常常采用事前分析估算的方法评价算法的好坏。;2．事前分析估算方法

这主要在计算机程序编制前，对算法依据数学中的统计方

法进行估算。这主要是因为算法的程序在计算机上的运行时

间取决于以下因素：

a．算法采用的策略、方法；

b．编译产生的代码质量；

c．问题的规模；

d．书写的程序语言，对于同一个算法，语言级别越高，执行效率越低；

e．机器执行指令的速度。;例如，斐波那契数列的算法和语句的的频度如下。

每一条语句的频度

f0=0;1

f1=1;