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