数据结构引言.ppt

教材 教科书 1） 《数据结构：思想与实现》，翁惠玉、俞勇，高等教育出版社，2009.8 2） 《数据结构：题解与拓展》，翁惠玉、俞勇，高等教育出版社，2011.8 参考书： 《数据结构》（C语言版），严蔚敏、吴伟民，清华大学出版社，1997.4 《数据结构与算法》（C++），窦延平等，上海交通大学出版社，2005.5 《算法导论》，Thomas H.Charles著，潘金贵译，机械工业出版社，2006.9 《算法之道》，邹恒明，机械工业出版社，2012.4 第一章 引言 什么是数据结构 算法分析 面向对象的数据结构 什么是数据结构 没有标准的定义，但有共识 数据结构：通过抽象的方法研究一组有特定关系的数据的存储与处理 数据结构的研究内容： 数据之间的逻辑关系，以及这种关系对应的操作 如何存储某种逻辑关系（存储实现） 在这种存储模式下，关系的操作是如何实现的（运算实现） 数据的逻辑结构 集合结构：元素间的次序是任意的。元素之间除了“属于同一集合”的联系外没有其他的关系。 线性结构：数据元素的有序序列。除了第一个和最后一个元素外，其余元素都有一个前趋和一个后继 树形结构：除了根元素外，每个节点有且仅有一个前趋，后继数目不限 图型结构：每个元素的前趋和后继数目都不限 数据结构的操作 创建：创建一个数据结构 清除：删除数据结构 插入：在数据结构指定的位置上插入一个新元素 删除：将数据结构中的某个元素删去 有哪些信誉好的足球投注网站：在数据结构中有哪些信誉好的足球投注网站满足特定条件的元素 更新：修改数据结构中的某个元素的值 访问：访问数据结构中的某个元素 遍历：按照某种次序访问数据结构中的每一元素，使每个元素恰好被访问一次 每一种数据结构的特定操作 数据结构的存储实现 包括两个部分： 数据元素的存储 数据元素之间的关系的存储 物理结构由三个部分组成： 存储结点，每个存储结点存放一个数据元素； 数据元素之间的关系的存储，也就是逻辑结构的机内表示； 附加信息，便于运算实现而设置的一些“哑结点”，如链表中的头结点。 基本的存储方式 数据元素的类型可以是各种各样的，通常不会是简单的内置类型，因此存储结点可以是一个结构体类型的变量或对象 数据结构主要讨论关系的存储。因此，数据结构主要采用泛型程序设计的思想 关系的存储 顺序存储：用存储的位置表示元素之间的关系。主要用数组实现。 链接存储：用指针显式地指出元素之间的关系，如单链表就是表示线性关系的 哈希存储方式：是专用于集合结构的数据存放方式。在哈希存储中，各个结点均匀地分布在一块连续的存储区域中，用一个哈希函数将数据元素和存储位置关联起来。 索引存储方式：所有的存储结点按照生成的次序连续存放。另外设置一个索引区域表示结点之间的关系。 第一章 引言 什么是数据结构 算法分析 面向对象的数据结构 算法分析 数据结构是讨论一组数据的处理问题。 每一种存储方式下对应的每一种操作的实现都是一个算法 每种操作有多种实现方式 如何评价这些算法的好坏 算法的质量评价 正确性：算法应能正确地实现预定的功能； 易读性：算法应易于阅读和理解，以便于调试、修改和扩充； 健壮性：当环境发生变化（如遇到非法输入）时，算法能适当地做出反应或进行处理，不会产生不正确的运算结果； 高效率：具有较高的时间和空间性能。 这四个指标往往是互相冲突的，数据结构主要考虑的是时空性能 算法效率分析 如何确定一个算法是高效的算法就是分析该算法所需要的资源。算法的资源包括： 时间：程序运行所需要的时间。要运行一年的算法是很难让人接受的 空间：程序运行所需要的空间。需要几个G的内存的算法同样也令人难以接受。 算法分析 时间复杂度的概念 算法运算量的计算 渐进表示法 时间复杂度的计算 算法的优化 空间复杂度的概念 程序的运行时间 影响运行时间的因素 问题规模和输入数据的分布 编译器生成的目标代码的质量 计算机系统的性能 程序采用的算法的优劣 关键是算法的优劣 有效算法的重要性 有效时间中能够处理的数据量 有效算法的重要性 时间复杂度 算法的时间复杂度是一种抽象的度量，即运算量与问题规模之间的关系。 算法的时间复杂度也与被处理的数据分布有关 算法的时间复杂度 最好情况的时间复杂度 最坏情况的时间复杂度 平均情况的时间复杂度 算法分析 时间复杂度的概念 算法运算量的计算 渐进表示法 时间复杂度的计算 算法的优化 空间复杂度的概念 算法运算量的计算 根据问题的特点合理地选择一种或几种操作作为“标准操作”，将标准操作作为一个抽象的运算单位； 确定每个算法在给定的输入下共执行了多少次标准操作；并将它作为算法的计算量。 实例 如果有一组正整数，存放在数组array中，要求设计一个算法求数组中的最大值与d的乘积。 运算量的计算 用乘法、赋值和条件判断作为标准操作 设输入的数组值