第01章 数据结构（Java版）（第2版）绪论

叶核亚数据结构（Java版）

（第2版）数据结构（Java版）（第2版）第0章Java程序设计基础第1章绪论 第2章线性表第3章栈与队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第10章综合应用设计第11章Java开发运行环境第1章绪论1.1数据结构的基本概念1.2算法目的：勾勒数据结构课程的轮廓。要求：掌握数据结构基本概念，理解抽象数 据类型概念；熟悉算法设计和分析方 法。重点：数据的逻辑结构和存储结构。难点：抽象数据类型，算法分析。数据结构（Java版）（第2版）》1.1数据结构的基本概念1.1.1为什么要学习数据结构1.1.2什么是数据结构1.1.3数据的逻辑结构1.1.4数据的存储结构1.1.5数据操作1.1.6用Java语言描述数据结构数据结构（Java版）（第2版）》1.1.1为什么要学习数据结构软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。“数据结构十算法=程序”。数据结构（Java版）（第2版）》1.1.2什么是数据结构数据、数据元素、数据项数据类型（datatype）是指一个类型和定义在这个类型上的操作集合。数据结构（datastructure）指数据元素之间存在的关系。抽象数据类型（AbstractDataType，ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。数据结构（Java版）（第2版）》1.1.3数据的逻辑结构线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。数据结构（Java版）（第2版）》1.线性结构学号姓名年龄20020001王红1820020002张明1920020003吴宁1820020004秦风17表1.1学生信息表

数据结构（Java版）（第2版）》2.树结构数据结构（Java版）（第2版）》3.图结构图1.3南京飞往昆明的航班路线图数据结构（Java版）（第2版）》1.1.4数据的存储结构顺序存储结构链式存储结构图1.4线性表(A,B,C,D)的两种存储结构数据结构（Java版）（第2版）》1.1.5数据的操作初始化。判断是否空状态。求长度：统计元素个数。包含：判断是否包含指定元素。遍历：按某种次序访问所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入：增加指定元素。删除：移去指定元素。数据结构（Java版）（第2版）》1.1.6用Java语言描述数据结构publicinterfaceStructure<E>{//E是泛型参数，指定元素类型

boolean

isEmpty();//判断是否为空

intlength();//返回元素个数

boolean

contain(Object

obj);//判断是否包含obj对象

boolean

add(Eelement);//插入元素

boolean

remove(Object

obj);//移去首次出现的obj对象

voidclear();//清空}数据结构（Java版）（第2版）》1.2算法1.2.1什么是算法1.2.2算法分析1.2.3算法设计实例1.2.4递归算法数据结构（Java版）（第2版）》1.2.1什么是算法算法定义有穷性确定性输入输出可行性算法与数据结构算法设计目标正确性可读性健壮性高时间效率高空间效率算法描述数据结构（Java版）（第2版）》图1.6线性表插入操作数据结构（Java版）（第2版）》1.2.2算法分析度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n))度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。S(n)=O(f(n))

数据结构（Java版）（第2版）》表1.2时间复杂度随n变化情况的比较时间复杂度n=8(23)n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(nlog2n)2433.22664.49966O(n2)6410010000106数据结构（Java版）（第2版）》一个简单语句的时间复杂度为O(1)。intcount=0;一个循环的时间复杂度为O(n)。intn=8,count=0;for(inti=1;i<=n;i++)count++;时间复杂度为O(log2

n)的循环语句。intn=8,count=0;for(inti=1;i<=n;i*=2)count++;时间复杂度为O(n2)的二重循环。intn=8,count=0;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)count++;【例1.1】算法时间复杂度分析。数据结构（Java版）（第2版）》时间复杂度为O(nlog2n)的二重循环。intn=8,count=0;for(inti=1;i<=n;i*=2)for(intj=1;j<=n;j++)count++;循环次数为。时间复杂度为O(nlog2n)。时间复杂度为O(n)的二重循环。intn=8,count=0;for(inti=1;i<=n;i*=2)for(intj=1;j<=i;j++)count++;总的循环次数为。时间复杂度为O(n)。数据结构（Java版）（第2版）》1.2.3算法设计实例【例1.2】交换两个变量值。

【例1.3】数组的顺序查找，以及对象比较相等方法。

【例1.4】已排序数组的顺序查找，以及对象比较大小方法。数据结构（Jav