《数据结构与算法讲义》由会员分享，可在线阅读，更多相关《数据结构与算法讲义（147页珍藏版）》请在金锄头文库上搜索。
1、第三章 数据结构与算法,主讲：乔志会,大学计算机基础,Page 2,第三章 数据结构与算法,Page 3,一.数据结构与算法,绪论,线性结构,树形结构,串、数组、图文件,Page 4,一.数据结构与算法,绪论,Page 5,1.1什么是数据结构,什么是数据结构非数值计算实例,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及操作对象之间的关系和操作的学科。,例1：学籍管理（线性结构）例2：输出n个对象的全排列（树形结构）例3：制定教学计划（图或网状结构）,Page 6,1.1什么是数据结构,例1：学籍管理（线性结构）,学生基本情况,Page 7,1.1什么是数据结构,例2：输出3
2、个对象的全排列（树形结构）,输出3个对象的全排列形式描述,Page 8,1.1什么是数据结构,例3：制定教学计划（图或网状结构）,计算机专业学生的必修课程,课程先后关系的图形描形式,Page 9,1.2基本概念和术语,数据,数据（Data）是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。它是计算机加工处理的对象，可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。,Page 10,1.2基本概念和术语,数据元素,数据元素（Data Eleme
3、nt）是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由一个或多个数据项组成，数据项（Data Item）是有独立含义的最小单位，此时的数据元素通常称为记录（Record）。例如学生基本情况中学生基本情况表是数据，每一个学生的记录就是一个数据元素，每个数据元素由学号、姓名、性别、出生年月、政治面貌等数据项组成。,Page 11,1.2基本概念和术语,数据对象,数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如整数数据对象是集合N=0，1，2，大写字母字符数据对象是集合C= A ， B ， Z ，学生基本情况表所示
4、的学生基本情况也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素集，只要性质相同，都是同一个数据对象。,Page 12,1.2基本概念和术语,数据结构,数据结构（Data Structure）是指数据元素之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，都存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，数据间关系有以下四类结构：,（1）集合结构。在集合结构中，数据元素间除了“同属于一个集合”的关系外，别无其他关系。集合是元素关系极为松散的一种结构。
5、 （2）线性结构。数据元素之间存在着一对一的关系。 （3）树形结构。数据元素之间存在着一对多的关系。 （4）图状结构。数据元素之间存在着多对多的关系，图状结构也称作网状结构。,Page 13,1.2基本概念和术语,数据类型,数据类型（Data Type）是和数据结构密切相关的一个概念。数据类型是一个值的集合和定义在该值的集合上的一组操作的总称。,Page 14,1.2基本概念和术语,抽象数据类型,抽象数据类型（Abstruct Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。,抽象数据
6、类型的描述为： ADT name 数据对象：D= 数据关系：R= 基本操作：创建；输出；插入；删除；等等; ADT name;,Page 15,1.2基本概念和术语,抽象数据类型举例,抽象数据类型的描述为： ADT name 数据对象：D= 数据关系：R= 基本操作：创建；输出；插入；删除；等等; ADT name;,复数的抽象数据类型： ADT Complex 数据对象：D= c1 ,c2 | c1 ,c2 float 数据关系：R= | c1,c2分别代表复数的实部和虚部基本操作：创建一个复数；输出一个复数；求两个复数的和；求两个复数的积；等等; ADT Complex;,Page 16,
7、1.3算法和算法分析,算法,算法（Algorithm）是对特定问题求解步骤的一种描述，是操作的有限序列。一个算法应具备下列特性：（1）有穷性。一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成；（2）确定性。算法的每一步必须有确切的含义，无二义性，并且在任何条件下，某一时刻算法只有唯一的一个操作被执行；（3）可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行来实现； （4）输入。一个算法有零个或多个输入，这些输入取自特定的数据对象集合；（5）输出。一个算法具有一个或多个输出，这些输出是同输入之间存在某种特定关系的量。,Page 17,1.3算法和算法分析,算法,算法与数
8、据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而选择的恰当与否将直接影响到算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。衡量一个算法的性能主要有以下几个标准：（1）正确性。算法的执行结果应当满足预先规定的功能和性能要求；（2）可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂；（3）健壮性。当输入不合法数据时，应能作适当处理，不至引起严重后果；（4）高效性。有效使用存储空间和有较高的时间效率。,Page 18,1.3算法和算法分析,算法分析,评价一个算法主要看这个算法所要占用机器资源的多少，而在这些资源中时间和空间是两个最主要的因素，因此，算法分析
9、中最关心的就是算法所需要的时间代价和空间代价。算法的优劣可以通过一个算法的时间复杂度与空间复杂度来评价。,Page 19,1.3算法和算法分析,算法分析,（1）时间复杂度 一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作：T(n)=O(f(n)它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。这里的“O”表示量级
10、（Order），常用大O记法表示时间复杂度，表示说只是有上界。 （2）空间复杂度一个算法的空间复杂度（Space Complexity）是指这个算法执行过程中所需的存储空间，包括算法本身所需存储空间、输入数据所占存储空间及算法执行过程中所需的额外空间，记作：S(n)=O(f(n)表示随着问题规模n的增大，算法运行所需的存储量的增长率与f(n)的增长率相同。,Page 20,1.3算法和算法分析,算法分析,（3）时间复杂度举例 x=x+1;算法中含基本操作“x=x+1”的语句频度为1，那么算法的时间复杂度记作：T(n)=O(1)，称为常量阶。 for(i=1;i=n;i+)x=x+1;算法中含基
11、本操作“x=x+1”的语句频度为n，该算法的时间复杂度记作：T(n)=O(n)，称为线性阶。 for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;算法中含基本操作“x=x+1”的语句频度为n2，该算法的时间复杂度记作：T(n)=O(n2)，称为平方阶。,Page 21,1.3算法和算法分析,算法分析,（3）时间复杂度举例 i=1;while(in) i=i*2;算法中含基本操作“i=i*2”的语句频度为log2n，该算法的时间复杂度记作：T(n)=O(log2n)，称为对数阶。 for(i=0;in;i+)for(j=0;ji;j+)for(k=0;kj;k+)x=x+1;
12、算法中含基本操作“x=x+1”的语句频度为n3，该算法的时间复杂度记作：T(n)=O(n3),Page 22,1.3算法和算法分析,算法分析,（3）时间复杂度举例 随着问题规模n的增大，其时间消耗T(n)也在增大。常见的渐进时间复杂度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)其中线性阶(n)、平方阶(n2)和对数阶(log2n)是“数据结构”算法分析常见的重要方法。不同数量级时间复杂度的性状如图所示。,Page 23,一.数据结构与算法,线性结构,Page 24,2.1线性表,线性表的定义,线性表（Linear List）是n(n0)个数据元素的有限序列。在表中，元
13、素之间存在着线性的逻辑关系：表中有且仅有一个开始结点；有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点（Predecessor）；除终端结点外，表中的每个结点均只有一个后继结点（Successor）。根据它们之间的关系可以排成一个线性序列，记作：(a1，a2，an)这里ai(1in)表示数据元素，具有相同的数据类型。n代表线性表的表长，即线性表中数据元素的个数。当n=0时，线性表为空表。对于ai，当1in时，它有一个直接前驱ai1； 当1in时，它有一个直接后继ai+1。,Page 25,2.1线性表,线性表的抽象数据类型,线性表的抽象数据类型定义为： ADT Linear
14、_list 数据对象：D=ai | aiElemSet , i=1,2,n, n0；数据关系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空线性表；求线性表表长；取线性表的第i个元素；在线性表的第i个位置插入元素x；删除线性表的第i个元素；修改线性表中的第i个元素；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；ADT Linear_list； 其中，ElemSet表示有数据元素具有的数据类型。,Page 26,2.1线性表,线性表的顺序存储结构,（1）线性表的顺序存储结构 （2）顺序表类定义 （3）顺序表的插入和删除算法,Page 27,2.1线性
15、表,线性表的顺序存储结构,（1）线性表的顺序存储结构线性表采用顺序存储的方式存储就称之为顺序表。线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。 顺序存储结构的特点： 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构依赖于存储结构（物理结构）的物理连续来表示； 在访问线性表时，只要确定了线性表的起始位置，线性表中任一数据元素的位置均可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,Page 28,2.1线性表,线性表的顺序存储结构,（2）顺序表类定义 在C+中使用一维数组来实现顺序存储结构。为了更好地体现信息隐蔽原则以及数据抽象原则，通常将数据元素的存储结构和对数据的操作封装在一个类中。其数组和线性表长度可以作为类的数据成员。线性表的各种操作的处理可以作为类的成员函数，且大多是公有函数，目的是提供类对外的接口。顺序表类定义如下： const int MAXSIZE=100; typedef int ElemType ; /假设线性表中元素为整型 class SqList private:ElemType elemMAXSIZE; /一维数组 int length ; /线性表长度 public:; /其他成员函数; ；,
