快动网公共基础知识视频教程配套电子教材(pdf完整版本)(3)

有序存放的，我们姑且现在把数组A称为无序数组，把数组B称为有序数组。

针对数组A我们可以使用迭代法对数组中的每个元素进行遍历并比较每个元素的数值是否与要查找的数值相等，如果相等就认为是找到了，如果数组元素也遍历完了也没有与要查找的数据相等的则说明该数组中没有要找的数。

对于数组B，数组里边元素本来就是从小到大排列好了的，下标小的元素的值就小，下标大的元素的值就大。针对数组B的这种特点有没有一种更简单快捷的方法进行查找呢？我们采用专门针对有序数组的查找方法：二分查找法。

二分查找的思路是：

第一步：取出中间的元素，我们可以计算得出数组的中间下标再根据下标获取元素，这里我们把22定为中间元素，获取到了中间元素就好比把数组一分为二了（这也是二分查找名称的由来），我们姑且认为是上一半和下一半，上一半的数比下一半的数都要小，因为本来就是已经排好序的。

数组B

第二步：拿要查找的数与上一步获取的中间元素进行比较，如果相等就找到了(当然这是最好了)，如果比中间元素大就说明在数组的下一半，如果比中间元素小则说明在上一半。

第三步：根据上一步判断的要查找的数所在的范围是上一半还是下一半，然后继续重复第一步的功能，把范围再缩小一半，然后再判断是在哪个更小的范围，直到范围的大小缩小到了0则就说明查找结束。

二分查找对数据比较的次数显然比一个一个的迭代查找对数据比较的次数要少。

这里就体现出了数据结构的重要意义了，一个是无序的数组，一个是有序的数组，数据元素虽然相同但排列的顺序不同或者说前后数据元素的关系不同那么进行运算时的效率却大大不一样。我们把数组元素之间的关系称为前后件关系。

数据结构是指相互有关联的数据元素的集合。它包括以下两个方面：

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

（1）数据元素的信息

（2）各数据元素之间的前后件关系

数据结构作为计算机的一门单独的学科就是研究数据的，它研究的内容包括：

（1）研究数据之间的逻辑关系，这里的数据不是单一的数据而是一个数据集合、是一批数据。（2）研究数据之间的逻辑关系如何在内存中进行存储即数据的存储结构

（3）研究对数据的不同的存储结构的运算和操作。包括：在数据结构中插入、删除、修改数据元

素以及对数据元素的一些运算处理。1.数据的逻辑结构

数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构。数据的逻辑结构有两个要素：（1）数据元素的集合，记作D

（2）数据之间的前后件关系，记作R则数据结构B=（D，R）

其中，B表示数据结构，为了反映D中数据元素之间的前后件关系，一般用二元组来表示。假如a和b是D中的两个数据元素，为了表示a是b的前件，b是a的后件，则使用二元组(a,b)来表示它们之间的关系。例如：

一年四季的数据结构可以表示成：B=（D，R）

D={春,夏,秋,冬}

R={{春,夏},{夏,秋},{秋,冬}}2.数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或称为数据的物理结构。我们可以认为数据的逻辑结构是数据结构的一种表达方式，而数据的存储结构是真正对数据结构的应用，因为在用计算机实际处理数据时就是将数据存放在计算机内存中。

据元素的信息，而且要存储数据元素之间的前后件关系的信息。

把数据元素存储在内存中我们在学习c语言变量时就学过，如果仅仅把数据元素在内存中存储那么它们在逻辑结构中表示的前后件关系将不能和内存中存储的位置相同，比如说，{春,夏}表示“春”是“夏”的前件，但是如果用计算机程序去存储“春”和“夏”这两个数据元素不一定存储“春”的内存地址就在“夏”的前边，所以说逻辑结构表示数据元素的位置关系和计算机内存中实际存储的位置关系是可能不相同的。

必须把数据元素之间的关系也存储起来才算是完整的对逻辑结构进行存储，我们才能按照逻辑结构的描述对数据元素方便的进行运算、操作。存储前后件关系就用到了c语言中的结构体和指针，至于如何具体操作下边马上要学到。

通常情况下，数据的逻辑结构在内存中进行存储可以有多种存储方式：顺序存储、链接存储、索引存储等,采用不同的存储结构其处理效率是不一样的。

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

1.2.2数据结构的图形表示

数据结构除了用逻辑结构的二元关系表示外还可以用图形表示：如下图所示：

图1一年四季数据结构图形表示

图2家庭成员辈分关系数据结构图形表示

从上图可以看出：

（1）中间标有元素值的方框表示数据元素，称为数据结点

（2）用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结点

注意：在结构图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也称叶子结点。例如图1中“春”结点就是根结点，“冬”结点就是叶子结点。图2中，“父亲”结点为根结点“儿子”和“女儿”结点为叶子结点。例子：

用图形表示数据结构：B={D,R}，其中D=｛c1,c2,c3,c4,c5｝，R={{c1,c3},{c2,c4},{c2,c5}}

图形表示如下：

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

1.2.3线性结构和非线性结构

一个数据结构中如果一个数据元素都没有，该数据结构称为空数据结构；在空数据结构中插入一个新的元素后数据结构变为非空数据结构；

将数据结构中的所有元素全部删除，则该数据结构就变成了空数据结构。如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：（1）有且只有一个根结点

（2）每一个结点最多只有一个前件，也最多只有一个后件

线性结构

非线性结构

注意：在线性结构表中插入或删除元素，该线性表仍然应满足线性结构。如果插入或删除后不满足线性结构的特点则它就不属于线性结构。如下图所示。

如上图，只有一个根结点c1，每个结点最多有一个前件和后件，现在来看这个数据结构就是线性结构，但是如果把c1删除，就不是线性结构了，因为删除c1以后就没有根结点了，所以这个数据结构不是线性结构。

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

如果一个数据结构不满足线性结构，则称为非线性结构。

线性结构和非线性结构都可以是空的数据结构，一个空的数据结构是属于线性的还是非线性的要看具体情况，如果按照线性结构的运算规则去处理则属于线性结构，如果按照非线性结构的运算规则去处理则属于非线性结构。

(快动网()计算机等级考试自学平台公共基础知识视频教程配套课件)

1.3线性表及其顺序存储结构1.3.1

基本概念

线性表是最简单、最常用的一种数据结构，它是一种线性结构，它由一组数据元素组成。注意：这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。它可以是一个学生信息表，一个矩阵等。

非空线性表结构有如下特征：

（1）有且只有一个根结点， …… 此处隐藏：2739字，全部文档内容请下载后查看。喜欢就下载吧 ……