本书涵盖数据结构基础知识和常见算法设计技术，主要内容包括线性表、树、图、散列等。全书重点介绍算法设计、算法描述和相应C程序编码，并给出相应的数据结构应用实例的讲解，适合作为高等院校计算机及相关专业学生的数据结构课程教材，也可作为计算机应用系统开发人员及相关人员学习数据结构知识的参考书或培训教材。

　　本书特点
　　●优选内容，侧重常用数据结构问题。
　　●建立由浅入深、由简到繁、由易到难的讲授体系。
　　●强化实践，特别注重算法设计过程的问题分析、逻辑思路、算法特点、算法表述和C语言程序设计能力的培养。
　　●强调数据结构的应用性，以阐明数据结构技术的价值。
　　●章首列出本章要点，章尾给出丰富的不同类型的习题，帮助学生掌握全章的知识要点。
　　●深入浅出、文句流畅、文图兼施、通俗易懂、重点突出。
　　●电子教案请登录机工新阅读网站(www.cmpreading.com)下载。

无

数据结构是计算机及相关专业的一门重要的基础课程。有人说，数学是锻炼思想的体操；我们说，数据结构是建立和运用逻辑思维的工具。其实，每个人每天都有许多问题需要解决，而问题的实质就是对象和行为两个方面。具体到计算机领域，所谓对象就是数据和数据的构造，行为就是数据的活动方式和活动过程。两者的结合就是“数据结构+算法”。将算法作用于数据结构的结果就是问题的解。在这个过程中，每个人都有意或无意地运用着数据结构知识、方法和技术。计算机系统本身是一个运行数据结构和算法的装置，软件更是如此。根据软件的定义，数据和程序是软件的主体。程序是作用于数据的算法或处理过程。开发软件的本质是构造数据和存储数据、设计算法和编写程序。因此，如果有意识地运用数据结构知识、方法和技术，就能开发出有效、可靠、优秀的软件成果。掌握数据结构的原理、知识和技术对灵活应用、深刻理解和全面认识现有软件也十分有益。
　　数据结构是一门技术性较强的课程。学习数据结构就是要掌握构造和存储数据以及设计和表述算法的方法和能力，甚至运用某种程序设计语言（如C语言）编写程序的方法和能力。作者在多年的数据结构课程教学实践中发现，绝大多数学生在课程结束时还不能写出正确成功的算法，哪怕要解决的是很简单的数据结构问题。因此，作者一直在思考如何改革教材的体系结构、内容重点和表述方法，以及教学方法和教学过程等问题。近几年，作者有机会参与和从事计算机应用型人才及职业技术人才的培养和教育工作，从中深深地认识到侧重技术教学、实践教学和能力培养的重要意义和实践意义，深知对这类教学层次之教材的迫切需求。在本书编写过程中，作者试图进行初步尝试和改革。第一，对内容进行优选，侧重常用数据结构问题。遵循“伤其十指不如断其一指”的原则，使学生掌握常用数据结构问题的算法设计，初步建立起逻辑思维基础和方法。通过相应训练，让学生能正确写出简单算法，增强学生的成就感和学习的信心。第二，建立由浅入深、由简到繁、由易到难的教材体系，使学生能循序渐进、自然地进入数据结构领域。尽管较早接触到的算法是极其简单的，但它仍是一个算法。麻雀虽小，五脏俱全。先从解剖麻雀、认识麻雀入手，再到解剖马、认识马，这是一个很好的学习方法，可以为之后学习较复杂数据结构问题奠定基础。第三，强化实践，注重能力，特别注重算法设计过程的问题分析、逻辑思路、算法特点、算法表述和C语言程序设计能力的培养。书中给出大量算法实例和程序，以及部分算法运行所需要的完整环境程序，供学生验证、实验和模仿。学生应能借助实例达到举一反三的目的。在编写C语言程序时，注意算法的表现力、可读性和易理解性。尽量使用朴素的程序设计技术，而不过高追求编程技巧。从这个角度来说，不要求读者精通C语言，只要有基本的C语言程序设计知识就可以。第四，强调数据结构的应用性，以阐明数据结构技术的价值。在讲述每种数据结构问题之后，都列举了学生比较熟悉的问题作为应用实例，做出比较透彻的分析，演示实例的运行过程，给出算法和程序。作为尝试，还将排序和查找作为应用问题分散到相关章中加以介绍和讨论。第五，为使学生抓住课程重点，每章开头列出本章要点和知识点。每章的习题类型丰富，力图覆盖全章的知识要点。第六，在内容表述上注意做到深入浅出、文句流畅、图文并茂、通俗易懂、重点突出，以期达到让读者“一看就懂，一学就会，一练就通，举一反三”的目的。
　　本书适合作为高等院校、职业技术院校计算机及其相关专业学生的数据结构课程教材，也可作为计算机应用系统开发人员及相关技术人员的学习参考书或培训教材。
　　全书共8章和1个附录，由3人参与编写。史九林编写了第1~5章。陶静编写了第7章，整理了全部附录。孙颖编写了第6章和第8章。陶静编制并调试通过了书中绝大部分C语言程序。全书由史九林策划、设计和统稿。
　　在本书编写过程中，得到了南京大学计算机科学与技术系徐洁磐教授的支持、指导、帮助和关怀；还得到了（南京）金肯职业技术学院计算机与通信工程系领导，以及计算机应用技术专业的支持。本书由南京大学成颖副教授审阅，并提出了许多建设性意见。在此一并表示感谢。
　　由于作者水平有限，时间仓促，书中疏漏和错误在所难免，希望读者批评指正。

　　作者
　　2008年2月于南京

本书涵盖数据结构基础知识和常见算法设计技术，主要内容包括线性表、树、图、散列等。全书重点介绍算法设计、算法描述和相应C程序编码，并给出相应的数据结构应用实例的讲解，适合作为高等院校计算机及相关专业学生的数据结构课程教材，也可作为计算机应用系统开发人员及相关人员学习数据结构知识的参考书或培训教材。

　　本书特点
　　●优选内容，侧重常用数据结构问题。
　　●建立由浅入深、由简到繁、由易到难的讲授体系。
　　●强化实践，特别注重算法设计过程的问题分析、逻辑思路、算法特点、算法表述和C语言程序设计能力的培养。
　　●强调数据结构的应用性，以阐明数据结构技术的价值。
　　●章首列出本章要点，章尾给出丰富的不同类型的习题，帮助学生掌握全章的知识要点。
　　●深入浅出、文句流畅、文图兼施、通俗易懂、重点突出。
　　●电子教案请登录华章网站(www.hzbook.com)下载。

前言

教学建议

第1章绪论

11数据和数据结构

111信息和数据

112数据项和数据元素

113数据结构

12算法

121什么是算法

122算法有什么要求

123如何设计算法

124怎样描述算法

13浅谈算法分析

131时间效率分析

132空间效率分析

14数据结构应用价值

习题一

第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4线性表结构的应用

　　241数据查重

　　242基于线性表的排序

　　243基于线性表的查找

　　习题二

第3章栈和队列

　　31栈

　　311栈的定义及其基本操作

　　312顺序栈及其操作

　　313链栈及其操作

　　314栈结构的应用

　　32队列

　　321队列的定义及其基本操作

　　322顺序队列及其操作

　　323循环队列及其操作

　　324链队列及其操作

　　325队列结构的应用

　　习题三

第4章串和数组

　　41串

　　411串的定义

　　412串间关系

　　413串的基本操作

　　414串的存储结构

415关于串的几个算法

　　42数组

　　421数组的定义

　　422一维数组

　　423二维数组

　　424矩阵和数组

　　43特殊矩阵的数组存储

　　431对角线矩阵的数组表示

　　432三角形矩阵的数组表示

　　433对称矩阵的数组表示

　　434稀疏矩阵的数组表示

　　435稀疏矩阵的转置算法

　　44数组和串的应用——书目检索

　　441一般讨论

　　442书目检索的基本算法

　　443书目检索的综合算法

　　习题四

第5章树

51一般树

　　511树的定义和基本操作

　　512关于树的几个术语

　　513树的结构特点

　　514树的基本操作

　　515树的存储结构

　　516树的遍历

　　52二叉树

　　521二叉树定义和主要性质

　　522二叉树的基本操作

　　523二叉树的存储结构

　　524二叉树的遍历

　　53树的常见应用

　　531哈夫曼树

　　532决策树

　　533二叉排序树

　　534折半查找与折半判定二
叉树

　　535快速排序与二叉树

　　536合并排序与二叉树

　　习题五

第6章文件

61文件的基本概念

611什么是文件

612文件的逻辑组织

613文件的存取方法

62文件的存储

621物理记录与逻辑记录的
关系

622文件存储结构

623磁盘空间管理

63文件目录

631文件目录的组成

632文件目录的结构

64文件索引

641多级索引

642B-树索引和B+树索引

643索引顺序文件

65文件操作

651文件管理系统

652记录的成组与分解

653文件缓冲区和用户区

654文件操作

习题六

第7章图

71图的基本概念

711图的定义

712关于图的若干术语

713图的基本性质

714图的基本操作

72图的存储结构

721邻接矩阵表示法

722有关邻接矩阵的算法

723邻接表表示法

73图的遍历

731深度优先遍历

732广度优先遍历

74图的常见应用

741最短路径问题

742最小代价生成树问题

743拓扑排序

习题七

第8章散列

81散列表和散列函数

811散列表

812散列函数及其设计

82冲突及其解决方法

821什么是冲突

822解决冲突的常用方法

83散列表的设计

831散列表的设计原则

832常用的散列表算法

84散列应用之一——散列词汇表

841词汇表及其应用

842散列词汇表的结构

85散列应用之二——散列文件

851散列文件的组织

852散列文件的操作

习题八

附录

参考文献