数据结构教案第1章绪论.ppt

《数据结构教案第1章绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构信息与电气工程学院计算机技术教研室主要授课内容第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表主要授课内容第六章树和二叉树第七章图第八章查找第九章内部排序第一章绪论1.1基本概念和术语1.2算法和算法分析1.1基本概念和术语1.数据(data)的形式定义是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称常用的几种数据形式：数值数据：是用0到9十个数字的组合描述一个实体。符号数据：是用公认的一些符号的组合描述一个实体。这种数据具有广泛性、模糊性。1.1基本概念和术

2、语图像（图形）数据是用图像、图形描述一个实体。这种数据能直观的表现实体各部分之间的关系，便于我们了解分实体的本质。虽然处理复杂，但是，我们仍然要使用它。语音数据：是用自然语言描述一个实体。总之，在计算机科学领域，凡是计算机能识别与处理的数字、符号、图像、图形、语言以及它们的汇集通称数据。1.1基本概念和术语2.数据元素数据元素(dataelement)是系统中数据的基本单位（即在内存中具有可访问地址号的最小数据单位）。在实际应用中一个数据元素往往是有几部分组成，其中每一部分称为一个数据项（数据项是数据处理时不可再分割的最小数

3、据单元）。每一个数据项都有一个值，习惯上称这个值为关键字。应用时，关键字又分主关键字与次关键字。主关键字是指它能唯一的标识一个数据元素。1.1基本概念和术语下表为一张学生登记表，在表中每一个学生为一个数据元素学号姓名性别年龄班级99001李明男19计199002王华女20计299003赵立男18计1…………………………1.1基本概念和术语3.数据对象（dataobject)是性质相同的数据元素的集合，是数据的一个子集。例：字母字符数据对象是集合C={‘A’，‘B’，…‘Z’}4.数据结构(datastructure)是相互之

4、间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D,S)1.1基本概念和术语四类基本结构：集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系。线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构（网状结构）：结构中的数据元素之间存在多个对多个的关系。1.1基本概念和术语4.逻辑结构：描述数据元素之间逻辑关系的结构5.物理结构：数据结构在计算机中的表示，又称为存储结构。6.数据元素

5、之间的关系的两种表示方法：顺序存储：把数据存储到地址连续的区间，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储：把数据存储到任意的地址区间，借助指示元素存储地址的指针表示数据元素之间的逻辑关系。返回1.2算法和算法分析1.算法的定义算法是对某类特定问题求解步骤的描述。它应满足下列特性：（1）有穷性（2）确定性（3）可行性（4）输入（5）输出1.2算法和算法分析2.算法设计的要求（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求1.2算法和算法分析3.对程序性能的分析为了对算法性能有个深刻的了解，

6、我们首先分析程序的性能。（程序的空间复杂性与程序的时间复杂性）（1）程序的性能（programperformance)是指运行一个程序所需要的内存大小和时间多少。一般使用两种方法来确定一个程序的性能：一个是分析法；一个是实验法法。在对程序进行性能分析（performanceanalysis)时，采用分析法，而在对程序进行性能测量(performancemeasurement)时，借助实验法。1.2算法和算法分析程序的空间复杂性(spacecomplexity)是指运行完一个程序所需要的内存大小。讨论程序的空间复杂性的主要原因

7、如下：●如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。●对任何一个计算机系统想提前知道是否有足够可用的内存来运行该程序。1.2算法和算法分析一个问题可能有若干个内存需求各不相同的解决方案。●可以利用空间复杂性来估算一个程序所能解决的问题的最大规模·程序的时间复杂性（timecomplexity)是指运行完该程序所需要的时间。讨论程序的时间复杂性的主要原因如下：1.2算法和算法分析●有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限程序将被强制结束。●正在开发的程序可能需要提供一个满意的

8、实时响应。●如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之间的性能差异。1.2算法和算法分析(2)程序空间复杂性的计算程序所需的空间主要由指令空间、环境栈空间两部分构成。指令空间（instructionspace)是指用来存储经过编译之后的程序指令所需的空间。