资源描述：
《【软件技术基础】基本数据结构及其运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章基本数据结构及其运算2.1数据结构的基本概念2.2线性表2.3栈及其应用2.4队列及其应用2.5线性链表2.6数组与字符串2.7树与二叉树2.8图2.9索引存储结构数据是计算机化的信息，即计算机处理的对象是数据。各数据之间的一定关系，称为数据的逻辑结构，数据在计算机中的存储位置有着一定的关系，称为数据的物理结构（或存储结构）。数据结构作为计算机的一门学科，它研究的内容，通常要涉及以下三个方面的问题：①数据的逻辑结构；②数据的存储结构；③对各种数据结构进行的运算。主要目的是为了提高数据处理的效率。包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计
2、算机存储空间。2.1数据结构的基本概念数据结构是指相互有关联的数据元素的集合。组成该数据结构（包括逻辑结构和存储结构）的数据元素称为一个结点。在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，反映了该集合中的数据元素所固有的一种结构。数据元素之间的任何关系都可以用前后件关系来描述。1．数据的逻辑结构所谓结构实际上就是指数据元素之间的前后件关系。一个数据结构应包含以下两方面的信息：①表示数据元素的信息。②表示各数据元素之间的前后件关系的信息。数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的
3、存储位置无关。数据结构实际上是数据的逻辑结构。数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=(D,R)例2.1一年四季的数据结构可以表示成B=(D,R)D={春,夏,秋,冬}R={(春,夏),(夏,秋),(秋,冬)}例2.3n维向量X=(x1,x2,…,xn)也是一种数据结构。即X=(D,R)，其中数据元素的集合为：D={x1,x2,…,xn}关系为：R={(x1,x2),(x2,x3),…,(xn–1,xn)}例
4、如，m×n的矩阵是一个数据结构。在这个数据结构中，矩阵的每一行Ai=(ai1，ai2，…，ain)，i=1,2,…,m可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为：D={A1，A2，…，Am}D上的一个关系为：R={(A1，A2)，(A2，A3)，…，(Ai，Ai+1)，…Am–1，Am}}显然，数据结构A中的每一个数据元素Ai（i=1,2,…,m）又是另一个数据结构，即数据元素的集合为：Di={ai1，ai2,…，ain}Di上的一个关系为：Ri={(ai1，ai2)，(ai2，ai3)，…，(ai，ai,j+1)，…，(ai,n–1，ain)}一个数据结构
5、除了用二元关系表示外，还可以直观地用图形表示。反映家庭成员间辈份关系的数据结构可以用图2.2所示的图形表示。例2.4用图形表示数据结构B=（D，R），其中D={di
6、1≤i≤7}={d1，d2，d3，d4，d5，d6，d7}R={(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}这个数据结构的图形表示如图2.3所示。在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。通常，一个数据结构中的元素结点可能是在动态变化的。数据结构中的结点（即数据元素）个数在动态地变化，而且，各数据元素之间的关系也有可能在动态地变化。如
7、果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。例如，图2.4所示的数据结构显然是满足上述两个条件的，但它不属于线性结构这个类型，因为如果在这个数据结构中删除结点A后，就不满足上述的条件①。一个数据结构不是线性结构，则称之为非线性结构。线性结构与
8、非线性结构都可以是空的数据结构。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。2．数据的存储结构一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。常用的存储结构有顺序、链接、索引、散列等存储结构。（1）顺序存储结构顺序存储结构主要用于线性结构。在这种存储方式中，把逻辑上相邻的数据元素
