魏振钢，男，教授，1984年6月毕业于山东大学计算机专业，1980.7―1986.6，山东大学讲师，1986.6―至今，中国海洋大学教授，兼任信息化教学中心主任。任全国高校计算机教育研究会理事，中国体育学会信息分会常务理事，青岛计算机学会常务理事。曾获得中国海洋大学教学名师，青岛市教学名师，教育部-英特尔精品课程、山东精品课程《数据结构》负责人，教育部-IBM精品课程《软件工程》负责人。先后主持国家自然科学基金1项，省级自然科学基金1项，主编教材1部，出版教材名称：《数据结构》，出版社：高等教育出版社，出版时间：2011年2月。

― 目  录 ―

第1章  绪论  / 1
1．1  何为算法  / 1
1．2  算法的特性  / 3
1．3 “敲7”游戏  / 4
1．3．1  数据元素  / 4
1．3．2  数据的逻辑结构  / 5
1．3．3  数据的存储结构  / 6
1．3．4  线性表的删除  / 7
1．3．5 “敲7”游戏的算法
设计  / 9
1．4  计算机求解问题的基本
步骤  / 10
1．5  总结与思考  / 11
第2章  《三体》在哪里  / 12
2．1  怎样找到《三体》
这本书  / 12
2．2  线性表的定义及表示  / 14
2．2．1  类型定义  / 14
2．2．2  线性表的顺序表示和实现  / 17
2．2．3  线性链表  / 20
2．2．4  循环链表  / 27
2．3  查找的定义  / 28
2．3．1  概念与术语  / 28
2．3．2  顺序表的查找  / 29
2．3．3  有序表的查找  / 33
2．4  如何查找《三体》
这本书  / 37
2．4．1  问题分析  / 37
2．4．2  算法设计  / 37
2．5  如何找到“小明”  / 38
2．5．1  问题描述  / 38
2．5．2  问题分析  / 39
2．6  总结与思考  / 39
第3章  奖学金争先  / 41
3．1  谁能拿到奖学金  / 41
3．2  常用排序方法介绍  / 42
3．2．1  概述  / 42
3．2．2  直接插入排序  / 43
3．2．3  起泡排序  / 46
3．2．4  快速排序  / 49
3．2．5  简单选择排序  / 51
3．3  奖学金竞争问题的
求解  / 53
3．3．1  问题分析  / 53
3．3．2  算法分析  / 53
3．3．3  算法设计  / 54
3．4  应用  / 55
3．4．1  荷兰国旗问题  / 55
3．4．2  货箱移动问题  / 57
3．5  总结与思考  / 58
第4章  网上冲浪  / 59
4．1  “Web导航”问题  / 59
4．1．1  问题描述  / 59
4．1．2  问题分析  / 61
4．2  什么是“栈”  / 62
4．2．1  栈的定义  / 62
4．2．2  栈的顺序表示和
实现  / 64
4．2．3  栈的应用举例  / 64
4．2．4  生活中的栈  / 67
4．3  如何实现“Web导航”  / 69
4．3．1  问题分析  / 69
4．3．2  算法设计  / 71
4．4  列车调度问题  / 73
4．4．1  问题描述  / 73
4．4．2  问题分析  / 73
4．4．3  算法设计  / 74
4．5  总结与思考  / 75
第5章  “汉诺塔”的智慧  / 77
5．1 “汉诺塔”问题  / 77
5．1．1  问题描述  / 77
5．1．2  问题分析  / 78
5．2  递归的基本概念与
应用  / 81
5．2．1  递归  / 81
5．2．2  递归函数  / 82
5．3 “汉诺塔”问题求解  / 83
5．3．1  问题分析  / 83
5．3．2  算法设计  / 84
5．4  应用  / 85
5．4．1  八皇后问题  / 85
5．4．2  快速排序  / 88
5．4．3  分苹果问题  / 88
5．5  总结与思考  / 89
第6章  舞伴的选择  / 91
6．1  舞伴组合  / 91
6．1．1  问题描述  / 91
6．1．2  问题分析  / 91
6．2  队列  / 92
6．2．1  队列的抽象数据类型定义  / 92
6．2．2  队列的基本
操作  / 93
6．2．3  生活中的队列  / 94
6．3  舞伴组合问题求解  / 95
6．3．1  算法分析  / 95
6．3．2  算法设计  / 95
6．3．3  算法设计  / 97
6．4  消息的加密和解密  / 98
6．4．1  问题描述  / 98
6．4．2  问题分析  / 98
6．4．3  算法设计  / 99
6．5  总结与思考  / 99
第7章  爱的密码  / 101
7．1  如何传输“I LOVE
YOU”  / 101
7．1．1  问题描述  / 101
7．1．2  问题分析  / 101
7．2  树及二叉树  / 102
7．2．1  树的定义  / 102
7．2．2  二叉树  / 104
7．3  哈夫曼树及其哈夫曼
编码  / 110
7．3．1  哈夫曼树  / 110
7．3．2  哈夫曼编码  / 113
7．3．3  传输“I LOVE YOU”的解决方案  / 114
7．4  农夫锯木板问题  / 117
7．4．1  问题描述  / 117
7．4．2  算法分析  / 117
7．4．3  算法设计  / 117
7．5  总结与思考  / 118
第8章  众里寻他千百度  / 120
8．1  微信通讯录  / 120
8．2  动态查找表  / 121
8．2．1  二叉排序树  / 121
8．2．2  平衡二叉树  / 127
8．2．3  B-树和B+树  / 129
8．3  哈希表  / 132
8．3．1  哈希表的定义  / 132
8．3．2  哈希表的查找  / 134
8．3．3  哈希表的应用  / 134
8．4  电话通讯录的实现  / 134
8．4．1  问题描述  / 134
8．4．2  问题分析  / 135
8．5  总结与思考  / 139
第9章  城市互连  / 140
9．1  城市公路连接问题  / 140
9．1．1  问题描述  / 140
9．1．2  问题分析  / 141
9．2  图的基本知识  / 141
9．2．1  图的定义和
术语  / 141
9．2．2  图的存储结构  / 144
9．3  最小生成树的求解  / 148
9．3．1  普里姆算法  / 148
9．3．2  克鲁斯卡尔
算法  / 152
9．4  城市公路连接问题的
求解  / 153
9．5  应城市之间的通信线路网建设问题  / 154
9．5．1  问题描述  / 154
9．5．2  问题分析  / 154
9．6  总结与思考  / 154
第10章  地图导航  / 155
10．1  如何去罗马  / 156
10．1．1  问题描述  / 156
10．1．2  问题分析  / 156
10．2  如何求解最短路径  / 157
10．2．1  从某个源点到
其余各顶点的最
短路径  / 157
10．2．2  每对顶点之间的
最短路径  / 160
10．3  如何实现去罗马  / 163
10．4  校园导航  / 163
10．4．1  问题描述  / 163
10．4．2  问题分析  / 164
10．4．3  算法设计  / 164
10．5  总结与思考  / 167
参考文献  / 169