1.2算法及算法分析.doc

数据结构（C语言版） 第1章 绪论 PAGE 6 高等职业教育“十二五”规划教材 PAGE 7 高等职业教育“十二五”规划教材 第1章 绪 论 数据的表示是计算机科学的基础。在众多计算机应用领域中，无论是科学计算、数据处理、过程控制还是对文件的存储和检索以及数据库技术等，都是对数据进行加工处理编制程序的过程。然而要设计出一个结构好、效率高的程序，分析研究程序处理数据的特性及数据之间的相互关系，并利用这些特性和关系设计出相应的算法以有效地支持程序的实现，就成了计算机科学的核心问题。 本章首先介绍了数据结构相关的概念和术语，然后介绍了算法及算法分析。通过对本章的学习，要求读者掌握数据结构的基本概念和常用术语并了解算法描述和算法分析。 1.1 基本概念和术语 在深入地学习数据结构之前，我们首先介绍数据结构的一些基本概念和术语。 （1）数据。数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅包括整型、实型等数值类型，还包括字符、声音、图像、视频等非数值类型。 简而言之，这里所说的数据即符号，但是这些符号必须有两个前提：可以输入到计算机中和能被计算机程序所处理。 （2）数据元素。数据元素是数据的基本单位，在计算机中通常作为整体处理，也称为节点或记录。 （3）数据项。一个数据元素可以由若干个数据项组成，是数据不可分割的最小单位。在数据结构这门课程中，我们把数据项定义为最小单位，这有助于我们更好地解决问题。 （4）数据对象。数据对象是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象，数据元素是数据对象的一个实例。如自然数数据对象是集合N={1,2,3,...}。 （5）数据结构。数据结构是指互相之间存在着一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着某种关系，这种数据元素之间的关系称为数据的逻辑结构。根据数据元素之间关系的不同，???以将数据结构分为集合结构、线性结构、树型结构和图型结构。 数据的逻辑结构是指数据对象中数据元素之间的相互关系。数据的逻辑结构分为线性结构和非线性结构。 线性结构的特点是结构中有且仅有一个首节点和一个尾节点，除首节点外每个节点有且仅有一个前趋节点，除尾节点外每个节点有且仅有一个后继节点。后面章节要学习的线性表、栈、队列等都属于线性结构。 不具备上述特点的逻辑结构都属于非线性结构。如后面章节要学习的图和树都属于非线性结构。 数据除了有逻辑结构外，还具有物理结构。物理结构也叫存储结构，是指数据的逻辑结构在计算机中的存储形式。数据的存储结构应正确地反映数据元素之间的逻辑关系，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。数据元素的存储结构分为顺序存储和链式存储两种。 顺序存储是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。例如，10以内的奇数1、3、5、7、9用顺序存储结构的方式依次存放在以300为起始地址的内存单元中，并且以两个字节存放一个奇数，如图1-1（a）所示。如要读取第三个奇数，它的地址可以通过起始地址和要读取奇数的位置序号计算得到。 链式存储对逻辑上相邻的元素不要求其存储的物理位置也相邻，元素间的逻辑关系通过附设的指针来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针类型来实现。若将上例中的奇数改用链式存储结构存放，那么，第一个奇数存放在地址为300的内存单元中，第二个奇数存放的地址和第一个奇数存放的地址无关，但第二个奇数所在的地址存放在第一个奇数相关的指针中，后面奇数的存放也按如此的规律。假设使用两个字节存放一个奇数，一个字节存放一个指针，如图1-1（b）所示。如要读取第三个奇数，只能从第一个奇数所在的地址开始，通过第一个奇数关联的指针得到第二个奇数存放的地址105，找到第二个奇数并通过其关联指针得到第三个奇数存放的地址400，才能读出第三个奇数。 （a）顺序存储结构示意图 （b）链式存储结构示意图图1-1 两种存储结构示意图 数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每一种数据的逻辑结构都有相应的运算。本书在介绍每一种数据结构时，除了要介绍数据的逻辑结构和存储结构外，还要介绍在该结构上的数据运算及主要运算的实现算法。 （6）数据类型。数据类型是一组性质相同的值的集合以及定义在此集合上的一些操作的总称。数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。数据类型就是用来