数据结构——用C语言描述

序

前言

第1章 算法分析

1．1 算法.

1．1．1 数组元素相加(add array members)

1．1．2 矩阵相乘(matrix multiplication)

1．1．3 顺序查找(sequential search)

1．1．4 折半查找(binary search)

1．1．5 斐波那契(fibonacci)数列(递归的程序段)

1．1．6 斐波那契数列(非递归的程序片段)

1．2 big-o(复杂度)

1．3 动动脑时间

第2章 数组

2．1 数组的表示法

2．1．1 一维数组(one dimension array)

2．1．2 二维数组

2．1．3 三维数组

2．1．4 n维数组

2．2 上三角形和下三角形表示法

2．2．1 以列为主

.2．2．2 以行为主

2．3 多项式表示法

2．4 魔术方阵

2．5 生命细胞游戏

2．6 动动脑时间

第3章 堆栈与队列

3．1 堆栈与队列的基本概念

3．2 堆栈的插入与删除

3．3 队列的插入与删除

3．4 循环队列

3．5 堆栈与队列的应用

3．6 如何计算后序表达式

3．7 动动脑时间

第4章 链表

4．1 单向链表

4．1．1 插入操作

4．1．2 删除操作

4．1．3 将两个单向链表相互连接

4．1．4 将一链表反转

4．1．5 计算链表的长度

4．2 循环链表

4．2．1 插入操作

4．2．2 删除操作

4．2．3 如何回收整个循环链表

4．2．4 计算循环链表的长度

4．3 双向链表

4．3．1 插入操作

4．3．2 删除操作

4．4 链表的应用

4．4．1 以链表表示堆栈

4．4．2 以链表表示队列

4．4．3 多项式相加

4．5 动动脑时间

第5章 递归

5．1 一些递归的基本范例

5．2 一个典型的递归范例：hanoi塔

5．3 另一个范例：8个皇后

5．4 何时不要使用递归

5．5 动动脑时间

第6章 树状结构

6．1 树状结构的一些专有名词

6．2 叉树

6．3 叉树的表示方法

6．4 叉树的遍历

6．5 线索二叉树

6．6 其他问题..

6．6．1 如何将一般树化为二叉树

6．6．2 确定惟一的二叉树

6．7 动动脑时间

第7章 二叉查找树

7．1 什么是二叉查找树

7．2 二叉查找树的插入

7．3 二叉查找树的删除

7．4 动动脑时间

第8章 堆

8．1 什么是堆

8．1．1 heap的插入

8．1．2 heap的删除

8．2 什么是min-heap

8．3 rain-maxheap

8．3．1 max-max-heap的插入

8．3．2 min-max-heap的删除

8．4 deap

8．4．1 dead的插入

8．4．2 deap的删除

8．5 动动脑时间

第9章 平衡二叉查找树

9．1 何谓平衡二叉查找树

9．2 avl-tree的插入与删除

9．2．1 ll型

9．2．2 rr型

9．2．3 lr型

9．2．4 rl型

9．3 avl-tree的删除

9．4 动动脑时间

第10章 2-3 tree与2-3-4 tree

10．1 2-3bee

10．1．1 2-3tree的插入

10．1．2 2-3tree的删除

10．2 2-3-4tree

10．2．1 2-3-4tree的插入

10．2．2 2-3-4tree的删除

10．3 动动脑时间

第11章 b-tree

11．1 m-way查找树

11．1．1 m-way查找树的插入

11．1．2 m-way查找树的删除

11．2 b-tree

11．2．1 b-tree的插入

11．2．2 b-tree的删除

11．3 动动脑时间

第12章 图

12．1 图的一些专有名词

12．2 图数据结构表示法

12．2．1 邻接矩阵(adjacency matrix)

12．2．2 邻接表(adjacency list)

12．3 图的遍历

12．3．1 深度优先搜索(depth first search)

12．3．2 广度优先搜索(breadth first search)

12．4 最小生成树

12．4．1 普里姆算法(prim'salgorithm)

12．4．2 克鲁斯卡尔算法(kmskal'salgorithm)

12．5 最短路径

12．6 拓扑排序

12．7 关键路径法

12．7．1 计算事件最早发生的时间

12．7．2 计算事件最晚发生的时间

12．8 动动脑时间

第13章 排序

13．1 起泡排序

13．2 选择排序

13．3 插入排序

13．4 归并排序(merge sort)

13．5 快速排序

13．6 堆排序

13．7 二叉树排序(binary tree sort)

13．8 希尔排序

13．9 基数排序

13．10 动动脑时间

第14章 查找

14．1 顺序查找

14．2 折半查找

14．3 哈希法...

14．3．1 哈希函数

14．3．2 解决溢出的方法(overflow handing)

14．4 动动脑时间

练习题参考答案