《高职数据结构课件讲解》由会员分享，可在线阅读，更多相关《高职数据结构课件讲解（20页珍藏版）》请在金锄头文库上搜索。
1、 第1章 绪 论 学习目标与要求： 了解数据、数据元素、数据项、数据对象、数 据类型及抽象数据类型等基本概念。 掌握数据结构和算法的概念。 掌握数据结构的逻辑结构、存储结构和数据操 作(运算)3个方面的概念及其相互之间的关系 。 掌握算法的评价标准。 分析算法的时间复杂度，评价一个算法的好坏 。 2 1.1 引 言 1968年美国唐欧克努特(Donald E.Knuth)开 创了数据结构的最初体系。 数据结构是一门介于数学、计算机硬件和计算 机软件三者之间的核心课程(如图1.1所示)。 3 1.1 引 言 为了使读者对数据结构有一个感性的认识 ，下面给出几个数据结构的示例，读者可 以通过这些示
2、例去理解数据结构的概念。 【示例1】 职工基本情况表。 参见教材P2 【示例2】 井字棋对弈问题。 【示例3】 教学计划编排问题。 4 1.2 基本概念与术语 数据(Data)是对客观事物的一种符号表示，是指所有能输入到 计算机中并被计算机程序加工处理的符号的总称。 数据元素(Data Element)是组成数据的基本单位，在计算机程 序中通常作为一个整体进行考虑和处理。 数据项(Data Item)是数据不可分割的、具有独立意义的最小数 据单位，是对数据元素属性的描述。 数据、数据元素、数据项反映了数据组织的3个层次，即数据可 以由若干个数据元素组成，数据元素又由若干个数据项组成。 数据对象
3、(Data Object)是性质相同的数据元素的集合。 数据类型(Data Type)是指一组结构相同的值构成的值集(类型) 和定义在这个值集(类型)上的操作集。 数据结构(Data Structure)是指数据元素之间的逻辑关系和这种 关系在计算机中的存储表示，以及在这种结构上定义的运算。 5 1.2 基本概念与术语 1. 逻辑结构 (1)线性结构。 (2)集合结构。 (3)树形结构。 (4)图状结构。 数据的四种基本逻辑结构如图1.4所示。 6 1.2 基本概念与术语 2. 存储结构 (1) 顺序存储结构是指把逻辑上相邻的结 点存储在物理上相邻的存储单元里，结点 之间的逻辑关系由存储单元位
4、置的邻接关 系来体现。 (2) 链式存储结构是把逻辑上相邻的结点 存储在物理上任意的存储单元里，结点之 间的逻辑关系由附加的指针域来体现。 (3) 索引存储结构是用结点的索引号来确 定结点的存储地址。 7 1.2 基本概念与术语 3. 数据的运算 对几种常用的运算进行简要介绍。 (1)检索：即在数据结构里查找满足一定条 件的结点，一般是给定某字段的值，找具 有该字段值的结点。 (2)插入：即往数据结构里增加新的结点。 (3)删除：把指定的结点从数据结构里去掉 。 (4)更新：改变指定结点的一个或多个字段 的值。 8 1.3 抽象数据类型 首先我们了解一下在程序设 计语言中出现的各种数据类 型。
5、 9 1.3.1 数据类型 数据类型是一个值的集合和定义在这个值集上 的一组操作的总称。 在高级程序设计语言中，数据类型可分为两类 ：一类是原子类型，另一类则是结构类型。 在某种意义上，数据结构可以看成是“一组具有 相同结构的值”，而数据类型则可被看成是由一 种数据结构和定义在其上的一组操作所组成的 。 10 1.3.2 抽象数据类型概述 抽象数据类型(Abstract Data Type，ADT)， 是指一个数学模型以及定义在此数学模型上的 一组操作。 抽象数据类型是与表示无关的数据类型，是一 个数据模型及定义在该模型上的一组运算。 抽象数据类型的描述包括给出抽象数据类型的 名称、数据的集合
6、、数据之间的关系和操作的 集合等方面的描述。 11 1.3.2 抽象数据类型概述 抽象数据类型的形式化定义如下： ADT=(D,S,P) D=数据对象 S=D上的关系集 P=对D的基本操作集 定义形式： ADT 抽象数据类型名称 数据对象： 数据关系： 基本操作： 操作名1： 操作名n： ADT抽象数据类型名称 12 1.4 算法和算法分析 在计算机领域，一个算法实质上是针对所处理问题的 需要，在数据的逻辑结构和存储结构的基础上实施的 一种运算。 由于数据的逻辑结构和存储结构不是唯一的，所以处 理同一个问题的算法也不是唯一的；即使对于具有相 同逻辑结构和存储结构的问题而言，由于设计思想和 设计
7、技巧不同，编写出来的算法也不大相同。 学习数据结构这门课程的目的，就是要学会根据实际 问题的需要，为数据选择合适的逻辑结构和存储结构 ，进而设计出合理和实用的算法。 13 1.4.1 算法的基本概念 1. 算法 2. 算法的特征 (1)有穷性。 (2)确定性。 (3)可行性。 (4)有输入。 (5)有输出。 3. 算法与程序的区别 (1)一个算法必须在有穷步之后结束，一个程序不一定 满足有穷性。 (2)程序中的指令必须是机器可执行的，而算法中的指 令则无此限制。 (3)算法代表了对问题的求解过程，而程序则是算法在 计算机上的实现。 (4)算法和数据结构是相辅相成的。 14 1.4.1 算法的基
8、本概念 4. 算法的设计目标 (1) 正确性。 (2) 可读性。 (3) 健壮性。 (4) 高效率。 (5) 低存储量需求。 15 1.4.1 算法的基本概念 5. 算法的描述 (1) 自然语言 (2) 流程图 (3) 高级程序设 计语言 (4) 类语言 16 1.4.2 算法的时间复杂度 一个程序的时间复杂度(Time Complexity)是指程序 运行从开始到结束所需要的时间。 一个算法是由控制结构和原操作构成的，其执行时间 取决于两者的综合效果。 定义(大O记号)：如果存在两个正常数c和n0，使得对 所有的n, nn0，有： f(n) cg(n) 则有： f(n) (g(n) 使用大O
9、记号表示的算法的时间复杂度，称为算法的 渐近时间复杂度(Asymptotic Complexity)。 17 1.4.3 算法的空间复杂度 算法的空间复杂度(Space Complexity)是指算 法从开始运行到运行结束所需的存储空间，即 算法执行过程中所需的最大存储空间。 类似于算法的时间复杂度，算法的空间复杂度 通常也是采用一个数量级来度量。记作： S(n)=O(g(n)，称S(n)为算法的渐近空间复杂 度。 算法运行所需的存储空间包括以下两部分： (1)固定部分。 (2)可变部分。 18 本 章 小 结 (1) 数据结构研究的三方面内容是数据的逻辑结构、数 据的存储结构和对数据的运算。数据的逻辑结构可分 为集合、线性、树和图四种基本结构。数据的存储结 构有顺序、链式、索引和散列四种存储结构。 (2) 算法是对特定问题求解步骤的一种描述，是指令的 有限序列。算法具有有穷性、确定性、可行性、输入 、输出特性。 (3) 一个好的算法应该达到正确性、可读性、健壮性、 高效性和低存储量等目标。 (4) 算法的效率通常用时间复杂度和空间复杂度来评价 ，应该掌握其基本分析方法。一般只要大致计算出相 应的数量级即可。一个算法的时间和空间复杂度越好 ，则算法的效率就越高。 19 习 题 一、填空题 参见教材P17 二、选择题 三、应用题 20
