数据结构-绪论剖析.ppt

1.1 数据结构的研究对象 1.1 数据结构的研究对象 1.1 数据结构的研究对象 例 2 迷宫问题。 1.1 数据结构的研究对象 例 3 多岔路口交通灯的管理问题。 1.1 数据结构的研究对象 二、数据结构的分类 一、算法和算法的五个重要特性 1.有穷性：执行有穷步后结束，且每一步在有穷时间内完成。 2.确定性：每一条指令必须有确切的含义，不会产生二义性。 并且在任何条件下，算法都只有一条执行的路径。 3.可行性：算法中描述的操作都是可以通过基本运算执行有 限次实现。 4.输入：有0个或多个输入。作为算法加工对象的量值，通常 体现为算法中的一组变量值，有些是算法执行过程 中输入的，有些已被嵌入在算法中。 5.输出：有一个或多个输出。是一组与输入有确定关系的量值， 是算法加工信息对象后得到的结果。这种确定关系 即为算法的功能。 ? 1.3 算法和算法的衡量 二、算法的设计原则 衡量算法性能的标准。 设计算法时，通常应考虑达到以下目标： 1.正确性 2.可读性 3.健壮性 4.高效率与低存储量的需求 1.3 算法和算法的衡量 1.正确性（有效性） 首先，算法能够正确地实现预先规定的功能。 其次，对正确性理解的四个层次： (1)程序中不含语法错误 (2)程序对几组输入数据能够得出满足要求的结果 (3)程序对精心选择的典型、苛刻而带有刁难性的几 组输入数据能得出满足要求的结果 (4)对一切合法的输入数据都能产生满足要求的结果 二、算法的设计原则 1.3 算法和算法的衡量 * * 本 课 程 教 学 内 容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第八章 动态存储管理 第九章 查找 第十章 内部排序 第十一章 外部排序 第十二章 文件 本 课 程 内 容 结 构 数据结构 线性结构 非线性结构 线性表 栈 队列 串 数组和广义表 顺序表 链表 单链表 双向链表 循环链表 两种存储结构 顺序存储 链式存储 树 图 二叉树的遍历 树和森林 哈夫曼树及哈夫曼编码 图的存储 图的遍历 最小生成树 拓扑排序和关键路径 最短路径 查找 排序 静态 动态 哈希表 内部 外部 第一章 绪 论 1.1 数据结构的研究对象 1.2 数据结构的基本概念 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 ?计算机的发展 仅能进行数值计算 能处理各种非数值数据 ?数据处理的种类 数值数据 非数值数据 数 (整数,实数) 字符 字符串 文字 图形 图象 声音 1.1 数据结构的研究对象 ? 数值问题与非数值问题 1）数值问题 例1 已知：游泳池的长len和宽wide，求面积area 问题涉及的对象：游泳池的长len 宽wide，面积area；对象之间的关系：area=len?wide 例2 线性方程组求解 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机1 00202 李梅 女 83/02/23 阳江 532 00计算机2 00301 马耀先 男 82/07/12 广州 509 00计算机3 2）非数值问题 例 1 已知某年级学生情况 , 要求分班并按入学成绩排列顺序。 在这类文档管理的数学模型中, 计算机处理的对象之间通常存在着一种最简单的线性关系 , 这类数学模型称为线性模型。 入口 出口 C D E A B 数据结构研究的问题： 非数值数据之间的结构关系 及如何表示，如何存储，如何处理。 1.2 数据结构的基本概念 一、基本概念 二、数据结构的分类 三、数据结构的存储 四、数据类型 1.数据 能被输入计算机且能被计算机处理的一切 对象。(是信息的载体，是客观事物的符号表示。) 例如：整数，实数，字符串、