数据结构 第一章 绪论

第一章 绪论 知 识 点 难 点 要 求 数据结构中常用的基本概念和术语 算法描述和分析方法 算法复杂性的分析方法 了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系 掌握算法复杂性的概念及分析方法 第一章 绪论

第一章目录 1.1 基本概念 1.2 算法的描述 1.3 算法的评价 1.4 应用举例及分析 小 结 习题与练习 第一章 绪论

1.1 基本概念(1) 数据(Data)：一切能够由计算机接受和处理的对象。 数据元素(Data element)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。 数据项(Data item)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。 第一章 绪论

1.1 基本概念(2) 数据结构(Data structure)：数据之间的相互关系，即数据的组织形式。 研究数据结构，是指研究数据的逻辑结构和物理结构 数据的逻辑结构：数据元素之间的逻辑关系 数据的物理结构：数据元素在计算机存储器中是如何存储的 定义一组有关数据元素的运算 第一章 绪论

1.1 基本概念(3) 算法(Algorithm)：对特定问题求解步骤的一种描述。 算法是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。 由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。 返回 第一章 绪论

1.2 算法的描述 本书将采用类C语言描述算法 类C语言是标准C语言的简化 ，与标准C语言的主要区别如下： 1.2 算法的描述 本书将采用类C语言描述算法 类C语言是标准C语言的简化 ，与标准C语言的主要区别如下： 1. 所有算法都以如下所示的函数形式表示： 函数类型 函数名（参数表） { 语句序列  } 类C语言的形参书写比标准C语言简单，如，int xyz(int a,int b,int c)可以简单写成int xyz (int a,b,c) 第一章 绪论

类C与标准C的主要区别(续) 2. 局部量的说明可以省略，必要时对其作用给予注释 。 3. 不含go to语句，增加一个出错处理语句error(字符串)，其功能是终止算法的执行并给出表示出错信息的字符串。 4. 输入/输出语句有： 输入语句 scanf([格式串]),变量1，…，变量N）； 输出语句 printf([格式串]),变量1，…，变量N）； 通常省略格式串 。 返回 第一章 绪论

1.3.1 评价算法的一般原则 正确性：算法应能正确地实现处理要求 。 易读性：有助于对算法的理解，便于纠正和扩充 。 1.3.1 评价算法的一般原则 正确性：算法应能正确地实现处理要求 。 易读性：有助于对算法的理解，便于纠正和扩充 。 简单性：使证明其正确性比较容易，对算法进行修改也比较方便。 高效率：达到所需的时、空性能。 第一章 绪论

1.3.2 算法复杂性的分析 算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性（所占存储空间），重点是时间复杂性 。 1.3.2 算法复杂性的分析 算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性（所占存储空间），重点是时间复杂性 。 一个算法所需的运算时间通常与所解决问题的规模大小有关。 用n 表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。 不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。 第一章 绪论

一个算法所需的执行时间就是该算法中所有语句执行次数之和。 渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂性。 时间复杂性常用数量级的形式来表示，记作T(n)=O(f(n))。 其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。 第一章 绪论

当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。 一般地，对于足够大的n，常用的时间复杂性存在以下顺序： O(1)< O(logn)< O(n)< O(n*logn)< O(n2)< O(n3)…<O(2n)<O(3n)<…<O(n!) 其中,O(1)为常数数量级,即算法的时间复杂性与输入规模n无关。 第一章 绪论

算法的运行时间往往还与具体输入的数据有关，通常用以下两种方法来确定一个算法的运算时间： 1. 平均时间复杂性：研究同样的n值时各种可能的输入，取它们运算时间的平均值。 2. 最坏时间复杂性：研究各种输入中运算最慢的一种情况下的运算时间。 返回 第一章 绪论

例1.1 计算下面交换i和j内容程序段的时间复杂性。 temp=i; i=j; j=temp; 解：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1). 第一章 绪论

例1.2 计算下面求累加和程序段的时间复杂性 （1） sum=0； （一次） （2） for(i=1;i<=n;i++) （n次 ） （3） for(j=1;j<=n;j++) （n2次 ） （4） sum++； （n2次 ） 解：T(n)=2n2+n+1 =O(n2) 返回 第一章 绪论

小 结 本章介绍了贯穿全书的基本概念和基本思想。 数据 数据结构 逻辑结构 物理结构 算法 算法的时间复杂性 返回 第一章 绪论

习题与练习 一、名词解释 二、简答 数据 数据项 数据元素 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性 数据 数据项 数据元素 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性 二、简答 1. 算法分析的目的是什么？ 2. 什么是算法的最坏和平均时间复杂性？ 第一章 绪论

三、分析下列算法的时间复杂性: 1．sum=0; for (i=1;i<=n;i++) { sum=sum+i; } 2．i=1; while(i<=n) i=i*10; 第一章 绪论

sum=sum+Array[i][j]; for(i=0;i<n;i++) for(j=0;j<n;j++) sum=sum+Array[i][j]; 返回 第一章 绪论