狠狠撸

叶核亚
数据结构（ Java
版）
（第 3 版）

数据结构（ Java 版）（第 3
版）
? 第 1 章绪论
? 第 2 章线性表
? 第 3 章串
? 第 4 章栈与队列
? 第 5 章数组和广义表
? 第 6 章树和二叉树
? 第 7 章图
? 第 8 章查找
? 第 9 章排序
? 第 10 章综合应用设计

《数据结构（ Java 版）（第 3 版）》
第 1 章绪论
? 1.1 数据结构的基本概念
? 1.2 算法
? 1.3 Java开发运行环境

目的和要求
? 目的：勾勒数据结构课程的轮廓。
? 内容：数据结构概念，算法设计与分析。
? 要求：理解数据结构基本概念，理解抽象数
据类型概念；熟悉算法设计和分析方法。
掌握编辑、编译、运行 Java Application
程序的基本技能。
? 重点：数据的逻辑结构和存储结构概念。
? 难点：抽象数据类型，算法分析。
? 实验：简单算法设计，回顾 Java++ 语言的
基本语法和面向对象基本概念。

1.1 数据结构的基本概念
1.1.1 为什么要学习数据结构
1.1.2 什么是数据结构
1.1.3 数据类型与抽象数据类型

1.1.1 为什么要学习数据
结构
? 软件设计是计算机学科各个领域的核心。
软件设计时要考虑的首要问题是数据的
表示、组织和处理方法。数据结构设计
和算法设计是软件系统设计的核心。
? “ 数据结构十算法 = 程序”。

1.1.2 什么是数据结
构
1. 数据（ data ）、数据元素（ data
element ）、数据项（ data
item ）。
2. 数据结构（ data structure ）指数
据元素之间存在的关系。

1. 数据的逻辑结构
（ 1 ）线性结构：数据元素只有一个前驱数据元素和一
个后继数据元素。
（ 2 ）树结构：每个数据元素只有一个前驱数据元素，
可有零个或若干个后继数据元素。
（ 3 ）图结构：每个数据元素可有零个或若干个前驱数
据元素，零个或若干个后继数据元素。

（ 1 ）线性结构
学号姓名年龄
20020001 王红 18
20020002 张明 19
20020003 吴宁 18
20020004 秦风 17
表 1-1 学生信息表

（ 3 ）图结构
图 1-3 　南京飞往昆明的航班路线
图

2. 数据的存储结构
（ 1 ）顺序存储结构
（ 2 ）链式存储结构

3. 数据操作
1. 初始化。
2. 判断是否空状态。
3. 求长度：统计元素个数。
4. 包含：判断是否包含指定元素。
5. 遍历：按某种次序访问所有元素，每个元
素只被访问一次。
6. 取值：获取指定元素值。
7. 置值：设置指定元素值。
8. 插入：增加指定元素。
9. 删除：移去指定元素。

1.1.3 数据类型与抽象数据类
型
1. 数据类型（ data type ）是指一个类型和
定义在这个类型上的操作集合。
2. 抽象数据类型（ Abstract Data Type ，
ADT ）是指一个逻辑概念上的类型和这
个类型上的操作集合。

复数抽象数据类型
ADT Complex
{
double real,imag; // 实部和
虚部
Complex(real,imag);
Complex add(Complex c); // 加
法
Complex sub(Complex c); // 减
法

ADT Set
{ 数据：集合中有 n （ n≥0 ）个数据元素，元素类型
为 T
操作：
boolean isEmpty(); // 判断集合是否为空
int size (); // 返回集合的元素
个数
boolean contains(T x); // 判断集合是否包含元
素 x
boolean add(T x); // 增加元素 x
boolean remove(T x); // 删除首次出现的元素
x
void clear(); // 删除集合所有元素
void print(); // 输出集合中所有元
素
boolean equals(Set s); // 比较集合是否相等
boolean containsAll(Set s);
// 判断是否包含 s 中的所有元素， s 是
否子集

1.1.6 用 Java 语言描述数据
结构
public interface SSet<T>
{ // 集合接口， T 是泛型参数，指定元
素类型
boolean isEmpty(); // 判断集合是否为空
int size(); // 返回集合的元素个数
String toString(); // 返回集合元素的描述字符
串
T search(T key); // 查找，返回关键字为
key 元素
boolean contain(T x); // 判断集合是否包含元素 x
void add(T x); // 增加元素 x

1.2 算法
1.2.1 什么是算法
1.2.2 算法分析
1.2.3 算法设计

1.2.1 什么是算法
1. 算法定义
a. 有穷性
b. 确定性
c. 输入
d. 输出
e. 可行性
2. 算法设计目标
a. 正确性
b. 可读性
c. 健壮性
d. 高时间效率
e. 高空间效率

3. 算法描述
元素 search( 关键字 key)
{
e = 数据序列的第一个元素 ;
while ( 数据序列未结束 && e 的关键字不是
key)
e = 数据序列的下一个元素 ;
返回查找到的元素或查找不成功标记 ;
}

4. 算法与数据结构
图 1-6 线性表插入操作

1.2.2 算法分析
1.度量算法的时间效率
算法的时间效率指算法的执行时间随问题规模
的增长而增长的趋势，通常采用时间复杂度来度
量算法的时间效率。
T(n)=O(f(n))
2.度量算法的空间效率
空间复杂度指算法在执行时为解决问题所需要
的额外内存空间，不包括输入数据所占用的存储
空间。
S(n)=O(f(n))

表 1-2 时间复杂度随 n 变
化情况的比较
时间复杂
度
n=8(23
) n=10 n=100 n=1000
O(1) 1 1 1 1
O(log2
n) 3 3.322 6.644 9.966
O(n) 8 10 100 1000
O(nlog2
n) 24 33.22 664.4 9966
O(n2
) 64 100 10000 106

1. 一个简单语句的时间复杂度为 O(1) 。
int count=0;
1. 一个循环的时间复杂度为 O(n) 。
int n=8, count=0;
for (int i=1; i<=n; i++)
count++;
1. 时间复杂度为 O(log2 n) 的循环语句。
int n=8, count=0;
for (int i=1; i<=n; i*=2)
count++;
1. 时间复杂度为 O(n2
) 的二重循环。
int n=8, count=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
count++;

【例 1.1 】算法时间复杂度分
析。
5. 时间复杂度为 O(nlog2n) 的二重循环。
int n=8, count=0;
for (int j=1; j<=n; j++)
count++;
循环次数为。时间复杂度为
O(nlog2n) 。
6. 时间复杂度为 O(n) 的二重循环。
int n=8, count=0;
for (int j=1; j<=i; j++)
count++; )(2
2log
1
nO
n
i
i
=∑=
)log( 2
log
1
2
nnOn
n
i
=∑=

1.2.3 算法设计
【例 1.2 】求两个整数的最大公约
数。
说明算法的必要性。
① 质因数分解法。已知
则
② 更相减损术。
(91,49)=(42,49)=(42,7)=7
③ 欧几里德（ Euclid ）的
辗转相除法。
232
753226460 ×××=
115312375 32
××=
4553)12375,26460( 2
=×=最大公约数

【例 1.3 】数组的顺序查找算
法。
a. 基本数据类型数组的顺序查找算法实现
b. 对象数组的顺序查找算法实现
public class Object
{
// 比较当前对象与 obj 是否相等
public boolean equals(Object obj)
{ return (this == obj);
// 若两个对象引用同一个实例，返回
true
}
}

public final class Integer extends Number
implements Comparable<Integer>
{
private final int value;
public boolean equals(Object obj)
{ // 覆盖 Object 类中方
法
if (obj instanceof Integer)
return value ==
((Integer)obj).intValue();
// 比较两个 Integer 对象
的值
return false;
}

③ 理解数组的动态特性和引用模
型
图 1-7 一维数组的引用模型

public static void swap(Object[] value, int i, int
j) // 交换下标为 i 、 j 的两个数组元
素
{
if (i!=j) // 若 i 、 j 超出 0 ～
value.length-1 范围，将抛出数组下标越界异常
{ Object temp = value[j];
value[j] = value[i];
value[i] = temp;
}
}

public static int[] concat(int x[], int y[]) //
合并数组 x 和 y 中的元素，返回新创建的数组
{
int i, temp[] = new int[x.length+y.length];
for (i=0; i<x.length; i++)
temp[i] = x[i];
for (int j=0; j<y.length; j++)
temp[i+j] = y[j];
return temp;
}

④ 理解运行时多态性
Object obj=new Integer(123);
// 父类对象 obj 引用子类 Integer 实例
System.out.println(obj.toString()); // 运行时多
态性，执行子类 Integer 的 toString() 方法
obj=new String("123");
System.out.println(obj.toString());
public static void print(Object[] value)
public static int indexOf(Object[] value,
Object key)

【例 1.4 】排序数组的顺序查
找算法。
① 对基本数据类型的排序数组进行顺序查找
Java 定义 < 、 <= 、 > 、 >= 关系运算符比较两
个基本数据类型数据值的大小。
② 对引用数据类型的排序数组进行顺序查找
对象用 Comparable 接口中的 compareTo() 方
法比较大小。
public interface Comparable<T>// 可比较接口
{
int compareTo(T obj)// 约定比较对象大小的规
则
}

public final class Integer extends Number
implements Comparable<Integer>
{
public int compareTo(Integer iobj)
// 比较两个对象值大小，返回 -1 、 0 或 1
{
return (this.value < iobj.value? -1 :
(this.value== iobj.value ? 0:1));
}
}

public final class String extends Object
implements Serializable,
Comparable<String>, CharSequence
{
public int compareTo(String s)
// 比较字符串的大小，实现 Comparable 接口
public int compareToIgnoreCase(String s)
// 比较字符串的大小，忽略字母大小写
}

例 1.5 判断给定字符串是否为
Java 关键字。

例 1.6 排序算法及其必要
性。
1. 排序算法的必要
性
2. 直接插入排序
3. 直接选择排序

1.3.1 JDK
1.3.2 MyEclipse
要求：掌握编辑、编译、运行 Java
Application 程序的基本技能。
重点：编辑、编译、运行 Java 程序。
难点：包， MyEclipse 的项目、工作区，
程序调试技术。
1.3 Java 开发运行环
境

1.3.1 JDK
1. 安装 JDK
2. 设置环境变量
a. 在 Windows XP 中设置环境变量
b. 设置环境变量的批命令
3. 编译和运行 Java 程序
a. 执行批命令设置环境变量
b. 编译
c. 运行 Application 应用程序
d. 命令行参数

4. 包
（ 1 ）包的概念
（ 2 ） Java API 的常用包
（ 3 ）引用包中的类
（ 4 ）查看 Java API
（ 5 ）查看 Java API 源程序及包等级
（ 6 ）导入包
（ 7 ）声明类所在的包
【例 1.7 】创建及使用 dataStructure
包。
（ 8 ）默认包路径
（ 9 ） Java 源程序结构
（ 10 ）包可以压缩成 jar 文件

1.3.2 MyEclipse
1. MyEclipse 集成开发环境
（ 1 ）安装 MyEclipse 并启动
（ 2 ）界面
（ 3 ）代码提示和源代码查看
（ 4 ）项目和工作区

2. 创建 Java 项目并运行
（ 1 ）新建 Java 项目
（ 2 ）新建 Java 类
（ 3 ）编辑、编译和运行
（ 4 ）重构
（ 5 ）切换工作区
（ 6 ）访问其他项目中的类和添加
JAR 包
（ 7 ）选择运行的类和设置命令行参

3. 程序调试技术
1. 程序错误、发现时刻及错误处理原
则
语法错、语义错、逻辑错
1. 程序运行方式
a. 正常运行
b. 单步运行
c. 分段运行
3. 调试过程
a. 设置断点
b. 调试界面
c. 单步或分段运行
d. 查看变量的当前值

狠狠撸

第01章绪论(java版)

More Related Content

第01章绪论(java版)

狠狠撸

第01章 绪论(java版)

More Related Content

第01章 绪论(java版)

第01章绪论(java版)

第01章绪论(java版)