《数据结构教程》第1章绪论.ppt

《《数据结构教程》第1章绪论.ppt》由会员分享，可在线阅读，更多相关《《数据结构教程》第1章绪论.ppt（78页珍藏版）》请在金锄头文库上搜索。

1、第第1章章绪论绪论 1.2算法及其描述算法及其描述 1.1什么是数据结构什么是数据结构1.3算法分析算法分析 本章小结本章小结1.4数据结构算法程序数据结构算法程序 1.1.1 1.1.1 数据结构的定义数据结构的定义1.1.2 1.1.2 逻辑结构类型逻辑结构类型 1.1.3 1.1.3 存储结构类型存储结构类型1.1.4 1.1.4 数据结构和数据类型数据结构和数据类型 1.1 1.1 什么是数据结构什么是数据结构数据数据：是所有能被输入到计算机中是所有能被输入到计算机中, ,且能被计算且能被计算机处理的符号的集合。它是计算机操作的对象的总机处理的符号的集合。它是计算机操作的对象的总称称,

2、 ,也是计算机处理的信息的某种特定的符号表示也是计算机处理的信息的某种特定的符号表示形式。形式。 数据元素数据元素：是数据：是数据(集合集合)中的一个中的一个“个体个体”,是数是数据的基本单位。据的基本单位。 1.1.1 1.1.1 数据结构的定义数据结构的定义数据对象数据对象：是具有相同性质的若干个数据元素的：是具有相同性质的若干个数据元素的集合。集合。 例如例如,200402班为一个学生数据对象班为一个学生数据对象,而其中的而其中的“张三张三”是一个数据元素是一个数据元素)。 数据结构：是指数据结构：是指数据数据以及数据元素相互之间的以及数据元素相互之间的联系联系。可以看作是相互之间存在着

3、某种特定关系的数据元素可以看作是相互之间存在着某种特定关系的数据元素的集合。的集合。因此因此,可时把数据结构看成是带结构的数据元素的可时把数据结构看成是带结构的数据元素的集合。集合。数据结构包括如下几个方面：数据结构包括如下几个方面：(1)数数据据元元素素之之间间的的逻逻辑辑关关系系,即即数数据据的的逻逻辑辑结结构。构。(2)数数据据元元素素及及其其关关系系在在计计算算机机存存储储器器中中的的存存储储方式方式,即数据的存储结构即数据的存储结构,也称为数据的物理结构。也称为数据的物理结构。(3)施加在该数据上的操作施加在该数据上的操作,即数据的运算即数据的运算。 例例1.1有有一一个个学学生生表

4、表如如表表1.1所所示示。这这个个表表中中的的数数据据元元素素是是学学生生记记录录,每每个个数数据据元元素素由由四四个个数数据项据项(即学号、姓别、性别和班号即学号、姓别、性别和班号)组成。组成。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1学生表学生表 该该表表中中的的记记录录顺顺序序反反映映了了数数据据元元素素之之间间的的逻逻辑辑关关系系, , 用学号标识每个学生记录用学号标识每个学生记录, ,这种逻辑关系可以表示为：这种逻辑关系可以

5、表示为： , 其其中中尖尖括括号号“”表表示示元元素素ai和和ai+1之之间间是是相相邻邻的的,即即ai在在ai+1之前之前,ai+1在在ai之后。之后。数数据据在在计计算算机机存存储储器器中中的的存存储储方方式式就就是是存存储储结构结构。C/C+语语言言中中，通通常常采采用用结结构构体体数数组组和和链链表表两两种方式实现其存储结构。种方式实现其存储结构。存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为：structintno;/*存储学号存储学号*/charname8;/*存储姓名存储姓名*/charsex2;/*存储性别存储性别*/charclass4;/*存储班号存储班

6、号*/Stud7=1,“张斌张斌”,“男男”,“9901”,5,王萍王萍,女女,9901;结构体数组结构体数组Stud各元素在内存中顺序存放各元素在内存中顺序存放,即即第第i(1i6)个学生对应的元素个学生对应的元素Studi存放在第存放在第i+1个学生对应的元素个学生对应的元素Studi+1之前之前,Studi+1正好正好在在Studi之后。之后。9901女王萍59901男张斌张斌1Stud0Stud6Stud数组起始地址数组起始地址 存放学生表的链表的结点类型存放学生表的链表的结点类型StudType定义为：定义为：typedefstructstudnodeintno;/*存储学号存储学号

7、*/charname8;/*存储姓名存储姓名*/charsex2;/*存储性别存储性别*/charclass4;/*存储班号存储班号*/structstudnode*next;/*存存储储指指向向下下一一个个学学生生的的指指针针*/StudType；链表首链表首结点地址结点地址headhead1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901 学生表构成的链学生表构成的链表如右图所示。其表如右图所示。其中的中的head为第一个为第一个数据元素的指针。数据元素的指针。 学

8、生表构成的链表学生表构成的链表 对对于于“学学生生表表”这这种种数数据据结结构构, ,可可以以进进行行一一系系列列的的运运算算, ,例例如如, ,增增加加一一个个学学生生记记录录、删删除除一一个个学学生生记记录录、查查找找性性别别为为“女女”的的学学生生记记录录、查查找找班班号号为为“9902”9902”的学生记录等等。的学生记录等等。 从从前前面面介介绍绍的的两两种种存存储储结结构构看看到到, ,同同样样的的运运算算, ,在在不同的存储结构中不同的存储结构中, ,其实现过程是不同的。其实现过程是不同的。 例如例如,查找学号为查找学号为20的学生的姓名的学生的姓名：对对 于于 Stud数数 组

9、组 ,可可 以以 从从 Stud0开开 始始 比比 较较,Stud0.no不不等等于于20,再再与与Stud1.no比比较较,直直到到Stud3.no等于等于20,返回返回Stud3.name。对对于于head为为首首结结点点指指针针的的链链表表,从从head所所指指结结点点开开始始比比较较,head-no不不等等于于20,从从它它的的next得得到到下下一一个个结结点点的的地地址址,再再与与下下一一个个结结点点的的no域域比比较较,直直到到某某结结点的点的no域等于域等于20,返回其返回其name域域。 为为了了更更确确切切地地描描述述一一种种数数据据结结构构,通通常常采采用用二二元组表示：

10、元组表示：B=(K,R)其中其中,B是一种数据结构是一种数据结构,它由数据元素的集合它由数据元素的集合K和和K上二元关系的集合上二元关系的集合R所组成。其中：所组成。其中：K=ki|1in,n0R=rj|1jm,m0 逻辑结构的描述或表示：逻辑结构的描述或表示： 其中：其中：ki表示集合表示集合K中的第中的第i个结点或数据元素。个结点或数据元素。n为为K中中结结点点的的个个数数,特特别别地地,若若n=0,则则K是是一一个个空空集集,因因而而B也也就就无无结结构构可可言言,有有时时也也可可以以认认为为它它具具有任一结构。有任一结构。rj表表示示集集合合R中中的的第第j个个二二元元关关系系(后后面

11、面均均简简称称关关系系)。m为为R中中关关系系的的个个数数,特特别别地地,若若m=0,则则R是是一一个个空空集集,表表明明集集合合K中中的的元元结结点点间间不不存存在在任任何何关关系系,彼彼此是独立的。此是独立的。序偶序偶(x,yK)x为第一结点为第一结点,y为第二结点。为第二结点。x为为y的的直接前驱结点直接前驱结点(通常简称通常简称前驱结点前驱结点)y为为x的的直接后继结点直接后继结点(通常简称通常简称后继结点后继结点)。若若某某个个结结点点没没有有前前驱驱结结点点,则则称称该该结结点点为为开开始始结结点点；若某个结点没有后继结点若某个结点没有后继结点,则称该结点为则称该结点为终端结点终端

12、结点。说明：说明：表示有向关系，表示有向关系，(x,y)表示无表示无向关系。采用离散数学的表示方法。向关系。采用离散数学的表示方法。 例如例如,采用二元组表示例采用二元组表示例1.1的学生表。的学生表。学学生生表表中中共共有有7个个结结点点,依依次次用用k1k7表表示示,则则对对应应的二元组表示为的二元组表示为B=(K,R),其中：其中：K=k1,k2,k3,k4,k5,k6,k7R=r/只有一种关系只有一种关系r=,又又例如例如, ,有如下数据即一个矩阵：有如下数据即一个矩阵： 对应的二元组表示为对应的二元组表示为B=(K,R),其中：其中：K=2,6,3,1,8,12,7,4,5,10,9

13、,11R=r1,r2其中其中,r1表示行关系表示行关系,r2表示列关系表示列关系r1=,r2=,一个二维数组一个二维数组 可以可以利用图形形象地表示逻辑结构。利用图形形象地表示逻辑结构。 例如，上述例如，上述“学生表学生表”数据结构用下图的图形表数据结构用下图的图形表示。示。学生表数据结构图示学生表数据结构图示 (1)线性结构线性结构 结点之间关系：结点之间关系：一对一。一对一。 特特点点：开开始始结结点点和和终终端端结结点点都都是是惟惟一一的的, ,除除了了开开始始结结点点和和终终端端结结点点以以外外, ,其其余余结结点点都都有有且且仅仅有有一一个个前前驱驱结结点点, ,有有且且仅仅有有一一

14、个个后后继继结结点点。顺顺序序表表就就是是典典型型的的线线性性结结构。构。1.1.2 1.1.2 逻辑结构类型逻辑结构类型 (2)树形结构树形结构 结点之间关系：结点之间关系：一对多。一对多。 特特点点：开开始始结结点点惟惟一一, ,终终端端结结点点不不惟惟一一。除除终终端端结结点点以以外外, ,每每个个结结点点有有一一个个或或多多个个后后续续结结点点；除除开开始始结结点点外外，每每个个结结点点有有且且仅仅有有一一个个前前驱结点。驱结点。 (3)图形结构图形结构 结点之间关系：结点之间关系：多对多。多对多。 特特点点：没没有有开开始始结结点点和和终终端端结结点点，所所有有结结点都可能有多个前驱

15、结点和多个后继结点。点都可能有多个前驱结点和多个后继结点。(2)链式存储方法链式存储方法(3)索引存储方法索引存储方法(4)散列存储方散列存储方法法1.1.3 1.1.3 存储结构类型存储结构类型(1)顺序存储方法顺序存储方法(1)数据类型数据类型高级程序语言中高级程序语言中,一般须对程序中出现的每个变量、一般须对程序中出现的每个变量、常量或表达式常量或表达式,明确说明它们所属的数据类型。不同明确说明它们所属的数据类型。不同类型的变量类型的变量,其所能取的值的范围不同其所能取的值的范围不同,所能进行的所能进行的操作不同。操作不同。数据类型数据类型是一个值的集合和定义在此集合上的一是一个值的集合

16、和定义在此集合上的一组操作的总称。组操作的总称。1.1.4 1.1.4 数据结构和数据类型数据结构和数据类型 如如C/C+中的中的int就是整型数据类型。它是所有整就是整型数据类型。它是所有整数的集合数的集合(在在16位计算机中为位计算机中为3276832767的全体整的全体整数数)和相关的整数运算和相关的整数运算(如、等如、等)。 (2)抽象数据类型抽象数据类型抽象数据类型抽象数据类型(AbstractDataType简写为简写为ADT)指的是用户进行软件系统设计时从问题的数学模型指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运中抽象出来的逻辑数据结构

17、和逻辑数据结构上的运算算,而不考虑计算机的具体存储结构和运算的具体实而不考虑计算机的具体存储结构和运算的具体实现算法。现算法。抽象数据类型抽象数据类型=数据元素集合抽象运算数据元素集合抽象运算例如例如,抽象数据类型抽象数据类型复数复数的定义：的定义：ADTComplex数据对象：数据对象：D=e1,e2|e1,e2均为实数均为实数数据关系：数据关系：R1=|e1是是复复数数的的实实数数部部分分,e2是是复复数数的的虚数部分虚数部分e1e2i基本操作：基本操作：AssignComplex(&Z,v1,v2)：构造复数构造复数Z。DestroyComplex(&Z):复数复数Z被销毁。被销毁。Ge

18、tReal(Z,&real):返回复数返回复数Z的实部值。的实部值。GetImag(Z,&Imag):返回复数返回复数Z的虚部值。的虚部值。Add(z1,z2,&sum):返回两个复数返回两个复数z1,z2的和。的和。ADTComplex1.2 1.2 算法及其描述算法及其描述 1.2.1什么是算法什么是算法 1.2.2算法描述算法描述1.2.1 1.2.1 什么是算法什么是算法 数据元素之间的关系有逻辑关系和物理关系数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。结构上的操作实现。通常把具体存储结构

19、上的操作实现步骤或过程通常把具体存储结构上的操作实现步骤或过程称为称为算法算法。算法的五个重要的特性算法的五个重要的特性 (1)有穷性有穷性:在有穷步之后结束。在有穷步之后结束。(2)确定性确定性:无二义性。无二义性。 (3)可行性可行性:可通过基本运算有限次执行来实可通过基本运算有限次执行来实现。现。(4)有输入有输入 (5)有输出有输出 例例1.2考虑下列两段描述：考虑下列两段描述：(1)描述一描述一voidexam1()n2;while(n%20)nn+2;printf(%dn,n);华中科大考研题华中科大考研题(2)描述二描述二voidexam2()y=0;x=5/y;printf(“

20、%d,%dn”,x,y);这这两两段段描描述述均均不不能能满满足足算算法法的的特特征征,试试问问它它们们违反了哪些特征？违反了哪些特征？ 解解：(1)算算法法是是一一个个死死循循环环,违违反反了了算算法法的的有有穷性特征。穷性特征。(2)算算法法包包含含除除零零错错误误,违违反反了了算算法法的的可可行行性性特特征。征。1.2.2 1.2.2 算法描述算法描述 本书中采用本书中采用C/C+C/C+语言描述算法。语言描述算法。说明：说明：C+语言中提供了一种语言中提供了一种引用引用运算符运算符“&”,引用是个别名引用是个别名,当建立引用时当建立引用时,程序用另一程序用另一个已定义的变量或对象个已定

21、义的变量或对象(目标目标)的名字初始化它的名字初始化它,从那时起从那时起,引用作为目标的别名而使用引用作为目标的别名而使用,对引用的对引用的改动实际就是对目标的改动。改动实际就是对目标的改动。注意：注意：TurboC不支持引用类型。不支持引用类型。编写一个函数编写一个函数swap1(x,y)，当执行语句，当执行语句swap1(a,b)时时,交换交换a和和b的值。的值。voidswap1(intx,inty)inttmp;tmp=x;x=y;y=tmp;注意：注意：a a和和b b的值不会发生了交换。的值不会发生了交换。为此，采用指针的方式来回传形参的值，需将上为此，采用指针的方式来回传形参的值

22、，需将上述函数改为：述函数改为：intswap2(int*x,int*y)inttmp;tmp=*x;/*将将x的值放在的值放在tmp中中*/*x=*y;/*将将x所指的值改为所指的值改为*y*/*y=tmp；/*将将y所指的值改为所指的值改为tmp*/上述函数的调用改为上述函数的调用改为swap2(&a,&b)，显然远不显然远不如采用引用方式简洁。所以本书后面很多算法都采如采用引用方式简洁。所以本书后面很多算法都采用引用形参。用引用形参。引入引入“引用引用”的概念的概念例如：例如：inta=4; /*a为普通的整型变量为普通的整型变量*/int&b=a;/*b是是a的引用变量的引用变量*/这

23、这里里说说明明b变变量量是是变变量量a的的引引用用,b也也等等于于4,之之后后这这两两个个变变量量同同步步改改变变。当当a改改变变时时b也也同同步步改改变变，同样，当同样，当b改变时改变时a也同步改变。也同步改变。难点难点main()inta=2;int&b=a;printf(a=%d,b=%dn,a,b);/*输出：输出：a=2,b=2*/b+;printf(a=%d,b=%dn,a,b);/*输出：输出：a=3,b=3*/a+;printf(a=%d,b=%dn,a,b);/*输出：输出：a=4,b=4*/引引用用常常用用于于函函数数形形参参中中,采采用用引引用用型型形形参参时时,在在函函

24、数数调调用用时时将将形形参参的的改改变变回回传传给给实实参参,例例如如,有有如如下下函函数数(其中的形参均为引用型形参其中的形参均为引用型形参)：voidswap(int&x,int&y)/*形参前的形参前的“&”符号不是指针运算符符号不是指针运算符*/inttmp=x;x=y;y=tmp当用执行语句当用执行语句swap(a,b)时时,a和和b的值发生了交换。的值发生了交换。 例例1.3编编写写一一个个算算法法,读读入入三三个个整整数数x,y和和z的的值值,要要求从大到小输出这三个数。求从大到小输出这三个数。解解：依依次次输输入入x,y和和z这这三三个个整整数数,通通过过比比较较交交换换后后,

25、使得使得xyz,然后输出然后输出x,y,z。在在算算法法中中应应考考虑虑对对这这三三个个元元素素作作尽尽可可能能少少的的比比较较和和移移动动,如如下下述述算算法法在在最最坏坏的的情情况况下下只只需需进进行行3次次比比较较和和7次移动。次移动。voidDescending()printf(输入输入x,y,z);scanf(%d,%d,%d,&x,&y,&z);if(x=y*/if(yz*/if(x=temp)y=temp；elsey=x;x=temp;printf(%d,%d,%dn,x,y,z);1.3 1.3 算法分析算法分析 1.3.1算法时间复杂度分析算法时间复杂度分析 1.3.2算法空

26、间复杂度分析算法空间复杂度分析 一一个个算算法法是是由由控控制制结结构构(顺顺序序、分分支支和和循循环环三三种种)和和原原操操作作(指指固固有有数数据据类类型型的的操操作作)构构成成的的,则算法时间取决于两者的综合效果。则算法时间取决于两者的综合效果。1.3.1 1.3.1 算法时间复杂度分析算法时间复杂度分析 控制语句控制语句1原操作原操作控制语句控制语句n原操作原操作一个算法一个算法同同一一问问题题可可以以采采用用多多种种算算法法实实现现。如如何何比较算法执行效率？比较算法执行效率？算法描述的语言不同算法描述的语言不同算法执行的环境不同算法执行的环境不同 其他因素其他因素 所以不能用绝对执

27、行时间进行比较所以不能用绝对执行时间进行比较为为了了便便于于比比较较同同一一问问题题的的不不同同算算法法,通通常常从从算算法法中中选选取取一一种种对对于于所所研研究究的的问问题题来来说说是是基基本本运运算算的的原原操操作作(以以下下将将基基本本运运算算的的原原操操作作简简称称为为基基本本运算运算)。算算法法执执行行时时间间大大致致为为基基本本运运算算所所需需的的时时间间与与其运算次数其运算次数(也称为频度也称为频度)的乘积。的乘积。被被视视为为算算法法基基本本运运算算的的一一般般是是最最深深层层循循环环内内的语句。的语句。 在在一一个个算算法法中中, ,进进行行基基本本运运算算的的次次数数越越

28、少少, ,其其运运行行时时间间也也就就相相对对地地越越少少；基基本本运运算算次次数数越越多多, ,其其运运行行时时间也就相对地越多。间也就相对地越多。 所所以以, ,通通常常把把算算法法中中包包含含基基本本运运算算次次数数的的多多少少称称为为算算法法的的时时间间复复杂杂度度, ,也也就就是是说说, ,一一个个算算法法的的时时间间复复杂杂度是指该算法的基本运算次数度是指该算法的基本运算次数。 算法中算法中基本运算次数基本运算次数T(n)是问题规模是问题规模n的某个函数的某个函数f(n),记作记作：T(n)=O(f(n) 记记号号“O”读读作作“大大O”,它它表表示示随随问问题题规规模模n的的增增

29、大大算算法法执执行行时时间间的的增增长长率率和和f(n)的的增增长长率率相相同同。“O”的形式定义为：的形式定义为：若若f(n)是是正正整整数数n的的一一个个函函数数,则则T(n)=O(f(n)表表示示存在一个正的常数存在一个正的常数M,使得当使得当nn0时都满足：时都满足：|T(n)|M|f(n)|也就是只求出也就是只求出T(n)的最高阶的最高阶,忽略其低忽略其低阶项和常系数阶项和常系数,这样既可简化这样既可简化T(n)的计算的计算,又又能比较客观地反映出当能比较客观地反映出当n很大时很大时,算法的时间算法的时间性能。性能。例如例如,T(n)=3n2-5n+10000=O(n2)本质上讲，是

30、一种本质上讲，是一种最高数量级的比较最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模一个没有循环的算法的基本运算次数与问题规模n无关无关,记作记作O(1),也称作也称作常数阶常数阶。一个只有一重循环的算法的基本运算次数与问题一个只有一重循环的算法的基本运算次数与问题规模规模n的增长呈线性增大关系的增长呈线性增大关系,记作记作O(n),也称也称线性阶线性阶。其余常用的还有平方阶其余常用的还有平方阶O(n2)、立方阶立方阶O(n3)、对对数阶数阶O(log2n)、指数阶指数阶O(2n)等。等。 各种不同数量级对应的值存在着如下关系：各种不同数量级对应的值存在着如下关系：O(1)O(lo

31、g2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)例例1.4求求两两个个n阶阶方方阵阵的的相相加加C=A+B的的算算法法如下如下,分析其时间复杂度。分析其时间复杂度。#defineMAX20/*定义最大的方阶定义最大的方阶*/voidmatrixadd(intn,intAMAXMAX,intBMAXMAX,intCMAXMAX)inti,j;for(i=0;in;i+)for(j=0;jn;j+)Cij=Aij+Bij; 该该算算法法中中的的基基本本运运算算是是两两重重循循环环中中最最深深层层的的语语句句Cij=Aij+Bij,分析它的频度分析它的频度,即即：T(n)

32、=O(n2)例例1.5分析以下算法的时间复杂度。分析以下算法的时间复杂度。intfun(intn)inti,j,k,s;s=0;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;k=j;k+)s+;return(s);基本语句或基本操作基本语句或基本操作 解：解：该算法的基本操作是语句该算法的基本操作是语句s+,其频度：其频度：T(n)=O(n3)则该算法的时间复杂度为则该算法的时间复杂度为O(n3)。例例1.6分析以下算法的时间复杂度。分析以下算法的时间复杂度。voidfunc(intn)inti=0,s=0;while(sn)i+;s=s+i;基本语句基本语句解：

33、对于解：对于while循环语句，设执行的次数为循环语句，设执行的次数为m，i从从0开始递增开始递增1，直到，直到m为止，有：为止，有：s=0+1+2+m-1=m(m-1)/2，并满足并满足s=m(m-1)/2n，则有则有m。T(n)=O()所以，该算法的时间复杂度为所以，该算法的时间复杂度为O()。例例1.7有如下算法：有如下算法：voidfun(inta,intn,intk)/*数组数组a共有共有n个元素个元素*/inti;if(k=n-1)for(i=0;in;i+)printf(%dn,ai);elsefor(i=k;in;i+)ai=ai+i*i;fun(a,n,k+1);调用上述算法

34、的语句为调用上述算法的语句为fun(a,n,0)，求其时间复杂度。求其时间复杂度。解解：设设fun(a,n,0)的的时时间间复复杂杂度度为为T(n),fun(a,n,k)的执行时间为的执行时间为T1(n,k)，由，由fun()算法可知：算法可知：T1(n,k)=n当当k=n-1时时T1(n,k)=(n-k)+T1(n,k+1)其他情况其他情况则则T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)+2+n=O(n2)所以调用所以调用fun(a,n,0)的时间复杂度为的时间复杂度为O(n2)。空间复杂度是对一个算法在

35、运行过程中空间复杂度是对一个算法在运行过程中临时占用的临时占用的存储空间存储空间大小的量度大小的量度,一般也作为问题规模一般也作为问题规模n的函数的函数,以以数量级形式给出数量级形式给出,记作：记作：S(n)=O(g(n)若若所所需需额额外外空空间间相相对对于于输输入入数数据据量量来来说说是是常常数数,则则称称此此算算法法为为原原地地工工作作。若若所所需需存存储储量量依依赖赖于于特特定定的的输输入入,则通常按最坏情况考虑。则通常按最坏情况考虑。1.3.2 1.3.2 算法空间复杂度分析算法空间复杂度分析 返回返回 例例1.8分析例分析例1.4和例和例1.5的空间复杂度。的空间复杂度。解：由于这

36、两个算法中临时变量的个数与问解：由于这两个算法中临时变量的个数与问题规模题规模n无关无关,所以空间复杂度均为所以空间复杂度均为O(1)。1.4数据结构算法程序数据结构算法程序 数据结构对算法的影响主要在两方面数据结构对算法的影响主要在两方面 （1 1）数据结构的存储能力）数据结构的存储能力数据结构存储能力强、存储信息多算法将数据结构存储能力强、存储信息多算法将会较好设计（时间少），存储空间大。会较好设计（时间少），存储空间大。时间和空间的平衡时间和空间的平衡（2 2）定义在数据结构上的操作）定义在数据结构上的操作在数据结构上定义基本操作算法调用这些在数据结构上定义基本操作算法调用这些基本操作。

37、基本操作。基本操作越完整，基本操作越完整，算法设计就越容算法设计就越容易易算法算法基本操作基本操作基本算法基本算法应用程序应用程序应用程序是通过应用程序是通过调用基本算法实调用基本算法实现的现的选择数据结构需要考虑的几个方面：选择数据结构需要考虑的几个方面：（1 1）数据结构要适应问题的状态描述）数据结构要适应问题的状态描述（2 2）数据结构应与所选择的算法相适应）数据结构应与所选择的算法相适应（3 3）数据结构的选择同时要兼顾程序设计的方便）数据结构的选择同时要兼顾程序设计的方便（4 4）灵活应用已有知识）灵活应用已有知识例如，有若干学生数据（学生数小于例如，有若干学生数据（学生数小于50）

38、，每个学生数据包含学号（每个学生学），每个学生数据包含学号（每个学生学号是惟一的，但学生记录不一定按学号顺序号是惟一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超个学生所选课程数目可能不等，但最多不超过过6门）。门）。要求设计一个程序输出每个学生的学号、要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从姓名和平均分以及每门课程（课程编号从16）的平均分。）的平均分。设计方案设计方案1 1：将学生的全部数据项放在一个表将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记

39、录。由于课中，一个学生的全部数据对应一条记录。由于课程最多可选程最多可选6 6门，对应的成绩项也应有门，对应的成绩项也应有6 6个。对应个。对应的数据结构如下：的数据结构如下：structstud intno;/*学号学号*/charname10;/*姓名姓名*/intbno;/*班号班号*/intdeg1;/*课程课程1分数分数*/intdeg2;/*课程课程2分数分数*/intdeg3;/*课程课程3分数分数*/intdeg4;/*课程课程4分数分数*/intdeg5;/*课程课程5分数分数*/intdeg6;/*课程课程6分数分数*/;nonamebnodeg1deg2deg3deg4d

40、eg5deg61张斌斌99017882639285838刘刘丽9902659572788079特点：特点：存储空间：中（若学生没有选该课程，对应空间仍存在）存储空间：中（若学生没有选该课程，对应空间仍存在）算法时间：少算法时间：少算法简洁性差：算法完全依赖数据结构算法简洁性差：算法完全依赖数据结构设计方案设计方案2 2：将学生的全部数据项放在一个表：将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：需增加

41、一个课程编号项。对应的数据结构如下：structstud intno;/*学号学号*/charname10;/*姓名姓名*/intbno;/*班号班号*/intcno;/*课程编号课程编号*/intdeg;/*课程分数课程分数*/;nonamebnocnodeg1张斌斌99011781张斌斌99012821张斌斌99013631张斌斌99014921张斌斌99015851张斌斌99016838刘刘丽99021658刘刘丽99022958刘刘丽99023728刘刘丽99024788刘刘丽99025808刘刘丽9902679特点：特点：存储空间：大存储空间：大算法时间：多算法时间：多算法简洁性：好

42、算法简洁性：好设计方案设计方案3 3：将学生的学号、姓名和班号放在将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如一门课程成绩对应一条记录。对应的数据结构如下：下：structstud1 intno;/*学号学号*/charname10;/*姓名姓名*/intbno;/*班号班号*/;structstud2 intno;/*学号学号*/intcno;/*课程编号课程编号*/intdeg;/*分数分数*/;n

43、onamebno1张斌斌99018刘刘丽9902nocnodeg117812821363149215851683816582958372847885808679特点：特点：存储空间：少存储空间：少算法时间：中算法时间：中算法简洁性：好算法简洁性：好最佳方案最佳方案数据结构数据结构算法算法数据类型数据类型ijk求解问题编写程序的代码：求解问题编写程序的代码：ijk种种优优选选最佳方案最佳方案本课程的目标本课程的目标本章小结本章小结 本章介绍了数据结构的基本概念本章介绍了数据结构的基本概念,主要学习要点主要学习要点如下：如下：(1)数数据据结结构构的的定定义义,数数据据结结构构包包含含的的逻逻辑辑结结构构、存储结构和运算三方面的相互关系。存储结构和运算三方面的相互关系。(2)各各种种逻逻辑辑结结构构即即线线性性结结构构、树树形形结结构构和和图图形形结构之间的差别。结构之间的差别。 (3)数据结构和数据类型的差别和联系。数据结构和数据类型的差别和联系。(4)算法的定义及其特性。算法的定义及其特性。(5)算法的时间复杂度和空间复杂度分析。算法的时间复杂度和空间复杂度分析。 练习题练习题1：习题习题3、习题、习题5和习题和习题6。上机题：上机题：熟悉熟悉VC+6.0环境环境