数据结构
2008-4
机械工业出版社
吴子东 编
191
《普通高等教育十一五国家级规划教材·数据结构（C语言版）》是根据高职高专教育的特点、培养目标和教学要求而编写。全书共分8章，依次介绍了数据结构的基本概念、线性表、链接表、数组和广义表、树、图、查找和排序等。每章用大量的实例和图表来说明基本概念和方法。每章后配有丰富的练习题并给出了习题的参考答案。教材采用C语言与类C相接合的方式作为算法的描述语言，算法也尽可能地少用抽象定义，而更多的是给出具体算法，并力求算法更接近于实际应用，使读者能更快地提高编程能力。结合现代教育技术，教材配有多媒体课件以辅助教学，对抽象的数据结构辅之以形象的动画，不仅能提高学生的学习兴趣，也加深了对抽象概念的理解。
前言第1章 绪论1.1 数据结构的基本概念和术语1.2 算法描术和算法分析习题第2章 线性表2.1线性表的定义和顺序存储2.2线性表运算的实现2.3栈2.4队列25字符串习题第3章 链接表第4章 数组和广义表第5章 树第6章 图第7章 查找第8章 排序附录参考文献
第1章 绪论 自从世界上的第一台电子计算机于1946年在美国面世以来，计算机的软硬件技术得到了飞速的发展。计算机的应用领域从最初的科学计算已发展到人类活动的各个领域。数据是计算机可以直接处理的最基本和最重要的对象。科学计算、数据处理、过程控制以及对文件的存储和检索及数据库技术等，都是对数据进行加工处理的过程。因此，必须研究数据的特性及数据间的相互关系及其对应的存储表示方法，并利用这些特性和关系设计出一个结构性好、效率高的算法和程序。数据结构这门学科就是在计算机的发展过程中应运而生的，它是计算机学科的核心课程，在计算机系统软件和应用软件中都要用到各种类型的数据结构。学好数据结构这门课程对于学习计算机专业的其他课程，如操作系统、编译原理（编译技术）、数据库管理系统、软件工程、人工智能等都是十分有益的。随着计算机的发展人们对数据结构越来越重视，认为程序设计的实质就是对要处理的问题选择一种好的数据结构，并在此结构上施加一种好的算法。著名的计算机科学家N．Wiah写的《算法+数据结构=程 序》一书正是体现了这种观点。对数据结构这一学科的主要研究范围包括：数据的逻辑结构和物理结构，并在这种结构上定义相关的操作运算，设计并实现相应的算法，分析算法的效率，以达到提高程序质量的目的。其中，逻辑结构是指数据元素之间的关联方式；物理结构又称存储结构，是指在计算机中如何具体存储数据的各种逻辑结构。同一种逻辑结构可以有几种不同的物理结构来实现。因此，从某种意义上讲研究物理结构更为重要。 1．1数据结构的基本概念和术语 1．数据（Data）数据是指能输入到计算机中并能被计算机处理的一切对象。在这里的所谓数据必须作广义的理解，它是指能够被计算机识别、存储和加工处理的一切信息。它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数等；非数值数据包括字符、文字、图形、图像、语音等。因此，大到一本书、一篇文章、一张图表、一幅照片、一首歌曲等，小到一条语句、一个单词、一个算式、一个数值、一个字符等都是数据。今后随着计算机的发展，数据的范围还将不断扩大。 2．数据元素（DataElement）数据元素是一个数据整体中相对独立的基本单位。由于数据的范围非常广泛，因此基本单位也是可大可小的。大到一本书、一张图表、一幅照片、一首歌曲等，小到一个数值、一个字符等都是数据元素。对于较大的单位，一个数据元素可由若干个数据 项（DataItem）组成，例如，一本书的目录卡片就可以包括书名、作者、出版社、出版日期等数据项。 3．数据对象（DataObject）数据对象是具有相同性质的数据元素的集合，是数据的一个子集。在某个具体问题中，数据元素都具有相同的性质，属于同一数据对象，例如：整数集、实数集、字符集等，不论是有限集合还是无限集合，都是数据的一个子集。 4．数据结构（DataStructure）数据结构是指相互之间存在着一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。
