软件技术基础1124.pptxVIP

1.1数据结构的主要内容

1.2基本概念和术语

1.3算法

1.4本章小结

自测习题

1.1数据结构的主要内容【例1-1】某学校课程表管理。表1-1中的课程表就是一个数据结构。课程表管理的主要功能包括：查找、浏览、插入、修改和删除。如果把表1-1中的一行看成一个记录，则在此表中，结点和结点之间的关系是一种最简单的线性关系。

【例1-2】家谱问题。图1-1所示为我国唐王朝初期的家谱，它像一棵倒立的树，清楚地描述了唐王朝家庭人员的继承关系。

图1-1唐王朝初期的家谱

【例1-3】最短路径问题。如图1-2所示，有8个城市，以0~7为其编号，带箭头的线表示城市之间的连接关系，线上的数字表示两个城市之间的距离。问题是如何确定一个城市与其他城市的最短距离。由上面三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中相关问题的学科，具体包括数据之间的逻辑关系和对数据的操作，同时还研究如何将具有逻辑关系的数据按一定的存储方式存放到计算机中。

图1-2城市之间的距离和连接关系

1.2基本概念和术语1.2.1数据、数据元素及数据项数据(Data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并能够被计算机程序处理的符号的总称。数据是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归于数据的范畴。

数据元素(DataElement)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素又称为元素、结点或记录。数据项(DataItem)是数据的不可分割的、含有独立意义的最小单位。数据项也被称为字段或域。以学生成绩表为例，如表1-2所示，整张表是数据，每一行记录称为数据元素，每一个字段称为数据项。

1.2.2数据结构数据结构(DataStructure)是相互之间存在一种或多种特定关系的数据元素的集合。这是对数据结构的一种简单解释。从1.1节中的三个例子可以看到，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系。根据数据元素之间关系的不同特性，通常有下列四类基本结构。

(1)集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。(2)线性结构：结构中的数据元素之间存在一个对一个的关系。(3)树形结构：结构中的数据元素之间存在一个对多个的关系。(4)图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。图1-3为上述四类基本结构的关系图。由于“集合”是数据元素之间关系极为松散的一种结构，因此在本书中不对其进行讨论。

图1-3四类基本结构

上述数据结构的定义只是对操作对象的一种数学描述，换句话说，是将操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构(DataLogicalStructure)。然而，讨论数据结构是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它。

数据结构在计算机中的表示(又称映像)称为数据的物理结构(DataPhysicalStructure)，又称存储结构。存储结构包括数据元素的表示和关系的表示。在计算机中，表示信息的最小单位是二进制数的一位，称为位(Bit)。在计算机中，可以用一个由若干位组合起来形成的一个位串表示一个数据元素(如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等)，通常称这个位串为元素(Element)或结点(Node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。因此，元素或结点可看成是数据元素在计算机中的映像。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储映像和非顺序存储映像，由此可得到两种主要的存储结构：顺序存储结构和链式存储结构。顺序存储的特点是：在内存中开辟一组连续的存储单元，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如，有一个数组A，含有n个元素，这n个数据元素的存储如图1-4所示。链式存储结构的特点是：借助指示元素存储地址的指针Pointer)表示数据元素之间的逻辑关系，数据元素的存储并不一定是连续的。例如，有两个数据元素，一个为“王家”，另一个为“李家”，二者的存储并不连续。为