数据结构牛小飞第1章引论

1、 主讲人：牛小飞e_mail: niujiaoxue163. compassword: niujiaoxue123e_mail: tel:论教学：理论教学：48学时学时实践教学：上机实践教学：上机8学时学时 2周集中课程设计周集中课程设计数据结构、算法与应用数据结构、算法与应用:java语言描述语言描述sartaj sanhi 著著 汪诗林等译汪诗林等译 机械工业出版社机械工业出版社 数据结构数据结构 java语言描述语言描述sichael main著著 机械工业出版社机械工业出版社 课程信息课程信息数据结构数据结构( java版版)(第第2版版) 叶核亚编著叶核亚编

2、著 电子工业出版社电子工业出版社 数据结构数据结构-java语言描述语言描述 朱战立编著朱战立编著 清华大学出版社清华大学出版社 要求要求不迟到、不旷课，良好的课堂纪律不迟到、不旷课，良好的课堂纪律作业按时交、字迹工整作业按时交、字迹工整实验认真准备实验认真准备课前预习、课后复习课前预习、课后复习数据结构相关概念数据结构相关概念引论引论小结和作业小结和作业本课程学习内容本课程学习内容用用javajava语言描述数据结构语言描述数据结构递归简论递归简论相关概念数据（data）2、形式3、含义数字、字符、图形、图像、音频、视频3089.2数据类型：int double char张三1、定义数据是描

3、述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。数据类型数据类型数据类型是指一个值的集合和定义在这个值集上的操作的集合。高级程序设计语言通常预定义一些基本数据类型和构造数据类型。java语言的基本数据类型有整数类型、浮点数类型、字符类型、布尔类型。构造类型(引用类型)有数组、类和接口。数据数据数据元素是数据的基本单位基本单位。一个数据元素可以是一个不可分割的原子项，也可以由多个数据项组成。 数据项是数据元素中有独立含义的、不可分割的最小标识单位最小标识单位。一个整数、一个字符都是原子项；一个学生数据元素由学号、姓名、性别和出生日期等数据项组成。结构（stru

4、cture）结构：关系（relation）数据结构data_structure=(d, s)d: a1, a2, a3, , ans: , , d：1, 7, 8, 9d：“abc”, “city”d：“张明”，“男”，19， “计算机”， “王明辉”，“男”，20，“法律”，从关系或结构分，数据结构可归结为以下四类:集合结构 线性结构树形结构 图状结构逻辑结构da1, a2, , ans 集合da1, a2, , ans |ai-1 ,ai d, i=2,.,n 线性da1, a2, ,ans |i j 对每个j，存在唯一的i有 树形da1, a2, ,ans |ai d, aj d 图状例

5、1有数据结构:d=1, 2, 3, 4, 5 s=, , , 什么数据结构?逻辑结构例1d=1, 2, 3, 4, 5 s=, , , 12345逻辑结构例2有数据结构:d=1, 2, 3, 4, 5, 6, 7 s=, , , , , 什么数据结构?逻辑结构例2d=1, 2, 3, 4, 5, 6, 7 s=, , , , , 1234675逻辑结构例3有数据结构:d=1, 2, 3, 4, 5, 6, 7,8 s=row, colrow=, , , , , col=, , , 什么数据结构?逻辑结构例31234675d=1, 2, 3, 4, 5, 6, 7,8 row=, , , , ,

6、 col=, , , 8逻辑结构物理结构数据在内存中如何表示？数据之间的关系在内存中如何表示？表示x, y的方法两种存储结构顺序映像-顺序存储结构 链式映像-链式存储结构存储器模型1、电子元器件构成存储单元2、地址寄存器4、地址总线6、数据寄存器物理模型逻辑模型5、数据总线3、地址译码器0123n存储器模型存储器模型假设有假设有5位同学的成绩表：位同学的成绩表：2006001 992006002 802006003 852006004 602006005 70顺序存储结构顺序存储结构元素元素n n.元素元素i i.元素元素2 2元素元素1 1lolo+mlo+(i-1)*mlo+（n-1)*m

7、存储地址存储地址存储内容存储内容2006001 992006002 802006003 852006004 602006005 70链式存储结构链式存储结构存储内容存储内容l0元素元素n n.元素元素2 2.元素元素3 3元素元素1 12006001 992006002 802006003 852006004 602006005 70p数据结构物理结构逻辑结构集合线性树形图状顺序存储结构链式存储结构数据操作数据操作数据操作是指对一种数据结构中的数据元素进行数据操作是指对一种数据结构中的数据元素进行各种运算和处理。每种数据结构都有一组数据操各种运算和处理。每种数据结构都有一组数据操作。基本操作有

8、：作。基本操作有：初始化初始化判断是否空状态判断是否空状态求长度：统计元素个数求长度：统计元素个数包含：判断是否包含指定元素包含：判断是否包含指定元素遍历：按某种次序访问所有元素，每个元素只被访问一次。遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。取值：获取指定元素值。置值：设置指定元素值。置值：设置指定元素值。插入、删除等。插入、删除等。学习内容学习内容1、如何使用存储结构实现逻辑结构、如何使用存储结构实现逻辑结构2、如何实现逻辑结构的常用操作、如何实现逻辑结构的常用操作3、如何评价？、如何评价？学习内容学习内容主要学习以下四种数据结构的实现方法：主要学习以下四种

9、数据结构的实现方法：1.线性表线性表 2.栈和队列栈和队列 3.树树 4.图图散列及排序问题的算法设计散列及排序问题的算法设计 通过学习，可以深刻理解数据结构的作用，通过学习，可以深刻理解数据结构的作用，基本具备针对具体问题设计选择数据结构的能基本具备针对具体问题设计选择数据结构的能力。力。n引论： 数据、数据元素、数据结构、数据类型的概念；递归程序；java描述数据结构n算法分析：时间复杂度和空间复杂度n线性表：线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；线性表的应用。n栈和队列：栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用。学习内容学习内

10、容n树和二叉树：树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码。n散列：哈希表；n图：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。学习内容学习内容学习内容学习内容n排序：介绍插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。递归简论递归简论(教材教材1.3)大部分数学函数由简单公式描述：大部分数学函数由简单公式描述： c=5(f-32)/9 将华氏温度转换成摄氏温度。将华氏温度转换成摄氏温度。f(x)=0 if x=0f(x

11、)=2f(x-1)+x2 if x0 当一个函数用它自己来定义时就称为是递归的。当一个函数用它自己来定义时就称为是递归的。public int f(int x) if(x=0) return 0; else return 2*f(x-1)+x*x;/基准情况基准情况/递归调用递归调用递归函数递归函数举例1f(x)=0 if x=0f(x)=2f(x-1)+x2 if x0 阶乘 n！，n=0,1,2,3basis: 0!=1induction: n!=n(n -1)! 4！= 43！3！= 32！2！= 21！1！= 10!0! = 1public int factorial(int n) i

12、f( 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=1int power(float x, int n) if( n = = 0 ) return 1; return (power(x, n-1)*x);举例3fibonacci数列 0 若n=0fib(n) = 1 若n=1 fib(n - 1) + fib(n - 2)0, 1, 1, 2, 3, 5递归函数

13、递归函数举例4ackerman函数 n + 1 若m=0ack(m, n)= ack(m - 1,1) 若n=0 ack(m - 1, ack(m, n - 1) 其它递归函数递归函数举例5一个规模为n的问题可以分解为若干个规模小于n的相同问题递归体现为一个函数调用自身，即函数的递归调用函数的递归调用可以用栈来实现递归简论递归简论用用javajava语言描述数据结构语言描述数据结构public class 线性表线性表/树树/图图 boolean isempty( );int length( );boolean contain(object obj);boolean add(elementty

14、pe element);boolean remove(object obj);public int thesize, count;用用javajava语言描述数据结构语言描述数据结构泛型特性构件泛型特性构件(教材教材1.4) 利用利用java实现泛型特性实现泛型特性(教材教材1.5) java泛型泛型n面向对象的一个重要特点是对代码重用的支持。n支持这个目标的一个重要机制就是泛型机制(generic mechanism)：如果除去对象的基本类型外，实现方法是相同的，就可以用泛型实现(generic implementation)来描述这种基本功能。javajava泛型泛型void swap(i

15、nt 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;javajava泛型泛型举例1javajava泛型泛型public anytype extends comparable 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)

16、for(int i=a.length-1;i0;i-)for(int j=0;jaj+1)0)swapreferences(a,j,j+1);带有限制的通配符举例2java泛型（generics）是jdk 5中引入的一个新特性，允许在定义类和接口的时候使用类型参数（type parameter）。声明的类型参数在使用时用具体的类型来替换。 泛型类与一般的java类基本相同，只是在类和接口定义上多出来了用声明的类型参数。javajava泛型泛型（1）简单的泛型类）简单的泛型类public class genericmemorycell public anytype read( ) return

17、storedvalue; public void write(anytype x) storedvalue=x; private anytype storedvalue; 当指定一个泛型类时，类的声明则包含一个或多个类型参数，这些参数被放到类名后面的一对尖括号内。举例3public class myclassanytype extends comparable带有限制的通配符带有限制的通配符（2）使用）使用object表示泛型表示泛型n泛型memorycell类public class memorycell public object read( ) return storedvalue; p

18、ublic void write(object x) storedvalue=x; private object storedvalue;java中的基本思想就是可以通过使用像object这样适当的超类来实现泛型类。举例4（2）使用）使用object表示泛型表示泛型n测试memorycell类public class testmemorycell public static void main(string args) memorycell m=new memorycell();m.write(“37”);string val=(string)m.read();system.out.print

19、ln(val); 不能使用基本类型不能使用基本类型（2）使用）使用object表示泛型表示泛型n泛型泛型memorycell类类public class memorycell public object read( ) return storedvalue; public void write(object x) storedvalue=x; private object storedvalue;只有引用类型能与object相容。引用类型:数组、接口、类（3）基本类型的包装）基本类型的包装nint类型的包装是integernbyte,short,long,float,double,boolean类型的包装为第一个字符大写，其余不变。ncha