南邮数据结构课件

《南邮数据结构课件》由会员分享，可在线阅读，更多相关《南邮数据结构课件（53页珍藏版）》请在金锄头文库上搜索。

1、南京邮电大学计算机学院 2006年9月,数据结构,Data Structures in C+,Instructor：陈慧南 Email: ,南京邮电大学计算机学院 2006年9月,数据结构A课程性质、任务和目的,性质：是计算机学科的一门专业基础课。 目的：在于学习如何组织和表示数据，并在相应的数据结构上实现对数据的操作。 基本任务: 是学习常见的基本数据结构，包括线性表、栈和队列、数组和字符串、树、搜索树、散列表、图和文件等，理解它们的逻辑结构、存储结构，领会在这些数据结构上定义的运算和实现运算的算法。学习和领会内、外排序算法。,南京邮电大学计算机学院 2006年9月,第1章 基础知识,南京邮

2、电大学计算机学院 2006年9月,1.1 算法与数据结构,1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法,南京邮电大学计算机学院 2006年9月,数据结构和算法是计算机学科的基础之一，更是软件技术的基础。 数据的组织和表示方法直接影响使用计算机求解问题的效率。 算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。,程序 = 数据结构+算法,南京邮电大学计算机学院 2006年9月,1.2 什么是数据结构,1.1 算法与数据结构 1.2 什

3、么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法 上机时间安排 作业 本章小结,南京邮电大学计算机学院 2006年9月,1.2.1 基本概念,基本术语 数据（data）：计算机加工处理的对象。 数据元素：组成数据的基本单位 数值数据(numerical data) 非数值数据(non-numerical data),南京邮电大学计算机学院 2006年9月,数据结构的由来 数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。,南京邮电大学计算机学院 2006年9月,什么

4、是数据结构,数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系； 存储结构：数据在计算机内的表示形式； 运算：在数据上执行的操作。,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,1.2.2 数据的逻辑结构,数据的逻辑结构 对数据元素间逻辑关系的描述被称为数据的逻辑结构(logical structure) ，它可以用一个二元组表示：DS=（D，R），其中，D是数据元素的有限集合，R是D中元素序偶的集合。,南京邮电大学计算机学院 2006年9月,四类基本逻辑结构 （a）集合结构 （b）线性结构 （c）树形结构 （d）图状结构,南京邮电大学计算机学院 2006年

5、9月,1.2.3 数据的存储表示,顺序存储 需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中。 Loc（ak）1022* k,南京邮电大学计算机学院 2006年9月,链接存储,几种存储结构 顺序结构 链接结构 索引结构 散列结构,Data Link,地址信息称为链。 表示空链。,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,1.2.4 数据结构的运算,数据结构最常见的运算 创建运算:创建一个数据结构； 清除运算:删除数据结构中的全部元素； 插入运算:在数据结构的指定位置上插入一个新元素； 删除运算:将数据结构中的某个元素删除； ,南京

6、邮电大学计算机学院 2006年9月,静态数据结构和动态数据结构 如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。,南京邮电大学计算机学院 2006年9月,例1.1 栈数据结构 堆栈是一种线性数据结构，可以向栈中加入元素，但只允许访问和删除最后入栈的元素 （1）向栈中加入一个元素（Push运算）； （2）从栈中删除最后加入的元素(Pop运算)； （3）访问最后加入栈中的元素(Top运算)；,南京邮电大学计算机学院 2006年9月,什么是数据结构 一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机

7、内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。,南京邮电大学计算机学院 2006年9月,1.3 数据抽象和抽象数据类型,1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法 上机时间安排 作业 本章小结,南京邮电大学计算机学院 2006年9月,抽 象：抽取事物的共同的和实质的东西，忽略其非本质的细节。 整型数个体： 126，235 整型数的共性：取值范围，共同的运算,南京邮电大学计算机学院 2006年9月,整型int的规范 变量

8、a 的取值范围是：-3276832767 对变量 a 执行的操作有： 算术运算 +、-、*、/、% 关系运算 、=、=、!= 赋值运算 = 整型int的实现 变量 a 在计算机内存储表示方法。 操作的具体实现方法。,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,1.3.1 抽象、数据抽象和过程抽象,抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。 数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。 过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。,南京邮电大学

9、计算机学院 2006年9月,1.3.2 封装与信息隐蔽,封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。 信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。 通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。,南京邮电大学计算机学院 2006年9月,模块应采用封装和信息隐蔽原则来设计,这样的模块被称为黑盒子。 封装和信息隐蔽的作用：错误局部化，降低问题求解的复杂性，提高程序的可靠性。 C+语言的类 可以封装数据和运算，其公有、保护和私有成员机制有利于实现信息隐蔽。,南京邮电大学计算机学院 20

10、06年9月,1.3.3 数据类型和抽象数据类型,数据类型 是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。 程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。,南京邮电大学计算机学院 2006年9月,数据类型是具有相同值集和操作集的数据对象（变量和常量）的抽象。 相同的数据类型的变量具有相同的取值范围，允许执行相同的操作； 对变量执行允许的操作，可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。,南京邮电大学计算机学院 2006年9月,抽象数据类型（abstract data t

11、ype ADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。,南京邮电大学计算机学院 2006年9月,1.3.4 数据结构与抽象数据类型,逻辑结构和运算的定义组成了数据结构的规范（specification） 数据的存储表示和运算算法的描述构成数据结构的实现(implementation)。 从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。 一种数据结构被视为一个抽象数据类型。,南京邮电大学计算机学院 2006年9月,1.3.4 数据结构与抽象数据类型,数据结构的抽象层次 抽象层：讨论数据的逻

12、辑结构及其运算定义， 实现层：讨论数据的存储表示以及运算的算法实现。,南京邮电大学计算机学院 2006年9月,逻辑结构和运算的定义组成了数据结构的规范。 数据的存储表示和运算算法的描述构成数据结构的实现。 从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。 一种数据结构被视为一个抽象数据类型。,南京邮电大学计算机学院 2006年9月,1.4 描述数据结构和算法,1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法 上机时间安排 作业 本章小结,南京邮电大学计算机学院 2006年9月,1.4.1 数据结构

13、的规范,数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。 数据结构可以形式地用一个C+的抽象模板类描述。,南京邮电大学计算机学院 2006年9月,ADT 1.1 栈ADT ADT Stack 数据： 0个或多个元素的线性序列（a0,a1,.,an-1）, 其最大允许长度为MaxStackSize。 运算： Create()： 建立一个空栈 Destroy()：撤消一个栈 Push(x)：值为x的新元素进栈，成为栈顶元素 Pop()：从栈中删除栈顶元素 Top(x)：在x中返回栈顶元素 ,南京邮电大学计算机学院 2006年9月,程序1.1 栈的模板抽象类 templat

14、e class Stack / 栈类Stack是一个模板抽象类， 其成员函数为纯虚函数，未定义数据成员。 public: virtual bool Push(T x)=0; virtual bool Pop()=0; virtual bool Top(T ,南京邮电大学计算机学院 2006年9月,1.4.2 实现数据结构,程序1.2 栈的顺序实现 template class SeqStack:public Stack public: private: int top; /top记录最后入栈的元素在s的下标 int maxTop; /最大栈顶指针 T *s; /s指向动态生成的一维数组，存放元

15、素 ;,南京邮电大学计算机学院 2006年9月,template SeqStack:SeqStack(int mSize) maxTop=mSize-1; /设置栈的容量值 s=new TmSize; /生成存储栈的数组 top=-1; /top=1表示空栈 ,南京邮电大学计算机学院 2006年9月,1.5 算法分析的基本方法,1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法,南京邮电大学计算机学院 2006年9月,1.5.1 算法及其性能标准,什么是算法 笼统的说，算法是求解一类问题的任意一种特殊的方法。较

16、严格的说法是一个算法是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：,南京邮电大学计算机学院 2006年9月,输入：算法有零个或多个输入 输出：算法至少产生一个输出 确定性：算法的每一条指令都有确切的定义，没有二义性。 能行性：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。 有穷性：算法必须总能在执行有限步之后终止。,南京邮电大学计算机学院 2006年9月,算法的性能标准 正确性：算法的执行结果应当满足预先规定的功能和性能要求。 简明性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。 健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。 效率：有效使用存储空间，并有高的时间效率。,南京邮电大学计算机学院 2006年9月,1.5.2