数据结构ch01电子笔记.doc

第 1 章 绪 论 7第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。程序设计的新问题：应如何组织待处理的数据以及数据之间的关系（结构）。70年代初，数据结构作为一门独立的课程开始进入大学课堂。请查找数据结构起源的资料：二、数据结构随着程序设计的发展而发展。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：无结构阶段结构化阶段面向对象阶段应用领域：科学计算；程序设计面向计算机 应用领域：科学计算与非数值处理；算法数据结构=程序应用领域：更多地应用于非数值处理；（算法数据结构）=程序三、数据结构的发展并未终结。1 数据结构将继续随着程序设计的发展而发展；2 面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中。札记：从程序设计的发展和数据结构的发展，你有什么感想？1.2 数据结构的研究对象表1-1 学生学籍登记表例1-1 学籍管理问题学 号姓 名性 别出生日期政治面貌0001陆 宇男1986/09/02团员0002李 明男1985/12/25党员0003汤晓影女1986/03/26团员例1-2 人机对弈问题.(a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系例1-3 教学计划编排问题课程编号课程名称先修课程(a) 计算机软件方向的一些课程 (b) 课程之间次序关系的示意图 图1-3 课程以及表示课程之间次序关系的图c6c1c3c5c7c2c4c1高等数学无c2计算机科学导论无c3离散数学c1 c4程序设计语言C+c1、c2c5数据结构c3、c4c6计算机原理c2、c4c7数据库原理c4、c5、c6结论：用计算机求解问题一般包含两个步骤： 数值问题抽象出的模型通常是 非数值问题抽象出的模型通常是数据结构是研究 问题中计算机的操作对象以及它们之间的关系和操作的学科。1.3 数据结构的基本概念1.3.1 数据结构1. 数据：在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数值数据：例如 数据 非数值数据：例如请列举一些实际的数据：2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 构成数据元素的不可分割的最小单位称为数据项。举例说明数据、数据元素和数据项之间的关系： 数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。3. 数据对象：是具有相同性质的数据元素的集合，是数据的子集。相同性质的含义是：4. 数据结构：是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构是指数据元素之间逻辑关系的整体。所谓逻辑关系是指根据数据元素之间逻辑关系的不同，数据结构分为四类： 集合 数据元素之间的关系是 。 线性结构 数据元素之间的关系是 。 树结构 数据元素之间的关系是 。 图结构 数据元素之间的关系是 。四种基本数据结构的逻辑结构图 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。 存储结构要存储两方面的内容： 数据元素； 数据元素之间的逻辑关系。有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。札记：关于逻辑结构： 关于存储结构： 1.3.2数据结构的访问接口数据结构的基本操作或基本运算是指：数据结构的基本操作的接口的全体称为数据结构的访问接口。某种操作的接口是指：例如：数据结构的基本操作应具有如下特性： 抽象性： 基本性： 完备性： 一般性： 1.3.3 抽象数据类型1数据类型数据类型是一组值的集合以及定义于这个值集上的一组操作的总称。数据类型规定了该类型数据的取值范围和对这些数据所能采取的操作。C+中有哪些基本数据类型，若有如下类型声明：int a, b; 如何理解数据类型规定了该类型数据的取值范围和对这些数据所能采取的操作？2抽象所谓抽象，就是抽出问题本质的特征而忽略非本质的细节，是对具体事物的一个概括。3抽象数据类型抽象数据类型（以下简称ADT）是一个数据结构以及定义在该结构上的一组操作的总称。ADT可理解为对数据类型的进一步抽象，数据类型和ADT的区别仅在于：数据类型指的是高级程序设计语言支持的基本数据类型，而ADT指的是自定义的数据类型。ADT逻辑结构操作集合数据结构存储结构算法设计(a) 使用视图ADT的定义 (b) 设计视图ADT的设计 (c) 实现视图ADT的实现 图1-7 ADT的不同视图类成员变量成员函数 一个ADT的定义不涉及它的实现细节，在形式上可繁可简，本书对ADT的定义包括抽象数据类型名、数据元素之间逻辑关系的定义、每种基本操作的接口（操作的名称和该操作的前置条件、输入、功能、输出、后置条件的定义），形式如下：ADT 抽象数据类型名Data 数据元素之间逻辑关系的定义Operation 操作1前置条件：执行此操作前数据所必须的状态 输入：执行此操作所需要的输入功能：该操作将完成的功能输出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 操作n endADT札记：如何理解数据、数据类型、抽象数据类型之间的关系？1.4 算法及算法分析1.4.1 算法1.什么是算法通俗地讲，算法是解决问题的方法；严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法必须满足下列五个重要特性： 输入： 输出： 有穷性： 确定性： 可行性： 2.什么是“好”算法一个“好”算法首先要满足算法的五大特性，此外还要具备下列特性： 正确性： 鲁棒性： 简单性： 抽象分级： 高效性： 3. 算法的描述方法常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。欧几里得算法用自然语言描述为：欧几里得算法用流程图描述为：欧几里得算法用C+语言书写的程序如下： 欧几里得算法采用符合C+语法的伪代码描述如下：上述伪代码可以再具体一些，用C+中的函数来描述，并且局部变量可以不声明。 int CommonFactor(int m, int n) 求最大公约数算法CommonFactor1.4.2 算法分析1度量算法效率的方法一种方法是事后统计的方法，先将算法实现，然后输入适当的数据运行，测算其时间和空间开销。其缺点： 编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣。 另一种是事前分析估算的方法渐进复杂度，它是对算法所消耗资源的一种估算方法。2算法的时间复杂度问题规模是指输入量的多少。运行算法所需要的时间T是问题规模n的函数。基本语句是执行次数与整个算法的执行次数成正比的语句。这种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。即当只考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，称作算法的渐进时间复杂度，简称时间复杂度，通常用大O（读作“大欧”）记号表示。定义1-1 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)（或称算法在O(f(n)中）。大O记号的含义:例1-4 求下面程序段的时间复杂度。解：基本语句是for (i=0; in; i+) for (j=0; jn; j+) x+;3最好、最坏和平均情况例如，在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k），顺序查找算法如下：int Find(int A , int n, int k) 顺序查找算法Find 4算法的空间复杂度算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。通常记作：S(n)=O(f(n)，其中，n为问题规模，分析方法与算法的时间复杂度类似。5. 算法分析举例定理1-1 若A(n)=amnm +am-1nm-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)。例1-5 +x; 解：基本语句是例1-6 for (i=1; i=n; +i)+x; 解：基本语句是例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j)+x; 解：基本语句是例1-8 for (i=1; i=n; +