数据结构是计算机专业教学计划中的一门核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。从事与计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构基础。本书对C十十语言进行简单介绍，然后介绍线性表、栈、队列、数组、广义表、树、图等数据结构，并介绍查找和排序的方法。全书用C十十语言描述并实现所有数据结构的类和程序，并附有习题，便于教学。 ???本书是高等院校数据结构课程的教材，可供计算机专业本科生使用，也可供从事计算机开发和应用的工程技术人员阅读、参考。 ???????????????第1章 ?绪论11.1 ?程序的定义11.2 ?数据结构的基本概念11.2.1 ?数据结构实例21.2.2 ?数据结构的定义31.3 ?算法性能与复杂度41.3.1 ?算法的定义41.3.2 ?算法的性能标准51.3.3 ?算法复杂度6习题19第2章 ?C十十程序设计语言简介122.1 ?C十十程序设计语言基础122.1.1 ?程序结构122.1.2 ?数据声明和作用域132.1.3 ?输入输出152.1.4 ?函数162.1.5 ?参数传递162.1.6 ?函数名重载172.1.7 ?动态内存分配182.1.8 ?结构与联合182.2 ?类与对象的基本概念222.2.1 ?类与对象222.2.2 ?消息与合作242.2.3 ?多态性242.3 ?面向对象的程序设计方法242.4 ?C十十类与对象252.5 ?构造函数和析构函数262.6 ?工具函数292.7 ?继承312.8 ?this指针的使用342.9 ?虚函数、多态性以及动态联编352.9.1 ?虚函数和多态性352.9.2 ?动态联编362.10 ?类模板37习题239第3章 ?线性表423.1 ?线性表的定义423.2 ?线性表的顺序存储433.2.1 ?顺序表类模板的定义433.2.2 ?顺序表相关算法的复杂度分析483.3 ?线性表的链式存储493.3.1 ?单链表493.3.2 ?双向循环链表573.3.3 ?静态链表643.4 ?线性表的应用653.4.1 ?集合的表示和相关运算的实现653.4.2 ?一元多项式表示和相关运算的实现66习题369第4章 ?栈、队列和递归724.1 ?栈724.1.1 ?顺序栈734.1.2 ?链式栈764.1.3 ?栈的应用—— 表达式求值794.2 ?队列864.2.1 ?顺序队列874.2.2 ?链式队列914.2.3 ?队列的应用——车厢调度944.3 ?递归964.3.1 ?递归的概念964.3.2 ?递归过程与递归工作栈974.3.3 ?消除递归98习题4102第5章 ?字符串、数组和广义表1055.1 ?字符串1055.1.1 ?字符串的基本概念1055.1.2 ?常用的C十十字符串函数1075.1.3 ?串类的定义及其实现1085.1.4 ?模式匹配1145.2 ?数组1185.2.1 ?数组的基本概念1185.2.2 ?数组的顺序存储结构1195.3 ?稀疏矩阵1215.3.1 ?非零元素的三元组定义1215.3.2 ?三元组顺序表1225.3.3 ?十字链表1255.4 ?广义表1305.4.1 ?广义表的定义1305.4.2 ?广义表的存储结构1315.4.3 ?n元多项式的表示136习题5138第6章 ?树和森林1416.1 ?树的概念1416.1.1 ?树的定义1416.1.2 ?树的术语1426.1.3 ?树的表示形式1436.1.4 ?树的基本操作1446.2 ?二叉树1446.2.1 ?二叉树的定义1446.2.2 ?二叉树的性质1456.2.3 ?二叉树的基本操作1466.3 ?二叉树的存储结构1476.3.1 ?顺序二叉树1476.3.2 ?二叉树的链表表示1486.3.3 ?二叉树的二叉链表类模板声明1496.4 ?遍历二叉树1536.4.1 ?先序遍历1546.4.2 ?中序遍历1546.4.3 ?后序遍历1556.4.4 ?层序遍历1566.5 ?线索二叉树1576.5.1 ?线索二叉树的定义1576.5.2 ?线索二叉树的类模板定义1596.6 ?二叉树的应用1656.6.1 ?堆1656.6.2 ?哈夫曼树1716.7 ?树和森林的实现1776.7.1 ?树的存储结构1776.7.2 ?树、森林和二叉树的转换1796.7.3 ?树的遍历1826.7.4 ?森林的遍历1826.8 ?等价类及其表示1836.8.1 ?等价关系与等价类1836.8.2 ?并查集184习题6189第7章 ?图1937.1 ?图的基本概念1937.1.1 ?图的定义1937.1.2 ?图的术语1947.1.3 ?图的基本操作1967.2 ?图的存储结构1967.2.1 ?邻接矩阵1977.2.2 ?邻接表2037.2.3 ?邻接多重表2127.2.4 ?十字链表2127.3 ?图的遍历与连通性2137.3.1 ?深度优先遍历2137.3.2 ?广度优先遍历2157.3.3 ?连通分量2177.4 ??小生成树2177.4.1 ?克鲁斯卡尔算法2187.4.2 ?普里姆算法2217.5 ??短路径2247.5.1 ?弧上权值为非负情形的单源点 短路径问题2247.5.2 ?弧上权值为任意值的单源点 短路径问题2277.5.3 ?所有顶点之间的 短路径2297.6 ?活动网络2317.6.1 ?用顶点表示活动的网络2317.6.2 ?用边表示活动的网络235习题7239第8章 ?查找2438.1 ?基本概念2438.2 ?顺序表2448.2.1 ?顺序表的查找2448.2.2 ?有序表的折半查找2458.2.3 ?有序表的其他查找2488.3 ?索引顺序表和倒排索引表2498.3.1 ?索引顺序表2498.3.2 ?倒排索引表2518.4 ?二叉排序树2538.4.1 ?二叉排序树定义2538.4.2 ?二叉排序树的查找2548.4.3 ?二叉排序树的插入2558.4.4 ?二叉排序树的删除2578.4.5 ?二叉排序树查找的性能分析2588.5 ?平衡二叉树2598.5.1 ?平衡二叉树的定义2598.5.2 ?平衡旋转2598.5.3 ?平衡二叉树中插入结点2618.5.4 ?平衡二叉树中删除结点2648.6 ?B树2668.6.1 ?动态的m路查找树2668.6.2 ?B树的定义2678.6.3 ?B树的插入2688.6.4 ?B树的删除2698.6.5 ?B十树2718.7 ?散列表2738.7.1 ?散列表的基本概念2738.7.2 ?散列函数2748.7.3 ?处理冲突的闭散列方法——开地址方法2768.7.4 ?闭散列方法的实现2798.7.5 ?处理冲突的开散列方法——链地址法2828.7.6 ?散列表分析283习题8284第9章 ?排序2889.1 ?基础知识2889.2 ?交换排序2899.2.1 ?冒泡排序2899.2.2 ?快速排序2919.3 ?插入排序2939.3.1 ?直接插入排序2939.3.2 ?折半插入排序2969.3.3 ?希尔排序2979.4 ?选择排序2989.4.1 ?简单选择排序2989.4.2 ?锦标赛排序3019.4.3 ?堆排序3029.5 ?归并排序3059.5.1 ?归并3059.5.2 ?两路归并排序3069.5.3 ?递归的归并排序3079.6 ?基数排序3109.6.1 ?多关键字排序3109.6.2 ?链式基数排序3119.7 ?各种排序方法的选择和使用313习题9314参考文献317