新编数据结构案例教程9787302510895

第1篇 绪论篇

第1章 绪论

1．1 什么是数据结构

1．1．1 数据结构的产生与发展

1．1．2 数据结构的基本概念

1．1．3 逻辑结构的种类

1．1．4 数据的存储结构

1．2 抽象数据

1．2．1 数据类型

1．2．2 抽象数据类型的表示与实现

1．3 算法及其性能分析

1．3．1 算法

1．3．2 算法设计的目标

1．3．3 算法的时间复杂度度量

1．3．4 算法的空间复杂度度量

1．4 STL概述

1．4．1 STL的发展和特点

1．4．2 C++标准库和STL

1．4．3 数据结构和STL的关系

1．5 综合案例

1．5．1 哥德巴赫猜想问题

1．5．2 连续整数问题

本章小结

第2篇 线性结构篇

第2章 线性表

2．1 线性表的抽象数据类型

2．1．1 线性表的定义

2．1．2 线性表的抽象数据类型描述

2．2 线性表的顺序存储结构

2．2．1 线性表的顺序存储结构——顺序表

2．2．2 顺序表基本运算的实现

2．3 线性表的链式存储结构

2．3．1 线性表的链式存储结构——链表

2．3．2 单链表基本运算的实现

2．3．3 双链表

2．3．4 循环链表

2．3．5 STL与链表

2．4 综合案例

2．4．1 一元多项式的表示及相加运算

2．4．2 魔法师发牌问题

2．4．3 约瑟夫问题

本章小结

第3章 栈与队列

3．1 栈

3．1．1 栈的概述

3．1．2 栈的顺序存储结构

3．1．3 栈的链式存储结构

3．2 栈综合案例

3．2．1 进制转换

3．2．2 表达式求值

3．2．3 检验表达式中的括号匹配情况

3．2．4 栈与递归问题

3．3 队列

3．3．1 队列的定义和抽象数据类型

3．3．2 队列的顺序存储

3．3．3 队列的链式存储

3．3．4 优先级队列

3．4 STL中的栈与队列

3．4．1 STL中的栈

3．4．2 STL中的队列

3．4．3 STL中的优先队列的使用方法

3．5 队列综合案例

3．5．1 打印杨辉三角形

3．5．2 报数问题

3．5．3 舞伴问题

……

第3篇 树形结构篇

第4篇 图形结构篇

第5篇 数据运算篇

附录A 全国计算机专业数据结构考研大纲

参考文献

第1章绪论

数据结构针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。学习此课程的目的是了解计算机处理对象的特性，将实际问题中涉及的处理对象在计算机中表示出来并对它们进行处理。例如公交车线路问题，如何换乘车用最短的时间到达目的地，或者如何用最短的距离到达目的地等。本章是数据结构的基础，主要介绍数据结构的基本概念、数据的逻辑结构和存储结构、抽象数据类型和算法性能分析等基础知识。

1.1什么是数据结构

1.1.1数据结构的产生与发展

“数据结构”是计算机及相关专业的专业基础课之一，主要学习用计算机实现数据组织和数据处理的方法。它也为计算机专业的后续课程(如操作系统、编译原理、数据库原理和软件工程等)的学习打下坚实的基础。

随着计算机应用领域的不断扩大，非数值计算问题占据了当今计算机应用的绝大部分，简单的数据类型已经远不能满足需要，各数据元素之间的复杂关系已经不是普通数学方程式所能表达的了，且无论是设计系统软件，还是应用软件，都会用到各种复杂的数据结构。因此，掌握好数据结构课程的知识，对于提高解决实际问题的能力将会有很大的帮助。实际上，一个“好”的程序无非是选择了一个合理的数据结构和一个好的算法，而好算法的选择很大程度上取决于描述实际问题所采用的数据结构。所以，要想编写出“好”的程序，仅学习计算机语言是不够的，必须扎实地掌握数据结构的基本知识和基本技能。因此，在程序设计中，往往遵循“程序=数据结构+算法”的法则。

在了解数据结构的重要性之后，开始讨论数据结构的相关定义。本节先从一个简单的学生表示例入手，然后给出数据结构严格的定义，接着分析数据结构的常见类型，最后给出数据结构和数据类型之间的区别和联系。

……

本书以绪论篇、线性结构篇、树型结构篇、图型结构篇、数据运算篇由易到难讲解知识点, 层次分明 ; 以STL框架在软件编程大赛中的综合应用进行分解完成知识点的应用, 实用性较强 ; 以算法应用案例总结每个篇章的数据结构知识点, 改变了目前数据结构教材中算法应用分散的弊端, 突出应用式驱动教学 ; 注重了数据结构知识点的“底层基础”和“顶层应用”。