数据结构与算法分析

目　录



第1章　绪论　1

1.1　数据结构的概念　1

1.1.1　数据结构的发展　1

1.1.2　什么是数据结构　2

1.1.3　数据结构的研究对象　4

1.1.4　数据结构相关概念及术语　6

1.2　数据类型和抽象数据类型　8

1.2.1　数据类型　8

1.2.2　抽象数据类型　9

1.3　算法和算法分析　11

1.3.1　算法特性　11

1.3.2　算法设计的要求　12

1.3.3　算法的性能分析与度量　12

习题一　17

第2章　线性表　21

2.1　线性表的基本概念　21

2.1.1　线性表的概念　21

2.1.2　线性表的抽象数据类型　22

2.2　线性表的顺序存储结构　25

2.2.1　线性表的顺序存储表示　26

2.2.2　顺序表的类定义和基本操作　26

2.2.3　顺序表的应用　33

2.2.4　顺序表的特点　35

2.3　线性表的链式存储结构　36

2.3.1　单链表　36

2.3.2　静态链表　43

2.3.3　循环链表　47

2.3.4　双向链表　48

2.4　线性表的应用：一元多项式的表示及

运算　50

2.4.1　一元多项式的表示　50

2.4.2　一元多项式的实现　51

习题二　56

第3章　栈和队列　59

3.1　栈的基本概念　59

3.1.1　栈的概念　59

3.1.2　栈的抽象数据类型　60

3.2　栈的顺序存储结构及实现　61

3.2.1　顺序栈的概念　61

3.2.2　顺序栈的类定义和基本操作　62

3.2.3　顺序栈的应用　63

3.3　栈的链式存储结构及实现　68

3.3.1　链栈的概念　69

3.3.2　链栈的类定义和基本操作　69

3.4　队列的基本概念　71

3.4.1　队列的概念　71

3.4.2　队列的抽象数据类型　71

3.5　队列的顺序存储　72

3.5.1　循环队列　73

3.5.2　循环队列的类定义和基本

操作　74

3.6　队列的链式存储　76

3.6.1　链队列的概念　76

3.6.2　链队列的类定义和基本操作　76

3.6.3　链队列的应用　78

习题三　83

第4章　串　86

4.1　串的基本概念　86

4.2　串的表示与实现　88

4.2.1　定长顺序存储表示　88

4.2