数据结构 教学课件 作者 方风波 王巧莲 主编 黄鹤鸣 副主编第一章 绪论.ppt

《数据结构 教学课件 作者 方风波 王巧莲 主编 黄鹤鸣 副主编第一章 绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章绪论第一章绪论知识点数据结构中常用的基本概念和术语算法描述和分析方法难点算法复杂性的分析方法要求了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系掌握算法复杂性的概念及分析方法第一章绪论第一章目录1.1基本概念1.2算法的描述1.3算法的评价1.4应用举例及分析小结习题与练习第一章绪论1.1基本概念(1)数据(Data)：一切能够由计算机接受和处理的对象。数据元素(Dataelement)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。数据项(

2、Dataitem)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。第一章绪论1.1基本概念(2)数据结构(Datastructure)：数据之间的相互关系，即数据的组织形式。研究数据结构，是指研究数据的逻辑结构和物理结构数据的逻辑结构：数据元素之间的逻辑关系数据的物理结构：数据元素在计算机存储器中是如何存储的定义一组有关数据元素的运算第一章绪论1.1基本概念(3)算法(Algorithm)：对特定问题求解步骤的一种描述。算法是一个有穷的规则序列，这些规则决定了解决某一特定问题的一

3、系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。返回第一章绪论1.2算法的描述本书将采用类C语言描述算法类C语言是标准C语言的简化，与标准C语言的主要区别如下：1.所有算法都以如下所示的函数形式表示：函数类型函数名（参数表）{语句序列}类C语言的形参书写比标准C语言简单，如，intxyz(inta,intb,intc)可以简单写成intxyz(inta,b,c)第一章绪论类C与标准C的主要区别(续)2.局部量的说明可以省略，必要时对其作用给

4、予注释。3.不含goto语句，增加一个出错处理语句error(字符串)，其功能是终止算法的执行并给出表示出错信息的字符串。4.输入/输出语句有：输入语句scanf([格式串]),变量1，…，变量N）；输出语句printf([格式串]),变量1，…，变量N）；通常省略格式串。返回第一章绪论1.3.1评价算法的一般原则正确性：算法应能正确地实现处理要求。易读性：有助于对算法的理解，便于纠正和扩充。简单性：使证明其正确性比较容易，对算法进行修改也比较方便。高效率：达到所需的时、空性能。第一章绪论1.3.

5、2算法复杂性的分析算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性（所占存储空间），重点是时间复杂性。一个算法所需的运算时间通常与所解决问题的规模大小有关。用n表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。第一章绪论一个算法所需的执行时间就是该算法中所有语句执行次数之和。渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂性。时间复杂性常用数量级的形式来表示，记作T(n)=O(f(n))。其中

6、，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。第一章绪论当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。一般地，对于足够大的n，常用的时间复杂性存在以下顺序：O(1)

7、均时间复杂性：研究同样的n值时各种可能的输入，取它们运算时间的平均值。2.最坏时间复杂性：研究各种输入中运算最慢的一种情况下的运算时间。返回第一章绪论例1.1计算下面交换i和j内容程序段的时间复杂性。temp=i;i=j;j=temp;解：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1).第一章绪论例1.2计算下面求二个矩阵相乘的时间复杂性（1）for(i=0;i

8、++)（n(n+1)次）（3）{c[i][j]=0;(n2)（4）for(k=0;k