《数据结构与算法(C++语言版)》第1章 绪论(精品·公开课件).ppt

* * * 本章总结 基本要求 （1）掌握数据项、数据元素、原子元素、数据对象、数据结构之间的区别及关系。 （2）掌握数据的逻辑结构与数据元素之间的逻辑关系和数据存储结构的含义。 （3）理解逻辑结构的4种基本组织形式和存储结构的4种不同表示方法及其特点。 （4）掌握算法分析的方法和时空复杂度的表示。 （5）弄清算法的概念、分类、与程序的区别、描述方法和工具（C++语言）。 （6）弄清算法与运算、运算的实现、操作的相互关系和区别。 本章总结 （7）掌握算法的时间复杂度和空间复杂度的含义及数量级的概念，计算方法和表示形式。 （8）弄清最坏情况下算法时间复杂度和平均时间复杂度的定义、区别、估算方法。 重点与难点 重点：数据结构的概念、逻辑结构和存储结构的组织和表示形式，描述算法的C++语言。 难点：最坏情况下算法的时间复杂度分析。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 数据结构与算法（C++语言版） 第1章 绪论 教科书介绍 出版社： 电子工业出版社 著者： 肖南峰 教授 赵洁 讲师等 ISBN： 978-7-121-08301-3 主要著者介绍 肖南峰博士，男，1962年11月生， 华南理工大学计算机科学与工程学 院教授，博士生导师。 1982年7月 毕业于华中工学院（现为华中科技 大学）自动控制与计算机工程系，获工学学 士学位；1989年1月毕业于东北工学院（现为 东北大学），获工学硕士学位；2001年6月毕 业于日本横浜国立大学，获工学博士学位。 2001年9月至2002年9月在澳大利亚Deakin大 学从事科学研究。 主要著者介绍（续） 他作为主持人先后完成了2项国家自然科学基金项目、2项广东省自然科学基金重点项目，1项教育部留学回国人员科研启动基金项目，以及由广东省教育厅和华南理工大学等资助的20多项教学与科研课题，在国内外发表学术论文120多篇，其中被三大索引收录近50篇，出版专著和教材5部，申请或获得发明及实用新型专利5项，软件版权10项。 课程内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 多维数组和广义表 第六章 树和二叉树 第七章 图 第八章 查找 第九章 内部排序 第十章 文件组织与外排序 第十一章 贪婪算法 第十二章 分而治之算法 第十三章 动态规划 第十四章 回溯 第一章 绪论 背景：从世界上第一台计算机诞生至今，已有60多年的历史。在这期间，计算机的发展和应用已经渗透到了人类社会的各个领域，计算机加工和处理的对象也从纯粹的数值发展到了字符、图像、声音等各种具有一定结构的数据。为了更好地设计程序，以提高计算机在解决复杂问题时的处理效率，研究数据的特性和数据之间存在的关系至关重要。“数据结构”作为计算机科学与技术领域中的一门专业基础课，它专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。因此，“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬件和计算机软件之间的一门核心课程，并将随着人类社会的各个领域中计算问题的不断深入研究而继续发展。 什么是数据结构 基本概念 （1）数据：信息的载体，是客观事物的符号表示。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如实数、字符串、图像和声音等。 （2）数据项：具有独立的含义的最小标识单位。例如，字段、域、属性等。 （3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。 什么是数据结构 （4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。 （5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构的形式化定义通常用一个二元组Data_Structure=(D, R)来表示，式中，D是数据元素的有限集（也即数据对象），R是D上关系的有限集。 什么是数据结构 数据结构的内涵 数据结构一般包含数据的逻辑结构和存储结构及数据运算。 数据的逻辑结构: 数据的逻辑结构是指数据元素以及它们相互之间的逻辑关系，数据的逻辑结构与数据的存储无关。根据数据元素之间关系的不同特性，通常有4类逻辑结构：① 集合，集合的逻辑结构中所有数据元素都属于同一个集合，所有数据元素杂乱无章地聚集在一起，各个数据元素之间无任何联系；② 线性结构，逻辑结构中的数据元素之间存在着一个对一个的关系，各个数据元素之间通常有严格的先后次序关系；③ 树形结构，逻