数据结构与算法 绪论教案1.ppt

数据结构与算法 主讲 ：李玉蓉 E_MAIL ：leanna@nuc.edu.cn ADDR ：软件学院215房间 问题引入 实际问题——布雷问题 第1章 绪论 ? 1.1 什么是数据结构 ? 1.2 基本概念和术语 ? 1.3 抽象数据类型的表示与实现 ? 1.4 算法和算法分析 引 论 对于一个课题，在计算机领域，一般遵循下面的解决原则： 需求分析 总体设计 模块分割 建立数学模型 解数学模型的算法 程序编制 调试 结果 数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。 数据结构的地位：数学、硬件、软件之间的核心专业基础课. 例1-1 图书目录检索 例1-2 井字棋问题 例 1-3 多叉路口交通灯问题 数据结构的发展 　 “数据结构”作为一门独立的课程在国外是从1968年开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系。 “数据结构”在计算机科学中是一门综合性的专业基础课，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 “数据结构”所处的地位 数据结构的定义 数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。 数据结构往往同高效的检索算法和索引技术有关。  一个数据结构是由数据元素依据某种逻辑联系组织起来的。 对数据元素间逻辑关系的描述称为数据的逻辑结构； 数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示； 讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 1.2 数据结构的基本概念和术语 1. 基本术语 （1）数据：描述客观事物的数字、字符以及所有能 输入到计算机中并被计算机程序处理的符号的总称。（数字、字符、声音、图形、图像等等） （2）数据元素：数据的基本单位，在计算机程序中 常常作为一个整体进行考虑和处理，如记录/结构。 （3）数据项：数据的不可分割的最小单位，如结构 中的域。 （4）数据对象：性质相同的数据元素的集合，是数 据的一个子集。 2. 数据结构 （1）定义：是相互之间存在一种或多种特定关系的 数据元素的集合。 数据之间不是相互独立的，它们之间有某种特定的关系，这种数据元素之间的关系，称为“结构” 结构 = 关系 + 实体 另一种定义：按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合。 形式定义：二元组 (D,S) 其中D是数据元素的有限集，S是D上关系的有限集。 （2）四种基本结构（逻辑结构） 集合：元素仅属于同一个集体，没有其他关系。 线性结构：存在一对一关系，序列相邻，次序关系。 树型结构：存在一对多关系，层次关系。 图状结构（网状结构）：存在多对多关系，任意性。 存储器模型：一个存储器M是一系列固定大小的存储单元，每个单元U有一个唯一的地址A(U)，该地址被连续地编码。每个单元U有一个唯一的后继单元 U’=succ(U) 物理结构就是逻辑结构到存储器的一个映射。 两种主要存储结构：顺序存储、链接存储。 3. 数据结构的划分 （1）按数据结构的性质划分 数据的逻辑结构——数据元素之间的逻辑关系 （设计算法——数学模型） 数据的物理结构——数据结构在计算机中的映像 （存储结构，算法的表示） 3. 数据结构的划分 （2）按数据结构在计算机内的存储方式来划分 顺序存储结构：借助元素在存储器的相 对位置来表示数据元素之间的逻辑关系。 链式存储结构：借助指示元素存储地址 的指针表示数据元素之间的逻辑关系。 3. 数据结构的划分 （3）按数据结构的操作来划分 静态结构：经过操作后，数据的结构特征保持不变（如数组）。 半静态结构：经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。 动态结构：经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。 1.3 抽象数据类型— ADT 定义：是指基于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。 抽象的与具体的相对应 示例： int a,b; 则a和b可以进行+、-、*、/的运算 2和6则是具体的int数据。 1.4 算法和算法分析 1. 算法 定义：指一系列确定的而且是在有限