南邮数据结构课件.ppt

数据结构 第1章 基础知识 1.1 算法与数据结构 1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法 1.2? 什么是数据结构 1.2.1 基本概念 基本术语 数据（data）：计算机加工处理的对象。 数据元素：组成数据的基本单位 数值数据(numerical data) 非数值数据(non-numerical data) 1.2.2? 数据的逻辑结构 1.2.3 数据的存储表示 顺序存储 需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中。 Loc（ak）＝102＋2* k 1.2.4 数据结构的运算 数据结构最常见的运算 创建运算:创建一个数据结构； 清除运算:删除数据结构中的全部元素； 插入运算:在数据结构的指定位置上插入一个新元素； 删除运算:将数据结构中的某个元素删除； …… 1.3 数据抽象和抽象数据类型  1.3.1 抽象、数据抽象和过程抽象 抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。 数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。 过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。 1.3.2 封装与信息隐蔽 封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。 信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。 通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。 1.3.3 数据类型和抽象数据类型 数据类型 是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。 程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。 1.3.4 数据结构与抽象数据类型 逻辑结构和运算的定义组成了数据结构的规范（specification） 数据的存储表示和运算算法的描述构成数据结构的实现(implementation)。 从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。 一种数据结构被视为一个抽象数据类型。 1.3.4 数据结构与抽象数据类型 数据结构的抽象层次 抽象层：讨论数据的逻辑结构及其运算定义， 实现层：讨论数据的存储表示以及运算的算法实现。 1.4 描述数据结构和算法 1.4.1 数据结构的规范 数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。 数据结构可以形式地用一个C++的抽象模板类描述。 1.4.2 实现数据结构 程序1.2 栈的顺序实现 templateclass T class SeqStack:public StackT { public: …… private: int top; //top记录最后入栈的元素在s的下标 int maxTop; //最大栈顶指针 T *s; //s指向动态生成的一维数组，存放元素 }; 1.5 算法分析的基本方法 1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法 1.5.1 算法及其性能标准 1.5.2 算法的时间复杂度 算法的时间复杂度 是程序运行从开始到结束所需的时间。 程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。 1.5.3 渐近时间复杂度 定义:（大O记号） 设f(n)和g(n) 是定义在正整数上的正函数，如果存在两个正常数 c 和n0 ，使得当 n? n0 时，有 f(n)? c g(n) 则记作 f(n)=O(g(n))。 1.5.4 最好、最坏和平均时间复杂度 例子：在一个有n个元素的数组中查找一个指定元素，某个有哪些信誉好的足球投注网站算法从第一个元素开始，一次检查一个数组元素。 1.5.5? 算法的空间复杂度 空间复杂度：一个算法的空间复杂度是指算法运行所需的存储量。 固定部分：这部分空间与问题实例的特征无关 可变部分：这部分空间大小与特定数据的大小和规模有关。 空间复杂度一般按最坏情况来分析。 逻辑结构和运算的定义组成了数据结构的规范。 数据的存储表示和运算算法的描述构成数据结构的实现。 从规范和实现两方面来讨论数据结构的方式是抽象数据类