《第1章绪论(MR)》由会员分享，可在线阅读，更多相关《第1章绪论(MR)（58页珍藏版）》请在金锄头文库上搜索。
1、信息学院 马睿数据结构2课程安排教材：数据结构(C语言版)作者：马睿、孙丽云等学时：72时（其中上机16学时）参考资料:数据结构(C语言版)严蔚敏,吴伟民著 清华大学出版社数据结构与算法许卓群,杨冬青等著 高等教育出版社数据结构(C语言版)赵坚,姜梅等 中国水利水电出版社3其它信息上机时间上机时间: :双周双周周五周五1 1、2 2节节上机地点上机地点:M402:M402办公地点办公地点:F:F座座103103室室邮箱邮箱::4考试方式笔试为主笔试为主, ,上机为辅上机为辅; ;总成绩总成绩= =考试考试(70%)+(70%)+平时平时(30%)(30%)平时包括出勤平时包括出勤, ,作业，期
2、中和上机情况作业，期中和上机情况5第1章 绪论本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用教学目的：了解数据结构的基本概念，理解常用术语术语教学重点：熟悉数据结构常用术语，掌握基本概教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与念，了解算法时间复杂度和空间复杂度的分析与评价评价 教学难点：数据元素间的教学难点：数据元素间的 4 4 种结构关系种结构关系。6本章主要内容1.1 1.1 引言引言1.2 1.2 基本概念和常用术语基本概念和常用术语1.3 1.3 算法和算法分析算法和算法分析71.
3、1.1为什么要学习数据结构对于计算机的相关专业：p专业基础课p考试课p考研课8 数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计的程序设计问题中计算机的操作对象以及它们之间的问题中计算机的操作对象以及它们之间的关系关系和操作和操作的学科。数据结构主要有以下内容：的学科。数据结构主要有以下内容： 数据的逻辑结构：数据的逻辑结构： 数据的存储结构：数据的存储结构： 算法：算法：什么是数据结构9什么是数据结构表表1-1 数据结构课程内容体系数据结构课程内容体系 方面方面层次层次数据表示数据表示数据处理数据处理抽象抽象逻辑结构逻辑结构基本运算基本运算实现实现存储结构存储结构算法算法评
4、价评价不同数据结构的比较及算法不同数据结构的比较及算法分析分析101.2.1 基本概念和术语1 1数据数据(Data)(Data) ：是对信息的一种符号表示是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包中并被计算机程序处理的符号的总称。包括括文字、表格、图象文字、表格、图象等。等。111.2.1 基本概念和术语2 2数据元素数据元素(Data (Data Element)Element)：是数据的基本是数据的基本单位，在计算机程序中通常作为一个整体单位，在计算机程序中通常作为一个整体进行考虑和处理。进行考虑和
5、处理。 一个数据元素可由若干个数据项组成。数一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。据项是数据的不可分割的最小单位。12 数据项：数据项：是数据结构中讨论的最小最小单位数据元素可以是数据项的集合数据元素可以是数据项的集合例如：描述一个运动员的数据元素如下：称之为初等项称之为初等项称之为组合项称之为组合项13概念之间的关系：概念之间的关系：数据数据对象数据元素数据项1.2.1 基本概念和术语3 3数据对象数据对象(Data Object) (Data Object) ：是性质相同的是性质相同的数据元素的集合。是数据的一个子集。数据元素的集合。是数据的一个子集。141.
6、2.2数据结构(Data Structure)数据结构： 按某种逻辑关系组织起来的一批数据，按一定的存储方式把它存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就叫一个数据结构。15数据的逻辑结构两个要素：数据的逻辑结构两个要素：p数据元素的集合数据元素的集合p关系的集合。关系的集合。 1.2.2数据结构(Data Structure)16数据的逻辑结构通常可以采用一个二元组来表示：Data_Structure （D, R）pData_Structure 是一种数据结构pD=di|1in,n0 pR=rj|1jm,m0pri= | 其中，x,yK 序偶表示：元素x和元素y之间存在关系
7、，并且称元素x为元素y的前驱，元素y为元素x的后继。如果元素x既是元素y的前驱，也是元素y的后继，既且，则用（x,y）形式表示。1.2.2数据结构(Data Structure)171.2.2数据结构(Data Structure)数据的逻辑结构可归结为以下四类: (1)集合结构 (2)线性结构 (3)树形结构 (4)图状结构18(1)(1)集合结构：数据元素之间除了同属于一个集合集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。之外，没有其他关系的数据结构。例子：从大街上随意例子：从大街上随意的找六个人组成一个的找六个人组成一个小组，编号分别为小组，编号分别为1 1、2
8、2、3 3、4 4、5 5、6 6，则这，则这六个人之间除了属于六个人之间除了属于同一组以外，相互间同一组以外，相互间不存在任何的关系。不存在任何的关系。 组成集合的数据组成集合的数据元素之间不存在任元素之间不存在任何的关系何的关系图1-1(a) 集合19(2)(2)线性结构：数据元素之间存在线性结构：数据元素之间存在“一对一一对一”线线性关系的数据结构。性关系的数据结构。例，一个学生管理程序所要处理的例，一个学生管理程序所要处理的数据可能是一张表格。除了第一条数据可能是一张表格。除了第一条和最后一条以外，每条记录都只有和最后一条以外，每条记录都只有唯一的前驱和后继元素。唯一的前驱和后继元素。
9、元素之间是元素之间是1 1：1 1关系，关系，都只有唯一的前驱和都只有唯一的前驱和唯一的后继唯一的后继序号序号学号学号姓名姓名性性别别专业专业出生日期出生日期1200802056刘文杰刘文杰男男软软件工程件工程1990，12200803011白萍白萍女女信息工程信息工程1989，33200701055刘刘丽丽女女计计算机科学与技算机科学与技术术1990，54200802033李莎莎李莎莎女女软软件工程件工程1990，105200701028徐涛徐涛男男计计算机科学与技算机科学与技术术1989，66200801065田磊田磊男男计计算机科学与技算机科学与技术术1989，2201.2.2数据结构(
10、Data Structure)【例1-1】一种数据结构L（D, R），其中 D=1，2，3，4，5，6 R=r r=， 试画出对应的逻辑结构图，说明它是何种数据结构，并给出哪些是开始结点，哪些是终端结点？21(3)(3)树型结构：数据元素之间存在树型结构：数据元素之间存在“一对多一对多”逻逻辑关系的数据结构。辑关系的数据结构。例：某磁盘例：某磁盘E E：盘包括一个根目录（：盘包括一个根目录（rootroot）和若干个一级子目录，如有电）和若干个一级子目录，如有电子图书、电子教案、自编教材等一级子目录，每个一级子目录中又包含子图书、电子教案、自编教材等一级子目录，每个一级子目录中又包含若干个二级
11、子目录，如在电子图书一级子目录下有若干个二级子目录，如在电子图书一级子目录下有C+C+程序设计程序设计, ,数据结数据结构构, ,计算机网络等二级子目录。这种关系很像自然界中的树，所以称为目计算机网络等二级子目录。这种关系很像自然界中的树，所以称为目录树。录树。元素之间的关系是元素之间的关系是1 1：n n，每个元素都只有唯，每个元素都只有唯一的前驱元素，但可一的前驱元素，但可以有多个后继元素以有多个后继元素221.2.2数据结构(Data Structure)【例1-2】一种数据结构T（D, R），其中 D=1，2，3，4，5，6，7，8 R=r r=， 试画出对应的逻辑结构图，说明它是何种
12、数据结构，并给出哪些是开始结点，哪些是终端结点？23(4)(4)图型结构：数据元素之间存在图型结构：数据元素之间存在“多对多多对多”逻辑关系的数据结构。逻辑关系的数据结构。元素之间的关系是元素之间的关系是m:nm:n，每，每个元素都可以有多个前驱元个元素都可以有多个前驱元素和多个后继元素素和多个后继元素241.2.2数据结构(Data Structure)【例1-3】一种数据结构G（D, R），其中 D=1，2，3，4，5，6 R=r r=， ， ， ， 试画出对应的逻辑结构图，并说明它是何种数据结构？251.2.2数据结构(Data Structure)存储结构又称物理结构，就是数据结构在计
13、算机中的存储方式。可分为以下四类：p顺序存储p链式存储p索引存储p散列存储0123.顺序结构空间示意图顺序结构空间示意图数组链式结构空间示意图链式结构空间示意图指针26顺序存储：所有元素存放在一片连续的存储空间中，顺序存储：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。逻辑上相邻的元素在内存中的物理位置也是相邻的。注意：注意：元素存放在连续的存储空间中，元素之间的元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。逻辑关系由在内存中的物理位置来体现。 例：对一个由（例：对一个由（A A，B B，C C，D D，E E）五个元）五个元素组
14、成的数据结构采素组成的数据结构采用顺序存储，则内存用顺序存储，则内存中的存储示意图如下中的存储示意图如下所示：所示：起始地址27链式存储：所有元素存放在可以不连续的存储单元链式存储：所有元素存放在可以不连续的存储单元中，以结点的形式存在，每个结点除了保存数据元素中，以结点的形式存在，每个结点除了保存数据元素信息外，还通过指针来保存元素之间的关系。信息外，还通过指针来保存元素之间的关系。注意：注意：既元素存储在不连续的存储单元中，元素间既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。的关系通过结点中的指针信息来体现。 例：对一个由（例：对一个由（A A,B B,C C,
15、D,ED,E）五个元素组成的数）五个元素组成的数据结构采用链式存储，据结构采用链式存储，则内存中的存储示意图则内存中的存储示意图如下所示：如下所示：281.2.2数据结构(Data Structure)运算是对数据的处理。运算与逻辑结构紧密相连，每种逻辑结构都有一个运算的集合。运算的种类很多，根据操作的结果，可将运算分为两种类型：p引用型运算p加工型运算291.2.2数据结构(Data Structure)主要的运算集合：p查找p插入p删除p修改p排序301.2.2数据结构(Data Structure)数据结构三方面的关系数据结构三方面的关系pp数据的逻辑结构、数据的存储结构及数据的运算三方
16、面数据的逻辑结构、数据的存储结构及数据的运算三方面数据的逻辑结构、数据的存储结构及数据的运算三方面数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。构成一个数据结构的整体。构成一个数据结构的整体。构成一个数据结构的整体。pp存储结构是对数据项的存储。同一逻辑结构可用不同存储结存储结构是对数据项的存储。同一逻辑结构可用不同存储结存储结构是对数据项的存储。同一逻辑结构可用不同存储结存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同的存储标识。构就对应不同的存储标识。构就对应不同的存储标识。构就对应不同的存储标识。 例如例如例如例如，线性表若采用顺序存储方式，称为
17、，线性表若采用顺序存储方式，称为，线性表若采用顺序存储方式，称为，线性表若采用顺序存储方式，称为顺序表顺序表顺序表顺序表；若；若；若；若采用链式存储方式，称为采用链式存储方式，称为采用链式存储方式，称为采用链式存储方式，称为链表链表链表链表；若采用散列存储方式，；若采用散列存储方式，；若采用散列存储方式，；若采用散列存储方式，可称为可称为可称为可称为散列表散列表散列表散列表。311.2.3抽象数据类型（Abstruct Data Type，ADT） 数据类型(Data Type):是一组性质相同的值的集合以及定义在这个集合上的一组操作的总称。321.2.2抽象数据类型（Abstruct Dat
18、a Type，ADT）抽象数据类型（Abstruct Data Type，简称ADT） ADT是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关331.3算法和算法分析算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法必须满足以下五个重要特性：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出34算法特性1有穷性: 对于任意一组合法输入值，在执行有穷步
19、骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。35算法特性2确定性: 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。36算法特性3可行性: 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。37算法特性4输入:作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。38算法特性5输出: 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算
20、法的功能。39算法描述 一个算法可以用自然语言、流程图或伪代码等来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等，本书选用C语言作为描述算法的工具。401.3.2 算法评价与分析算法设计的要求 设计算法时，通常应考虑达到以下目标：1正确性正确性2. . 可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求411 1正确性正确性 对算法是否“正确正确”的的理解可以有以下两个层次两个层次：a a程序中不含语法错误；程序中不含语法错误；b b在合理的数据输入下，能够在有在合理的数据输入下，能够在有限的运行时间内得到正确的执行结果限的运行时间内得到正确的执
21、行结果422. . 可读性可读性 算法主要是为了人的阅读与交流，算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该其次才是为计算机执行，因此算法应该易易于人的理解于人的理解；另一方面，晦涩难读的程序；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。易于隐藏较多错误而难以调试。433健壮性健壮性 当当输入的数据非法输入的数据非法时，算法应当恰当时，算法应当恰当地作出反映或地作出反映或进行相应处理进行相应处理，而不是产，而不是产生莫名奇妙的输出结果。并且，处理出生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应错的方法不应是中断程序的执行，而应是返回一个表示错误
22、或错误性质的值，是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。以便在更高的抽象层次上进行处理。444高效率与低存储量需求高效率与低存储量需求通常，效率指的是通常，效率指的是算法执行时间算法执行时间；存储量指的是算法执行过程中存储量指的是算法执行过程中所需的所需的最大存储空间最大存储空间，两者都与问题的规模，两者都与问题的规模有关。有关。451.3.3 算法效率的度量 1 1时间复杂度（时间复杂度（Time complexityTime complexity） 一个算法的时间复杂度是指算法运行从开始到结束所一个算法的时间复杂度是指算法运行从开始到结束所需要的时间需要的时间。一
23、般用算法所执行的基本运算次数来度一般用算法所执行的基本运算次数来度量。而算法所执行的基本运算次数是问题规模的函数量。而算法所执行的基本运算次数是问题规模的函数T(nT(n) ) ，常采用数量级的形式表示。，常采用数量级的形式表示。记作：记作： T(n)=O(f(n)T(n)=O(f(n) 称称T(n)T(n)为算法的为算法的( (渐近渐近) )时间复杂度。时间复杂度。461.3.3 算法效率的度量【例1-5】下面的程序段实现1n的累加求和。int sum(int n) int i,s=0; for(i=1;i=n;i+) s+=i; return s;T (n) 1+1+（n+1）+n+n+1
24、=3n+4算法的时间复杂度 若语句很少执行且与规模若语句很少执行且与规模n n无关，则可忽略不计；无关，则可忽略不计； 若若所所有有语语句句都都与与规规模模n n无无关关，则则即即使使有有上上千千条条语语句句，其其执执行行时时间间也也不不过过是是一一个个较较大大的的常常数数，故故时时间间复复杂杂度的量级也只是度的量级也只是O(nO(n0 0)=O(1)=O(1)；一般可只考虑与程序规模有关的频度最大的语句，一般可只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等如循环语句的循环体，多重循环的内循环等。 算法的时间复杂度常见时间复杂度的量级有：常数阶O(1)、线性阶O(
25、n)、平方阶O(n2)、指数阶O(2n )、对数阶O(log2n)、线性对数阶O(nlog2n)。491.3.3 算法效率的度量【例1-6】简单选择排序。 void SelectSort(int a , int n) int i,j,k,x; for (i=0; in-1; i+) k=i; for(j=i+1; jaj) k=j; x=ai; ai=ak; ak=x; 501.3.3 算法效率的度量【例1-7】下面的程序段用来求两个n阶方阵A和B的乘积C。void MatrixMult(int A,int B,int C,int n) int i,j,k; for(i=0;in;i+) fo
26、r(j=0;jn;j+) Cij=0; for(k=0;kn;k+) Cij+=Aik*Bkj; 练习：练习：说明下列各个程序段的时间复杂度。说明下列各个程序段的时间复杂度。 /*交换交换a和和b的内容的内容*/ t=a; a=b; b=t; /*求求n以以内内所所有有2的的幂幂次次数数的的和和，即即 1+21+22+2k，2kn */ sum=0; for(i=1;i=n;i*=2) sum+=i; /*给二维数组给二维数组a赋值赋值i+j*/ for(i=0;in;i+) for(j=0;jn;j+) aij=i+j; O(1)O(log2n)O(n2)算法的时间复杂度 在具体分析一个算法
27、的工作量时，还会存在这样在具体分析一个算法的工作量时，还会存在这样的问题：的问题：对于一个固定的规模，算法所执行的基本对于一个固定的规模，算法所执行的基本运算次数，还可能与特定的输入有关，而实际上又运算次数，还可能与特定的输入有关，而实际上又不可能将所有可能情况的算法所执行的基本运算次不可能将所有可能情况的算法所执行的基本运算次数都列举出来数都列举出来。例如：在长度为。例如：在长度为n n的一维数组中，的一维数组中，采用顺序搜索法查找值为采用顺序搜索法查找值为x x的元素。的元素。算法的时间复杂度平均性态最坏情况复杂性541.3.3 算法效率的度量 2空间复杂度（Space complexit
28、y） 一个算法的空间复杂度是指算法运行从开始到结束所需的存储量。算法的存储量指的是算法执行过程中所需的最大存储空间。 算法执行期间所需要的存储量应该包括以下三部分： (1) 输入数据所占空间； (2) 程序本身所占空间； (3) 辅助变量所占空间。 通常以算法的空间复杂度作为算法所需存储空间的量度。定义：S(n)=O(g(n)称S(n)为算法的空间复杂度。55 若输入数据所占空间只取决于问题若输入数据所占空间只取决于问题 本身，和算法无关，则只需要分析本身，和算法无关，则只需要分析除除 输入和程序之外的辅助变量所占额外输入和程序之外的辅助变量所占额外 空间空间。 若所需额外空间相对于输入数据量若所需额外空间相对于输入数据量 来说是常数，则称此算法为来说是常数，则称此算法为原地工作原地工作。 若所需存储量依赖于特定的输入，若所需存储量依赖于特定的输入，则通常按最坏情况考虑。则通常按最坏情况考虑。561. 熟悉各名词、术语的含义，掌握熟悉各名词、术语的含义，掌握基本概念。基本概念。2. 理解算法五个要素的确切含义。理解算法五个要素的确切含义。本章学习要点本章学习要点3. 掌握估算算法时间复杂度和空间掌握估算算法时间复杂度和空间复杂度的方法。复杂度的方法。作业：课后习题：P14 第一题、第二题和第四题。58谢 谢！
