本书按照循序渐进的原则介绍线性表、栈、队列、串、树、图等数据结构的逻辑结构、存储结构和数据运算,对于经典算法使用C 构造可执行的程序,帮助读者利用*少的时间和空间资源编写出*秀*合理的程序。本书可以作为高等院校信息管理与信息系统专业、软件专业、计算机专业的本科教材,也可以作为其他理工科专业的选修教材。教师可以根据本学校的专业特点、学生情况和教学学时,选讲部分章节的内容。

第1章绪论1 1.1数据结构与程序设计1 1.1.1学习数据结构的意义1 1.1.2数据与数据结构2 1.1.3数据结构的类型4 1.2抽象数据类型5 1.2.1C 中的数据类型6 1.2.2抽象数据类型与C 特性6 1.3算法分析10 1.3.1问题、算法与程序10 1.3.2算法效率的度量10 本章小结14 第2章线性表15 2.1线性表的基本概念15 2.1.1线性表的定义与特点15 2.1.2线性表的存储结构15 2.2顺序表的算法实现17 2.2.1顺序表的创建和插入19 2.2.2顺序表内结点的查找23 2.2.3顺序表内元素的删除28 2.3单链表的算法实现30 2.3.1单链表的结点结构和一般形式30 2.3.2单链表的创建和插入32 2.3.3单链表内数据元素的查找37 2.3.4单链表内数据元素的删除40 2.3.5单链表的合并43 2.4双向链表的算法实现47 2.4.1双向链表的结点结构和一般形式47 2.4.2双向链表的创建和插入49 2.4.3双向链表内元素的查找53 2.4.4双向链表内元素的删除55 2.5循环链表的算法实现57 2.5.1循环链表的结点结构和一般形式57 2.5.2循环链表的创建58 2.6线性表的应用——一元多项式的存储和相加63 2.6.1一元多项式的存储和相加的实现方式63 2.6.2一元多项式的存储和相加的实现65 2.7STL的使用68 2.7.1STL简介68 2.7.2STL应用实例68 本章小结69 第3章栈与���列71 3.1栈的基本概念71 3.1.1栈的定义与特点71 3.1.2栈的两类存储结构71 3.2顺序栈的算法实现72 3.2.1顺序栈的建立和顺序栈入栈72 3.2.2顺序栈出栈74 3.3队列的基本概念76 3.3.1队列的定义与特点76 3.3.2队列的存储结构77 3.4顺序队列的算法实现78 3.4.1顺序队列的建立和顺序队列入队79 3.4.2顺序队列出队80 3.5循环队列的算法实现83 3.5.1循环队列的建立和循环队列入队83 3.5.2循环队列出队85 3.6链队列的算法实现87 3.6.1链队列的建立和链队列入队87 3.6.2链队列出队88 3.7栈和队列的应用——算术表达式的转化和求值89 本章小结96 第4章串97 4.1串的基本概念97 4.1.1串的定义与特点97 4.1.2串的存储结构98 4.2串的算法实现100 4.2.1串赋值算法100 4.2.2求子串算法102 4.2.3串比较算法104 4.2.4串连接算法106 4.3串的模式匹配算法实现107 4.3.1串的朴素模式匹配算法107 4.3.2改进的模式匹配算法109 本章小结114 第5章数组和广义表115 5.1数组的基本概念115 5.1.1数组的定义与特点115 5.1.2数组的存储结构116 5.2特殊矩阵的压缩存储117 5.3矩阵的算法实现120 5.4广义表的基本概念126 5.4.1广义表的定义与图形表示126 5.4.2广义表的存储结构127 5.5广义表的算法实现128 本章小结134 第6章树和二叉树135 6.1树的基本概念135 6.1.1树的定义与基本术语135 6.1.2树的表示形式和存储结构136 6.2二叉树的基本概念140 6.2.1二叉树的定义与性质140 6.2.2二叉树的存储结构142 6.2.3树、森林和二叉树的转换144 6.2.4二叉树的遍历146 6.3二叉树算法实现147 6.3.1二叉树的建立147 6.3.2递归的二叉树前序遍历、中序遍历、后序遍历150 6.3.3非递归的二叉树前序遍历153 6.3.4非递归的二叉树中序遍历155 6.3.5非递归的二叉树后序遍历157 6.4哈夫曼树及其应用161 6.4.1哈夫曼树与哈夫曼编码161 6.4.2哈夫曼算法实现162 本章小结168 第7章图169 7.1图的基本概念169 7.1.1图的定义和术语169 7.1.2图的表示与存储结构173 7.2图的构造算法实现176 7.2.1图的基本类定义176 7.2.2构造顺序表存储的图179 7.2.3构造邻接表存储的无向图与有向图182 7.2.4构造十字链表存储的有向图188 7.2.5构造邻接多重表存储的无向图193 7.3图的遍历算法实现197 7.3.1深度优先遍历算法198 7.3.2广度优先遍历算法200 7.4*小生成树算法实现204 7.4.1普里姆算法205 7.4.2克鲁斯卡尔算法209 7.5图的应用216 7.5.1拓扑排序216 7.5.2关键路径220 7.5.3*短路径——迪杰斯克拉算法225 7.5.4*短路径——弗洛伊德算法229 本章小结234 第8章查找235 8.1查找的基本概念235 8.1.1查找的相关术语235 8.1.2查找表结构236 8.2顺序表查找算法实现236 8.3有序顺序表的折半查找算法实现240 8.4索引顺序表的分块查找算法实现245 8.4.1索引表245 8.4.2分块查找算法实现246 8.5二叉排序树及其算法实现250 8.5.1二叉排序树及其查找过程250 8.5.2二叉排序树建立及插入结点的过程251 8.5.3二叉排序树删除结点的过程251 8.5.4二叉排序树的算法实现253 8.6平衡二叉树及其算法实现258 8.6.1平衡二叉排序树及其构造258 8.6.2平衡二叉排序树算法实现261 8.7B树及其算法实现268 8.7.1B树268 8.7.2B树的查找269 8.7.3B树的插入269 8.7.4B树的删除271 8.7.5B树的算法实现273 8.8哈希查找的算法实现282 8.8.1哈希表282 8.8.2哈希函数的构造方法282 8.8.3哈希冲突的处理方法283 8.8.4哈希表的算法实现285 本章小结289 第9章排序290 9.1排序的基本概念290 9.1.1排序相关术语介绍290 9.1.2常用的内部排序算法类型简介291 9.2插入排序的算法实现292 9.2.1直接插入排序292 9.2.2希尔排序295 9.3交换排序的算法实现299 9.4选择排序的算法实现303 9.4.1直接选择排序303 9.4.2堆排序306 9.5归并排序的算法实现313 9.6基数排序的算法实现316 9.7各种内部排序方法的比较321 9.7.1时间性能321 9.7.2空间性能321 9.7.3排序方法的稳定性322 9.8外部排序322 本章小结322 第10章综合案例323 10.1背景介绍323 10.2问题分解323 10.2.1旅行商问题323 10.2.2动态规划325 10.2.3带酒店选择的旅行商问题328 10.3总结与思考331 附录A文件夹结构332 附录BUML类图334 B.1第2章线性表的相关类图334 B.2第3章栈与队列的相关类图336 B.3第4章串的相关类图337 B.4第5章数组和广义表的相关类图338 B.5第6章树和二叉树的相关类图339 B.6第7章图的相关类图341 B.7第8章查找的相关类图344 B.8第9章排序的相关类图346 参考文献347