算法与数据结构学习指导第一章
第1章概述
讲课提要
【主要内容】
1．数据结构的研究目的和研究内容
2．数据结构中的几个重要概念和术语
3．算法设计的基本要求以及算法复杂度的分析和计算方法
【教学目标】
1．了解数据结构的研究目的和研究内容
2．掌握数据结构中的重要概念和术语
3．掌握算法设计的基本要求以及算法复杂度的分析和计算方法
【所需课时】数据结构与算法分析答案
2次课。
[第一次课]
1．数据结构的研究目的和研究内容
2．数据结构中的重要概念和术语
[第二次课]
3．算法设计的基本要求以及算法复杂度的分析和计算方法
学习指导
1．概念和术语
数据：是能输入到计算机中并能被计算机程序处理的符号的总称。
数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。
数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。
数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。
数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。
数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。
算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。
2．逻辑结构的四种基本形态
根据数据元素之间关系的不同特征，通常有下列四类基本结构：
（1）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。
（2）线性结构：结构中的数据元素之间存在一个对一个的关系。
（3）树型结构：结构中的数据元素之间存在一个对多个的关系。
（4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。
3．数据存储结构的基本组织方式
数据存储结构有顺序和链式两种方式。
（1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。
（2）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。
在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。
（1）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查效率，避免盲目查。
（2）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查时同样可大大提高效率。
4．数据结构的研究内容
数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。
5．算法的五个重要特征
（1）有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。
（2）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。
（3）可行性：每一个操作步骤都必须在有限的时间内完成。
（4）输入：一个算法可以有一个或多个输入，也可以没有输入。
（5）输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。
6．算法的评价标准
（1）正确性。
（2）易读性。
（3）高效性。
（4）可维护性。
7．算法分析的目的
算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度分析作为重点。
8．算法的时间复杂度分析
（1）算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。
（2）算法运行时间的分析规则
通常把一个程序的运行时间定义为一个T （n ），其中n 是该程序输入数据的规模，而不是某一个具体的输入。T (n )的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：T (n )=O (f (n ))，其中f (n )表示数据输入规模。
常见的算法时间复杂度的形式按性能降序的排列如下：
O (1)<="" )
2)
【例1-1】分析以下程序段的时间复杂度。
for(i=0;i<n;i++)< p="">
for(j=0;j<m;j++)< p="">
A[i][j]=0; 解：该程序段的时间复杂度为O (m*n )。
【例1-2】分析以下程序段的时间复杂度。
i=s=0; ①
while(s<n)< p="">
{ i++; ②
s+=i; ③ }
解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。其时间复杂度按线性累加规则为O (x )。此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。所以有：1+2+3+…+x ≥n ，可以推出： x=n n 24
1212811+±-=+±- x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环
体由线性累加规则得到该程序段的时间复杂度为O (n ）。
【例1-3】分析以下程序段的时间复杂度。
i=1; ①
while(i<=n)
i=2*i; ②
解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2
。
得：T （n ）=O (n 2log )
【例1-4】有如下递归函数fact (n )，分析其时间复杂度。
fact(int n)
{ if(n<=1)
return(1); ①
else
return(n*fact(n-1)); ②
} 解：设fact （n ）的运行时间函数是T (n )。该函数中语句①的运行时间是O (1)，语句②的运行时间是T (n-1)+ O (1)，其中O (1)为常量运行时间。
由此可得fact （n ）的时间复杂度为 O (n )。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。