数据结构与算法分析.ppt

1,主讲：朱立华副教授南邮计算机学院E_mail:,DATA STRUCTURE,2,教材：1、数据结构部分：数据结构用C+语言描述，陈慧南主编，南大学出版社2、算法分析与设计部分：计算机算法设计与分析，王晓东编著，电子工业出版社课时安排：第一次面授：数据结构第一章到第五章第二次面授：数据结构第六章到第十章第三次面授：算法分析第二章到第七章（部分）考试时间及方式：第三次面授最后半天，复习加考试，开卷。,3,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,内容提要：1给出数据结构的概念2介绍抽象数据类型和面向对 象的基本概念3回顾C+语言的基本特征4说明数据结构的描述方法5介绍算法和算法分析的基本 方法,第一章 绪论,数据结构,DATA STRUCTURE,4,第一章 绪论 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,数据结构由数据元素依某种逻辑关系组织起来，在数据结构上需要定义一组操作（运算）。,1、数据结构学科的定义：主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。,5,1.数据：是信息的载体,是计算机加工处理的对象.2.数值数据和非数值数据(1)数值数据：包括整数、实数或复数。主要用于工程计算、科学计算。(2)非数值数据：包括字符、文字、图形、图象、语音等。用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。3.数据元素：组成数据的基本单位。,第一章 绪论 1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构,一、数据和数据元素,6,例如：一维数组A=（a1,a2,a3,a4）(1)数据元素间的逻辑关系：B=（D，R）其中，D是数据元素的有限集合，R是D上关系的有限集合。本书中一般只考虑R包含一个关系的情况，即R=r。D=a1,a2,a3,a4 r=,R=r,第一章 绪论 1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构 1.数据结构举例（1）数据元素之间的 逻辑关系,二、什么是数据结构,1.数据结构举例,7,1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构 1.数据结构举例（1）数据元素之间的 逻辑关系（2）数据在计算机内 的表示,(2)数据在计算机内的表示,例如：一维数组A=（a1,a2,a3,a4）,8,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,9,2.4种基本的逻辑结构,集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；线性结构：结构中的数据元素之间存在一对一的关系；树形结构：结构中的数据元素之间存在一对多的关系；图结构：结构中的数据元素之间存在多对多的关系。,1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构 1.数据结构举例 2.4种基本的结构关系 3.什么是数据结构,10,1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构 1.数据结构举例 2.4 种基本的结构关系 3.什么是数据结构,2.4种基本的逻辑结构,11,第一章 绪论1.1 什么是数据结构 一、数据和数据元素 二、什么是数据结构 1.数据结构举例 2.4种基本的结构关系 3.什么是数据结构,数据结构包括以下四个方面：(1)数据元素及特性 是数据结构中的最基本信息单元。(2)数据的逻辑结构 对数据元素间的逻辑关系的描述。(3)数据的存储表示（存储结构）数据在计算机内的组织方式。(4)运算的定义和算法 数据结构上执行的运算和实现。,3.什么是数据结构,12,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,1.2 数据抽象和抽象数据类型,抽 象 抽取事物的共同的和实质的东西，忽略其非本质的细节。,例如，“学生”这一概念是对学生群体的抽象，它 抽取了学生这一群体的共性，忽略 了每个学生的特殊性。,13,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 1.C 语言的数据类型 二、数据抽象 三、抽象数据类型,一、数据类型,1.C 语言的数据类型(1)基本类型：字符、整数、枚举、实数、双精度数(2)构造类型：数组、结构和联合(3)指针类型：指针,例如，二维整型数组int a35;定义了一个包含15个整数的二维数组。,14,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 1.C 语言的数据类型 二、为什么要研究数 据结构 三、什么是数据结构,又如，结构类型 struct Studentchar*name;int student_id;char grade;定义了结构类型Student,包括以下三个域：name,student_id和grade。,15,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 1.C 语言的数据类型 2.数据类型 二、数据抽象 三、抽象数据类型,2.数据类型 一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。,例如，int a;变量a 的取值范围是：-3276832767对变量a执行的操作有：算术运算+、-、*、/、%关系运算、=、=、!=赋值运算=,16,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 二、数据抽象 三、抽象数据类型,二、数据抽象,数据类型 是具有相同值集和操作集的数据对象（变量和常量）的抽象。相同的数据类型的变量具有相 同的取值范围，允许执行相同的操作；对变量执行允许的操作，可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。,17,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 二、数据抽象 三、抽象数据类型,三、抽象数据类型,抽象数据类型（abstract data structure ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该对象的表示和操作的实现分离，即使用和实现分离，并实行封装和信息隐蔽。,18,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 二、数据抽象 三、抽象数据类型,例如，int a;整型int 的规范包括变量 a 的取值范围是：-3276832767对变量 a 执行的操作有：算术运算+、-、*、/、%关系运算、=、=、!=赋值运算=整型int 的实现是指变量 a 在计算机内存储表示方法。操作的实现是指整型上定义的操作的具体实现方法。,19,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 二、数据抽象 三、抽象数据类型,使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。封装和信息隐蔽：将数据和代码组合在一起；数据类型的细节对外部是隐蔽的。,例如，int a;其实现是隐蔽的，使用者只能通过整型上定义的一组运算对变量 a 执行操作。,20,第一章 绪论 1.2 数据抽象和 抽象数据类型 一、数据类型 二、数据抽象 三、抽象数据类型 四、数据结构的规范 和实现,数据结构可分成以下两部分：(1)数据结构的规范：逻辑结构和运算的定义(2)数据结构的实现：存储结构和运算算法实现,规范是实现的准则和依据。规范指明“做什么”，实现解决“怎样做”。,21,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象方法1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,1.3 面向对象方法,例子，问题的陈述：开发一个非常简单的字处理程序。该系统允许用户产生文档；所产生的文档存储在一个用户目录中；用户可以打印和显示文档；文档可以改变，也可以被删除。,对象 服务 文档 产生、存储、打印 显示、改变、删除 目录 存储、删除,22,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象方法1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,1.3 面向对象方法,对象 应用领域内的实体和概念，它们通常是问题陈述中的名词。属性 刻划对象的特征。服务或运算 施于对象属性的操作，它们通常是问题陈述中的动词。,同类对象具有相同的属性和服务。同一个类（class)中的每个对象称为该类的一个实例。,23,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象方法1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,继承 是指派生类（子类）可自动共享基类（父类）的公有的和保护的属性和服务的机制。它是面向对象方法最重要的共享机制，从而减少数据和代码的重复。这也是面向对象方法最有特色的方面。,24,第一章 绪论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模板,25,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数的返回值 3.函数原型,1.4.1函数与参数传递,#includeint Abc(int a,int,1.传值参数与引用参数（见dsapg4.cpp）,运行结果:,z=8,x=3,y=4,原因：x 3 a 3 a+a 4y 3 y 4 b b+b,26,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数的返回值 3.函数原型,常量引用参数：const int&c（见dsapg4.cpp）,#includeint Abc(int a,const int 运行结果：z=6,27,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数的返回值 3.函数原型,函数执行时，(1)传值参数 实在参数的值赋给了形式参数，形式参数得到了实在参数的一个副本。函数执行后，实在参数的值不会改变。(2)引用参数 实在参数的地址传给了形式参数。函数执行后，实在参数的值将可能改变。常量引用参数 函数不得修改该引用参数，否则将导致编译出错。,28,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数返回值 3.函数原型,(1)函数返回一个值int Abc(int a,int,2.函数返回值（见dsapg5.cpp）,29,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数的返回值 3.函数原型,3.函数原型,函数原型包括 函数名、返回类型和参数表,例如，下面的程序由三个文件组成：greet.h，greet.cpp，main.cpp。（见greet文件夹）/*存放在头文件greet.h*/void Greet();/函数原型,30,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递 1.传值参数和引用参数 2.函数的返回值 3.函数原型,/*存放在源代码文件greet.cpp中*/#include#include“greet.h”/预处理指令void Greet()/函数 char Name16;coutenter your name:;cin.get(Name,sizeof(Name);coutngreetings,Name n;/*存放在源代码文件main.cpp中*/#include greet.h/预处理指令void main()/主程序 Greet();,31,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递1.4.2 动态存储分配,1.4.2动态存储分配,C语言的动态分配和释放函数 malloc()和free(),int*x;x=(int*)malloc(sizeof(int);*x=10;printf(x=%dn,*x);free(x);int a100;,32,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递1.4.2 动态存储分配,例如：int*y;y=new int;*y=10;三步合并为：int*y=new int(10);,C+的动态分配和释放函数 new()和delete(),33,第一章 绪论1.4 C+程序设计1.4.1 函数与参数传递1.4.2 动态存储分配,例如：分配包括10个整数的数组 int*a=new int 10;a2=5;*(a+3)=7;/a3=7;printf(”a2=%d n”,a2);printf(”a3=%d n”,*(a+3);释放数组空间 deletea;（例见dsapg6.cpp）,C+的数组动态分配和释放 new()和delete(),34,1.C+类,数据和操作组合成类。C+类体现了抽象数据类型的思想，支持面向对象程序设计，实现封装和信息隐蔽的原则。,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类,1.4.3 C+类,三种存取级别：public、private、protected,35,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类,public域 共有成员，可被程 序的其它部分访问。private域 私有成员，只能 由该类的成员函数以及被声明 为友元的函数或类的对象访问。protected域 保护成员，除 了具有private访问权限外，还 允许该类的子类访问它们。,private域用来保护对象内部的数据，实现信息隐蔽。private 是缺省的存取级别。,36,（完整程序见dsapg7.cpp）class Faculty/C+类举例 protected:char*name;int age;public:Faculty(char*name,int age);Faculty();void Change(char*name,int age);/建立类的对象（实例化）Faulty emp;Faulty*emp1=new Faulty;delete emp1;/释放对象存储空间,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类,37,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载,Complex Complex:operator+(const Complex/复数相加,38,C+编译器将com1+com2解释为 com1.operator+(com2)；表达式com1+100是错误的 因为100不是Complex类的一个对象。#The End#,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载,39,3.友元函数和友元类,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载3.友元函数和友元类,友元函数 在类的声明中使用了保留字friend,给出一个普通函数的原型，将此函数定义为该类的友元函数。友元类 在类的声明中使用了保留字friend,将另一个类的所有函数定义为该类的友元函数。,40,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载3.友元函数和友元类,友元类举例 class Y;class X friend Y;class Y,友元函数 可以存取类的私有成员和保护成员。,41,（程序见dsapg8.cpp）class Complex private:double real,image;public:/构造函数 Complex()real=0.0;image=0.0;Complex(double r,double i=0.0)real=r;image=i;Complex(Complex,42,重载加法操作符+实现两个复数相加Complex operator+(Complex,43,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载3.友元函数和友元类,void main()Complex c1(2.3),c2(5,6),c3;c3=c1+c2;coutc1c2c3;运行结果2.3+0i5+6i7.3+6i,定义3个复数对象：c1=2.3，c2=5+6i，c3计算：c3=c1+c2,44,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类,1.4.4 继承性和派生类,继承性 派生类继承基类所定义的数据和方法。,public 继承性（派生）基类所有的公有成员成为派生类的公有成员，基类所有的保护成员成为派生类的保护成员。,45,class Faculty protected:char*name;int age;public:Faculty(char*name,int age);Faculty();void Change(char*name,int age);,class Professor:public Faculty public:void ChangeLevel(int n);Professor(char*name,int age,int level);Professor();private:int level;,C+类Faculty,Professor继承了Faculty所定义的数据和方法。本例称为public继承(派生）。,从类Faculty派生类Professor,46,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编,1.4.5 多态性、虚函数与动态联编,多态性 允许同一个函数（或操作符）有多个版本，对不同的对象执行不同的版本。(1)函数或操作符重载(2)虚函数,1.多态性,47,一个虚函数的例子：（见dsapg10.cpp）#includeclass Base public:virtual void who()coutBasen;,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编,虚函数 虚函数在基类中被声明为virtual，并在一个或多个派生类中被重定义。,2.虚函数,48,class first_d:public Base public:void who()coutFirst derivationn;class second_d:public Base public:void who()coutSecond derivationn;,main(void)Base*p;Base bo;first_d fo;second_d so;p=,输出结果：Base First derivation Second derivation,49,动态联编与静态联编 当一个派生类的对象用基类指针指示时，C+将根据该指针所指向的派生类对象的实际对象类型，在运行时确定应调用哪一个函数。这种在运行时才将对象连接到它的成员函数的做法称为动态联编。动态联编是通过使用派生类和虚函数来完成的。在编译时已明确所调用的对象的成员函数，称为对函数的静态联编。如函数调用、重载函数和操作符调用。,3.动态联编,Complex c1(2.3),c2(5,6),c3;c3=c1+c2;p=,50,4.操作符重载,在构造类时，如果希望能使用C+的操作符，对类的对象进行操作，必须重新定义操作符的意义，称为操作符重载。保留字operator称为操作符函数名，后跟需重定义的操作符。,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.C+类2.操作符重载,重载加法运算符“+”为了将加法运算符“+”用于复数相加，可重载加法运算符“+”。Complex Complex:operator+(const Complex&c)；,51,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编1.4.6 纯虚函数与抽象类,1.4.6 纯虚函数与抽象类,纯虚函数 在基类中只给出虚函数的声明而不给出具体定义的虚函数称为纯虚函数。,抽象类 至少有一个纯虚函数的类称为抽象类。抽象类不能生成实例，因为抽象类中至少有一个函数无定义。抽象类作为基类被其它类继承。,52,包含纯虚函数的类称为抽象类。纯虚函数被初始化为0。（对dsapg10.cpp直接修改）class Base public:virtual void who()=0；;,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编1.4.6 纯虚函数与抽象类,53,class first_d:public Base public:void who()coutFirst derivationn;class second_d:public Base public:void who()coutSecond derivationn;,main(void)Base*p;first_d fo;second_d so;p=,输出结果：First derivation Second derivation,54,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编1.4.6 纯虚函数与抽象类1.4.7 模板,1.4.7 模板,模板函数的定义 template 其中，T1,Tn为n个通用数据类型 参数。保留字class可以称为类型。使用该模板函数时，将以实在的参数类型取代通用数据类型。,1.模板函数 使用通用的函数代码处理不同的数据类型。,55,void main()int x=2;int z=Abc(3,x);cout z=z;float r=2.2F,r1=3.2F;float y=Abc(r1,r);cout y=y;Complex c1(2.3),c2(5,6);Complex c3=Abc(c1,c2);cout c3=c3;运行结果：z=5 y=5.4 c3=7.3+6i,（见dsapg12.cpp）template T 其中，a为传值参数，b为引用参数，函数返回一个引用参数。,56,第一章 绪论1.4 C+程序设计1.4.1函数与参数传递1.4.2动态存储分配1.4.3C+类1.4.4 继承性和派生类1.4.5 多态性、虚函数 与动态联编1.4.6 纯虚函数与抽象类1.4.7 模板,模板类的定义 template 其中，T1,Tn为n个通用数据类型 参数。模板类的成员函数如果在类声明外部定义时，必须定义为带模板参数的模板函数。所有将类作为类型的引用都必须包含模板类型。,2.模板类 类的定义中包含通用类型的数据成员和成员函数。,57,程序1-1 堆栈类（见dsapg13.cpp）基类Stack为：抽象类，模板类const int MaxSize=50;templateclass Stack public:Stack();/构造函数virtual void Push(const T/判断堆栈是否满,58,const int MaxSize=50;templateclass SeqStack:public Stack/派生类：顺序栈SeqStack private:T sMaxSize;int top;public:SeqStack()top=-1;/构造函数 void Push(const T,59,主程序:建立一个数据元素为整数的顺序栈实例 istkvoid main()/模板类实例化，应给出实在类型 SeqStack istk;/建立一个整数顺序栈对象 istk.Push(5);/向栈中插入整数 5 istk.Push(9);/向栈中插入整数 9 coutistk.Top()endl;/输出栈顶元素9 istk.Pop();/删除栈顶元素9 coutistk.Top()endl;/输出栈顶元素5,60,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,1.5 数据结构的描述,1.数据结构的抽象层次 数据结构抽象为一种聚集结构。,61,数据结构被看成是一个类属抽象数据类型，用格式化的自然语言来描述之。另外，数据结构可以形式地用一个C+的抽象模板类描述之。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,2.数据结构的描述方法,62,堆栈数据结构举例,63,ADT 1.1 栈抽象数据类型ADT Stack Data:零个或多个元素的线性序列（a1，a2，an)，遵循LIFO 原则。Operations:Create()：创建一个空栈。Push(x)：在栈中插入元素x。Pop()：删除栈顶元素。Top()：返回栈顶元素。IsEmpty()：若栈空，则返回true，否则返回false。IsFull()：若栈满，则返回true，否则返回false。,用ADT描述数据结构堆栈的例子,64,程序 1-2 栈的C+抽象类templateclass Stackpublic:Stack();virtual void Push(const T 除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。,65,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,1.6 算法及其性能分析,内容提要：1.6.1 算法及其性能分析 1.6.2 算法的空间复杂度 1.6.3 算法的时间复杂度 1.6.4 渐近时间复杂度,66,1.什么是算法 一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：(1)输入 算法有零个或多个输入。(2)输出 算法至少产生一个输出(3)确定性 算法的每一条指令都有确切的定义，没有二义性。(4)能行性 算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。(5)有穷性 算法必须总能在执行有限步之后终止。,1.6.1 算法及其性能分析,67,2.算法描述方法 算法可以自然语言、表格法、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中主要使用C+语言描述。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,68,3.算法的性能标准(1)正确性 算法的执行结果应当满足预先规定的功能和性能要求。(2)简明性 一个算法应当思路清晰、层次分明、简单明了、易读易懂。(3)健壮性 当输入不合法数据时，应能做适当处理，不至于引起严重后果。(4)效率 有效使用存储空间和有高的时间效率。(5)最优性 解决同一个问题可能有多种算法，应进行比较，选择最佳算法。,69,算法的空间复杂度 是程序运行从开始到结束所需的存储量。,1.6.2 算法的空间复杂度,问题实例的特征 与问题的具体实例有关的量。,例如，对一组特定个数的元素进行排序，对该组元素的排序是排序问题的一个实例。元素的个数可视为该实例的特征。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,70,程序运行所需的存储空间包括两部分：（1）固定部分 这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分 这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100个元素的两个数组相加，与分别为10个元素的两个数组相加，所需的存储空间显然是不同的。,71,1.6.3 算法的时间复杂度,程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。,算法的时间复杂度 是程序运行从开始到结束所需的时间。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,72,程序1.2 求一个数组元素的累加之和float sum(float list,const int n)float tempsum=0.0;count+;/针对赋值语句 for(int i=0;in;i+)count+；/针对for语句 tempsum+=listi;count+;/针对赋值语句 count+;/针对for的最后一次执行 count+;/针对return语句 return tempsum;返回,count 是全局变量，用来计算程序步数。每一程序步均与问题实例的规模n无关。程序步数为2n+3。,73,1.6.4 渐近时间复杂度,（一）大O记号 如果存在两个正常数c 和 n0，使得对所有的n，n n0，有f(n)cg(n)则有 f(n)=O(g(n)。即函数f(n)当n充分大时上有界，且g(n)是它的一个上界，也称f(n)的阶不高于g(n)的阶。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,例如，设 T(n)=3.6n3+2.5 n2+2.8，取n0=1,则当nn0 时，T(n)3.6n3+2.5n3+2.8n3=8.9n3取c=8.9,则根据大O记号的定义得：T(n)=O(n3),74,渐近时间复杂性 使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂性。,在大O记号下，可用程序步来估计算法的执行时间。很多情况下，可以通过考察一个算法中的关键操作（关键操作被认为是一个程序步）的执行次数来计算算法的渐近时间复杂性。,常见的渐近时间复杂性从小到大排列有：O(1)O(log2 n)O(n)O(nlog2 n)O(n2)O(n3),75,例如，程序1.2为求一个数组元素的累加之和的算法。（1）其总的程序步数为2n+3，则渐近时间复杂性为O(n)。（2）语句tempsum+=listi可认为是关键操作，它的执行次数为n次，则渐近时间复杂性为O(n)。,第一章 绪论1.1 什么是数据结构1.2 数据抽象和抽象 数据类型 1.3 面向对象程序设计1.4 C+程序设计1.5 数据结构的描述1.6 算法及其性能分析,76,void Mult(int ann,bnn,cnn,int n)/nn矩阵a与b 相乘得到c。for(int i=0;in;i+)/n+1 for(int j=0;jn;j+)/n(n+1)cij=0;/n2 for(int k=0;kn;k+)/n2（n+1)cij+=aik*bkj;/n3 程序步为：2n3+3n2+2n+1 渐近时间复杂度为：T(n)=O(n3),再看一例：,77,（二）记号 如果存在两个正常数c 和 n0，使得对所有的n，n n0，有f(n)cg(n)，则有 f(n)=(g(n)。即函数f(n)当n充分大时下有界，且g(n)是它的一个下界，也称f(n)的阶不低于g(n)的阶。,（三）记号 f(n)=(g(n)，当且仅当f(n)=O(g(n)且f(n)=(g(n)，这时称f(n)与g(n)同阶。,（四）对于O、和的定义，可用求极限的方法作判断：若lim(f(n)/g(n)=C(当n-时）（1）当C0时，说明f(n)与g(n)同阶，记为f(n)=(g(n)（2）当C=0时，说明f(n)比g(n)低阶，记为f(n)=O(g(n)（3）当C=时，说明f(n)比g(n)高阶，记为f(n)=(g(n),78,对于O、和的定义，重点是理解O,（一）O的运算性质：(1)0(f)+O(g)=0(max(f,g)(2)0(f)+O(g)=0(f+g)(3)0(f)O(g)=0(fg)(4)若g(n)=0(f),则0(f)+0(g)=0(f)(5)0(cf(n)=0(f(n)(6)f=O(f),79,（二）O的运算性质的证明：性质(1)0(f)+O(g)=0(max(f,g)证明：设F(N)=0(f),根据0的定义，存在正常数C1和自然数N1，使得对所有的NN1，有 F(N)C1f(N),同理，设G(N)=0(g),根据0的定义，存在正常数C2和自然数N2，使得对所有的NN2，有 F(N)C2f(N).现在令C3=max(C1,C2),N3=max(N1,N2),h(N)=max(f(N),g(N),则当NN3时，必有：F(N)C1f(N)C3f(N)C3h(N)和 G(N)C2g(N)C3g(N)C3h(N)上面两式相加,得:F(N)+G(N)2C3h(N),取C=2C3,则当 NN3时，有:0(f)+0(g)Ch(N)=Cmax(f,g),再根据0的定义可得,0(f)+0(g)=0(max(f,g),80,第1章绪论是预备知识，也是学习数据结构必备的知识。首先给出传统的数据结构的概念，继而介绍抽象数据类型和面向对象的基本概念，回顾C+语言的基本特征，以及算法的效率和算法分析的基本方法。本章的学习将贯穿全书。通过本章学习，希望掌握如下内容：1.了解下列有关数据结构的术语和概念：数据、数据元素、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型、数据结构的规范和实现。2.复习下列面向对象的术语和概念：对象、属性、服务、对象类、继承、父类、子类,本章小结 第1章 绪论,81,3.复习下列 C+概念：传值参数、引用参数、常量引用参数、函数原型、动态存储分配、操作符重载、友元函数、友元类、继承、基类、派生类、多态性、虚函数、动态联编、纯虚函数、抽象类、模板函数和模板类。4.了解数据结构的抽象层次。5.学会使用类属抽象数据类型和模板抽象类描述数据结构的方法。6.算法、算法的空间复杂性、算法的时间复杂性、程