数据结构

章节摘录

　　1.数据的逻辑结构　　这些数据之间存在什么样的内在联系？在这些数据中，有且只有一个结点是表首结点，它前面没有其他结点，后面有一个和它相邻的结点；有且只有一个结点是表尾结点，它后面没有其他结点，前面有一个和它相邻的结点；除这两个结点之外，表中所有其他的结点都有且仅有一个和它相邻的位于它之前的结点，也有且仅有一个和它相邻的位于它之后的结点。上述这些就是用户信息表的逻辑结构。　　2.数据的存储结构　　数据在计算机中的存储方式称为存储结构。将用户信息表中的所有结点存人计算机时，就必须考虑存储结构。使用C语言进行设计时，常见的方式是用一个结构数组来存储整个用户信息表，每一个结构数组元素是一个结构，它对应于用户信息表中的一个结点。用户信息表中相邻的结点，对应的结构数组元素也是相邻的，或者说在这种存储方式下，逻辑相邻的结点就必须物理相邻。这是一种被称为顺序存储的方式，当然，还有其他的存储方式。　　3.数据的运算集合　　对数据的处理必定涉及到相关的运算。在上述用户信息表中，可以进行删除一个用户、增加一个用户和查找某个用户等操作。应该明确指出这些操作的含义。比如删除操作，是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作。为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。　　对于一批待处理的数据，只有分析清楚上面3个方面的问题，才能进行有效的处理。　　数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。　　在讨论一个数据结构时，数据结构所含的3个方面缺一不可，也就是说，只有给定一批数据的逻辑结构和它们在计算机中的存储结构，并且定义了数据运算集合，才能确定一个数据结构。例如，在后面的章节中将要介绍的栈和队列，它们的逻辑结构是一样的，它们都可以用同样的存储结构，但是由于所定义的运算性质不同，它们成为两种不同的数据结构。

前言

　　数据结构是计算机专业重要的专业基础课程与核心课程之一。从2009年开始，全国硕士研究生入学统一考试计算机科学与技术学科实行全国联考，考试科目定名为计算机学科专业基础综合，该考试科目涵盖4门课程，数据结构为其中重要的1门，其所占比例和分值最高。　　数据结构课程主要是学习基本数据结构及其应用、检索和排序算法的各种实现方法与分析比较，对于选用何种描述工具对数据结构和算法进行描述，我们认为各有千秋。通过近几年教学实践和教学改革研究表明，在数据结构教学中，对数据结构本质和各种算法思想的掌握与理解并不是依赖于描述工具。实践表明，对于熟练掌握C语言的读者，使用C语言描述算法，读者可以将学习精力集中于算法思想的理解，有利于数据结构的教学。　　为适应我国计算机科学技术的应用和发展，进一步提高汁算机专业和相关专业“数据结构”课程的教学质量，2004年，笔者根据多年教学的体会，结合高等教育大众化的趋势，在分析国内、外多种同类教材的基础上，编写出版了《数据结构（C语言版）》。该书先后印刷多次，受到读者的关注和欢迎。　　本书修正了第1版中的一些错误，对全书内容做了进一步的优化、补充和完善。主要的修订如下。　　1.对基本的数据结构，重点讨论其基本操作，仍然采用抽象数据类型的观点进行描述。在第1版中，对一个数据结构讨论时，我们往往给出了较多的操作，比如插入操作，就有“在某个位置插入”和“在某个元素值后插入”等，在修订时，我们对操作进行了删减与合并，每一种数据结构只对主要的操作算法进行讨论和描述，这样既突出了重点，又可以保证教学效果。　　2.尽量使用简短、容易记忆的函数名。在第1版中，我们在对算法实现的函数命名时，使用了较为完整的表达形式，如第1版中，建立一个空的链式栈的函数为initlinkstack（），第2版中改为init（）。我们在教学中发现，在C语言编程环境下，使用简洁的函数名更适合教学需要。

书籍目录

第1章　概论　　1.1　数据结构的基本概念与术语　　  1.1.1　数据结构的基本概念　　  1.1.2　数据的逻辑结构　　　1.1.3　数据的存储结构　　　1.1.4　数据的运算集合　　1.2　数据类型和抽象数据类型　　　1.2.1　数据类型　　　1.2.2　抽象数据类型　　　1.2.3　抽象数据类型的描述和实现　　1.3　算法和算法分析　　　1.3.1　算法的基本概念和基本特征　　　1.3.2　算法的时间复杂度和空间复杂度　　习题　　第2章　线性表及其顺序存储　　2.1　线性表　　2.2　顺序表　　　2.2.1　顺序表的基本概念及描述　　　2.2.2　顺序表的实现　　2.3　栈　　　2.3.1　栈的基本概念及描述　　　2.3.2　顺序栈及其实现　　　2.3.3　栈的应用之一——括号匹配　　　2.3.4　栈的应用之二——算术表达式求值　　2.4　队列　　　2.4.1　队列的基本概念及描述　　　2.4.2　顺序队列及其实现　　　2.4.3　顺序循环队列及其实现　　习题　　第3章　线性表的链式存储　　3.1　链式存储　　3.2　单链表　　　3.2.1　单链表的基本概念及描述　　　3.2.2　单链表的实现　　3.3　带头结点的单链表　　　3.3.1　带头结点的单链表的基本概念及描述　　　3.3.2　带头结点的单链表的实现　　3.4　循环单链表　　　3.4.1　循环单链表的基本概念及描述　　　3.4.2　循环单链表的实现　　3.5　双链表　　　3.5.1　双链表的基本概念及描述　　　3.5.2　双链表的实现　　3.6　链式栈　　　3.6.1　链式栈的基本概念及描述　　　3.6.2　链式栈的实现　　3.7　链式队列　　　3.7.1　链式队列的基本概念及描述　　　3.7.2　链式队列的实现　　习题　　第4章　字符串、数组和特殊矩阵　　4.1　字符串　　　4.1.1　字符串的基本概念　　　4.1.2　字符串类的定义　　　4.1.3　字符串的存储及其实现　　4.2　字符串的模式匹配　　　4.2.1　朴素的模式匹配算法　　　4.2.2　快速模式匹配算法　　4.3　数组　　　4.3.1　数组和数组元素　　　4.3.2　数组类的定义　　　4.3.3　数组的顺序存储及实现　　4.4　特殊矩阵　　　4.4.1　对称矩阵的压缩存储　　　4.4.2　三角矩阵的压缩存储　　　4.4.3　带状矩阵的压缩存储　　4.5　稀疏矩阵　　　4.5.1　稀疏矩阵类的定义　　　4.5.2　稀疏矩阵的顺序存储及其实现　　　4.5.3　稀疏矩阵的链式存储及实现　　习题　　第5章　递归　第6章　树型结构　第7章　二叉树　第8章　图　第9章　检索　第10章　内排序　参考文献　

编辑推荐

　　理论与实践并重，内容涵盖考研大纲要求。算法要点有详细的图示，算法采用C语言描述，可以直接调用。教学资源丰富，提供教学计件、所有算法的源代码、测试用例等。

作者简介

《数据结构(C语言版)(第2版)》介绍了数据结构的基本概念和基本算法。全书共分为10章，包括线性表及其顺序存储、线性表的链式存储、字符串、数组、特殊矩阵、递归、树型结构、二叉树、图、检索、内排序等内容。《数据结构(C语言版)(第2版)》内容丰富，逻辑性强，文字清晰流畅，既注重理论知识，又强调工程实用。书中既体现了抽象数据类型的观点，又对每个算法的具体实现给出了完整的C语言源代码描述。

与《数据结构(C语言版)(第2版)》配套的电子教案和书中所有算法的源代码均可从人民邮电出版社教学服务与资源网(www.ptpedu.com.cn)上免费下载。

《数据结构(C语言版)(第2版)》可作为高等院校计算机专业及相关专业本科生“数据结构”课程的教材，也可以作为从事计算机工程与应用的广大读者的参考书。

图书封面

---

 数据结构下载

---