第一章 绪论-3学时课件.pptVIP

数据结构学习基础与要求 讨论话题 来大学干嘛？ 想从大学里得到什么？ 大学太舒服，我都不知道怎么过好？ 这个专业学什么，以后干什么？ 学习、技能 创新、创业 社会实践 入行（行业） 第1章 绪 论 马伟锋( Wei-feng MA) 信息与电子工程学院 School of Information and Electronic Engineering 105012@zust.edu.cn 第1章 绪论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准 课本章节安排 1.1 什么是数据结构 1.2 数据结构基本概念 1.3 抽象数据类型描述 1.4 算法和算法分析 1.1 什么是数据结构课程发展的背景与地位 计算机处理的特点： 所处理的数据量大且具有一定的关系； 对其操作不再是单纯的数值计算，而更多地非数值计算如字符、声音、文本以及图像等，还需要对其进行组织、管理和检索。 数据结构： 1968年，美国唐·欧·克努特教授； 沃思(N.Wirth)：算法＋数据结构 ＝ 程序设计； 计算机以及相关专业核心(重要)课程； 计算机处理问题的过程 利用计算机处理实际问题的过程： 实践问题——数学模型——算法——程序 工程师 数学家 程序员 分析问题，提取操作对象，找出他们之间的关系，并且利用计算机语言描述、实现。 该问题特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 该问题特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构； 对它的操作有：建立树形结构，输出最低层结点内容等等。 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。 要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。 逻辑结构： 集合、线性结构（表、堆栈等）和非线性结构（树、图等）。 存储(物理)结构 存储结构： 在计算机中对数据元素本身和相互间的关系的表示。 数据元素表示：二进制形式，以字节组织。 常见的存储结构： 顺序存储结构，特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构； 链式存储结构，特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构； 其他：索引存储方法和散列存储方法。 1.3 抽象数据类型描述 描述：类C的伪代码，介于伪代码和C； 实现： 利用已有的数据类型和操作组合 C语言来实现，掌握C语言基础 实例： 抽象数据类型Triplet，表示和实现。 1.4 算法描述 1.4.1 算法的概念 算法，是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。 算法应该具有下列五个特性 （1）有穷性：一个算法必须在执行有穷步之后结束。 （2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。 （3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。 举例： 问题：按从小到大的顺序重新排列x，y，z 三个数值的内容。 算法： （1）输入x，y，z三个数值； （2）从三个数值中挑选出最小者并换到x中； （3）从y，z中挑选出较小者并换到y中； （4）输出排序后的结果。 1.4.2 算法设计的要求 (1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的