绪论知识要点和习题分析ppt课件

1、第1章 绪论知识要点与习题分析数据的有关概念：数据；数据项；数据元素；数据的有关概念：数据；数据项；数据元素；数据类型；抽象数据类型；数据表示；数据对数据类型；抽象数据类型；数据表示；数据对象等要搞清楚。象等要搞清楚。数据结构的有关概念：数据结构数据结构的有关概念：数据结构(数据结构是指数据结构是指相互之间存在一种或多种特定关系的数据元素相互之间存在一种或多种特定关系的数据元素所组成的集合所组成的集合)；数据逻辑结构；数据物理结构；数据逻辑结构；数据物理结构存储结构线性结构；非线性结构等。存储结构线性结构；非线性结构等。抽象数据类型：是数据类型的引申，是抽象数据类型：是数据类型的引申，是由一组

2、数据及施加其上的操作集合所形由一组数据及施加其上的操作集合所形成的数据模板。简单地理解为：数据结成的数据模板。简单地理解为：数据结构构+ +操作集合。操作集合。抽象数据类型的引入优点：既可描述数抽象数据类型的引入优点：既可描述数据逻辑结构的说明和运算的定义，突出据逻辑结构的说明和运算的定义，突出在某种关系的数据对象上做什么；又可在某种关系的数据对象上做什么；又可描述计算机中如何存储数据和实现定义描述计算机中如何存储数据和实现定义的运算，解决怎样做的问题。的运算，解决怎样做的问题。逻辑结构与存储结构：从逻辑结构上来逻辑结构与存储结构：从逻辑结构上来分，有集合结构、线性结构、树形结构分，有集合结构

3、、线性结构、树形结构和图形结构网状结构四种。从存储和图形结构网状结构四种。从存储结构来分，有顺序存储、链式存储、索结构来分，有顺序存储、链式存储、索引存储和散列存储四种。引存储和散列存储四种。逻辑结构特点：集合中数据元素之间逻辑结构特点：集合中数据元素之间不存在关系，线性结构的数据元素之不存在关系，线性结构的数据元素之间存在一对一的线性关系，树形结构间存在一对一的线性关系，树形结构的数据元素之间存在一对多的非线性的数据元素之间存在一对多的非线性关系，图形结构的数据元素之间多对关系，图形结构的数据元素之间多对多的非线性关系。多的非线性关系。存储结构：顺序存储结构：使用一片地存储结构：顺序存储结构

4、：使用一片地址连续的存储单元依此存放逻辑上相邻址连续的存储单元依此存放逻辑上相邻的结点；相当于的结点；相当于CC语言中的一维数组存语言中的一维数组存储；链式存储则是使用地址不一定连续储；链式存储则是使用地址不一定连续的存储单元存放数据元素，但数据元素的存储单元存放数据元素，但数据元素之间的逻辑关系用指针来表示。之间的逻辑关系用指针来表示。算法：是对特定问题求解步骤的一种描算法：是对特定问题求解步骤的一种描述；它是指令的有限序列，其中一条指述；它是指令的有限序列，其中一条指令表示一个或者多个操作。令表示一个或者多个操作。算法的基本特征：有穷性，确定性，可算法的基本特征：有穷性，确定性，可行性，输

5、入性和输出性。行性，输入性和输出性。算法的设计要求：正确性，易读性、健算法的设计要求：正确性，易读性、健壮性、时空效率。壮性、时空效率。算法的有关概念算法的有关概念时间复杂度计算时间复杂度计算方法：方法： 事后统计法和事前分析估算法；事后统计法和事前分析估算法；计算思想：语句频度：语句的重复执行次数计算思想：语句频度：语句的重复执行次数称为语句频度，记作称为语句频度，记作f(n)f(n)，也称之为时间频，也称之为时间频度。度。时间复杂度，记作时间复杂度，记作T(n)T(n)：T(n)=O(f(n)T(n)=O(f(n)空间复杂度：算法对存储空间的占用度量。空间复杂度：算法对存储空间的占用度量。

6、典型例题分析典型例题分析例例1 1 设有如图所示的数据逻辑结构图，试给出其数据结构表示。设有如图所示的数据逻辑结构图，试给出其数据结构表示。abdcef解：数据结构定义解：数据结构定义S=S=（K K，R R），），其中：其中：K=a,b,c,d,e,fK=a,b,c,d,e,fR=(a,b),(b,e),(a,d),(d,c),(c,e),R=(a,b),(b,e),(a,d),(d,c),(c,e),(c,f),(d,f)(c,f),(d,f)例例2 设数据结构设数据结构S=（K，R），），K=k1,k2,k3, ,k9R=, , , 画出这个逻辑结构的图示，并确定哪些结点为开始结点？哪些

7、是画出这个逻辑结构的图示，并确定哪些结点为开始结点？哪些是终端结点？解释终端结点？解释S是什么结构？是什么结构？k2k6k3k5k8k7k4k1k9解：解：k1k1为开始结点无前驱），为开始结点无前驱）， k2,k9,k7,k5k2,k9,k7,k5为终端结点无后为终端结点无后继），继），S S为树形结构。为树形结构。算法典型题分析：算法典型题分析：例例1 1 讨论矩阵相乘算法的时间复杂度讨论矩阵相乘算法的时间复杂度nxnnxn矩阵相乘算法的为矩阵相乘算法的为: :for (i=1;i=n;+i) for (i=1;i=n;+i) for(j=1;j=n;+j) for(j=1;j=n;+j)

8、 cij=0; cij=0; for(k=1;k=n;+k) for(k=1;k=n;+k) cij+=aik cij+=aik* *bkj; /bkj; /留意：这个语句为基本语句留意：这个语句为基本语句 因为基本语句的重复执行次数为因为基本语句的重复执行次数为n3n3，即频度，即频度f(n)=n3f(n)=n3，所以有，所以有算法时间复杂度为：算法时间复杂度为： T(n)=O(n3) / T(n)=O(n3) /即时间的增长率与语句频度即时间的增长率与语句频度n3n3增长率相同增长率相同. .例例2 2 判断下列算法的时间复杂度判断下列算法的时间复杂度int s=0;int s=0;for

9、 (i=1;i=n;+i) for (i=1;i=n;+i) for(j=1;j=m;+j) for(j=1;j=m;+j) for(k=1;k=q;+k) for(k=1;k=q;+k) s+; / s+; /留意：这个语句为基本语句留意：这个语句为基本语句 因为基本语句的重复执行次数为因为基本语句的重复执行次数为nxmxqnxmxq，即频度，即频度f(n)=mxnxqf(n)=mxnxq，所以有算法时间复杂度为：，所以有算法时间复杂度为： T(n)=O(nxmxq) T(n)=O(nxmxq) 例例3 3 以以+x+x为基本语句讨论下述三个程序段的时间复杂度为基本语句讨论下述三个程序段的时

10、间复杂度 1 1）+x+x；+x+x；+x+x；s=0s=0； 2 2for (i=1;i=n;+i) +xfor (i=1;i=n;+i) +x；s+=xs+=x； 3 3for(j=1;j=n;+j) for(j=1;j=n;+j) for(k=1;k=n;+k) +x for(k=1;k=n;+k) +x；s+=xs+=x； 因为频度分别为：因为频度分别为：3 3，n n和和n2n2。则三段程序的时间复杂度分。则三段程序的时间复杂度分别为：别为：O(1)O(1)，O(n)O(n)，O(n2)O(n2)。例例4 4 求下列算法段的基本语句频度求下列算法段的基本语句频度 for(i=1; i

11、=n; i+) for(i=1; i=n; i+) for(j =1; j =i ; j+) for(j =1; j =i ; j+) x=x+1; x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数与外循环有关，显然，时间频度数相乘，但内循环次数与外循环有关，显然，时间频度 f(n)=1+2+3+n= n(n+1)/2 f(n)=1+2+3+n= n(n+1)/2则时间复杂度为：则时间复杂度为：T(n)=O(n2) T(n)=O(n2) 。为简单起见，时间复杂度。为简单起见，时间复杂度一般取为基本语句频度表达式

12、中同阶增长最快的项。一般取为基本语句频度表达式中同阶增长最快的项。例例5 5 分析下列算法程序段的时间复杂度分析下列算法程序段的时间复杂度 for (i=1;i=n;i+) for (i=1;i=n;i+) for(j=1;j=i;j+) for(j=1;j=i;j+) for(k=1;k=j;k+) for(k=1;k=j;k+) x+ x+； / /基本语句基本语句解：计算见下页解：计算见下页分析算法规律可知语句频度分析算法规律可知语句频度f(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n)f(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = = = +

13、 = + = + = + = n(n+1)(n+2)/6 = n(n+1)(n+2)/6显然有：显然有：T Tn)=(n3)n)=(n3)。nkk1).321 (nkkk12)1(nkk122nkk12216)12)(1(nnn2)1(nn例例6 6 分析以下程序的复杂度分析以下程序的复杂度 i=1; i=1; while(i=n) while(i=n) i=i i=i* *2; /2; /基本语句基本语句解：设基本语句的频度为解：设基本语句的频度为f(n)f(n)，则，则2f(n)=n,2f(n)=n, 即即f(n)=log2nf(n)=log2n，取最大为，取最大为f(n)= log2nf

14、(n)= log2n T(n)=O( log2n) T(n)=O( log2n)留意：若将基本语句中的留意：若将基本语句中的2 2换作换作3 3、4 4等，会有什么结果。等，会有什么结果。例例7 7 分析下列分析下列order()order()函数的复杂度函数的复杂度 / /排序算法排序算法 int a =a1,a2,an; int a =a1,a2,an; order(int j,int n) order(int j,int n) int i,temp; int i,temp; if(jn) if(jn) for(i=j;i=n;i+) for(i=j;i=n;i+)if(aiaj) if(

15、aiaj) temp=ai; temp=ai; ai=aj; ai=aj; aj=temp; /end if aj=temp; /end ifj+;j+;order(j,n);order(j,n); / end if / end if /end order() /end order() main() main() int i; int i; order(0,n-1) / order(0,n-1) /基本语句基本语句 for(i=0;in;i+) for(i=0;i1f(n)=f(n-1)+n-1 ,n1。又由于。又由于f(1)=0f(1)=0，则递推得：则递推得： f(n)=f(n-1)+n-

16、1=f(n-2)+n-2+n-1=f(n-3)+n-3+n-2+n-1 f(n)=f(n-1)+n-1=f(n-2)+n-2+n-1=f(n-3)+n-3+n-2+n-1 =1+2+3+ +n-2+n-1=n(n-1)/2 =1+2+3+ +n-2+n-1=n(n-1)/2 T(n)=O(n2) T(n)=O(n2)类似习题类似习题1.81.8，请大家拿出作业本看看答案。，请大家拿出作业本看看答案。顺序表和链表要点总结：顺序表和链表要点总结：（1 1实现方法：顺序表是用数组实现的，数据元素的线性关系实现方法：顺序表是用数组实现的，数据元素的线性关系用相对地址的相邻来反映；而链表是用指针或用相对

17、地址的相邻来反映；而链表是用指针或“游标来实游标来实现的，即用指针将前驱结点与后继结点链在一起。现的，即用指针将前驱结点与后继结点链在一起。（2 2顺序表主要优点：随机存取，无需额外存储空间；顺序表主要优点：随机存取，无需额外存储空间；（3 3顺序表主要缺点：插入、删除运算不方便，移动大量的结顺序表主要缺点：插入、删除运算不方便，移动大量的结点；表长变化较大时间，不容易分配空间，要么不够用，点；表长变化较大时间，不容易分配空间，要么不够用，要么浪费空间；要么浪费空间；（4 4时间复杂度：插入、删除为时间复杂度：插入、删除为OOn n）第第2 2章章 线性表小结与要点分析线性表小结与要点分析顺序

18、表和链表要点总结：顺序表和链表要点总结：（1 1链表主要优点：存储空间按需动态分配；插入、删除等链表主要优点：存储空间按需动态分配；插入、删除等操作不需要移动数据元素。操作不需要移动数据元素。（2 2链表主要缺点：每一结点需要附加一指针域，存储密度链表主要缺点：每一结点需要附加一指针域，存储密度11；不能随机存取。；不能随机存取。（3 3存储密度存储密度 = = 结点数据本身所占的存储量结点数据本身所占的存储量/ /结点结构所占结点结构所占的存储总量。则顺序表的存储密度的存储总量。则顺序表的存储密度 = 1 = 1，链表的存储密，链表的存储密度度 1 1。（4 4时间复杂度：插入、删除为时间复

19、杂度：插入、删除为OOn n），主要用于查找。），主要用于查找。第第2 2章章 线性表小结与要点分析线性表小结与要点分析顺序表与链表适应场合比较：顺序表与链表适应场合比较：（1 1若线性表的操作主要是查找，很少涉及到插入、若线性表的操作主要是查找，很少涉及到插入、删除操作时，可采用顺序表结构；若要频繁地进行插删除操作时，可采用顺序表结构；若要频繁地进行插入和删除操作，宜采用链表作为存储结构。入和删除操作，宜采用链表作为存储结构。（2 2若线性表的长度已知且变化不大，则适宜用顺序若线性表的长度已知且变化不大，则适宜用顺序表；否则，用链表。表；否则，用链表。 ADT List 数据对象：D ai

20、| ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n 基本操作：抽象数据类型线性表的定义、表示与算法实现（1结构初始化 InitList( &L ) 操作结果：构造一个空的线性表L。（2销毁结构 DestroyList( &L )初始条件：线性表L已存在。操作结果：销毁线性表L。 ListEmpty( L )初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。 ListLength( L )初始条件：线性表L已存在。操作结果：返回L中元素个数。 NextElem( L, cur_e, &a

21、mp;next_e )初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。 PriorElem( L, cur_e, &pre_e )初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。GetElem( L, i, &e )初始条件：线性表L已存在， 1iLengthList(L)操作结果：用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) )初始条件：线性表L已存在，co

22、mpare( )是元素判定函数。操作结果：返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( ) 线性表遍历初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。 ClearList( &L )初始条件：线性表L已存在。操作结果：将L重置为空表。 PutElem( L, i, &e )初始条件：线性表L已存在，1iLengthList(L)操作结果：L中第i个元素赋值同e的值。 ListInsert( &L, i, e

23、 )初始条件：线性表L已存在，1iLengthList(L)+1操作结果：在L的第i个元素之前即第i个位置插入一新元素e，L的长度增1。 ListDelete(&L, i, &e)初始条件：线性表L已存在且非空，1iLengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。 ADT List 4 4、线性链表存储结构的表示与实现、线性链表存储结构的表示与实现typedef struct LNode typedef struct LNode ElemType data ElemType data； struct LNode struct LNode *

24、 *nextnext； LNode LNode，* *LinkListLinkList；注：注：LnodeLnode和和* *LinkListLinkList分别为结点类型和结点类型指针。分别为结点类型和结点类型指针。！生成一个链表新结点：！生成一个链表新结点：p=(LinkList )malloc(sizeof(LNode);p=(LinkList )malloc(sizeof(LNode);系统回收系统回收p p结点：结点：free(p)free(p)5、创建带头结点单链表算法：、创建带头结点单链表算法： 逆序建立带头结点的单链表算法逆序建立带头结点的单链表算法 nOnTVoid Crea

25、teLink_List(LinkList &L,int n)Void CreateLink_List(LinkList &L,int n) / /逆序创建，依次存储元素逆序创建，依次存储元素anan，an-1an-1，a1a1L=(LinkList)malloc(sizeof(LNode);L=(LinkList)malloc(sizeof(LNode);L-next=NULL;L-next=NULL;for(i=n;i0;i-) for(i=n;i0;i-) p=(LinkList)malloc(sizeof(LNode); p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); scanf(&p-data