---
marp: true
theme: kurzus
paginate: true
footer: 数据结构 · 第 1 周 · 绪论、基本数据类型
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# 数据结构

## 第 1 周 – 绪论、数据与基本数据类型

Koczka Ferenc 博士 · 埃斯特哈齐·卡罗伊大学 · 2026

---

## 关于主讲教师

- <strong>Koczka Ferenc 博士</strong>，助理教授
- 埃斯特哈齐·卡罗伊大学（Eszterházy Károly Egyetem），匈牙利埃格尔
- 电子邮件：<strong>koczka.ferenc@uni-eszterhazy.hu</strong>
- 答疑：课后，或通过电子邮件预约

> “先解决问题，再写代码。” – John Johnson

<!--
时间安排（讲课，90 分钟）：导入 10' · 算法 15' · 数据类型 35' · 数据结构 30'。
-->

---

<!-- _class: kicsi -->

## 课程安排

| 周 | 主题 | 周 | 主题 |
|---|---|---|---|
| 1 | 绪论、基本数据类型 | 9 | 动态内存、链表 |
| 2 | 效率、查找 | 10 | 带哨兵的链表、双向链表、循环链表 |
| 3 | 数组 | 11 | 链栈与链队列、哈希表 |
| 4 | 字符串 | 12 | 递归 |
| 5 | 排序 I（简单排序） | 13 | 排序 II（归并排序、快速排序） |
| 6 | 集合 | 14 | 树、二叉树、遍历 |
| 7 | 栈 | 15 | 二叉搜索树、堆、总结 |
| 8 | 队列 | 16 | <strong>期末笔试和上机考试</strong> |

每周：<strong>2 学时讲课 + 2 学时实践课</strong>（Java 和 Go）

---

## 考核方式与工具

<div class="ket-hasab">
<div>

### 考核（第 16 周）

- <strong>期末笔试</strong>（理论，60 分钟）
  判断题、选择题、代码阅读、伪代码填空
- <strong>上机考试</strong>（在计算机上）
  用 Java <strong>或</strong> Go 实现一个数据结构

</div>
<div>

### 工具

- <strong>Java</strong> – JDK 17 或更新版本
- <strong>Go</strong> – 1.23 或更新版本
- 编辑器：VS Code、IntelliJ IDEA 或 Eclipse
- 示例程序：`code/java/wXX`、`code/go/wXX`

</div>
</div>

---

## 为什么要学习数据结构？

> <strong>算法 + 数据结构 = 程序</strong>
> – Niklaus Wirth(1976)

- 同一个任务，用<strong>好的</strong>数据结构很快，用<strong>差的</strong>数据结构可能慢得无法使用
- 每一种编程语言都建立在这些基础之上（`ArrayList`、`HashMap`、Go 的 `slice`、`map` …）
- 求职面试中最常见的话题之一
- 后续课程（数据库、操作系统、人工智能）都以这些知识为前提

<div class="doboz tipp">

<strong>目标：</strong>掌握基本的数据结构、它们的操作及其效率 – 并且能够<strong>动手实现</strong>它们。

</div>

---

<!-- _class: fejezet -->

# 问题求解与算法

---

## 问题求解的步骤

![w:1100](kepek/h01_lepesek.svg)

- <strong>规格说明：</strong>输入是什么，输出是什么，必须满足哪些条件？
- <strong>数据结构 + 算法：</strong>如何存储数据，按什么步骤处理数据？
- 本课程讲的就是中间这一步

---

## 算法的概念

<strong>算法：</strong>由有限个定义明确的步骤组成、用于解决某个问题的过程。

算法的特性：

- <strong>有穷性</strong> – 在有限步之后结束
- <strong>确定性</strong> – 每一步都有精确的定义
- <strong>有输入</strong> – 零个或多个数据
- <strong>有输出</strong> – 至少一个结果
- <strong>可行性</strong> – 每一步都能够实际执行
- <strong>通用性</strong> – 解决一类问题，而不只是某一个情况

---

## 算法的描述方法

| 工具 | 优点 | 缺点 |
|---|---|---|
| 自然语言 | 人人都能看懂 | 不精确、冗长 |
| 流程图 | 直观 | 问题较大时难以阅读 |
| <strong>伪代码</strong> | 精确、与语言无关 | 需要学习记号 |
| 程序代码 | 可以执行 | 有语言相关的细节 |

本课程：讲课和笔试中使用<strong>伪代码</strong>，实践课中使用 <strong>Java 和 Go</strong>。

---

<!-- _class: kicsi -->

## 伪代码记号

| 记号 | 含义 |
|---|---|
| `x ← expression` | 赋值 |
| `If condition then … else … End if` | 选择（分支） |
| `While condition … End while` | 当型循环（先判断） |
| `For i ← 1 to n … End for` | 计数循环 |
| `Function Name(parameters) … Return value … End function` | 函数 |
| `Procedure Name(parameters) … End procedure` | 过程（没有返回值） |
| `A[i]` | 数组的第 <em>i</em> 个元素 – <strong>下标从 1 开始</strong> |
| `and`、`or`、`not` · `div`、`mod` | 逻辑运算 · 整除、取余 |

<div class="doboz figyelem">

在 Java 和 Go 中数组下标从 <strong>0</strong> 开始 – 写代码时一定要注意！

</div>

---

<!-- _class: kicsi -->

## 示例：最大公约数（欧几里得算法）

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function GCD(a, b)
  While b ≠ 0
    m ← a mod b
    a ← b
    b ← m
  End while
  Return a
End function
```

| a | b | a mod b |
|---|---|---|
| 1071 | 462 | 147 |
| 462 | 147 | 21 |
| 147 | 21 | 0 |
| <strong>21</strong> | 0 | |

</div>
<div>

<span class="cimke java">Java</span>

```java
static int gcd(int a, int b) {
    while (b != 0) {
        int m = a % b;
        a = b;
        b = m;
    }
    return a;
}
```

<span class="cimke go">Go</span>

```go
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
```

</div>
</div>

<!-- 代码:code/java/w01/Gcd.java、code/go/w01/gcd -->

---

<!-- _class: fejezet -->

# 数据与数据类型

---

## 数据与信息

- <strong>数据：</strong>对现实事物某种属性的记录，是可以被处理的形式
  例如 `37.2`、`"Wuhan"`、`true`
- <strong>信息：</strong>数据在特定语境中的含义
  例如“病人的体温是 37.2 °C”
- 计算机处理的是<strong>数据</strong> – 含义由程序（以及程序员）赋予

### 数据的属性

- <strong>名字</strong>（标识符） – 我们如何引用它：`temperature`
- <strong>类型</strong> – 它能取哪些值，能对它做什么
- <strong>值</strong> – 它当前的内容
- <strong>地址</strong> – 它在内存中的位置

---

## 数据类型

<strong>数据类型</strong>规定了三件事：

1. <strong>值的集合</strong> – 可以取哪些值
2. <strong>运算</strong> – 可以对这些值做什么
3. <strong>表示</strong> – 机器如何存储它（多少位、什么编码）

<div class="doboz">

<strong>示例 – Java 的 `int`:</strong>
取值：−2 147 483 648 … 2 147 483 647 · 运算：`+ − * / % == < …` · 表示：32 位，补码

</div>

### 分类

- <strong>基本（简单）类型：</strong>不能再分解 – 布尔、字符、整数、实数、指针
- <strong>构造类型（数据结构）：</strong>由基本数据组成 – 数组、记录、链表 …

---

<!-- _class: kicsi -->

## Java 和 Go 中的基本类型

| 种类 | Java | Go | 大小 |
|---|---|---|---|
| 布尔 | `boolean` | `bool` | – |
| 字符 | `char`（UTF-16 代码单元） | `rune`（= `int32`,Unicode 码点） | 16 / 32 位 |
| 字节 | `byte`（有符号） | `byte`（= `uint8`，无符号） | 8 位 |
| 整数 | `short`、`int`、`long` | `int8`、`int16`、`int32`、`int64`、`int` | 16 / 32 / 64 位 |
| 无符号整数 | – | `uint8` … `uint64`、`uint` | 8 … 64 位 |
| 实数 | `float`、`double` | `float32`、`float64` | 32 / 64 位 |
| 指针 / 引用 | 引用（指向对象） | `*T` 指针 | 64 位 |

<div class="doboz tipp">

Go 中 `int` 的大小取决于机器（如今几乎总是 64 位）；Java 中 `int` 永远是 32 位。

</div>

---

## 整数的表示

![w:820](kepek/h01_bitek.svg)

- 用 <em>n</em> 位可以表示 <strong>2ⁿ</strong> 个不同的值
- 有符号整数（补码）：<strong>−2ⁿ⁻¹ … 2ⁿ⁻¹ − 1</strong>
- Java 的 `int`（32 位）：−2 147 483 648 … 2 147 483 647

---

## 溢出

如果运算结果放不进该类型，值就会<strong>“回绕”</strong> – 而且没有任何错误提示！

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int max = Integer.MAX_VALUE;
System.out.println(max + 1);
// -2147483648

byte b = 127;
b++;              // -128
```

</div>
<div>

<span class="cimke go">Go</span>

```go
var max int32 = math.MaxInt32
max++
fmt.Println(max)
// -2147483648

var b int8 = 127
b++               // -128
```

</div>
</div>

<div class="doboz figyelem">

一定要选择能放下最大预期值的类型（例如 `long` / `int64`）。

</div>

---

## 实数：浮点表示

- 形式：<strong>符号 × 尾数 × 2^指数</strong>（IEEE 754 标准）
- `float` / `float32`：约 7 位有效数字 · `double` / `float64`：约 15–16 位有效数字
- 大多数十进制小数（例如 0.1）在二进制中<strong>无法精确表示</strong>

<div class="ket-hasab">
<div>

```java
double s = 0.1 + 0.2;
System.out.println(s);
// 0.30000000000000004
System.out.println(s == 0.3); // false
```

</div>
<div>

<strong>解决办法：</strong>带容差比较

```java
final double EPS = 1e-9;
Math.abs(s - 0.3) < EPS   // true
```

</div>
</div>

<div class="doboz tipp">

金额计算中使用整数（例如以“分”为单位）或 `BigDecimal` 类型。

</div>

---

## 整数除法与类型转换

- 两个整数相除的商是<strong>整数</strong>：`7 / 2 == 3`，余数：`7 % 2 == 1`
- 只要有一个操作数是实数，结果就是实数：`7 / 2.0 == 3.5`

```java
double f = 9 / 5 * celsius + 32;     // 错误:9 / 5 == 1
double f = 9.0 / 5 * celsius + 32;   // 正确
```

<strong>类型转换（强制类型转换）：</strong>

- <strong>拓宽</strong>（`int` → `long`、`int` → `double`）：安全，Java 中自动进行
- <strong>收窄</strong>（`double` → `int`、`int` → `byte`）：可能丢失数据，只有显式要求时才进行
  `(int) 3.99 == 3`（截断） · `(byte) 300 == 44`（只保留最低 8 位）
- Go 中<strong>每一次</strong>转换都必须显式写出：`float64(a) / float64(b)`

---

## 字符：ASCII 与 Unicode

- <strong>ASCII:</strong>7 位，128 个字符（英文字母、数字、标点）
  `'A' = 65`、`'a' = 97`、`'0' = 48` → `'a' - 'A' == 32`
- <strong>Unicode：</strong>涵盖世界上所有文字，超过 150 000 个字符
  `'中' = U+4E2D = 20013` · `'é' = U+00E9 = 233`
- <strong>UTF-8：</strong>变长编码（1–4 字节） – Web 和 Go 的默认编码

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
char c = 'A';
System.out.println((int) c);   // 65
char d = (char) (c + 1);        // 'B'
```

</div>
<div>

<span class="cimke go">Go</span>

```go
c := 'A'               // rune
fmt.Println(c)         // 65
fmt.Printf("%c", '中') // 中
```

</div>
</div>

字符串将在<strong>第 4 周</strong>详细讲解。

---

## 布尔类型与逻辑运算

<div class="ket-hasab">
<div>

| a | b | a <strong>and</strong> b | a <strong>or</strong> b | <strong>not</strong> a |
|---|---|---|---|---|
| 假 | 假 | 假 | 假 | 真 |
| 假 | 真 | 假 | 真 | 真 |
| 真 | 假 | 假 | 真 | 假 |
| 真 | 真 | 真 | 真 | 假 |

</div>
<div>

| 运算 | Java | Go |
|---|---|---|
| 与 | `&&` | `&&` |
| 或 | `\|\|` | `\|\|` |
| 非 | `!` | `!` |
| 异或 | `^` | `!=` |

</div>
</div>

- <strong>短路求值：</strong>在 `a && b` 中，如果 `a` 为假，`b` 根本不会被计算
  `if (i < n && t[i] > 0)` – 永远不会越过数组末尾！

---

## 字面量、变量、常量

- <strong>字面量：</strong>直接写在程序文本中的值
  `42`、`0x2A`、`0b101010`、`3.14`、`2.5e3`、`'A'`、`"hello"`、`true`
- <strong>变量：</strong>有名字的存储位置，程序运行时其值可以改变
- <strong>常量：</strong><strong>不能改变</strong>的有名字的值

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int count = 0;              // 变量
final int DAYS = 7;         // 常量
long big = 9_000_000_000L;  // L:long
float f = 2.5f;             // f:float
```

</div>
<div>

<span class="cimke go">Go</span>

```go
var count int      // 零值为 0
n := 10            // 短变量声明
const Days = 7     // 常量
var f float32 = 2.5
```

</div>
</div>

---

## 指针与引用

![w:1050](kepek/h01_ertek_referencia.svg)

- <strong>指针：</strong>值为<strong>内存地址</strong>的数据
- 通过指针可以间接访问另一个数据
- 特殊值：<strong>null / nil</strong> – “不指向任何地方”

---

<!-- _class: kicsi -->

## Java 中的引用，Go 中的指针

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

- 基本类型（`int`、`double` …）：变量中存放<strong>值本身</strong>
- 对象（数组、`String`、自定义类）：变量中存放<strong>引用</strong>
- 没有指针运算，地址不可见

```java
int[] a = {10, 20, 30};
int[] b = a;      // 同一个数组!
b[0] = 99;
System.out.println(a[0]);  // 99
```

</div>
<div>

<span class="cimke go">Go</span>

- 所有类型都按值复制 – 甚至数组（`[3]int`）也是
- 指针：`&x` 是地址，`*p` 是所指向的值
- 切片（`[]int`）和 `map` 内部包含引用

```go
x := 5
p := &x        // p 中存放地址
*p = 6
fmt.Println(x) // 6
```

</div>
</div>

<div class="doboz">

指针/引用使<strong>动态数据结构</strong>（链表、树）成为可能 – 见第 9 周起的内容。

</div>

---

<!-- _class: fejezet -->

# 数据结构

---

## 什么是数据结构？

<strong>数据结构</strong>是一组逻辑上相关的数据元素，由以下三方面确定：

1. 它的<strong>元素</strong>（及其类型），
2. 元素之间的<strong>关系</strong>，
3. 可以进行的<strong>操作</strong>。

<div class="doboz">

<strong>示例 – 班级名单：</strong>元素：姓名（字符串） · 关系：按字母顺序（每个人都有前驱和后继） · 操作：查找、插入新名字、删除名字

</div>

数据结构可以按多种标准分类 ▶

---

## 分类：元素的类型与个数

### 按元素的类型

- <strong>同构：</strong>所有元素类型相同 – 数组、字符串、集合
- <strong>异构：</strong>元素可以有不同的类型 – 记录（`class` / `struct`）

### 按元素的个数

- <strong>静态：</strong>元素个数在创建时确定，以后不再改变
  Java 数组 `new int[10]`、Go 数组 `[10]int`
- <strong>动态：</strong>元素个数在运行时可以改变
  链表、`ArrayList`、Go 的 `slice`、树

---

## 分类：存储方式

![w:1050](kepek/h01_tarolas.svg)

- <strong>顺序存储：</strong>第 <em>i</em> 个元素的地址可以计算：`基地址 + (i − 1) · 元素大小`
- <strong>链式存储：</strong>每个元素存放下一个元素的位置（指针） – 插入时无需移动元素

---

## 分类：元素的访问方式

- <strong>直接（随机）访问：</strong>按下标，访问每个元素的时间相同
  数组：`t[1000]` 和 `t[0]` 一样快
- <strong>顺序访问：</strong>只能经过前面的元素才能到达某个元素
  链表、（磁带）
- <strong>关联（按内容）访问：</strong>通过键访问元素
  哈希表：`map["Wuhan"]`
- <strong>受限访问：</strong>只能访问特定的元素
  栈（只能访问栈顶）、队列（只能访问队头）

---

## 分类：元素之间的关系

![w:1100](kepek/h01_osztalyozas.svg)

---

<!-- _class: kicsi -->

## 总览：本课程的数据结构

| 数据结构 | 元素 | 大小 | 存储 | 访问 | 关系 | 周 |
|---|---|---|---|---|---|---|
| 数组 | 同构 | 静态 | 顺序 | 直接 | 线性 | 3 |
| 字符串 | 同构 | 静态* | 顺序 | 直接 | 线性 | 4 |
| 集合 | 同构 | 可变 | 多种 | – | 无 | 6 |
| 栈、队列 | 同构 | 动态 | 顺序或链式 | 受限 | 线性 | 7、8、11 |
| 链表 | 同构 | 动态 | 链式 | 顺序 | 线性 | 9、10 |
| 哈希表 | 同构 | 动态 | 混合 | 关联 | 无 | 11 |
| 二叉树 | 同构 | 动态 | 链式（或数组） | 顺序 | 层次 | 14、15 |
| 记录 | 异构 | 静态 | 顺序 | 直接（字段名） | – | – |

<span class="halvany">* Java 和 Go 中的字符串是不可变的。</span>

---

## 数据结构上的操作

| 操作 | 含义 |
|---|---|
| <strong>创建</strong> | 建立一个空的结构 |
| <strong>插入</strong> | 加入新元素 |
| <strong>删除</strong> | 移除元素 |
| <strong>修改</strong> | 改变某个元素的值 |
| <strong>查找</strong> | 找到具有给定性质的元素 |
| <strong>遍历（处理）</strong> | 每个元素访问一次 |
| <strong>排序</strong> | 把元素排成一定的顺序 |

如果一个数据结构的<strong>最常用操作很快</strong>，它就适合这个任务。

---

## 抽象数据类型（ADT）

- <strong>ADT：</strong>由<strong>操作</strong>定义的数据结构 – 说明它能*做什么*，而不是*怎么做*
- 实现（表示）可以隐藏，也可以替换

<div class="ket-hasab">
<div>

<span class="cimke java">Java – 接口</span>

```java
interface Stack {
    void push(int x);
    int pop();
    boolean isEmpty();
}
```

</div>
<div>

<span class="cimke go">Go – 接口</span>

```go
type Stack interface {
    Push(x int)
    Pop() int
    IsEmpty() bool
}
```

</div>
</div>

同一个栈既可以用<strong>数组</strong>实现（第 7 周），也可以用<strong>链表</strong>实现（第 11 周） – 使用者的代码不需要改变。

---

## 小结

- 程序 = <strong>算法 + 数据结构</strong>
- 算法是有限的、定义明确的步骤序列；我们用<strong>伪代码</strong>描述它（下标从 1 开始）
- <strong>数据类型</strong> = 值的集合 + 运算 + 表示
- 表示是有局限的：<strong>溢出</strong>、<strong>浮点误差</strong>、<strong>整数除法</strong>
- <strong>指针/引用</strong>存放内存地址
- 数据结构的分类：同构/异构 · 静态/动态 · 顺序/链式 · 直接/顺序访问 · 线性/层次/网状

<strong>下周：</strong>如何衡量算法的效率？顺序查找与二分查找。

---

## 复习题

判断对错：

1. 数组是异构数据结构。
2. 链表的元素按顺序访问。
3. 在 Java 中，`Integer.MAX_VALUE + 1` 会引起运行时错误。
4. 在 Java 中，表达式 `0.1 + 0.2 == 0.3` 的值为假。
5. 指针的值是一个内存地址。
6. 静态数据结构中元素的值不能改变。

<!--
答案：1. 错（同构）  2. 对  3. 错（回绕为 -2147483648）  4. 对  5. 对
6. 错 – “静态”指的是元素的个数；元素的值可以修改。
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# 实践课

---

<!-- _class: gyak -->

## 搭建环境

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```bash
java -version          # 17 或更新版本
cd code/java/w01
java Types.java        # 编译 + 运行
```

或者用传统方式：

```bash
javac Types.java
java Types
```

</div>
<div>

<span class="cimke go">Go</span>

```bash
go version             # 1.23 或更新版本
cd code/go
go run ./w01/types
```

格式化与检查：

```bash
gofmt -w .
go vet ./...
```

</div>
</div>

---

<!-- _class: gyak -->

## 示例程序

| 程序 | Java | Go | 演示内容 |
|---|---|---|---|
| 基本类型 | `Types.java` | `w01/types` | 取值范围、字面量、字符编码、常量 |
| 常见陷阱 | `Pitfalls.java` | `w01/pitfalls` | 溢出、整数除法、0.1 + 0.2、类型转换 |
| 值与引用 | `ValueRef.java` | `w01/valueref` | 参数传递、别名、null/nil、交换 |
| 欧几里得算法 | `Gcd.java` | `w01/gcd` | 伪代码 → 代码，打印每一步 |

<div class="doboz tipp">

逐个运行它们，并且在运行<strong>之前</strong>先猜一猜会输出什么！我们会讨论出人意料的那几行。

</div>

<!--
Go 特有的说明：在 Go 中，作为常量表达式的 0.1 + 0.2 恰好等于 0.3（编译器使用任意精度计算），
因此 pitfalls 程序使用变量来演示误差。
-->

---

<!-- _class: gyak -->

## 练习

1. <strong>位数：</strong>编写函数，返回存放整数 <em>n</em> ≥ 0 需要多少位！（`255 → 8`,`256 → 9`）
2. <strong>二进制形式：</strong>用反复除以 2 的方法输出一个正整数的二进制形式！（`50 → 110010`）
3. <strong>大写字母：</strong>利用字符编码把小写字母转换成大写字母（不使用库函数）！
4. <strong>实数比较：</strong>编写带容差的 `almostEqual(x, y)` 函数！
5. <strong>真值表：</strong>输出 `and`、`or`、`not` 和`异或`的真值表！
6. <strong>溢出检查：</strong>在<strong>相加之前</strong>判断 `x + y` 是否会溢出（`int` / `int32`）！

参考答案：`Exercises01.java`、`w01/exercises`

---

<!-- _class: gyak -->

## 课后作业

1. Java 中 `(byte) 200` 的值是多少？Go 中 `int8(200)` 呢？先手工计算，再上机验证！
2. 16 位无符号整数可以存放多少个不同的值？最大值是多少？
3. 编写程序，输出文本 `"Hello, 世界"` 的每个字符及其 Unicode 编码！
4. 找出生活中<strong>栈</strong>、<strong>队列</strong>和<strong>树</strong>结构的例子！

<!--
答案：1. 200 = 1100 1000 → -56。  2. 65 536 个值，最大值为 65 535。
3. Java:for (char c : s.toCharArray()) ...（在 BMP 范围内没问题）；Go:for _, r := range s { fmt.Printf("%c %d\n", r, r) }
4. 栈：一摞盘子、浏览器的“后退”按钮；队列：食堂排队、打印队列；树：文件夹结构、家谱、组织结构图。
-->