第一讲数据结构与算法.pptVIP

2012年康杰中学信息学竞赛数据结构讲义 计算机编程解决问题的基本步骤： 1、分析具体问题，抽象数学模型； 2、设计数据结构，选择有效算法； 3、编写程序，实现算法； 4、设计测试数据，反复调试直至得到最终解答。 数据结构+算法=程序设计 运用数据结构的知识更好地进行算法设计与算法分析，掌握计算机进行数据处理的基本原理、基本方法和技巧，进一步提高程序设计的水平和能力。 一、数据结构的基本概念 数据—— 是对客观事物的符号表示，在计算机系统中指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素—— 是数据的基本单位，是数据这个集合中的一个一个的元素。 构成数据元素的不可分割的数据单位称为数据项。例如，对于学生花名册，其中每个学生记录就是一个数据元素，而学生的姓名、年龄等项目为数据项。数据元素是讨论数据结构时涉及的最小数据单位。 数据对象—— 是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0，±1，±2，…}。 数据结构—— 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在存在着某种关系，数据元素相互之间的关系称为结构。把相互之间存在着一定关系的数据元素的集合及定义在其上的基本操作（运算）称为数据结构。如果不考虑定义在数据结构上的操作，则数据结构也可借助集合论术语定义为：数据结构是一个二元组（D，S），其中D是数据元素的有限集，S是D上的关系的有限集。 二、数据结构的分类 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系，则称这种结构为集合。在集合中，各元素是“平等”的，它们的共同关系是都属于同一个集合。 线性结构 结构中的数据元素之间存在一个对一个的关系；在线性结构中，第一个元素可以没有前驱，最后一个可以没有后继，其余的每个元素都有唯一的前驱和后继。 树形结构 结构中的数据元素之间存在一个对多个的关系；在树形结构中，除第一个特殊元素没有前驱外，其它每个元素都有唯一的前驱。 图状结构 结构中的数据元素之间存在多个对多个的关系 。 三、数据的逻辑结构与物理结构 数据结构定义中描述的“关系”是数据元素之间的逻辑关系，称为数据的逻辑结构。 数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，并由此得出两种不同的存储结构：顺序存储结构和链式存储结构。 1.顺序存储结构 用一组地址连续的存储单元依次存放数据元素， 数据元素之间的逻辑关系通过元素的地址直接反映。 用一组地址任意的存储单元依次存放数据元素， 数据元素之间的逻辑关系通过指针间接地反映。 2.链式存储结构 元素1 元素2 元素3 元素4 元素n 元素n-1 元素1 元素2 元素3 元素4 元素n-1 元素n ^ 链表结构 例 姓 名 性别 民族 年龄 其 他 刘晓光 男 男 男 女 汉 汉 回 壮 16 17 19 24 马广生 王 民 张淑华 … … … … … … … … … a1 a2 a3 ? a30 逻辑结构: 线性结构（线性表） 存储结构: 1. 顺序存储结构 … d1 d2 d3 d4 … d30 a1 a2 a3 a4 a30 … d1 d2 d3 d4 a2 a1 a4 a3 d4 d1 d5 d3 2. 链式存储结构 list a1 a2 a3 a30 ∧ … 用一片地址任意的存储空间 链表 四. 数据结构课程研究的主要内容 1、研究数据元素之间的客观联系。 2、研究具有某种逻辑关系的数据在计算 机存储器内的存储方式。 3、研究如何在数据的各种关系(逻辑的和 物理的)的基础上对数据实施一系列有 效的基本操作。 逻辑结构 存储结构 算法 五、算法的概念 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法具有下列五个重要特性： 1）有穷性 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成； 2）确定性 算法中的每一条指令必须有确切的含义，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只