数据结构——Python语言描述 PDF下载

第1章　绪论　1


　1.1 数据结构概述　2


1.1.1　什么是数据结构　2


1.1.2　数据的逻辑结构　3


1.1.3　数据的存储结构　4


　1.2 数据类型概述　6


1.2.1　数据类型　6


1.2.2　抽象数据类型　7


　1.3 算法概述　9


1.3.1　什么是算法　9


1.3.2　算法的时间复杂度　9


1.3.3　算法的空间复杂度　12


　1.4 本章小结　13


　1.5 上机实验　14


1.5.1　基础实验　14


1.5.2　综合实验　15


　习题　16


第2章　线性表　18


　2.1 线性表简介　19


　2.2 顺序表　21


2.2.1　顺序表的概念　21


2.2.2　顺序表的操作　22


2.2.3　顺序表的应用　29


　2.3 链表　31


2.3.1　链表的基本概念　32


2.3.2　单链表　35


2.3.3　循环单链表　45


2.3.4　双链表　50


2.3.5　循环双链表　58


2.3.6　链表的应用　64


　2.4 本章小结　78


　2.5 上机实验　79


2.5.1　基础实验　79


2.5.2　综合实验　81


　习题　85


第3章　栈、队列和递归　87


　3.1 栈　88


3.1.1　栈的基本概念　88


3.1.2　栈的顺序存储　89


3.1.3　栈的链式存储　97


3.1.4　栈的典型应用　107


　3.2 队列　112


3.2.1　队列的基本概念　112


3.2.2　队列的顺序存储　113


3.2.3　队列的链式存储　125


3.2.4　队列的典型应用　136


　3.3 递归　139


3.3.1　什么是递归　139


3.3.2　递归算法的设计和实现　141


3.3.3　递归到非递归的转换　146


　3.4 本章小结　154


　3.5 上机实验　154


3.5.1　基础实验　154


3.5.2　综合实验　156


　习题　158


第4章　串、数组和广义表　160


　4.1 串　161


4.1.1　串的基本概念　161


4.1.2　串的顺序存储及运算　163


4.1.3　串的链式存储及运算　167


4.1.4　串的模式匹配　173


　4.2 数组和特殊矩阵　185


4.2.1　数组的基本概念　185


4.2.2　数组的顺序存储　187


4.2.3　特殊矩阵　188


　4.3 广义表　192


4.3.1　广义表的基本概念　192


4.3.2　广义表的存储　194


4.3.3　广义表的操作　196


　4.4 本章小结　202


　4.5 上机实验　202


4.5.1　基础实验　202


4.5.2　综合实验　204


　习题　206


第5章　树、二叉树和森林　208


　5.1 树　209


5.1.1　树的基本概念　209


5.1.2　树的存储　215


5.1.3　树的遍历　219


　5.2 二叉树　220


5.2.1　二叉树的基本概念　220


5.2.2　二叉树的存储　225


5.2.3　二叉树的遍历　228


5.2.4　线索二叉树　242


5.2.5　二叉树的典型应用　247


　5.3 森林　253


5.3.1　森林的定义　253


5.3.2　树、森林和二叉树　254


5.3.3　树或森林转换为二叉树　255


5.3.4　二叉树转换为森林或树　256


　5.4 哈夫曼树　257


5.4.1　哈夫曼树的基本概念　258


5.4.2　哈夫曼算法及实现　259


5.4.3　哈夫曼编码及应用　262


　5.5 本章小结　266


　5.6 上机实验　267


5.6.1　基础实验　267


5.6.2　综合实验　269


　习题　271


第6章　图　273


　6.1 图的基本概念　274


6.1.1　图的定义　274


6.1.2　图的相关术语　275


6.1.3　图的性质　280


　6.2 图的存储结构　280


6.2.1　数组表示法　280


6.2.2　邻接表表示法　282


6.2.3　十字链表表示法　285


6.2.4　邻接多重表表示法　287


　6.3 图的遍历　289


6.3.1　深度优先遍历　289


6.3.2　广度优先遍历　291


　6.4 图的最小生成树　293


6.4.1　基本概念　293


6.4.2　Prim算法　294


6.4.3　Kruskal算法　296


6.4.4　应用实例　298


　6.5 最短路径　300


6.5.1　基本概念　300


6.5.2　从某源点到其余各顶点的最短


路径　300


6.5.3　每一对顶点之间的最短路径　303


6.5.4　应用实例　305


　6.6 拓扑排序　306


6.6.1　基本概念　306


6.6.2　拓扑排序的实现　307


　6.7 关键路径　310


6.7.1　基本概念　310


6.7.2　求关键路径的算法　311


　6.8 本章小结　316


　6.9 上机实验　317


6.9.1　基础实验　317


6.9.2　综合实验　319


　习题　322


第7章　查找　326


　7.1 查找的基本概念　327


7.1.1　相关术语　327


7.1.2　查找表的基本操作　328


　7.2 基于静态查找表的查找　329


7.2.1　顺序查找　330


7.2.2　折半查找　332


7.2.3　索引查找　336


　7.3 基于动态查找表的查找　338


7.3.1　树查找　338


7.3.2　哈希表查找　369


　7.4 本章小结　384


　7.5 上机实验　385


7.5.1　基础实验　385


7.5.2　综合实验　386


　习题　387


第8章　内排序　389


　8.1 排序的基本概念　390


　8.2 插入排序　393


8.2.1　直接插入排序　393


8.2.2　折半插入排序　396


8.2.3　希尔排序　398


8.2.4　表插入排序　401


　8.3 交换排序　403


8.3.1　冒泡排序　403


8.3.2　快速排序　407


　8.4 选择排序　410


8.4.1　简单选择排序　410


8.4.2　树形选择排序　412


8.4.3　堆排序　414


　8.5 归并排序　418


　8.6 基数排序　421


8.6.1　多关键字排序　421


8.6.2　链式基数排序　423


　8.7 本章小结　427


　8.8 上机实验　429


8.8.1　基础实验　429


8.8.2　综合实验　431


　习题　434


第9章　外排序　436


　9.1 外排序概述　437


9.1.1　典型的外存储设备　437


9.1.2　外排序的基本方法　438


　9.2 磁盘排序　439


9.2.1　磁盘排序过程　439


9.2.2　多路平衡归并　441


9.2.3　初始归并段的生成　444


9.2.4　最佳归并树　446


　9.3 本章小结　449


　9.4 上机实验　449


9.4.1　基础实验　449


9.4.2　综合实验　449


　习题　451