吉林师范大学计算机学院《数据结构》课件：1.ppt

数据结构 C语言版 第0章　指导思想和目标 第1章　绪 论 小结 本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 需要达到识记层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。 需要达到领会层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。 对基本概念的理解 数据 数据元素 数据结构 　　例如一个表（数据库） 逻辑结构： 　　线性结构和非线性结构 存储方法： 　　顺序存储方法，链接存储方法，索引存储方法，散列存储方法 难点问题： 　　算法的描述和分析，主要是算法复杂度的分析 习 题 一 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 1.3 常用的存储表示方法有哪几种? 1.4 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大? 1.5 按增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2) * * 一、指导思想 ??????基础性；系统性；先进性；实践性 二、教学目标 ???? 通过本课程学习，要求掌握数据结构和算法的基本概念和技术，从而能够对于给定问题选择合适的 数据结构，并设计相应的操作算法。掌握数组、线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及内排序、查找等重要技术。 　参考书 1、数据结构题集 严蔚敏 吴伟民 清华大学出版社 2、数据结构习题与解析 李春葆 清华大学出版社 3、数据结构与离散数学分册（计算机专业研究生入学考试全真题解） 前沿考试研究室 人民邮电出版社 4、数据结构-用C语言描述 唐策善等 高等教育出版社 5、C语言程序设计 谭浩强 清华大学出版社 6、C＋＋程序设计 1.1《数据结构》课程研究的内容 1.2 《数据结构》课程的发展历史及课程的重要性 1.3 基本概念和术语 1.4 抽象数据类型的表示与实现 1.5 算法和算法分析 1.1《数据结构》课程研究的内容 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。它主要研究： ①数据的逻辑结构--数据关系之间的逻辑关系 ②数据的存储结构--数据的逻辑结构在计算机中的表示 ③操作算法--插入、删除、修改、查询、排序等 1.2 《数据结构》课程的发展历史及课程的重要性 ?·1968年在美国开设。它随着大型程序的出现而出现。 ?·我国80年代初开设。它是计算机专业的核心课程，考研必考。 ·学习《数据结构》的目的：???????①提高复杂程序设计的能力???????②培养算法设计能力???????③为后继课程（如操作系统、编译原理等）打基础。 1.3 基本概念和术语 1、数据 2、数据元素 3、数据项 4、数据对象 5、数据结构 6、存储结构 7、数据类型 8、抽象数据类型 数据:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项:是数据的不可分割的最小单位。 数据对象:是性质相同的数据元素的集合，是数据的一个子集。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。????根据数据元素之间关系的不同特性，通常有下列四类基本结构：?? ????①集合 ??? ②线性结构 ?????? ③树形结构 ④图状结构或网状结构 ????它可形式定义为：数据结构是一个二元组Data_Structure=(D,S) 其中：D是数据元素的有限集、 S 是D上关系的有限集。 存储结构：是数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。 ????有两种不同的存储结构：???? ????顺序存储结构---- 其特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 ???? ????链式存储结构---- 其特点是借助