南邮数据结构课件

南京邮电大学计算机学院2006年9月数据结构DataStructuresinC++Instructor：陈慧南Email:[e-mail]南京邮电大学计算机学院2006年9月《数据结构A》课程性质、任务和目的性质：是计算机学科的一门专业基础课。目的：在于学习如何组织和表示数据，并在相应的数据结构上实现对数据的操作。基本任务:是学习常见的基本数据结构，包括线性表、栈和队列、数组和字符串、树、搜索树、散列表、图和文件等，理解它们的逻辑结构、存储结构，领会在这些数据结构上定义的运算和实现运算的算法。学习和领会内、外排序算法。南京邮电大学计算机学院2006年9月第1章基础知识南京邮电大学计算机学院2006年9月1.1算法与数据结构1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法南京邮电大学计算机学院2006年9月数据结构和算法是计算机学科的基础之一，更是软件技术的基础。数据的组织和表示方法直接影响使用计算机求解问题的效率。算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。程序=数据结构+算法南京邮电大学计算机学院2006年9月1.2什么是数据结构1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法上机时间安排作业本章小结南京邮电大学计算机学院2006年9月1.2.1基本概念基本术语数据（data）：计算机加工处理的对象。数据元素：组成数据的基本单位数值数据(numericaldata)非数值数据(non-numericaldata)南京邮电大学计算机学院2006年9月数据结构的由来数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。南京邮电大学计算机学院2006年9月什么是数据结构数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。南京邮电大学计算机学院2006年9月南京邮电大学计算机学院2006年9月1.2.2数据的逻辑结构数据的逻辑结构对数据元素间逻辑关系的描述被称为数据的逻辑结构(logicalstructure)，它可以用一个二元组表示：DS=（D，R），其中，D是数据元素的有限集合，R是D中元素序偶的集合。南京邮电大学计算机学院2006年9月四类基本逻辑结构（a）集合结构（b）线性结构（c）树形结构（d）图状结构南京邮电大学计算机学院2006年9月1.2.3数据的存储表示顺序存储需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中。Loc（ak）＝102＋2*k南京邮电大学计算机学院2006年9月链接存储几种存储结构顺序结构链接结构索引结构散列结构DataLink地址信息称为链。∧表示空链。南京邮电大学计算机学院2006年9月逻辑结构存储结构概念数据元素之间逻辑关系的描述数据在计算机内的组织方式面向面向应用问题面向计算机关系存储结构是逻辑结构在计算机内的映像南京邮电大学计算机学院2006年9月1.2.4数据结构的运算数据结构最常见的运算创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……南京邮电大学计算机学院2006年9月静态数据结构和动态数据结构如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。南京邮电大学计算机学院2006年9月例1.1栈数据结构堆栈是一种线性数据结构，可以向栈中加入元素，但只允许访问和删除最后入栈的元素（1）向栈中加入一个元素（Push运算）；（2）从栈中删除最后加入的元素(Pop运算)；（3）访问最后加入栈中的元素(Top运算)；南京邮电大学计算机学院2006年9月什么是数据结构一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。南京邮电大学计算机学院2006年9月1.3数据抽象和抽象数据类型1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法上机时间安排作业本章小结南京邮电大学计算机学院2006年9月抽象：抽取事物的共同的和实质的东西，忽略其非本质的细节。整型数个体：126，235整型数的共性：取值范围，共同的运算南京邮电大学计算机学院2006年9月整型int的规范变量a的取值范围是：-32768~32767对变量a执行的操作有：算术运算+、-、*、/、%关系运算、、=、=、==、!=赋值运算=整型int的实现变量a在计算机内存储表示方法。操作的具体实现方法。南京邮电大学计算机学院2006年9月南京邮电大学计算机学院2006年9月1.3.1抽象、数据抽象和过程抽象抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。南京邮电大学计算机学院2006年9月1.3.2封装与信息隐蔽封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。南京邮电大学计算机学院2006年9月模块应采用封装和信息隐蔽原则来设计,这样的模块被称为黑盒子。封装和信息隐蔽的作用：错误局部化，降低问题求解的复杂性，提高程序的可靠性。C++语言的类可以封装数据和运算，其公有、保护和私有成员机制有利于实现信息隐蔽。南京邮电大学计算机学院2006年9月1.3.3数据类型和抽象数据类型数据类型是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。南京邮电大学计算机学院2006年9月数据类型是具有相同值集和操作集的数据对象（变量和常量）的抽象。相同的数据类型的变量具有相同的取值范围，允许执行相同的操作；对变量执行允许的操作，可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。南京邮电大学计算机学院2006年9月抽象数据类型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。南京邮电大学计算机学院2006年9月1.3.4数据结构与抽象数据类型逻辑结构和运算的定义组成了数据结构的规范（specification）数据的存储表示和运算算法的描述构成数据结构的实现(implementation)。从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。南京邮电大学计算机学院2006年9月1.3.4数据结构与抽象数据类型数据结构的抽象层次抽象层：讨论数据的逻辑结构及其运算定义，实现层：讨论数据的存储表示以及运算的算法实现。南京邮电大学计算机学院2006年9月逻辑结构和运算的定义组成了数据结构的规范。数据的存储表示和运算算法的描述构成数据结构的实现。从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。南京邮电大学计算机学院2006年9月1.4描述数据结构和算法1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法上机时间安排作业本章小结南京邮电大学计算机学院2006年9月1.4.1数据结构的规范数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。数据结构可以形式地用一个C++的抽象模板类描述。南京邮电大学计算机学院2006年9月ADT1.1栈ADTADTStack{数据：0个或多个元素的线性序列（a0,a1,...,an-1）,其最大允许长度为MaxStackSize。运算：Create()：建立一个空栈Destroy()：撤消一个栈Push(x)：值为x的新元素进栈，成为栈顶元素Pop()：从栈中删除栈顶元素Top(x)：在x中返回栈顶元素}南京邮电大学计算机学院2006年9月程序1.1栈的模板抽象类templateclassTclassStack{//栈类Stack是一个模板抽象类，其成员函数为纯虚函数，未定义数据成员。public:virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;……};南京邮电大学计算机学院2006年9月1.4.2实现数据结构程序1.2栈的顺序实现templateclassTclassSeqStack:publicStackT{public:……private:inttop;//top记录最后入栈的元素在s的下标intmaxTop;//最大栈顶指针T*s;//s指向动态生成的一维数组，存放元素};南京邮电大学计算机学院2006年9月templateclassTSeqStackT::SeqStack(intmSize){maxTop=mSize-1;//设置栈的容量值s=newT[mSize];//生成存储栈的数组top=-1;//top==－1表示空栈}南京邮电大学计算机学院2006年9月1.5算法分析的基本方法1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法南京邮电大学计算机学院2006年9月1.5.1算法及其性能标准什么是算法笼统的说，算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：南京邮电大学计算机学院2006年9月输入：算法有零个或多个输入输出：算法至少产生一个输出确定性：算法的每一条指令都有确切的定义，没有二义性。能行性：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。有穷性：算法必须总能在执行有限步之后终止。南京邮电大学计算机学院2006年9月算法的性能标准正确性：算法的执行结果应当满足预先规定的功能和性能要求。简明性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。效率：有效使用存储空间，并有高的时间效率。南京邮电大学计算机学院2006年9月1.5.2算法的时间复杂度算法的时间复杂度是程序运行从开始到结束所需的时间。程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。南京邮电大学计算机学院2006年9月floatSum(floatlist[],constintn){//此程序的程序步数为2n＋3floattempsum=0.0;count++;//针对赋值语句for(inti=0;in;i++){count++；//针对for循环语句tempsum+=list[i];count++;//针对赋值语句}count++;//针对for的最后一次执行count++;//针对return语句returntempsum;}南京邮电大学计算机学院2006年9月1.5.3渐近时间复杂度定义:（大O记号）设f(n)