数据结构(牛小飞)第1章引论.ppt
数据结构,主讲人：牛小飞E_mail:Password:niujiaoxue123,理论教学：48学时,实践教学：上机8学时 2周集中课程设计,数据结构、算法与应用:Java语言描述Sartaj Sanhi 著 汪诗林等译 机械工业出版社,数据结构 Java语言描述Sichael Main著 机械工业出版社,课程信息,数据结构(Java版)(第2版)叶核亚编著 电子工业出版社,数据结构-Java语言描述 朱战立编著 清华大学出版社,要求,不迟到、不旷课，良好的课堂纪律作业按时交、字迹工整实验认真准备课前预习、课后复习,数据结构相关概念,引论,小结和作业,本课程学习内容,用Java语言描述数据结构,递归简论,相关概念数据（Data）,2、形式,3、含义,数字、字符、图形、图像、音频、视频,30,89.2,数据类型：int double char,张三,1、定义,数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。,数据类型,数据类型是指一个值的集合和定义在这个值集上的操作的集合。,高级程序设计语言通常预定义一些基本数据类型和构造数据类型。,Java语言的基本数据类型有整数类型、浮点数类型、字符类型、布尔类型。构造类型(引用类型)有数组、类和接口。,数据,数据元素是数据的基本单位。一个数据元素可以是一个不可分割的原子项，也可以由多个数据项组成。,数据项是数据元素中有独立含义的、不可分割的最小标识单位。,一个整数、一个字符都是原子项；一个学生数据元素由学号、姓名、性别和出生日期等数据项组成。,结构（Structure）,结构：关系（Relation）,数据结构,Data_Structure=(D,S),D:a1,a2,a3,an,S:,D：1,7,8,9,D：“ABC”,“City”,D：“张明”，“男”，19，“计算机”，“王明辉”，“男”，20，“法律”，,从关系或结构分，数据结构可归结为以下四类:,集合结构 线性结构树形结构 图状结构,逻辑结构,Da1,a2,an,S,集合,Da1,a2,an,S|ai-1,ai D,i=2,.,n,线性,Da1,a2,an,S|i j 对每个j，存在唯一的i有,树形,Da1,a2,an,S|ai D,aj D,图状,例1,有数据结构:D=1,2,3,4,5 S=,什么数据结构?,逻辑结构,例1,D=1,2,3,4,5 S=,1,2,3,4,5,逻辑结构,例2,有数据结构:D=1,2,3,4,5,6,7 S=,什么数据结构?,逻辑结构,例2,D=1,2,3,4,5,6,7 S=,1,2,3,4,6,7,5,逻辑结构,例3,有数据结构:D=1,2,3,4,5,6,7,8 S=row,colrow=,col=,什么数据结构?,逻辑结构,例3,1,2,3,4,6,7,5,D=1,2,3,4,5,6,7,8 row=,col=,8,逻辑结构,物理结构,数据在内存中如何表示？,数据之间的关系在内存中如何表示？,表示x,y的方法,两种存储结构顺序映像-顺序存储结构 链式映像-链式存储结构,存储器模型,1、电子元器件构成存储单元,2、地址寄存器,4、地址总线,6、数据寄存器,物理模型,逻辑模型,5、数据总线,3、地址译码器,存储器模型,假设有5位同学的成绩表：2006001 992006002 802006003 852006004 602006005 70,顺序存储结构,链式存储结构,存储内容,数据结构,物理结构,逻辑结构,集合,线性,树形,图状,顺序存储结构,链式存储结构,数据操作,数据操作是指对一种数据结构中的数据元素进行各种运算和处理。每种数据结构都有一组数据操作。基本操作有：,初始化判断是否空状态求长度：统计元素个数包含：判断是否包含指定元素遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入、删除等。,学习内容,1、如何使用存储结构实现逻辑结构,2、如何实现逻辑结构的常用操作,3、如何评价？,学习内容,主要学习以下四种数据结构的实现方法：,1.线性表 2.栈和队列 3.树 4.图,散列及排序问题的算法设计,通过学习，可以深刻理解数据结构的作用，基本具备针对具体问题设计选择数据结构的能力。,引论：数据、数据元素、数据结构、数据类型的概念；递归程序；Java描述数据结构算法分析：时间复杂度和空间复杂度线性表：线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；线性表的应用。栈和队列：栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用。,学习内容,树和二叉树：树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码。散列：哈希表；图：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。,学习内容,学习内容,排序：介绍插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。,递归简论(教材1.3),大部分数学函数由简单公式描述：C=5(F-32)/9 将华氏温度转换成摄氏温度。,当一个函数用它自己来定义时就称为是递归的。,public int f(int x)if(x=0)return 0;else return 2*f(x-1)+x*x;,/基准情况,/递归调用,递归函数,举例1,阶乘 n！，n=0,1,2,3Basis:0!=1Induction:n!=n(n-1)!,4！=43！3！=32！2！=21！1！=10!0!=1,public int factorial(int n)if(n=0)return 1;return n*factorial(n-1);,递归函数,举例2,递归函数,xn，n=0,1,2,3Basis:x0=1Induction:xn=xn-1x,x4=x3xx3=x2xx2=x1xx1=x0 xx0=1,int power(float x,int n)if(n=0)return 1;return(power(x,n-1)*x);,举例3,递归函数,举例4,递归函数,举例5,一个规模为n的问题可以分解为若干个规模小于n的相同问题,递归体现为一个函数调用自身，即函数的递归调用,函数的递归调用可以用栈来实现,递归简论,用Java语言描述数据结构,public class 线性表/树/图,boolean isEmpty();int length();boolean contain(Object obj);boolean add(ElementType element);boolean remove(Object obj);,public int theSize,count;,用Java语言描述数据结构,泛型特性构件(教材1.4),利用java实现泛型特性(教材1.5),Java泛型,面向对象的一个重要特点是对代码重用的支持。支持这个目标的一个重要机制就是泛型机制(generic mechanism)：如果除去对象的基本类型外，实现方法是相同的，就可以用泛型实现(generic implementation)来描述这种基本功能。,Java泛型,void swap(int a,int i,int j)int temp=ai;ai=aj;aj=temp;,void swap(AnyType a,int i,int j)AnyType temp=ai;ai=aj;aj=temp;,Java泛型,举例1,Java泛型,public void BubbleSort(AnyType a)for(int i=a.length-1;i0;i-)for(int j=0;j0)SwapReferences(a,j,j+1);,public void BubbleSort(int a)for(int i=a.length-1;i0;i-)for(int j=0;jaj+1)0)SwapReferences(a,j,j+1);,举例2,泛型类与一般的Java类基本相同，只是在类和接口定义上多出来了用声明的类型参数。,Java泛型,（1）简单的泛型类,public class GenericMemoryCell public AnyType read()return storedValue;public void write(AnyType x)storedValue=x;private AnyType storedValue;,当指定一个泛型类时，类的声明则包含一个或多个类型参数，这些参数被放到类名后面的一对尖括号内。,举例3,public class myClass,带有限制的通配符,（2）使用object表示泛型,泛型MemoryCell类,public class MemoryCell public Object read()return storedValue;public void write(Object x)storedValue=x;private Object storedValue;,Java中的基本思想就是可以通过使用像Object这样适当的超类来实现泛型类。,举例4,（2）使用object表示泛型,测试MemoryCell类,public class TestMemoryCell public static void main(String args)MemoryCell m=new MemoryCell();m.write(“37”);String val=(String)m.read();System.out.println(val);,不能使用基本类型,（2）使用object表示泛型,泛型MemoryCell类,public class MemoryCell public Object read()return storedValue;public void write(Object x)storedValue=x;private Object storedValue;,只有引用类型能与Object相容。,引用类型:数组、接口、类,（3）基本类型的包装,int类型的包装是Integerbyte,short,long,float,double,boolean类型的包装为第一个字符大写，其余不变。char类型的包装是Character,8中基本类型不能与Object相容。所以，java为这8种基本类型提供了包装类。,每种类型的包装类是不可变的。基本类型不能用做类型参数。GenericMemoryCell是非法的，必须使用包装类。,（3）基本类型的包装,public class TestMemoryCell public static void main(String args)MemoryCell m=new MemoryCell();m.write(new Integer(37);Integer wrapperVal=(Integer)m.read();int val=wrapperVal.intValue();System.out.println(val);,举例5,能否简化?,小结和作业,物理结构,逻辑结构,集合,线性表,树,图,顺序结构,链式结构,数据结构,递归,用Java语言描述数据结构泛型,作业P19：1.1,1.5,1.15,要求：1、独立完成作业2、字迹工整，美观3、按时交作业4、做错了的题下次要改正,小结和作业,练习,2、数据的()包括集合、线性、树和图结构四种类型。,A.存储结构 B.逻辑结构 C.物理结构 D.基本运算,1、数据结构有（）结构和（）结构两种，通常是指（）结构,
