数据结构 黄刘生 0512-87161118(O) 0551-3602445(L)

Ch.1 绪论 重要性 人类社会已步入信息社会 “计算”已成为理论研究、实验研究之后的第3种科学研究手段 “给我一根杠杆，我就能撬动地球” “给我一个接口，我就能驱动地球”

§ Ch.1 绪论 信息领域 硬件 软件-----核心问题是算法 算法实际上是加工数据的过程 算法+数据结构=程序设计（N.Wirth,84年图灵奖得主） 产品 软 件 本课程是IT所有学科的核心课程

§ Ch.1 绪论 先修课程及条件 程序设计的经验、C、离散数学、概率分析 特点：抽象、难度 考核： 参考书 C++ 数据结构，William Ford 清华影印版 数据结构和程序设计， Robert,Kruse.2nd版 算法导论，Thomas H. Corman等

能由计算机程序识别、存储和加工处理的符号集合 §1.1 基本概念和术语 数据：信息载体 能由计算机程序识别、存储和加工处理的符号集合 所有能够数字化的信息均可认为是数据 数据元素：数据的基本单位 同义词：元素、结点、顶点、记录、对象、元组等 数据项：具有独立含义的最小标识单位 同义词：字段、域、属性等

§1.1 基本概念和术语 数据结构：没有统一定义，通常指数据元素之间的相互关系，即数据的组织形式 数据的逻辑结构：数据元素之间的逻辑关系 数据的存储结构：数据元素及其关系在计算机存储器内的表示 数据的运算：对数据施加的操作

数据类型：是一个值的集合以及定义在这些值上的一组操作的总称，可看作是高级语言提供的数据结构 §1.1 基本概念和术语 数据类型：是一个值的集合以及定义在这些值上的一组操作的总称，可看作是高级语言提供的数据结构 原子类型：值不可分，一般是基本的预定义类型 int，char等，定义了“+”，“-”等 结构类型：可供用户定义的新类型，构造类型、导出类型、派生类型等 由基本类型组织而成，如sturct等

抽象的数据组织和与之相关的操作，可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作 §1.1 基本概念和术语 抽象数据类型（Abstract Data Type） 抽象的数据组织和与之相关的操作，可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作 特点 ①封装与隐藏：将数据和操作封装在一起，内部结构和实现细节对外屏蔽，实现信息隐藏 ②抽象：用户只能通过ADT里定义的接口和说明来访问和操作数据。他反映了程序设计的两层抽象： 概念层（抽象）---ADT、类说明 实现层---类实现，相当于普通类型 应用层----如main(){…}，通过操作对象解决实际问题

§1.1 基本概念和术语 ADT ADT_Name{ 抽象数据类型（Abstract Data Type） Data: 数据结构说明 Operations： Constructor：//构造函数，创建对象实例 Operation1：//用C++或C函数原型描述 input： Preconditions：//初始条件，执行本操作前系统 //需满足的状态 process：//对数据执行的操作 output：//对返回数据的说明 Postconditions：//执行本操作后系统的状态 Operation2： }

§1.1 基本概念和术语 行：结点(对象、记录、元组等)； 数据结构举例 系别 姓名 职称 SCI EI 经费 1 张明 教授 5 20 王华 6 3 15 … 23 李立 60 行：结点(对象、记录、元组等)； 列：数据项(属性、域、字段等) 逻辑结构：开始结点？终端结点？内部结点？ 结点之间的逻辑关系：有且仅有1个开始结点和1个终端结点，表中任1结点最多只有1个直接前驱和1个直接后继-----线性关系 存储结构：用数组实现，还是用指针实现？ 运算：创建、插入、删除、查找等

§1.1 基本概念和术语 数据结构（逻辑结构）分类 存储结构分类 线性结构：任一结点最多只有1个直接前驱和1个直接后继 非线性结构：一结点可有多个直接前驱和多个直接后继 集合结构：元素间无关系，只有元素是否属于集合的关系 存储结构分类 (1)顺序存储方法 逻辑上相邻的结点存储在物理位置上相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系来体现 借助于数组描述 应用于线性的数据结构，非线性的数据结构的线性化

§1.1 基本概念和术语 存储结构分类 (2)链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻 借助于指针来表示结点间的逻辑关系 (3)索引存储方法 在存储结点信息的同时，建立附加的索引表。 表中每项称为索引项 (关键字，地址) 稠密索引：每个结点对应1个索引项 稀疏索引：一组结点对应1个索引项 (4)散列存储方法 根据结点的Key直接计算出该结点的存储地址。

§1.1 基本概念和术语 数据结构3方面之联系 同一逻辑结构的不同存储结构，则用不同名称称谓 例如， 线性表顺序表 链表 散列表 运算不同，称谓也不同 线性表栈、队列 顺序栈、顺序队列

§1.2 算法描述 分析 算法 重要性：数据的运算是通过算法描述的 定义：非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出。因此，一个算法就是一系列将输入转换为输出的计算步骤。 5要素 输入、输出、有穷性（每条指令的执行次数须有限） 确定性、可行性（每条指令执行时间须有限） 算法与程序的联系与区别

§1.2 算法描述 分析 输入实例 一个问题的输入实例是由满足问题陈述中的限制、并能计算出该问题解的所有输入构成的。 算法描述 自然语言、数学语言、伪语言、程序语言等均可 本课程以C为主，但不拘泥于细节 算法评价 正确 时空性能 易读、易编码、易调试等

§1.2 算法描述与分析 算法分析 算法的时间是每语句执行时间的总和 每语句的执行时间=该语句执行次数（频度） X该语句执行1次的时间 假定：每语句执行1次的时间为1个时间单位 则：算法的执行时间=∑各语句频度 问题的规模（Size）n 输入量的大小，如… 时间复杂度：算法的运行时间，是问题规模的函数

§1.2 算法描述与分析 时间复杂度 例1：（p15）矩阵乘法 for ( i=0; i＜n; i++) //n+1 for ( j=0; j＜n; j++) { //n(n+1) C[i] [j]=0; //n2 for ( k=0;k＜n; k++) //n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n3 } 详细分析： T(n)=2n3+3n2+2n+1 简单分析：频度最大的语句 T(n)= =n3

从宏观上评价时间性能，只关心当n趋向无穷大时，T(n)的数量级(阶) §1.2 算法描述与分析 渐近时间复杂度（简称时间复杂度） 从宏观上评价时间性能，只关心当n趋向无穷大时，T(n)的数量级(阶) 即：T(n) 和n3同阶，数量级相同 记作：T(n)=O(n3)

§1.2 算法描述与分析 大O的数学定义 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在两个正的常数c和n0， 使得当n≥n0时都满足0≤T(n)≤c·f(n)。 平均性能 等概率假设 空间复杂性 S(n)=O(g(n))

§1.2 算法描述 分析 错误处理函数：简化错误处理代码 # include <stdlib.h> //其中有exit的说明 # include <stdio.h> //其中有stderr的说明 void Error(char * message) { fprintf (stderr, “Error: % s \ n”, message); //输出错误信息 exit(1); //终止程序，返回1给操作系统 }

§1.2 算法描述 分析 关于引用 当一变量声明为引用时，即成为被引用对象的“别名” 相当于指针常量