数据结构第一章：绪论.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,主 讲：易 娜,第一章：概述,课程简介：本课程是一门专业技术基础课程，课程分析、研究计算机加工数据的特征、数据的逻辑结构、数据的存储结构、数据涉及的算法、以及不同特征数据应用情况,内容提要：,本章将介绍数据结构的基本概念：数据、数据元素、数据结构、数据的逻辑结构和存储结构、数据运算、算法和算法分析等，了解这些概念有助于对以后章节加深理解,。,第一章：概述,第,1,章,概论,1.1,概述,1.2,数据结构的基本概念,1.2.1,数据结构的基本术语,1.2.2,数据的逻辑结构,1.2.3,数据的存储结构,1.3,算法性能分析与度量,1.3.1,算法和算法的描述方法,1.3.2,算法的特性,1.3.3,算法设计的要求,1.3.4,算法时间复杂度的度量,1.3.5,算法存储空间的需求,1.1,概述,1,、什么是数据结构,数据结构是指数据之间的相互关系，即数据的组织形式。（至今没有对数据结构准确的定义）但一般它包含三个方面的内容：,数据元素之间的逻辑关系,数据的逻辑结构,数据结构及其关系在计算机存储器内的表示,数据的存储结构,数据的运算,对数据施加的操作,数据结构的实例,1,、电话号码检索,【,例,1.1,】,2,、字典查找,【,例,1.2,】,【,例,1.1,】,电话号码自动查询问题,。,电话号码查询的最主要的工作是，当给出某个单位名称或某个人的姓名时，能在电话号码表中迅速找到其电话号码，若找不到，则给出该单位或个人的电话号码不存在的信息。此外，当有新用户要加入、旧用户要改号或撤销时，要对电话号码表进行相应的修改。,那么，如何组织电话号码表，实现上述查询、插入、删除和修改等操作呢？,为了提高查找效率，可以重新组织电话号码表，将单位和私人电话分开登记。单位电话按行业分类组织，将同行业的电话登录在一起，并建立一个分类索引表（分类简表）和行业分类目录，如图,1.1,所示。而私人电话则按姓氏笔画进行登录，同时建立一个姓氏笔画索引表，如图,1.2,所示。,假设电话号码表的组成见表,1.1,。表中各用户的电话号码是随机罗列出来的。若要查找某人或某单位的电话号码，就必须从表的开始依次往后顺序查找。若该用户确实注册，就会找到该用户的电话号码。但是，采用这种方式进行查找，效率是很低的。,【,例,1.1,】,电话号码自动查询问题。,图,1.1,单位电话号码组织构造的示意图,图,1.2,私人住宅电话索引表和电话登记表的示意图,【,例,1.2】,无序表的顺序查找和有序表的二分查找。,假设某校选修课成绩登记表和学生情况登记表分别参见表,1.2,和表,1.3,。,在表,1.2,中，学生记录的排列顺序是没有规律的，因此称为,无序表,。,在表,1.3,中，每个学生记录按学号从小到大顺序排列，因此称为,有序表,。,请考虑在这两个表中进行查找的问题,。,表,1.2 2001,年第一学期计算机基础选修课成绩登记表,表,1.3 2001,级计算机应用专业学生情况登记表,首先考虑在表,1.2,所示的无序表中进行查找。,在这个表中，若要查找某位学生的记录，必须从表的第一个记录开始，逐个将表中的记录与所给的学生记录进行比较。若表中的某个学生记录与所给的学生记录完全相同，则查找成功；若表中没有找到所给的学生记录，则查找失败。,这种从头至尾逐个在表中查找记录的方法称为,顺序查找。,显然，在顺序查找中，如果被查找的记录在表的前部，则需要比较的次数就少；如果被查找的记录在表的尾部，则需要比较的次数就多。特别是当要查找的学生记录刚好是登记表中的第一个元素时，只需比较一次就查找成功；但是，当要查找的学生记录刚好是表中最后一个元素时，则需要与表中所有的元素进行比较。当表很大时，顺序查找方法是很费时间的,。,现在考虑在表,1.3,所示的有序表中进行查找。,由于有序表中的学生记录是按学号从小到大顺序排列的，所以采用有序表的二分查找方法，可以提高查找的效率。,有序表的二分查找方法是：,将被查找数与表的中间元素进行比较：若相等，则表示查找成功，结束查找；若被查找数大于表的中间元素，则表示被查找数在表的后半部，此时可以抛弃表的前半部而保留后半部；若被查找数小于表的中间元素，则表示被查找数在表的前半部，此时可以抛弃表的后半部而保留表的前半部。然后对剩下的部分再按上述方法进行查找。这个过程一直做到在某一次的比较中相等（查找成功）或剩下部分已空（查找失败）为止。,这种查找方法称为,有序表的二分查找,。,由此可见，数据的组织方式和数据在表中的排列顺序，都会影响查找的效率。,综上所述，我们可以说：数据结构就是选择适当的组织方式按照某种关系来组织大量的数据，以一定的存储方式把它们存储到计算机中，并在这些数据上定义一个相应的运算，以提高计算机的数据处理能力的一门学科。,1.2,数据结构的基本概念,在这一节中，我们将对书中一些常用的名词和术语给出确切的定义，以便在今后的学习中能有一个统一的概念。,（,1,）数据,（,2,）数据元素,（,3,）数据对象,（,4,）数据类型,（,5,）数据结构,（,6,）数据处理,（,7,）数据的图形表示,1.2.1,数据结构的基本,术语,（,1,）,数据,：,数据是信息的载体，是描述客观事物的数、字符，以及所有能够输入到计算机中并被计算机程序识别和处理的一切对象,。,例如，解代数方程的程序中所用到的整数和实数，文本编辑中所用到的函数和字符串等，都是计算机程序加工和处理的对象。,数据大致分为两类：一类是数值型数据,，包括整数、浮点数、双精度数等，主要用于工程和科学计算，以及商业事务处理；,另一类是非数值型数据,，主要包括字符以及文字、声音、图像等。,（,2,）数据元素,：,是数据的基本单位，亦称为,结点,、,元素,、,顶点,和,记录,等，在计算机程序中通常作为一个整体进行考虑和处理。,有时一个数据元素可由若干个数据项组成,。,数据项,是具有独立意义的最小的数据单位，是对数据元素属性的描述。,（,3,）数据对象,：,是具有相同性质的数据元素的集合，是数据的一个子集。,例如，,整数的数据对象,可以是集合,N,=0,，,1,，,2,，,，,英文字母组成的数据对象,可以是集合,C,=A,，,B,，,Z,，,一年四季的名称,所组成的数据对象可以是集合,S,=,春，夏，秋，冬,，家庭成员名称所组成的数据对象可以是集合,F,=,祖父，父亲，叔叔，儿子，女儿，孙子，,。,（,3,）数据对象（续）,：是具有相同性质的数据元素的集合，是数据的一个子集。,在学校中，学生是更复杂的数据对象，它的每一个数据元素就是一个学生记录，每个学生记录包括：学号、姓名、性别、出生年月、家庭住址等数据项，以表明学生在某一方面的属性，,参见表,1.3,。,在学生选课系统中，可能以一个班级的学生记录作为学生数据对象，也可能以一个年级或一个学校的学生记录作为学生数据对象,参见表,1.2,。,因此，如何选择数据对象将依据要求不同而定。,（,4,）数据类型,：,是具有相同性质的计算机数据的集合和定义在这个数据集合上的一组操作的总称。,例如，,C,语言中的整数类型，它的值是,MAXINT,MAXINT,区间上的整数，定义在这个整数集上的操作为：加、减、乘、除和取模等算术运算,。,数据类型可以分为两类：,原子数据类型和结构数据类型,。,（,4,）数据类型（续）,：,原子数据类型,是由计算机语言提供的，其值是不可分解的。,例如，,C,语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。,结构数据类型,是由用户自己定义的，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构类型的，也可以是结构类型的。,例如，,C,语言中的数组和结构类型等。,（,5,）数据结构、数据的逻辑结构和物理结构,数据结构,：,是指某一数据对象及该对象中所有数据元素之间的关系组成。,一个数据对象中所有数据成员之间一定存在某种联系。,逻辑结构：,数据元素之间的相互关系称为,数据的逻辑结构。,物理结构,：,在计算机中存储数据时，不仅要存储数据本身的信息，还要存储各数据之间的前后关系的信息（即逻辑结构）。数据及其关系在计算机中的存储方式，称为,数据的存储结构,，,或数据的物理结构,数据及其关系在计算机中的存储方法称为,数据的物理结构。,数据的逻辑结构是从解决问题的需要出发，,为实现必要的功能所建立的数据结构。它属于用户的视图，是面向问题的，例如，在选修课成绩系统中建立按成绩排列的有序表。数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储位置无关。,数据的物理结构是指数据在计算机中如何存放,，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。数据的逻辑结构根据问题所要实现的功能建立，数据的物理结构根据问题所要求的响应速度、处理时间、修改时间、存储空间和单位时间的处理量等建立，是逻辑数据的存储映像。,数据逻辑结构的二元组表示,数据的逻辑结构可以看成从具体问题抽象出来的数学模型，因此，可用二元组表示：,B,=(,D,R,),式中,B,表示数据结构；,D,是某一数据对象，是数据元素的集合；,R,D,中各数据元素间关系的集合，用二元组表示。,（,6),数据处理,：,是指对数据进行检索、插入、删除、合并、排序、统计、简单计算、转换、输入和输出等操作过程。,例如，计算机情报检索系统、经济信息管理系统、图书管理系统、物资调配系统、银行核算系统、财务管理系统等都是计算机在数据处理领域的具体应用。数据结构是进行数据处理的软件基础。,（,7,）数据结构的图形表示：,一个数据结构除了可用二元组表示外，还可以用图形来形象地表示。,在数据结构的图形中,，,每个结点（或顶点）表示一个数据元素，用中间标有元素值的方框表示，两个结点之间用带箭头的连线（称作,有向边,或,弧,）表示对应关系中的一个序偶，其中序偶的第一个元素（称为第二个元素的,前驱结点,）为有向边的起始结点，第二个元素（称为第一个元素的,后继结点,）为有向边的终止结点，即箭头所指的结点。,1,、数据结构的分类：,线性结构：,线性结构中每一个数据元素（除第一个和最后一个数据元素外），仅有一个直接前驱和一个直接后继；而第一个数据元素只有一个直接后继，没有直接前驱；最后一个数据元素只有一个直接前驱，没有直接后继。,线性结构也称为,线性表,。选修课成绩表（表,1.2,）和学生情况登记表（表,1.3,）就是典型的线性结构。,非线性结构：,一个数据元素可能有多个直接前驱和直接后继。,例如，,树型结构和图结构。,1.2.2,数据的逻辑结构,0-0,1-1,1-N,N-N,数据的,逻辑,结构也可分为：,集合、线性结构、树状结构、网状结构,2,、数据的逻辑结构的几个实例,【,例,1.3,】,一年四季名称组成的数据结构可表示为：,B,=(,D,R,),D,=,春，夏，秋，冬,R,=,春，夏,，,夏，秋,，,秋，冬,图,1.3,是一年四季名称数据结构的图形表示。,图,1.3,线性数据结构示例,一年四季名称数据结构的图形表示,该结构的数据元素是一年中四个季节的名称。各季节间的顺序关系是：“春”是“夏”的直接前驱，“夏”是“秋”的直接前驱，而“秋”是“冬”的直接前驱，反之“夏”是“春”的直接后继。在该结构中，数据元素之间是一个对一个的关系，即,线性关系,。,我们把具有这种特点的数据结构称为,线性结构,。,图,1.3,是一年四季名称数据结构的图形表示,。在数据结构的图形表示中，数据集合,D,中的每个数据元素用中间标有元素值的方框表示，数据元素间的关系用带箭头的线段表示。,【,例,1.4】,考试成绩统计表见表,1.4,。,表,1.4,中的每一行是一名考生的记录，每个记录由准考证号、姓名、各科成绩及总分等数据项组成。其中，准考证号为该记录的主关键字。若将所有考生记录按总分从高到低排列，则高考成绩统计表是一个按成绩排列的有序表。表中每个学生记录所组成的数据结构可表示为：,B,=(,D,R,),D,=,胡桃，黎明，肖红，唐平，程程，房芳,R,=,胡桃，黎明,，,黎明，肖红,，,肖红，唐平,，,唐平，程程,，,程程，房芳,【,例,1.4】,表,1.4,考试成绩统计表,图,1.4,线性数据结构示例,考生成绩统计表图形表示,这是一个典型的线性结构。,考生成绩统计表是一个线性表，线性表中所有数据元素按成绩从高到低顺序排列。线性表中第一个记录没有直接前驱，称为,开始结点,，而最后一个记录没有直接后继，称为,终端结点,。除第一个记录和最后一个记录外，其他记录仅有一个直接前驱结点和一个直接后继结点。,例如，“胡桃”没有前驱结点故为开始结点，而“房芳”没有后继结点是终端结点；“黎明”的前驱结点是“胡桃”，其后继结点是“肖红”。,图,1.4,就是考生成绩统计表这个数据结构对应的图形表示,。,【,例,1.5,】,假设家庭成员组成的数据结构,B,=(,D,R,),D,=,祖父，叔叔，父亲，儿子，女儿，孙子,R,=,祖父，父亲,，,祖父，叔叔,，,父亲，儿子,，,父亲，女儿,，,儿子，孙子,图,1.5,树型数据结构示例,家庭成员间辈分关系图形表示,这是一个典型的树型数据结构。,组成这个结构的数据元素是家庭成员名，在考虑家庭成员间的辈分关系时，则“祖父”是“父亲”的直接前驱，而“儿子”和“女儿”都是“父亲”的直接后继；“儿子”是“孙子”的直接前驱，而“孙子”则是“儿子”的直接后继。,图,1.5,是家庭成员间辈分关系数据结构的图形表示,。该图形就像一棵倒画的树。在这棵树中，最上面一个没有前驱的结点称为,根结点,，最下面一层只有前驱没有后继的结点称为,叶结点,。在一棵树中，每个结点有且仅有一个直接前驱结点（除第一个结点称为,树的根结点,外），但可以有任意多个后继结点。这种数据结构的特点是，数据元素之间是一个对多个的关系，即层次关系。我们把具有这种特点的数据结构称为,树型结构,，简称为,树,。,【,例,1.6,】,假设国内若干城市之间的航线组成的数据结构可表示成：,B,=(,D,R,),D,=,北京，上海，武汉，香港，重庆，广州,R,=,r,1,r,2,r,3,r,4,r,1,=(,北京，上海,),，,(,北京，香港,),，,(,北京，广州,),，,(,北京，重庆,),，,(,北京，武汉,),r,2,=(,上海，香港,),，,(,上海，重庆,),，,(,上海，武汉,),，,(,上海，广州,),r,3,=(,武汉，香港,),，,(,武汉，重庆,),，,(,武汉，广州,),r,4,=(,香港，重庆,),，,(,香港，广州,),，,(,广州，重庆,),图,1.6,是国内若干城市间部分航线示意图，,这是典型的图型数据结构。,图,1.6,图型数据结构,国内若干城市间部分航线示意图,图,1.6,是国内若干城市间部分航线示意图,，,这是典型的图型数据结构。组成这种数据结构的数据元素是城市名称（顶点），在图中，每个城市（顶点）都可以与若干城市（顶点）相连，是一种多对多的关系。,在航线图中，对每个城市的描述可用一个顶点来表示，而每个城市的基本信息，如城市名称、机场位置、航线的多少等则可以用顶点中的数据项来描述。这些描述在航线图中被省略了。,从图,1.6,中可以看出,，,R,是,D,上的对称关系，这种结构的特点是数据元素之间的联系是多对多的关系，即,网状关系,；也就是说，每个结点可以有任意多个前驱结点和任意多个后继结点。我们把具有这种特点的数据结构称为,图型结构,，简称,图,。,1.2.3,数据的存储结构,数据处理是计算机应用的一个重要领域。在实际进行数据处理时，所有要处理的数据都要存放到计算机的存储器中。,数据在计算机中的存储方式有多种：,顺序,链接,索引,散列,因此，同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构。,数据在计算机中常用的四种存储方式,：,1,、顺序存储结构：,利用在存储器中的物理关系来表示逻辑关系。,2,、链式存储结构：,用在存储器中附加指针的方式来表示逻辑关系。,3,、索引存储结构：,在存储结点信息的同时，建立一个附加的索引表。,4,、散列存储方法：,是一种重要的存储方法，也是一种常见的查找方法。它的基本思想是：根据结点关键字,key,直接计算出该结点的存储地址。不同的关键字可能得到同一个散列地址，即,key,1,key,2,，但,f(key,1,)=f(key,2,),，,这种现象称为,冲突,。,1,顺序存储方法,顺序存储方法,是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里，也就是将所有存储结点相继存放在一个连续相邻的存储区里。用存储结点间的位置关系来表示结点之间的逻辑关系。因此，顺序存储结构只需要存储结点的信息，不需要存储结点之间的关系。,计算机的存储器是由很多存储单元组成的，每个存储单元都有惟一的地址（编号）。每个存储单元的地址编号都是线性连续的。我们把两个互为前驱、后继的存储单元称为相邻存储单元，把一片相邻的存储单元称为存储区域。,顺序存储结构通常可用,C,语言的数组来描述,。,【,例,1.7,】,请用顺序存储方式表示一周,7,天，假设一周,7,天的数据结构为：,B,=(,D,R,),D,=Sun,Mon,Tue,Wed,Thu,Fri,Sat,R,=,，,，,，,，,，,若采用顺序存储方法将一周,7,天存储在计算机中，其顺序存储结构如图,1.7,所示。,图,1.7,线性结构的顺序存储结构示例,2,链接存储方法,链接存储方法：,在存储每个结点信息的同时，需要增加一个指针来表示结点间的逻辑关系。该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链接存储结构中的每个结点由两部分组成：一部分用于存储结点本身的信息，称为,数据域,；另一部分用于存储该结点的后继结点（或前驱结点）的存储单元地址，称为,指针域,。指针域可以包含一个或多个指针，这由结点之间的关系所决定。,【,例,1.8,】,链接存储方式表示一周,7,天，假设一周,7,天的数据结构为：,B,=(,D,R,),D,=Sun,Mon,Tue,Wed,Thu,Fri,Sat,R,=,，,，,，,，,，,该数据结构的链接存储结构如图,1.8,（,a,）,所示，图,1.8,（,b,）,是该链接存储结构的图形表示。在图中，方框表示一个结点，框中数字为该结点的值，箭头代表指针，它表示各结点之间的关系。,图,1.8,线性结构的链接存储结构示例,3,索引存储方法,索引存储方法,是在存储结点信息的同时，建立一个附加的索引表。索引表中每一项称为一个,索引项,。索引项的一般形式是：（关键字，地址），,关键字,是能惟一标识一个结点的数据项。索引存储分为,稠密索引,和,稀疏索引,两种。,（,1,）,稠密索引,：,每一个结点在索引表中都有一个索引项。索引项的地址指出结点所在的存储位置。稠密索引也称为,密集索引,。如图,1.9,所示采用的是稠密索引方式。,（,2,）,稀疏索引,：一组结点在索引表中只对应一个索引项。索引项的地址指示一组结点的起始存储位置。稀疏索引也称为,分块索引,。例如，图,1.1,（,a,）、（,b,）,和图,1.2,（,a,）,所示的电话号码索引表就是稀疏索引方式。,【,例,1.9,】,某单位职工档案文件。,每个职工的档案信息都包括：职工号、姓名、性别和年龄,4,项。其中，职工号为记录的主关键字，每个职工的信息存放在一条记录中。假设采用索引非顺序文件存储方法来存储职工档案信息。由于职工记录信息是随机输入的，并不按记录关键字的顺序排列，因此，可以采用稠密索引方式为每个职工记录建立一个索引项。,采用索引非顺序文件存储方式建立的职工档案文件存储结构如图,1.9,所示,。,图,1.9,索引非顺序文件存储结构示例,4,、散列存储方法,散列存储方法：,是一种重要的存储方法，也是一种常见的查找方法。它的基本思想是：根据结点关键字,key,直接计算出该结点的存储地址。不同的关键字可能得到同一个散列地址，即,key,1,key,2,，但,f(key,1,)=f(key,2,),，,这种现象称为,冲突,。,散列存储方法,：,根据结点的关键字,key,直接计算出该结点的存储地址。即以线性表中的每个结点的关键字,key,为自变量，通过一个确定的函数关系,f,，,计算出对应的函数值,f(key),，,然后把这个值解释为一块连续存储空间的存储地址，将结点存储到,f(key),所指的存储单元中，使每个关键字和结构中一个惟一的存储地址相对应。,因而查找时，根据给定的关键字,key,，,只要用同样的函数,f(key),计算出散列关键字的地址，然后到相应的单元里取出关键字为,key,的结点即可。用散列方法存储的线性表称为,散列表,，,散列存储中使用的函数,f(key),称为,散列函数,，它实现关键字到存储地址的映射（或称为,转换,）,，,f(key),的值,是,key,的存储地址，称为,散列地址。,通常，散列表的存储空间是一个一维数组，散列地址是数组的下标。我们将这个一维数组简称为,散列表,。,在一般情况下，散列函数是很难一一对应。因此会出现这样的情况：不同关键字可能得到同一个散列地址，即,key,1,key,2,，但,f(key,1,)=f(key,2,),，,这种现象称为,冲突,。,通常把具有不同关键字而具有相同散列地址的元素称做,同义词,。,因此，如何尽量避免冲突和冲突发生后如何解决冲突是散列存储的两个关键问题。,处理冲突最基本的方法有两种：,开放定址法和拉链法。,开放定址法,就是当冲突发生时，使用某种,探测,技术在开放的散列表中查找出一个空闲的存储单元，把发生冲突的待插入结点存入该空单元中以此来解决冲突。,拉链法,就是把所有发生冲突的同义词元素（结点）链接存储在同一个单链表中。,存储结构是数据结构不可缺少的一个方面。同一种逻辑结构采用不同的存储方式，可以得到不同的存储结构。若存储结构不同，则其数据处理的效率也完全不同。因此，数据处理时选择合适的存储结构是非常重要的。究竟选择何种存储结构来表示相应的逻辑结构，应根据具体问题的要求而定，主要考虑的是运算方便及算法的时间和空间要求。,同一种逻辑结构的不同存储结构，我们常常冠以不同的数据结构名称来加以区别。,例如，对于一周,7,天这个数据结构，若采用顺序存储方式，该结构就称为,顺序表,；若采用链接存储方式，该结构就称为,链表,；若采用散列存储表示，则该结构称为,散列表,。,存储结构小结,第,1,章 概论,1.3,算法性能分析与度量,1.3.1,算法和算法的描述方法,1.3.2,算法的特性,1.3.3,算法设计的要求,1.3.4,算法时间复杂度的度量,1.3.5,算法存储空间的需求,1.3.1,算法和算法的描述方法,算法,：,对特定问题求解步骤的一种描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。广义地说，为解决一个问题而采取的方法和步骤，就称为,算法,。解决一个问题的过程就是实现一个算法的过程。,计算机算法,就是计算机能够实现的算法。,算法分类：数值算法和非数值算法,解决数值问题的算法称为,数值算法,。科学和工程计算方面的算法都属于数值算法。,例如求解数值积分、求解线性方程组、求解代数方程、求解微分方程等。,解决非数值问题的算法称为,非数值算法,。数据处理方面的算法都属于非数值算法。,例如对各种数据结构的排序算法、图书情报资料检索、计算机绘图等。,算法描述方法：,通常算法描述方法有以下,4,种：,流程图：以文字框图进行图示的算法流程图。,自然语言：用自然语言描述的算法规则及算法的基本思想。,伪代码：体现结构化程序设计原则的类,C,或者,类,Pascal,语言的描述方式。,程序设计语言：用计算机程序设计语言来描述算法，如,用,C,或,C+,等。,不管用哪种方式描述算法，惟一的要求是：能够精确地描述计算过程。,1.3,算法性能分析与度量,在计算机领域，一个算法实质上是针对所处理问题，在数据的逻辑结构和存储结构的基础上施加的一种运算。由于数据的逻辑结构和存储结构不是惟一的，算法的设计思想和技巧也不是惟一的，所以处理同一个问题的算法也不是惟一的。,学习数据结构这门课程的目的，就是要学会根据数据处理问题的需要，为待处理的数据选择合适的逻辑结构和存储结构，从而设计出比较满意的算法（程序）。,【,例,1.11,】,求两个正整数,m,和,n,的最大公约数。,【,算法分析,】,假设,m,为被除数,，,n,为除数，,r,为余数。用“辗转相除法”求最大公约数的算法如下。,比较,m,和,n,的大小,。若,m,n,，,则交换,m,和,n,，,保证大数放,在,m,中，小数放在,n,中。,求余数：计算,m,/,n,的余数,r,，即,r,=,m,/,n,。,若,r,0,，则令,m,=,n,；,n,=,r,；,返回并重新执行第步。,若,r,=0,，,则算法结束。,n,就是两个正整数,m,和,n,最大的公约数。,求两个正整数最大公约数的,C,语言算法,main()/*,求两个正整数的最大公约数算法*,/,int,m,n,r,temp;,printf,(,请输入两个正整数,m,n:);,scanf(%d%d,if(n m)/*,将大数,放在,m,中小数放在,n,中*,/,temp=m;m=n;n=temp;,r=m%n;/*,将,m/n,的余数存放在,r,中*,/,while(r!=0)/*,求,m,和,n,最大公约数，当,r=0,时结束*,/,m=n;,/*,令,m=n,，,n=r*/,n=r;,r=m%n;,/*,计算余数,r=m/n,，,直到,r=0,为止*,/,printf(M,和,N,的最大公约数是：,%2dnn,n);,/*MAIN*/,1.3.2,算法的特性,（,1,）有穷性。,一个算法必须总是在执行有穷步之后结束，且每一步都可在有限时间内完成。,（,2,）确定性。,一个算法中的每一条指令都必须有确切的定义，无二义性。在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。,（,3,）可行性,。,算法中要执行的每一个步骤都应该在有限的时间内完成。可行性与有穷性和确定性是相容的。,（,4,）输入。,一个算法有零个或多个输入信息。这些输入信息取自于某个特定的对象的集合。例如，求素数要求输入一个正整数,n,，,而求最大公约数则要求输入两个正整数,m,和,n,。,（,5,）,输出。,一个算法有一个或多个输出信息。这些输出是与输入有着某些特定关系的量。算法的目的是求“解”，“解”就是“输出”。例如，判断素数的输出信息是“,n,是素数”或,“,n,不是素数”，求最大公约数的输出是两个正整数,m,和,n,的最大公约数。,1.3.3,算法设计的要求,算法衡量方法和准则有以下几个方面：,正确性,健壮性,时间复杂度,空间复杂度,可读性,简单性,1.3.3,算法设计的要求,（,1,）正确性,。,算法应当满足具体问题的需求。这是算法设计的基本目标。,（,2,）健壮性,。,当输入非法数据时，算法要能够做出适当的处理和反应，而不会产生莫名其妙的输出结果。一个好的算法，应该能够识别出错误的输入数据并进行相应的处理。对错误数据的处理一般包括打印错误信息，采用错误处理程序，返回标识错误的特定信息和终止程序运行等。,（,3,）时间效率高。,算法的时间效率指的是算法的执行时间。执行时间短的算法称做时间效率高的算法。对于同一个问题，若有多个算法可以解决，应尽可能选择执行时间短的算法。,（,4,）存储空间少。,算法的存储空间指的是算法执行过程中所需要的最大存储空间，其中主要考虑辅助的存储空间。存储空间小的算法称做,内存要求低的算法。,同一个问题若有多个算法可供选择，应尽可能选择内存要求低的算法。当然效率与存储空间的需求都与问题的规模有关，求,100,个素数和求,10000,个素数所需的执行时间和存储空间显然是有差别的。,（,5,）可读性,1.3.4,算法时间复杂度的度量,算法的时间复杂度是指执行算法所需要的计算工作量。（一般用算法所执行的基本运算次数来衡量）,一条语句在算法中被重复执行的次数称为语句的频度。,语句频度,：,算法中每条语句的执行次数与其执行一次所需时间的乘积。,假设,n,表示求解问题的规模，例如，排序运算时,n,为参加排序的记录数，在矩阵运算中,n,为矩阵的阶数，在图的遍历中,n,为图的顶点数，则一个算法的语句频度是其求解问题规模,n,的函数，,记为,T,(,n,),。,【,例,1.13】,下面算法为,求,n,个自然数的和,S,=1+2+3+,n,。,请给出该算法的语句频度。,sum(,int,n),int,i,s=0;,语句执行次数,for(i=1;i=n;i+),n,+1,次,s=s+i;,n,次,printf(%dn,s);1,次,/*SUM*/,【,解,】,算法右边是各语句的执行次数。算法的语句频度就是算法中所有语句的执行次数之和。因此，该算法的语句频度为,：,T,(,n,)=1+,n,+,n,+1=2,n,+2,算法的空间复杂度,是算法所需存储空间的度量，它也是问题规模,n,的函数。渐进的空间复杂度简称为空间复杂度，,记为,S,(,n,),。,一个算法在计算机存储器上所占用的存储空间应该包括三个方面：,存储算法本身所占用的存储空间，算法输入或输出数据所占用的空间，以及算法运行过程中临时占用的存储空间。,算法的空间需求一般用空间复杂度的数量级给出，记做：,S,(,n,)=O(,F,(,n,),通常，一个算法的复杂度是算法的时间复杂度和空间复杂度的总称,。,1.3.5,算法,空间,复杂度的度量,本章小结,本章主要介绍了贯穿和应用于整个“数据结构”课程的基本概念和算法分析方法，概括地反映了后续各章的基本内容，为进入具体内容的学习提供了必要的引导。学好本章内容，将为后续章节的学习打下良好的基础。,本章的复习要点,（,1,）理解数据、数据元素、数据项、数据类型、数据对象的概念及其相互关系。,（,2,）理解数据的逻辑结构、数据的存储结构、数据处理及数据结构的概念和意义，以及它们之间的联系，理解存储结构和逻辑结构的区别。,（,3,）了解数据的逻辑结构的分类方法，掌握线性结构和非线性结构的逻辑特征。,（,4,）了解数据在计算机中的,4,种基本存储方式。,（,5,）理解算法、算法的时间复杂度和空间复杂性，以及与算法有关的一些概念；必须清楚地了解算法的定义、特性及对算法编制的质量要求；掌握算法性能（时间和空间）的简单分析方法，能够分析所给的程序（程序段和函数），并能用数量级的形式表示算法的时间复杂度。,（,6,）理解算法的几种描述方法。本书的全部算法均,用,C,语言来描述，因此，要求,熟练掌握用,C,语言编写应用程序的基本技术。,本章的重点和难点,本章的重点是：,数据、数据元素、数据结构等基本概念和术语；,数据结构的逻辑结构、存储结构，以及数据处理的概念和相互间的关系；,算法的概念、算法的评价标准和算法性能（时间和空间）的分析方法。,本章的难点是：,数据的逻辑结构,算法时间,复杂度的数量级表示。（不做教学要求）,习题,1,1.1,什么是数据结构？数据结构讨论哪三个方面的问题？,1.2,什么是数据元素？什么是数据项？数据与数据元素有何区别？,1.3,什么是数据的逻辑结构？什么是数据的物理结构？,1.4,什么是线性结构？什么是非线性结构？,1.5,数据的逻辑结构与存储结构有什么关系？,1.6,数据的逻辑结构分为线性结构和非线性结构两大类。这两类结构各自的特点是什么？,1.7,数据的存储方法有,4,种：顺序存储、链接存储、索引存储和散列存储方法，简述各存储结构的特点。,1.8,什么是算法？算法的,5,个特性是什么？试根据算法的特性解释算法与程序的区别。,1.9,什么是算法的时间复杂度？算法的时间复杂度是如何表示的？,