数据结构(清华)第一章绪论.ppt

数据结构,教材:数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社,计算机科学与技术学院,开设本课程的背景：数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的存储结构以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。,本课程讲述的主要内容：分别讲述数据结构的基本概念、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序等内容。学习本课程的基本方法：,上课认真听讲；仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；独立完成每个章节的练习题和作业题。,1.1什么是数据结构,第一章绪论,1.3算法和算法分析,1.2基本概念和术语,学习提要：1.熟悉各名词术语的含义，掌握基本概念。2.了解抽象数据类型的定义、表示和实现方法。3.理解算法五个要素的确切含义，掌握估算算法时间复杂度的方法。重难点内容：数据的逻辑结构、数据存储结构、时间复杂度的估算方法,1.1什么是数据结构,程序设计:为计算机处理问题编制一组指令集。算法:处理问题的策略。数据结构:问题的数学模型。,程序=算法+数据结构,数值计算的程序设计问题：例如：结构静力分析计算线性代数方程组预报人口增长情况微分方程,非数值计算的程序设计问题：,算法:?模型：？,基本操作是“比较两个数的大小”,取决于整数值的范围,例1：求一组(n个)整数中的最大值。,例2书目自动检索系统,书目文件,算法：需要检索的书目？如何检索？用户界面？模型：？,例3人机对奕问题,算法：对奕的规则和策略模型：？,例4教学计划编排问题,算法：如何确定课程的次序关系?模型：？,概括地说：,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,1.2基本概念和术语,一、数据与数据结构,二、数据类型,三、抽象数据类型,数据（data)：所有能被输入到计算机中，且被计算机处理的符号的集合，是计算机操作的对象的总称。数据元素（dataelement）：是数据（集合）中的一个“个体”，是数据的基本单位，由若干个数据项组成，也称结点、元素、顶点或记录。,一、数据与数据结构,数据项：,是数据结构中讨论的最小单位。,例如：,描述一个学生基本信息的数据元素可以是,称之为组合项,数据结构(datastructure)：是指互相之间存在着一种或多种关系的数据元素的集合。或者说，数据结构是带结构的数据元素的集合。,例：一个含12位数的十进制数可以用三个4位的十进制数表示3214,6587,9345a1(3214),a2(6587),a3(9345)在a1、a2、a3之间存在“次序”关系：a1,a2、a2,a3,3214，6587，9345a1a2a3,6587，3214，9345a2a1a3,又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6,行的次序关系:列的次序关系:,row=,col=,a1a3a5a2a4a6,a1a2a3a4a5a6,再例，在一维数组a1,a2,a3,a4,a5,a6的数据元素之间存在如下的次序关系:,|i=1,2,3,4,5,可见，不同的“关系”构成不同的“结构”。,集合结构：数据元素间“同属于一个集合”,数据的逻辑结构可归结为以下四类:,线性结构：一个对一个,树形结构：一个对多个,图状结构：多个对多个,数据结构的形式定义为:,数据结构是一个二元组,Data_Structure=(D,S),其中:D是数据元素的有限集，S是D上关系的有限集。,例：在计算机科学中，复数可取如下定义Complex=（C，R）其中，C是含两个实数集合c1，c2；R=P，P是定义在集合C上的一种关系。,数据的逻辑结构：只抽象反映数据元素的逻辑关系。,数据的存储结构：逻辑结构在存储器中的映象。,“数据元素”的映象？,“关系”的映象？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素。,(321)10=(501)8=(101000001)2,A=(101)8=(001000001)2,关系的映象方法：,（表示x,y的方法）,1、顺序映象,以相对的存储位置表示后继关系。,例如:令y的存储位置和x的存储位置之间差一个常量C。,而C是一个隐含值，整个存储结构中只含数据元素本身的信息,xy,2、链式映象,以附加信息(指针)表示后继关系。,需要用一个和x在一起的附加信息指示y的存储位置。,yx,例如：复数z1=3.0-2.3i，z2=-0.7+4.8i的存储结构。,顺序存储结构,链式存储结构,二、数据类型,在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。,例：C语言中，提供int,char,float等基本数据类型，数组、结构体、共用体、枚举等构造数据类型指针、空(void)类型等。用户也可用typedef自己定义数据类型,typedefstructintnum;charname20;floatscore;STUDENT;STUDENTstu1,stu2,*p;,数据类型是一个值的集合和定义在此集合上的一组操作的总称。,不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,三、抽象数据类型(AbstractDataType简称ADT),ADT定义：指一个数学模型以及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。,例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型。,ADT的描述方法：,抽象数据类型可用三元组（D，S，P）表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。,ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名,其中基本操作的定义格式为:,基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,赋值参数:只为操作提供输入值。引用参数:以s=0;,T(n)=(1),T(n)=O(n),(1)(log2n)(n)(n2)(n3)(2n),例3for(i=1;i=n;+i)+x;s+=x;,例4for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;,T(n)=O(n2),change=FALSE;/change为元素进行交换标志for(j=0;jaj+1)ajaj+1;change=TRUE;/一趟起泡,voidbubble_sort(int-i)/bubble_sort,基本操作:交换操作,时间复杂