数据结构 第1章 绪论(精品·公开课件).ppt

数据结构 主讲教师：徐沛娟 xpj1021@163.com 课程相关信息 教材：《数据结构》，刘大有等编著，高等教育出版社，2010年9月. 参考书目：清华大学出版社、高等教育出版社和机械出版社等出版的数据结构教材. 教学形式：理论＋实验 考核方式：考试 参考书 1、《数据结构》 严蔚敏、吴伟民编著 清华大学出版社。 2、《数据结构》 （用面向对象方法与C++描述） 殷人昆、陶永雷等编著 清华大学出版社 教学计划 第一章 绪论(算法分析基础) 第二章 线性表、堆栈、队列 第三章 数组、字符串 第四章 树 第五章 图 第六章 递归 第七章 排序 第八章 查找 第一章 绪论 1.1 为什么要学习数据结构 1.2 数据结构概念 1.3 算法 1.4 算法的正确性证明 1.5 算法分析基础 1.1 为什么学习数据结构 计算机学科中一门重要的专业基础课。 提高计算机的工作效率。 是程序设计的重要基础； 是许多计算机专业课的基础，如算法分析、编译原理、操作系统、数据库系统等。 最短路径算法在物流配送问题中的应用； 树结构在数据挖掘领域中的应用； 散列技术在数据加密领域中的应用； 查找技术在数据库领域中的应用； 倒排文件、查找算法在有哪些信誉好的足球投注网站引擎中的应用。 第一章 绪论 1.1 为什么要学习数据结构 1.2 数据结构概念 1.3 算法 1.4 算法的正确性证明 1.5 算法分析基础 [例] 个人书库管理程序所要处理的数据可能是如下的表格。 1.2 数据结构概念1. 数据 数据是对象的表示。 计算机程序要处理的“原料”，它可以被计算机识别、存储和加工处理。 包括：数值、文字、表格、图像、声音、源程序等。 数据元素 是组成数据的基本单位。 在程序中通常把一个数据元素作为一个整体来考虑和处理。 数据元素还可被称为结点或顶点。 例如，在上表中，把其中的每一行（代表一本书）作为一个基本单位来考虑。 数据项 一个数据元素含有若干个数据项。 例如，在上表数据中，每个数据元素由登录号、书号、书名、作者、出版社和价格六个数据项构成。 数据项是构成数据的最小单位。 [例] 电话号码薄的查询问题。   ((a1，b1 ), (a2，b2),… (an，bn )) 2. 逻辑结构 逻辑结构的形式化表示 [例] L=(N,R)， N={k1,k2,…,k9}, R={r}，r={k1,k2, k1,k3, k1,k4, k1,k7, k1,k8, k4,k5, k4,k6, k8,k9} 存储结构分类 1）顺序存储结构 把一组结点存放在地址相邻的存储单元里，结点间的逻辑关系用存储单元的自然顺序关系表达。 存储结构分类 3）索引存储结构 索引表把整数索引值映射到结点的存储地址。 索引表存储一串指针，每个指针指向存储区域的一个数据结点。 存储结构分类 4）散列存储结构 适用于大数据量、高速检索的场合。 索引存储的一种延伸和扩展，利用散列函数进行索引值的计算，并通过索引表求出结点的指针地址。 存储结构总结 顺序、链接、索引和散列存储结构，可以单独使用，也可以组合使用。 存储结构要正确反映逻辑结构，并便于操作。 4. 对数据的操作 插入 删除 修改 排序 查找 5.数据结构的概念 数据结构的概念 按某种逻辑关系将一批数据元素组织起来； 按一定的存储方式把它们存储起来； 在数据上定义需要施加的操作。 数据结构课程的目的 从对问题抽象和求解的角度来学习常用的数据结构，阐明其内在的逻辑关系和在计算机中的存储表示，以及刻画施加于其上之各种操作的算法。 学习上述理论知识，综合运用相关知识，再结合上机实践，使我们具备求解比较复杂的问题的能力，即掌握问题求解建模，选择恰当数据结构，或构造新的数据结构，设计较优算法，证明算法（或算法之关键步骤）正确性，分析算法的时空复杂性，对算法编程、调试等能力。 数据类型：是一个值的集合以及在这些值上定义的一组操作的集合的总称。 抽象数据类型：由一组数据结构和在该组数据结构上的一组操作所组成。 第一章 绪论 1.1 为什么要学习数据结构 1.2 数据结构的概念 1.3 算法 1.4 算法的正确性证明 1.5 算法分析基础 1.3 算法1.算法的概念 计算机解决问题的步骤： ①从具体问题中抽象出一个适当的数学模型； ②设计解此模型的方法； ③编出程序、进行测试、调试，直至得到最终解答。 计算机处理问