数据结构(牛小飞)第1章引论.pptVIP

链式存储结构存储内容L0元素n……..元素2……..元素3元素1200600199200600280200600385200600460200600570P物理结构逻辑结构集合图状树形顺序存储结构线性链式存储结构数据结构数据操作数据操作是指对一种数据结构中的数据元素进行各种运算和处理。每种数据结构都有一组数据操作。基本操作有：初始化判断是否空状态求长度：统计元素个数包含：判断是否包含指定元素遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入、删除等。如何实现逻辑结构的常用操作贰如何使用存储结构实现逻辑结构壹如何评价？叁学习内容主要学习以下四种数据结构的实现方法：01线性表2.栈和队列3.树4.图02散列及排序问题的算法设计03通过学习，可以深刻理解数据结构的作用，基本具备针对具体问题设计选择数据结构的能力。04学习内容引论：数据、数据元素、数据结构、数据类型的概念；递归程序；Java描述数据结构1算法分析：时间复杂度和空间复杂度2线性表：线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；线性表的应用。3栈和队列：栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用。4学习内容树和二叉树：树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码。散列：哈希表；图：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。学习内容学习内容排序：介绍插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。递归简论(教材1.3)大部分数学函数由简单公式描述：C=5(F-32)/9将华氏温度转换成摄氏温度。f(x)=0ifx=0f(x)=2f(x-1)+x2ifx0当一个函数用它自己来定义时就称为是递归的。递归函数publicintf(intx){if(x==0)return0;else return2*f(x-1)+x*x;}//基准情况//递归调用举例1f(x)=0ifx=0f(x)=2f(x-1)+x2ifx0递归函数阶乘n！，n=0,1,2,3…Basis:0!=1Induction:n!=n(n-1)! 4！=4×3！3！=3×2！2！=2×1！1！=1×0!0!=1publicintfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}举例2递归函数xn，n=0,1,2,3…Basis:x0=1Induction:xn=xn-1x x4=x3xx3=x2xx2=x1xx1=x0xx0=1intpower(floatx,intn){if(n==0)return1;return(power(x,n-1)*x);}举例3递归函数Fibonacci数列 0若n=0Fib(n)=1若n=1 Fib(n-1)+Fib(n-2)0,1,1,2,3,5…举例4递归函数Ackerman函数n+1若m=0Ack(m,n)=Ack(m-1,1)若n=0Ack(m-1,Ack(m,n-1))其它举例5********主讲人：牛小飞E_mail:niujiaoxue@163.comPassword:niujiaoxue123课程信息理论教学：48学时实践教学：上机8学时2周集中课程设计《数据结构、算法与应用:Java语言描述》SartajSanhi著汪诗林等译