数据结构与算法分析

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,主讲：朱立华副教授,南邮计算机学院,E_mail:,DATA STRUCTURE,1,教材：,1、数据结构部分：数据结构用C+语言描述，陈慧南主编，南大学出版社,2、算法分析与设计部分：计算机算法设计与分析，王晓东编著，电子工业出版社,课时安排：,第一次面授：数据结构第一章到第五章,第二次面授：数据结构第六章到第十章,第三次面授：算法分析第二章到第七章（部分）,考试时间及方式：,第三次面授最后半天，复习加考试，开卷。,2,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象程序设计,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,内容提要：,1,给出数据结构的概念,2,介绍抽象数据类型和面向对,象的基本概念,3,回顾C+语言的基本特征,4,说明数据结构的描述方法,5,介绍算法和算法分析的基本,方法,第一章 绪论,数据结构,DATA STRUCTURE,3,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象程序设计,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,1.1 什么是数据结构,在程序设计时就已经遇到过。,一维数组是一个数据结构,例如：一维数组A=（a,1,a,2,a,3,a,4,）,int a4;,/,定义并创建一维整型,/数组(a,0,a1,a2,a3),x=a2;,/读数组元素a2的值,a2=x;,/置a2的值为x,数据结构由数据元素依某种逻辑关系组织起来，在数据结构上需要定义一组操作（运算）。,1、数据结构学科的定义：,主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。,4,1.数据：,是信息的载体,是,计算机加工处理的对象.,2.数值数据和非数值数据,(1)数值数据：,包括整数、实数或复数。主要用于工程计算、科学计算。,(2)非数值数据：,包括字符、文字、图形、图象、语音等。,用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。,3.,数据元素：,组成数据的基本单位。,第一章 绪论,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,一、数据和数据元素,5,例如：一维数组A=（a,1,a,2,a,3,a,4,）,(1)数据元素间的逻辑关系：,B=（D，R）,其中，D是数据元素的有限集合，R是D上关系的有限集合。本书中一般只考虑R包含一个关系的情况，即R=r。,D=a,1,a,2,a,3,a,4,r=,R=r,第一章 绪论,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,（1）数据元素之间的,逻辑关系,二、什么是数据结构,1.数据结构举例,6,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,（1）数据元素之间的,逻辑关系,（2）数据在计算机内,的表示,(2)数据在计算机内的表示,例如：一维数组A=（a,1,a,2,a,3,a,4,）,7,Create():建立一个数组。,Retrieve(i):返回下标为i的元素值。,Store(i,x):将下标为i的数据元素,的值置为x。,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,（1）数据元素之间的,逻辑关系,（2）数据在计算机内,的表示,（3）运算的定义和算法,(3)运算的定义和算法,例如：,int a4;/定义一个一维整型数组,/(a0,a1,a2,a3),x=a2;/读数组元素a2的值,a2=x;/置a2的值为x,8,2.4种基本的逻辑结构,集合结构：,结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；,线性结构：,结构中的数据元素之间存在一对一的关系；,树形结构：,结构中的数据元素之间存在一对多的关系；,图结构：,结构中的数据元素之间存在多对多的关系。,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,2.4种基本的结构关系,3.什么是数据结构,9,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,2.4 种基本的结构关系,3.什么是数据结构,2.4种基本的逻辑结构,10,第一章 绪论,1.1 什么是数据结构,一、数据和数据元素,二、什么是数据结构,1.数据结构举例,2.4种基本的结构关系,3.什么是数据结构,数据结构包括以下四个方面：,(1)数据元素及特性,是数据结构中的最基本信息单元。,(2)数据的逻辑结构,对数据元素间的逻辑关系的描述。,(3)数据的存储表示（存储结构）,数据在计算机内的组织方式。,(4)运算的定义和算法,数据结构上执行的运算和实现。,3.什么是数据结构,11,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象程序设计,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,1.2 数据抽象和抽象数据类型,抽 象,抽取事物的共同的和实质的东西，忽略其非本质的细节。,例如,，,“学生”,这一概念是对学生群体的抽象，它,抽取了学生这一群体的共性，忽略,了每个学生的特殊性。,12,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,1.C 语言的数据类型,二、数据抽象,三、抽象数据类型,一、数据类型,1.,C 语言的数据类型,(1)基本类型：,字符、整数、,枚举、实数、双精度数,(2)构造类型：,数组、结构和联合,(3)指针类型：,指针,例如，,二维整型数组,int a35;,定义了一个包含15个整数的二维数组。,13,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,1.C 语言的数据类型,二、为什么要研究数,据结构,三、什么是数据结构,又如，,结构类型,struct,Student,char*name;,int student_id;,char grade;,;,定义了结构类型Student,包括以下三个域：,name,student_id和grade。,14,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,1.C 语言的数据类型,2.数据类型,二、数据抽象,三、抽象数据类型,2.,数据类型,一个数据类型定义了一个值,的集合以及作用于该值集的操作的集合。,例如，,int a;,变量,a,的取值范围是：-32768,32767,对变量,a,执行的操作有：,算术运算 +、-、*、/、%,关系运算 、=、=、!=,赋值运算 =,15,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,二、数据抽象,三、抽象数据类型,二、数据抽象,数据类型,是具有相同值集和操作集的数据对象（变量和常量）的抽象。,相同的数据类型的变量具有相,同的取值范围，允许执行相同的操作；,对变量执行允许的操作，可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。,16,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,二、数据抽象,三、抽象数据类型,三、抽象数据类型,抽象数据类型,（,abstract data structure,ADT）,是一个数据类型，其主要特征是该类型的,对象及其操作的,规范,与该,对象的,表示,和操作的,实现,分离，即,使用,和,实现,分离，并实行,封装,和,信息隐蔽,。,17,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,二、数据抽象,三、抽象数据类型,例如，,int a;,整型,int,的,规范,包括,变量,a,的取值范围是：-32768,32767,对变量,a,执行的操作有：,算术运算 +、-、*、/、%,关系运算 、=、=、!=,赋值运算 =,整型,int,的,实现,是指变量,a,在计算机内存储表示方法。操作的,实现,是指整型上定义的操作的具体实现方法。,18,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,二、数据抽象,三、抽象数据类型,使用和实现分离：,使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。,封装和信息隐蔽,：,将数据和代码组合在一起；数据类型的细节对外部是隐蔽的。,例如，,int a;,其实现是隐蔽的，使用者只能通过整型上定义的一组运算对变量,a,执行操作。,19,第一章 绪论,1.2 数据抽象和,抽象数据类型,一、数据类型,二、数据抽象,三、抽象数据类型,四、数据结构的规范,和实现,数据结构可分成以下两部分：,(1)数据结构的规范：,逻辑结构和运算的定义,(2)数据结构的实现：,存储结构和运算算法实现,规范是实现的准则和依据。,规范指明“做什么”，,实现解决“怎样做”。,20,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象方法,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,1.3 面向对象方法,例子，问题的陈述：开发一个非常简单的字处理程序。该系统允许用户,产生,文档,；所产生的文档,存储,在一个用户,目录,中；用户可以,打印,和,显示,文档；文档可以,改变,，也可以被,删除,。,对象 服务,文档 产生、存储、打印,显示、改变、删除,目录 存储、删除,21,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象方法,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,1.3 面向对象方法,对象,应用领域内的实体和概念，,它们通常是问题陈述中的名词。,属性,刻划对象的特征。,服务或运算,施于对象属性的操作，它们通常是问题陈述中的动词。,同类对象具有相同的属性和服务。,同一个类（class)中的每个对象,称为该类的一个实例。,22,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象方法,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,继承,是指派生类（子类）可自动共享基类（父类）的公有的和保护的属性和服务的机制。它是面向对象方法最重要的共享机制，从而减少数据和代码的重复。这也是面向对象方法最有特色的方面。,23,第一章 绪论,1.1 什么是数据结构,1.2 数据抽象和抽象,数据类型,1.3 面向对象程序设计,1.4 C+程序设计,1.5 数据结构的描述,1.6 算法及其性能分析,1.4 C+程序设计,回顾C+语言的基本特征,内容提要：,1.4.1函数与参数传递,1.4.2动态存储分配,1.4.3C+类,1.4.4继承和派生类,1.4.5多态性、虚函数和动态联编,1.4.6纯虚函数和抽象类,1.4.7模板,24,第一章 绪论,1.4 C+程序设计,1.4.1 函数与参数传递,1.传值参数和引用参数,2.函数的返回值,3.函数原型,1.4.1函数与参数传递,#include,int Abc(,int a,int&b,),a+;,b+;,return a+b;,void main(),int x=3,y=3;,int z=,Abc(x,y);,rintf(z=%d,y=%dn,z,y);,1.传值参数与引用参数,（见dsapg4.cpp）,运行结果:,z=8,x=3,y=4,原因：,x 3 a 3 a+a 4,y 3 y 4,b b+b,25,第一章 绪论,1.4 C+程序设计,1.4.1 函数与参数传递,1.传值参数和引用参数,2.函数的返回值,3.函数原型,常量引用参数：const int&c,（见dsapg4.cpp）,#include,int Abc(int a,const,int&c,),/c+;若加上，则编译错,return a+c;,void main(),int y=3;,int z=Abc(3,y);,printf(z=%dn,z);,运行结果：z=6,26,第一章 绪论,1.4