第1章 绪论1.ppt

*,*,数据结构,授课教师：王英华,手机：,13330118603,QQ,：,107313652,群：,172443865,DATA STRUCTURE,1,教材,数据结构,(C,语言版,),严蔚敏、吴伟民,清华大学出版社,2,成绩评定,闭卷考试,课程组成,64,学时,=,上课,48+,上机,16,平时成绩,30%,考 勤,30%,(,旷课达,1/10,取消考试资格,),学习态度,10%,书面作业,20%(,缺,1/3,同上,),上机练习,40%(,缺报告,同上,),笔试成绩,70%,3,考勤评分：,缺课：,每次扣,5,分，三次及以上取消考试资格。,早退等同缺课。,迟到：,每次扣,3,分。,请假：,前两次不扣分；,从第三次起，每次扣,2,分。,4,上机评分：,第一次玩游戏警告，第二次玩游戏扣,10,分，第三次取消考试资格。,每次上机每位同学至少要能够独立完成一个程序的设计、调试及运行过程。（不定期抽查）,每次上机要完成所布置的上机实验及实验报告。,5,课堂纪律：,讲课期间，不允许聊天、睡觉、吃东西。,讲课期间，不允许讲电话、玩手机、戴耳机。,讲课期间，不允许随便进出教室。,答疑,：,地点：创新大楼西侧软件理论教研室,时间：周三晚上,说明：周三上课时预约，否则可能不在,6,1.1,什么是数据结构,1.2,基本概念和术语,1.4,算法和算法分析,第一章 绪 论,1.3,抽象数据类型的表示与实现,7,1.1,什么是数据结构,用计算机解决具体问题的步骤：,1.,抽象出一个,数学模型,；,2.,设计一个解此数学模型的,算法,；,3.,编程、测试、调整。,寻求数学模型：,分析,问题,、提取,操作,的,对象,及其对象之间的,关系,并进行描述。,8,Niklaus,Wirth,：,Algorithm,+Data Structures=Programs,程序设计,:,算法,:,+,数据结构,:,为计算机处理问题编制,一组指令集,处理问题的策略,问题的数学模型,9,举例：,1.,数值计算的程序设计问题,已知：游泳池的长,len,和宽,width,，求面积,area,；,第一步：建数学模型,问题涉及的对象：游泳池的长,len,，宽,width,，,面积,area,；对象之间的关系：,area=,lenwidth,第二步：设计求解问题的方法,第三步：编程,main(),int,len,width,area;,cin,len,width;area=,len,*width;,cout,“area=”,数据元素,数据项,例：班级通讯录,个人记录,姓名、年龄,21,例如：学生成绩,数据,学号,姓名,性别,数学,英语,C,语言,20080301,张三,男,87,68,90,20080302,李梅,女,78,69,80,20080303,王五,男,90,55,68,20080304,一个数据元素,一个数据项,整个表记录的是学生成绩数据，单个学生的成绩是其中的一个数据元素。,关键字,表,1-1,学生成绩表,关键字,指的是能识别一个或多个,数据元素,的,数据项,。若能起唯一识别作用，则称之为,主,关键字，否则称之为,次,关键字。,22,数据对象,:,是具有相同特性的数据元素的集合，如,:,一个班级的成绩表可以看作一个数据对象。它是数据的一个子集。,数据结构：,若在特性相同的数据元素集合中的数据元素之间存在一种或多种,特定的关系,，则称该数据元素的集合为“数据结构“。,数据结构,是带“,结构,”的,数据元素,的集合。,指数据元素之间存在的关系,23,数据对象,:,是性质相同的,数据元素,的集合。,是数据的子集。,结 构,:,数据元素相互之间的关系。,数据结构：,带,结构,的,数据元素,的集合。,数据元素之间的,逻辑关系,。,关 系：,又称为,逻辑结构,。,24,例,1,：,假设用三个,4,位的十进制数表示一个含,12,位数的,十进制长整数,。,分析：数学模型,它是一个含三个,数据元素,a1,a2,a3,的集合，且在集合上存在下列次序,关系,：,，,。,意为,x,和,y,之间存在,x,领先于,y,的次序关系。,长整数,“,321465879345,”,可用,a1=3214,，,a2=4658,和,a3=9345,的集合表示,3214,6587,9345,a1,(3214),a2,(6587),a3,(9345),3214,，,6587,，,9345,6587,，,3214,，,9345,a1,a2,a3,a2,a1,a3,25,【,例,】,在,2,行,3,列的二维数组,a1,a2,a3,a4,a5,a6,中六个元素之间存在两个关系,:,行的次序关系,:,row,=,col,=,a1 a3 a5,a2 a4 a6,a1 a2 a3,a4 a5 a6,a1,a2,a3,a4,a5,a6,列的次序关系,:,26,例,3:,管理关系,关系可如下描述：,层次关系,通常用,有序对的集合,来表示,数据元素之间的关系,27,数据（逻辑）结构的种类,根据数据元素之间关系的不同特性分类：,(1),集合,:,数据元素间除,“,同属于一个集合,”,外，无其它关系。,(2),线性结构,:,一个对一个，如线性表、栈、队列。,(3),树形结构,:,一个对多个，如树。,(4),图状结构,:,多个对多个，如图。,28,例：有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示。,(1)A=(K,R),其中,K=,a,b,c,d,R,=,(2)B=(K,R),其中,K=,a,b,c,d,R,=r,r=,(3)C=(K,R),其中,K=,a,b,c,d,e,R,=r,r=,a,b,c,d,d,b,e,a,c,a,b,c,d,29,a,b,c,d,a,b,c,d,d,b,e,a,c,或者说，,数据结构,是相互之间存在着某种,逻辑关系,的,数据元素的集合,。,可见，不同的“关系”构成不同的“结构”。,30,数据结构的形式定义为,:,数据结构,是一个,二元组,Data_Structures=(D,S),其中,:D,是,数据元素,的有限集,，,S,是,D,上,关系,的有限集。,31,数据结构,数据的逻辑结构,数据的物理结构,是对数据元素之间存在的逻辑关系的描述。,是数据逻辑结构在计算机存储器中的表示和实现，故又称数据,存储结构,。,存储结构是逻辑结构在存储器中的映象,完整的数据结构,数据元素的映象,关系的映象,32,(1),数据元素的映象,位串：元素或结点，表示一个数据元素，是数据元素在计算机中的映象。,子位串：,位串中对应各个,数据项,的,数据域,。,(2),关系的映象,关系的最小单位是一个,的有序对,顺序,映象,借助元素在存储器中的,相对位置,来,表示数据元素间的逻辑关系,链式,映象,借助指示元素存储地址的,指针,表示,数据元素间的逻辑关系,33,数据元素的映象方法：,用二进制位,(,bit,),串表示数据元素。,(321),10,=(501),8,=(101000001),2,A =(101),8,=(001000001),2,34,关系的映象方法：,（表示,x,y,的方法）,顺序映象：,以,相对的存储位置,表示逻辑关系,令,y,的存储位置和,x,的存储位置之间差一个,常量,C,而,C,是一个,隐含值,，整个存储结构中只含,数据元素本身,的信息。,x,y,35,非顺序映象：,以,附加信息,(,指针,),表示逻辑关系,需要用一个,指示元素存储地址的指针,指示,y,的存储位置。,y x,36,元素,n,.,元素,i,.,元素,2,元素,1,L0,L0+m,L0+(i-1)*m,L0+（n-1)*m,存储地址,存储内容,Loc(,元素,i)=L0+,（,i-1,）*,m,顺序存储结构,37,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,1345,h,存储地址,存储内容,指针,1345,元素,1,1400,1346,元素,4,.,.,.,1400,元素,2,1536,.,.,.,1536,元素,3,1346,链式存储结构,h,38,在不同的编程环境中，存储结构可有不同的描述方法。,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的,数据类型,描述。称之为,“,虚拟存储结构,”,【,例,】,以三个带有次序关系的整数表示一个长整数时，可利用,C,语言中提供的整数数组类型,typedef,int,Long_int,3,定义长整数为,:,数据的逻辑结构与存储结构密切相关,算法设计 数据,(,逻辑,),结构,算法实现 存储结构,39,