Python是国际流行的用于教授入门级程序设计课程的语言,国内高校也开始使用。本书是结合国内数据结构课程现状,以Python作为工作语言,编撰的一本数据结构教程。书中结合抽象数据类型结构的思想,基于Python的面向对象机制,讨论了各种基本数据结构的思想、性质、问题和实现,相关算法的设计、实现和特性等。书中还研究了一些数据结构的应用案例。本书要求学习者已有基本Python程序设计的知识和经验,可以作为基于Python的计算机基础课程中的数据结构课程教材,也可以作为学习Python语言基本内容之后的面向对象等**编程技术的进阶读物。

前言 第1章 绪论1 1.1 计算机问题求解1 1.1.1 程序开发过程1 1.1.2 一个简单例子3 1.2 问题求解:交叉路口的红绿灯安排4 1.2.1 问题分析和严格化5 1.2.2 图的顶点分组和算法6 1.2.3 算法的精化和Python描述7 1.2.4 讨论8 1.3 算法和算法分析10 1.3.1 问题、问题实例和算法10 1.3.2 算法的代价及其度量13 1.3.3 算法分析19 1.3.4 Python程序的计算代价(复杂度)21 1.4 数据结构24 1.4.1 数据结构及其分类24 1.4.2 计算机内存对象表示27 1.4.3 Python对象和数据结构30 练习32 第2章 抽象数据类型和Python类34 2.1 抽象数据类型34 2.1.1 数据类型和数据构造34 2.1.2 抽象数据类型的概念36 2.1.3 抽象数据类型的描述37 2.2 Python的类和面向对象编程39 2.2.1 类的定义和使用39 2.2.2 继承44 2.2.3 异常类和自定义异常48 2.2.4 本书采用的ADT描述形式50 总结50 练习51 ���3章 线性表53 3.1 线性表的概念和表抽象数据类型53 3.1.1 表的概念和性质53 3.1.2 表抽象数据类型53 3.1.3 线性表的实现:基本考虑55 3.2 顺序表56 3.2.1 基本实现方式56 3.2.2 顺序表基本操作的实现57 3.2.3 顺序表的实现结构61 3.2.4 Python的list64 3.2.5 顺序表的简单总结65 3.3 链接表66 3.3.1 线性表的基本需要和链接表66 3.3.2 单链表67 3.3.3 单链表类的实现72 3.4 链表的变形和操作75 3.4.1 单链表的简单变形75 3.4.2 循环单链表78 3.4.3 双链表79 3.4.4 两个链表操作81 3.4.5 在顺序表里实现“链表”85 3.4.6 不同链表的简单总结86 3.5 表的应用87 3.5.1 Josephus问题和基于数组概念的解法87 3.5.2 基于顺序表的解88 3.5.3 基于循环单链表的解88 *3.6 广义表和数组 本书中标星号的小节为选学/选讲内容。89 3.6.1 广义表89 3.6.2 数组92 3.6.3 矩阵94 总结97 练习98 第4章 字符串102 4.1 字符集、字符串和字符串操作102 4.1.1 字符串的相关概念102 4.1.2 字符串抽象数据类型104 4.2 字符串的实现104 4.2.1 基本实现问题和技术104 4.2.2 实际语言里的字符串105 4.2.3 Python的字符串106 4.3 字符串匹配(子串查找)107 4.3.1 字符串匹配问题107 4.3.2 串匹配和朴素匹配算法108 4.3.3 无回溯串匹配算法(KMP算法)110 4.4 字符串匹配问题115 4.4.1 串匹配/搜索的不同需要115 4.4.2 一种简化的正则表达式117 *4.5 Python正则表达式119 4.5.1 正则表达式标准库包re119 4.5.2 基本情况119 4.5.3 主要操作120 4.5.4 正则表达式的构造121 4.5.5 正则表达式的使用127 总结127 练习128 第5章 栈和队列130 5.1 概述130 5.1.1 栈、队列和数据使用顺序130 5.1.2 应用环境131 5.2 栈:概念和实现131 5.2.1 栈抽象数据类型131 5.2.2 栈的顺序表实现132 5.2.3 栈的链接表实现134 5.3 栈的应用134 5.3.1 简单应用:括号匹配问题135 5.3.2 表达式的表示、计算和变换137 5.3.3 栈与递归144 5.4 队列149 5.4.1 队列抽象数据类型149 5.4.2 队列的链接表实现150 5.4.3 队列的顺序表实现150 5.4.4 队列的list实现152 5.4.5 队列的应用155 5.5 迷宫求解和状态空间搜索156 5.5.1 迷宫求解:分析和设计156 5.5.2 求解迷宫的算法159 5.5.3 迷宫问题和搜索161 5.6 几点补充166 5.6.1 与栈或队列相关的几种结构166 5.6.2 顺序实现和链接实现166 总结167 练习168 第6章 二叉树和树170 6.1 二叉树170 6.1.1 概念和性质170 6.1.2 抽象数据类型175 6.1.3 遍历二叉树176 6.2 二叉树的list实现177 6.2.1 设计和实现178 6.2.2 二叉树的简单应用:表达式树179 6.3 优先队列182 6.3.1 概念182 6.3.2 基于线性表的实现183 6.3.3 树形结构和堆185 6.3.4 优先队列的堆实现186 6.3.5 堆的应用:堆排序189 6.4 应用:离散事件模拟190 6.4.1 通用的模拟框架191 6.4.2 海关检查站模拟系统192 6.5 二叉树的类实现196 6.5.1 二叉树结点类197 6.5.2 遍历算法198 6.5.3 二叉树类202 6.6 哈夫曼树203 6.6.1 哈夫曼树和哈夫曼算法203 6.6.2 哈夫曼算法的实现204 6.6.3 哈夫曼编码205 6.7 树和树林207 6.7.1 实例和表示207 6.7.2 定义和相关概念208 6.7.3 抽象数据类型和操作210 6.7.4 树的实现211 6.7.5 树的Python实现212 *6.8 等价类和查并集214 6.8.1 概念和问