数据结构与算法分析数据结构

《数据结构与算法分析数据结构》由会员分享，可在线阅读，更多相关《数据结构与算法分析数据结构（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.