数据结构第一章绪论

1、2022年8月17日第 1 页第一章 绪论1.1 程序 = 数据结构 + 算法1.2 数据结构的基本概念1.3 算法的概念与描述1.4 小结2022年8月17日第 2 页1.1 程序 = 数据结构 + 算法计算机是帮助人们对各种数据进行处理的机器。 数据结构是一门对计算机处理的数据进行表示、组织及操作进行研究的学科。程序 = 数据结构 + 算法 （N.Wirth）本课程内容：基本数据结构基本算法2022年8月17日第 3 页1.2 数据结构的基本概念数据与结构数据的类型数据元素数据对象数据结构基本数据结构类型线性数据结构树型数据结构图型数据结构2022年8月17日第 4 页1.2 数据结构的基

2、本概念（1）数据与结构数据的类型数据类型指的是一个值的集合以及定义在该集合上的操作的集合。分为固有数据类型和用户自定义数据类型两种。 2022年8月17日第 5 页1.2 数据结构的基本概念（2）数据与结构数据元素是用于描述数据的基本单位。可由数据项组成。数据项是数据表示中不可分割的最小标识单位。 2022年8月17日第 6 页1.2 数据结构的基本概念（3）数据与结构数据对象是具有相同性质的数据元素所组成的集合。一般情况下，数据对象中所包含的数据元素之间具有一定的组织形式和结构关系。2022年8月17日第 7 页1.2 数据结构的基本概念（4）数据与结构数据结构是对数据元素及其相互关系的描述

3、。包含了两方面的内容：是对数据元素的有限集合即数据对象的描述，是对数据对象中数据元素的关系的描述。有三种基本类型：线性数据结构树型数据结构图型数据结构2022年8月17日第 8 页1.2 数据结构的基本概念（5）基本数据结构类型线性数据结构工 号姓 名工 资奖 金合 计001张三500001000060000002李四600001000070000003王五55000800063000004赵六700001200082000.表1-1 线性数据结构示例 2022年8月17日第 9 页1.2 数据结构的基本概念（6）总经理部门经理2职员2部门经理1职员1部门经理3职员3基本数据结构类型树型数据结

4、构图1-1-1 树型数据结构示例 2022年8月17日第 10 页1.2 数据结构的基本概念（7）基本数据结构类型图型数据结构北京武汉杭州上海重庆香港济南城市间的航线图图1-1-2 图型数据结构示例 2022年8月17日第 11 页1.3 算法的概念与描述什么是算法？算法的特点算法描述语言本课程采用的算法描述语言2022年8月17日第 12 页1.3 算法的概念与描述（1）什么是算法？算法描述的是计算机解决问题的具体步骤的序列；这个序列必须是有限的。 2022年8月17日第 13 页1.3 算法的概念与描述（2）算法的特点确定性：算法的每一个步骤都必须有确定的含义，不能有二义性和模糊性，也就是

5、说对于同样的初始状态应得出相同的结果。可行性：算法中的每一步都应在有限的执行时间内完成，否则该算法就不可能得到实现。有穷性：算法应在有限的执行步骤里完成。输入：每个算法都应具有零个或多个输入以描述问题的初始状态。输出：每个算法也都应具有至少一个以上的输出作为它的结果。 2022年8月17日第 14 页1.3 算法的概念与描述（3）算法描述语言种类：自然语言程序语言：C、BASIC、PASCAL等形式化语言：例如ADT2022年8月17日第 15 页1.3 算法的概念与描述（4）本课程采用的算法描述语言采用的是结合自然语言的一种类C语言的描述方法。优点：便于交流和理解；突出重点，不拘泥于局部的细节；条理性更好，便于表达；准确，便于程序实现和算法性能分析。 2022年8月17日第 16 页1.3 算法的概念与描述（5）本课程采用的算法描述语言基本语言要素：数据类型说明变量和符号常量数据运算赋值语句控制语句：条件、循环函数的定义、声明与调用输入、输出结束语句注释2022