《数据结构》课件1第1章 绪论

第1章绪论数据结构的研究内容数据结构的基本概念抽象数据类型及其实现算法和算法分析1.1数据结构的研究内容2对于数值计算问题的求解，一般经过以下几个步骤：首先从具体问题抽象出数学模型，然后设计一个求解此数学模型的算法，最后编写程序，并进行测试、调试，直到解决问题。在此过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。例如，预测人口增长情况的数学模型为常微分方程，求解数学方程的方法是计算数学研究的范畴。数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型。非数值计算问题的数学模型不再是数学方程，而是线性表、树、图等数据结构。因此，简单地说，数据结构的研究范畴主要是非数值计算问题的操作对象和它们之间的关系以及在计算机中的表示和实现。1.2数据结构的基本概念数据数据是客观事物的符号表示，是所有能输入到计算机中并能被计算机处理的符号的总称。数据可以指数值型数据，如整数、实数、复数等；也可以是非数值型数据，如文字、图形、图像、声音、动画等。数据元素数据元素是数据的基本单位，在计算机中通常作为一个整体进行处理。在有些情况下，数据元素也称为元素、记录、结点、顶点等。数据元素用于完整地描述一个对象，例如，学生基本信息表中每个学生记录是一个数据元素。数据项数据项是组成数据元素的、有独立含义的、不可分割的最小单位，是对数据元素属性的描述。例如，学生基本信息表中，每个数据元素（即学生记录）是由学号、姓名、性别、出生日期、籍贯和专业等数据项组成的数据对象数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0，±1，±2，⋯}，字母字符数据对象是集合C={‘A’，‘B’，⋯，‘Z’，‘a’，‘b’，⋯，‘z’}，学生基本信息表也是一个数据对象。1.数据、数据元素、数据项和数据对象31.2数据结构的基本概念数据结构（DataStructure）是相互之间存在着一定关系的数据元素的集合。换句话说，数据结构是带结构的数据元素的集合，结构就是指数据元素之间存在的关系。数据结构包括逻辑结构和存储结构两个层次。2.数据结构4逻辑结构存储结构1.2数据结构的基本概念逻辑结构2.数据结构5数据的逻辑结构是指数据元素以及数据元素之间的逻辑关系，是从实际问题抽象出的数据模型，形式上可定义为一个二元组：DataStructure＝（D，R）其中D是一个数据元素的有限集合，R是定义在D中的数据元素之间的关系的集合。根据数据元素之间逻辑关系的不同，通常有四类基本结构：(1)集合结构：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系。(2)线性结构：数据元素之间存在一对一的关系。(3)树结构：数据元素之间存在一对多的关系。(4)图结构：数据元素之间存在多对多的关系。树结构和图结构也称为非线性结构。1.2数据结构的基本概念存储结构2.数据结构6数据的存储结构又称为物理结构，是数据对象在计算机中的存储表示。把数据对象存储到计算机时，除了存储数据元素之外，还必须隐式或显式地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链式存储结构。顺序存储结构使用一组连续的存储单元依次存储数据元素，元素之间的逻辑关系由元素在存储器中的相对位置来表示。链式存储结构是用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。1.3抽象数据类型71.数据类型数据类型是一组性质相同的值的集合以及定义在此集合上的一组操作的总称，是程序设计语言中已实现的数据结构。在程序设计语言中，每一个数据都属于某种数据类型。类型显式或隐式地规定了数据的取值范围、存储方式以及允许进行的运算。2.抽象数据类型抽象数据类型一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述，一般包括数据对象、数据关系和基本操作三方面的内容，描述格式如下：ADT抽象数据类型名{

数据对象：数据对象的声明 数据关系：数据关系的声明 基本操作：基本操作的声明}1.3抽象数据类型类的定义3.C++的类和对象8类的定义格式一般分为两大部分：声明部分和实现两部分，声明部分用来声明该类中的成员，包括数据成员和成员函数（方法或操作）。实现部分用来给出说明部分中所说明的成员函数的实现和定义。class<类名>{private:

私有数据成员和成员函数;public:公有数据成员和成员函数;protected:

保护数据成员和成员函数;};C++中用关键字class来声明类，格式如下：类的成员函数是类的行为，是程序算法的具体实现。成员函数必须在类体内进行原型说明，一般情况下，不写出函数体，它们的实现写在类外。在类外定义成员函数的格式为：函数类型类名::成员函数名([参数表>]) {

函数体;}【例1.4】Complex类的定义对象的定义类名对象名;或类名对象名([实参表]);【例1.5】使用Complex类实现复数的加减运算1.3抽象数据类型C++提供了动态存储分配机制，使得程序在运行期间根据需要动态地申请和释放内存空间。4.C++的动态存储分配9C++使用new运算符分配存储空间，格式如下：new数据类型;

//建立单个数据元素或new数据类型[元素个数];//建立数组例如：int*p1=newint; int*p2=newint[3]; 释放存储空间用new运算符开辟的内存空间，如果程序不主动收回，那么这段空间就一直存在，直到程序结束。分配存储空间C++中使用delete运算符释放动态分配的内存空间，格式如下：delete指针变量; //释放单个数据元素或delete[]指针变量; //释放数组1.3抽象数据类型C++中的模板有两种形式：函数模板和类模板。5.C++的模板10定义函数模板的一般形式为：template<模板形参表>函数定义模板形参表中可以包含一个或多个模板形参，如果有多个，必须用逗号分隔。模板形参的格式为：typename模板类型标识符或class模板类型标识符例如，求两个数中最大值的函数模板定义：函数模板template<typenameT>Tmax(Ta,Tb){ return(a>b)?a:b;}在主函数中使用函数模板：intmain(){inta=10,b=25;doublec=20.8,d=13.4;cout<<max(a,b)<<endl;cout<<max(c,d)<<endl;return0;}1.3抽象数据类型C++中的模板有两种形式：函数模板和类模板。5.C++的模板11类模板声明的语法形式为：template<模板参数表>class类名{

类成员声明;}如果需要在类模板以外定义其成员函数，则采用以下形式：template<模板参数表>类型名类名<模板类型标识符>::函数名([形参表])程序中使用模板类定义对象变量，一般采用以下形式：模板类名<模板参数>对象名1,对象名2,…,对象名n;其中模板参数是确定的数据类型，编译器根据模板参数创建相应类型的对象变量，并以适当的形式调用模板函数。【例1.6】类模板应用示例类模板1.

4算法和算法分析1.算法12算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的定义及特性有穷性确定性可行性输入输出算法的特性：评价算法优劣的基本标准正确性可读性健壮性高效性1.

4算法和算法分析2.算法分析13(1)问题规模和语句频度时间复杂度问题规模是指输入量的多少，一般可以从问题描述中得到。语句的重复执行次数称作语句频度。个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的频度和执行一次所需时间的乘积。

1.

4算法和算法分析2.算法分析14(2)算法的时间复杂度定义时间复杂度为了客观地反映一个算法的执行时间，可以只用算法中基本语句的执行次数来度量算法的工作量。基本语句是执行次数与整个算法的执行次数成正比的语句，基本语句对算法运行时间的贡献最大。通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。

1.

4算法和算法分析时间复杂度分析示例15【例1.8】常数阶示例。 intsum=0; for(inti=1;i<=100;i++) sum+=i; 【例1.9】线性阶示例。 intsum=0; for(inti=1;i<=n;i++) sum+=i;【例1.10】平方阶示例。 ints=0; for(inti=1;i<=n;i++) for(intj=1;j<=2*i;j++) s++;

1.

4算法和算法分析2.算法分析16算法在运行过程中所需的存储空间包括：(1)输入输出数据占用的空间；(2)算法本身占用的空间；(3)执行算法需要的辅助空间。空间复杂度其中，输入输出数据占用的空间取决于问题，与算法无关；算法本身占用的空间虽然与算法相关，但一般其大小是固定的。所以，算法的空间复杂性是指在算法的执行过程中需要的辅助空间数量，也就是除算法本身和输入输出数据所占用的空间外，算法临时开辟的存储空间，这个辅助存储空间数量也应该是输入规模的函数，通常记作：S(n)=O(f(n))其中，n为输入输出规模，分析方法与算法的时间复杂度类似。本章小结(1)数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。(2)数据结构包括：数据的逻辑结构和存储结构。逻辑结构是指数据元素以及数据元素之间的逻辑关系，是从实际问题抽象出的数据模型。根据数据元素之间关系的不同特性，通常有四类基本逻辑结构：集合结构、线性结构、树形结构和图状结构。存储结构是逻辑结构在计算机中的存储表示，通常有两种存储结构：顺序存储结构和链式存储结构。(3)抽象数据类型是指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，一般包括数据对象、数据关系和基本操作三方面的内容。