《数据结构(C语言描述)》第1章学习数据结构的意义课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,21,世纪高等院校规划教材,数据结构（,C,语言描述）,ISDN 7-5084-3301-7,斯庆巴拉 主编,中国水利水电出版社,21世纪高等院校规划教材数据结构（C语言描述）ISDN 7,第一章 学习数据结构课程,的意义,学习重点,掌握学习本课程的意义,掌握本课程的主体框架和讨论范围,掌握如何对算法进行描述和分析,第一章 学习数据结构课程的意义学习重点,引入：,一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。,引入：,1.1,实例：高校选修课程管理,1.2,数据结构的主要内容,1.3,算法和算法分析,本章总结,1.1 实例：高校选修课程管理,1.1,实例：高校选修课程管理,1.1.1,问题描述,1.1.2,问题的分析,1.1.3,学习本课程的意义,1.1 实例：高校选修课程管理1.1.1 问题描述,1.1.1 问题描述,表,1-1,是一所学校学生选修课程的选修情况登记表。要求用计算机来完成对学生选修课程的全程管理。,通常必备的功能有,登记,，,修改,、,查询,和,打印,等。在本例中,重点完成查询功能,。,1.1.1 问题描述 表1-1是一所学校学生选修,学号,姓名,系别,选修课程名,学分,成绩,课程名,课程代码,等级,分数,0351103,王杰,计算机,摄影技术,501,3,0351212,李丽,计算机,电脑音乐,502,1,0351220,商立,计算机,摄影技术,501,3,0432233,赵燕,机械,三维动画,303,2,0432118,张欣,机械,三维动画,303,2,0322140,王芳,材料,证券投资,205,3,表,1-1 某,学校学生选修课程情况登记表,学号姓名系别选修课程名学分成绩课程名课程代码等级分数0351,1.1.2,问题的分析,利用计算机解决实际问题的步骤：,第一步：从具体问题抽象出一个适当的数据模型。,第二步：进行算法设计。,第三步：实现抽象数据类型定义，即从编程语言的角度确定抽象数据类型的存储形式和确定抽象数据类型中每一种操作的具体实现算法。,第四步：编制相应的程序代码并进行调试。,1.1.2 问题的分析 利用计算机解决实际问题的步骤：,第一步：抽象数据模型一般包括,三部分,：处理的,数据对象,、对象间的,关系,和需要实现的,操作,。,常用以下格式描述：,ADT,选修课程,数据对象：,D=a,i,| a,i,记录类型，,i=1,2,n , n0,数据关系：,R=R,i,| R,i,记录间关系，,i=1,2,m, m,0,基本操作：,DengjiList ( &L),完成功能：对学生选修情况进行登记,EditList(&L),完成功能：对选修情况登记表进行修改,LocateList(&L,查询条件,),完成功能：根据给定的查询条件，从登记表中查找满足条件的记录,PrintList(L),完成功能：打印学生选修情况登记表,ADT,选修课程,第一步：抽象数据模型一般包括三部分：处理的数据对象、对象间的,第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的,算法描述,。,下面以查询操作为例给出伪代码表示：,int LocateList(,选修课程,&,L,查询条件,),对给定的查询条件进行分析，确定是对表中哪个数据项进行查询；,对表中元素按给定的查询条件进行查询；,若查询成功，返回记录的位置；否则返回,0,值，表示表中不存在满足给定条件的记录；,第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算,第三步：确定表中的,记录的类型,（结构体），表在内存中,存储方式,（按输入顺序存放）。,具体定义如下：,struct,kechengsrtuct,/,选修课程名类型定义,char *kechengming ; /,课程名,int kechengdaima ; /,课程代码, ;,struct,chengjistruct, /,成绩类型定义,char *dengji ; /,成绩等级,int fenshu ; /,分数, ;,第三步：确定表中的记录的类型（结构体），表在内存中存储方式（,struct,student,/,表中学生记录类型定义,long int num ; /,学号,char *name ; /,姓名,char *xibie ; /,系别,kechengstruct kechent ;,int xuefen ; /,学分,chengjistruct chengji ;, ;,表在内存中的存储类型定义：,struct sqlist ,student *A ;,/,将记录顺序存放在一个一维数组中,int len ; /,表中记录的个数, ;,struct student / 表中学生记录类型,结论：,数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的,操作对象,以及它们之间的,关系,和,运算操作,的一门学科。,结论：,1.1.3,学习本课程的意义,数据结构作为一门独立的课程在国外是从,1968,年开始设立的,。,瑞士著名计算机科学家,N.Wirth,提出的著名公式,“程序,=,算法,+,数据结构”,。,数据结构是一门介于,数学,、,计算机硬件,和,软件,三者之间的核心课程。,用一句话概括,：本课程就是,从实际问题抽象出数据类型的手段,。主要研究计算机所处理的,数据对象,、对象间存在的,关系,及进行的各种,操作,。,1.1.3 学习本课程的意义 数据结构作为一门独立的课程在,1.2,数据结构的主要内容,1.2.1,基本概念和术语,1.2.2,数据结构定义,1.2.3,逻辑结构的表示方法,1.2 数据结构的主要内容 1.2.1 基本概念和术语,1.2.1,基本概念和术语,数据,是对客观事物的符号表示，是一种信息的载体，是所有,能输入到计算机中并被识别、存储和加以处理的信息的总称,。,数据元素,是数据的,基本单位,。一个数据元素也可以由若干个,数据项,组成,。,数据对象,是性质相同的数据元素的集合，是数据的一个子集。,数据类型,是对计算机中表示的,数据对象,、对象,特征,及该数据对象上的一组,操作,的描述。,抽象数据类型,是指一个数学模型及定义在该数学模型上的一组操作。,定义取决于它的逻辑特性，与其在计算机内部如何表示（存储）和实现无关。,1.2.1 基本概念和术语 数据是对客观事物的符号表示，是,1.2.2,数据结构定义,数据结构,是,指相互间存在一种或多种特定关系的数据元素的集合,。,数据,具有相同属性的数据元素的集合；,结构,数据元素间存在的一种或多种关系。,对一个给定的数据结构进行分析时，一般从它的,逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论,。,（本课程的主要讨论点）,1.2.2 数据结构定义 数据结构是指相互间存在一种或多种,逻辑结构,是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。,通常,按元素间存在的逻辑关系的不同特征,，将数据结构,分为四类,：,集合结构,线性结构,树型结构,图型结构,逻辑结构是对给定数据结构的一种描述方式，是从实际问,集合结构：,数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。,例子：从大街上随意的找五个人组成一个小组，编号分别为,1,、,2,、,3,、,4,、,5,，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。,组成集合的数据元素之间不存在任何的关系,集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的,线性结构：,数据元素之间存在“一对一”线性关系的数据结构。,学号,姓名,系别,学分,0351103,王杰,计算机,3,0351212,李丽,计算机,1,例：,学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。,元素之间是1：1关系，都只有唯一的前驱和唯一的后继,线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号,树型结构：,数据元素之间存在,“一对多,”逻辑关系的数据结构。,例：,一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业,元素之间的关系是1：,n，,每个元素都只有唯一的前驱元素，但可以有多个后继元素,树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。例：,图型结构：,数据元素之间存在,“多对多”,逻辑关系的数据结构。,例：,五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。,元素之间的关系是,m:n，,每个元素都可以有多个前驱元素和多个后继元素,图型结构：数据元素之间存在“多对多”逻辑关系的数据结构。例：,存储结构又称物理结构，,就是数据结构在计算机中的存储方式。它包括,数据元素在计算机中的存储方式,，还包括元素之间,关系在内存中的表示,。,根据,存储空间的不同分配方式,将数据结构分为两类：,顺序存储,链式存储,第一方面,第二方面,存储结构又称物理结构，就是数据结构在计算机中的存储,顺序存储：,所有元素存放在一片,连续的,存储空间中，,逻辑上相邻的元素在内存中的物理位置也是相邻的,。,注意：,元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。,例：对一个由（1，2，3，4，5）五个元素组成的数据结构采用顺序存储，则内存中的存储示意图如下所示：,元素,1,元素,2,元素,3,元素,4,元素,5,起始地址,顺序存储：所有元素存放在一片连续的存储空间中，逻辑上,链式存储：,所有元素存放在,可以不连续,的存储单元中，以,结点的形式,存在，每个结点除了保存数据元素信息外，还,通过指针来保存元素之间的关系,。,注意：,既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。,元素,1,元素,4,元素,3,元素,2,例：对一个由（1，2，3，4）四个元素组成的数据结构采用链式存储，则内存中的存储示意图如下所示：,链式存储：所有元素存放在可以不连续的存储单元中，以结,1.2.3,逻辑结构的表示方法,二元组表示法,表示形式为：,D=,（,K,，,R,）,其中，,K=a,1, a,2, a,n,，,为数据元素的集合,R=r,1, r,2, r,m,，,为元素之间关系的集合,r,1,= |,其中，,x,y,K,序偶表示：元素,x,和元素,y,之间存在关系，并且称,元素,x,为元素,y,的前驱,，,元素,y,为元素,x,的后继,。如果元素,x,既是元素,y,的前驱，也是元素,y,的后继，既,且,，,则用,（,x,y,）,形式表示。,1.2.3 逻辑结构的表示方法 二元组表示法,图形表示法,用,圆圈,来代表数据元素，用,带箭头的连线,来表示元素之间的关系，如图所示。,二元组表示法：,D1=( K , R ),其中，,K=a,b,c,d,e,R=r,r = , , , ,图形表示法二元组表示法：D1=( K , R ),1.3,算法和算法分析,1.3.1,算法定义,1.3.2,算法分析,1.3 算法和算法分析 1.3.1 算法定义,1.3.1,算法定义,算法,是对特定问题求解步骤的一种描述，是一组指令的有限序列，其中每一条指令都代表解题过程中的一个或者多个操作。,算法特点,：,有穷性、确定性、可行性、输入、输出,算法描述,可以有多种方式，如：用流程图描述、用自然语言描述、还可用数学语言或特定的符号进行描述。本书中所有算法都是,用,C,语言,来进行描述,。,1.3.1 算法定义 算法是对特定问题求解步骤的一种描述，,1.3.2,算法分析,算法的设计要求,如下：,正确性,可读性,健壮性,效率与低存储量的需求,其中，效率指的是,算法执行的时间,。存储量需求指的是,算法执行过程中所需要的最大存储空间,，通常主要考虑算法所需的辅助存储空间。,这四个设计要求中最主要的是算法的,执行时间,和执行时,所占的存储空间,大小。,1.3.2 算法分析 算法的设计要求如下：,算法的执行时间,是指一个算法在计算机上运行时所花费的时间。,=简单操作所需要的时间简单操作的次数,影响算法执行时间的两个因素：,（1）每个简单操作执行时所需时间与机器有关，而与算法无关。讨论,算法中包含的简单操作的执行次数,。,（2）另外一个与算法的执行时间相关的是,问题的规模,。,算法的执行时间是指一个算法在计算机上运行时所花费的时,通常算法的执行时间用,时间复杂度,表示：,T(n) = O( f ( n ) ),其中，,n,为问题的规模,T,（,n,）,为时间复杂度,此式子表示，随着问题规模,n,的增大，算法执行时间的增长率和,f(n),的增长率相同。所以只,要求出简单操作的次数关于,n,的增长率即可，然后用,n,的最高数量级来表示算法的时间复杂度,。,通常算法的执行时间用时间复杂度表示：,例：,for (j=1;j=n;j+),for (k=1;k=m;k+), +x;,s+=x; ,分析：,各个简单操作的执行次数如下所示：,for (j=1;j=n;j+)/,次数为,1+,（,n+1,）,+n,for (k=1;k=n;k+),/,执行次数为（,1+,（,n+1,）,+n,）,n, +x; /,执行次数为,n*n,s+=x; /,执行次数为,n*n,简单操作的执行次数之和为：,4,n,2,+4n+2，,用,n,的最高数量级表示,，时间复杂度为：,O,（,n,2,）,。,例： for (j=1;j=n;j+),衡量一个算法性能的另一个标准就是,算法执行时所占的存储空间的大小,。一般一个算法所占的存储空间包括存储算法所占用的存储空间、算法的输入,/,输出数据所占用的存储空间和程序运行过程中临时占用的存储空间这三个方面。其中，只有,算法执行过程中所占的临时空间与算法有着密切关系,。,通常一个算法在执行过程中所占用的临时存储空间的大小由,空间复杂度来衡量，,记作：,S（,n,）,= O,（,f,（,n,）,其中，,n,为问题的规模,；,S,（,n,）,为空间复杂度。,通常用,n,的最高数量级来表示。,衡量一个算法性能的另一个标准就是算法执行时所占的存储空间的大,本章总结：,本章介绍了学习数据结构课程的意义、本课程的主题框架及相关内容和如何对算法进行评价。,数据结构主要,研究计算机所处理的数据对象、对象之间存在的各种关系及进行的各种操作,，是用计算机来解决实际问题与编写相应程序两者之间的纽带。,数据结构从定义上可以理解为数据,+,结构。其中，,数据指的是所要处理的若干个数据元素的集合,；,结构指的是数据元素之间的关系,。按逻辑结构可分为集合结构、线性结构、树型结构和图型结构四种。按存储结构可分为顺序存储和链式存储两种。,本章总结：本章介绍了学习数据结构课程的意义、本课程的主题框架,算法,是解决问题步骤的一种描述，它有,有穷性、确定性、可行性、输入和输出,等五个特点。,一个好的算法应该满足,正确性、可读性、健壮性和效率与低存储量需求,等四个要求，其中算法的执行效率和低存储量需求是衡量一个算法的最主要的标准。通常,用时间复杂度来衡量算法的执行时间，用空间复杂度来衡量算法执行过程中所占用的临时存储空间的大小,。它们都是,问题的规模,n,的一个函数,，所以用,n,的最高数量级来表示。,算法是解决问题步骤的一种描述，它有有穷性、确定性、可,