第 1 章 概 论

　　本章要求 ：

　　1 、理解数据、数据元素和数据项的概念及其相互关系。

　　2 、理解逻辑结构、基本运算和数据结构的概念、意义和分类。

　　3 、理解存储结构与逻辑结构的关系及四种基本存储方式。

　　4 、理解算法的概念；了解算法分析的基本概念、时间复杂性及其量级的概念。

　　本章重点 ：逻辑结构和数据结构的概念。

　　本章难点 ：算法的时间复杂性分析。

　　本章在历年的国家自学考试中一般占 8 分左右，题型是选择题和填空题。

　　考核的知识点

　　一、数据、数据元素和数据项的概念

　　数据是指所有能输入计算机中并能被计算机加工、处理的符号的集合。它是信息的载体，其含义极其广泛，诸如数字、符号、文字、图形、图象、声音等都可以看作是数据。

　　数据元素是数据的 基本单位 ，通常具有完整、确定的实际意义，并被当作运算的基本单位。根据需要，数据元素又被称为元素、记录、结点、顶点。

　　数据项是数据不可再分的 最小标识单位 ，它不具有完整的实际意义，通常仅反映数据元素某一方面的属性。在很多场合下，数据项又被称为字段、数据域。

　　数据、数据元素和数据项反映出了数据组织的三个层次，它们之间的关系是数据可由若干个数据元素构成，而数据元素又可由若干个数据项构成。

　　二、数据的逻辑结构

　　所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间的逻辑关系的整体就称为数据的逻辑结构。数据的逻辑结构实际上就是数据的组织形式。

　　数据的逻辑结构分为 4 种基本类型：

　　① 集合 集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。

　　② 线性结构 线性结构中的 结点按逻辑关系依次排列形成一个“锁链”。

　　③ 树形结构 树形结构具有分支、层次特性，其形态有点象自然界中的树。

　　④ 图状结构 图状结构中的结点按逻辑关系互相缠绕，任何两个结点都可以邻接。

　　关于逻辑结构，需特别注意：

　　逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。

　　三、运算和基本运算

　　运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。根据操作的效果，可将运算分成以下两种基本类型：

　　① 加工型运算 其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；如：初始化、插入、删除、更新等操作。

　　② 引用型运算 其操作不改变原逻辑结构的“值”，只从中提取某些信息作为运算的结果。如：查找、读取等操作。

　　四、存储实现

　　存储实现的基本目标是建立数据的机内表示。数据的机内表示称为数据的存储结构。一个存储结构包括以下三个主要部分：

　　① 存储结点，每个存储结点存放一个数据元素。

　　② 数据元素之间关联方式的表示，也就是逻辑结构的机内表示。

　　③ 附加设施，如为便于运算实现而设置的“哑结点”等；如单链表的头结点。

　　四种基本存储方式：

　　① 顺序存储方式 每个存储结点只含一个数据元素。所有存储结点相继存放在一个连续的存储区里。用存储结点间的位置关系表示数据元素之间的逻辑关系。按这种方式表示逻辑关系的存储结构称为顺序存储结构。

　　② 链式存储方式 每个存储结点不仅含有一个数据元素，还包含一组指针。每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。按这种方式组织起来的存储结构称为链式存储结构。

　　③ 索引存储方式 每个存储结点只含有一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为索引存储结构。

　　④ 散列存储方式 每个结点含有一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各结点的存储位置或位置区间端点。相应的存储结构称为散列存储结构。

　　注意：可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑结构中数据元素之间的逻辑关系。也就是说，一种逻辑结构可以用多种存储结构表示，一种存储结构可以表示多种逻辑结构。

　　五、运算实现

　　一个运算的实现是指一个完成该运算功能的程序。运算实现的核心是处理步骤的规定，即算法设计。

　　算法就是解决问题的方法和步骤，可以用语言来描述。根据描述算法语言的不同，将算法分为三类：运行终止的程序可执行部分、伪语言算法和非形式算法。

　　非形式算法：用自然语言(如汉语)，同时可能还使用了程序设计语言或伪程序设计语言描述的算法称为非形式算法。

　　算法与程序的关系：算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。

　　六、算法分析

　　通常从以下几个方面评价算法(包括程序)的质量：

　　① 正确性 算法应能正确地实现预定的功能(即处理要求)。

　　② 易读性 算法应易于阅读和理解，以便于调试、修改和扩充。

　　③ 健壮性 当环境发生变化(如遇到非法输入)时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。

　　④ 高效性 即达到所需要的时空性能。

　　一个算法的时空性能是指该算法的时间性能(或时间效率)和空间性能(或空间效率)。

　　最坏情况时间复杂性和平均时间复杂性统称为时间复杂性(或时间复杂度)，用 T ( n )＝ O ( f ( n ))表示。其中 f ( n )是算法中频度最大的那条语句频度的数量级。

　　例、下列程序段的时间复杂性的量级为 。　　　　　　　　　

　　for ( i=1 ； i

　　for ( j=i ； j

　　t=t +1 ；

　　【分析】本题程序段中的执行频度最大的语句为双循环体内的 t=t+l ，它的执行频度为( n-1 ) + ( n-2 ) + … +2+1=n ( n-1 ) / 2 ，则 时间复杂性的量级为 O ( n 2 )。

　　【解答】 O ( n 2 )

　　常见时间复杂性的量级有：常数阶 O ( 1 )(即算法的时间复杂性与输入规模 n 无关或 n 恒为常数)、对数阶 O ( log 2 n )、线性阶 O ( n )、平方阶 O ( n 2 )和指数阶 O ( 2 n )。

　　空间复杂性主要关心一个算法除输入数据占用存储空间之外的附加存储空间的大小。

　　七、数据结构的概念

　　一个数据结构是由一个逻辑结构 S 和 S 上的一个基本运算集△构成的整体( S ，△)。

　　数据结构的基本任务：数据结构的设计和实现。

　　数据结构课程的主要内容就可以概括为：

　　① 数据结构(包括逻辑结构和基本运算集)的定义。

　　② 数据结构的实现(包括存储实现和运算实现)。

　　③ 数据结构的评价和选择(包括逻辑结构的选择、基本运算集的选择和存储方式的选择)。

　　程序设计的实质是数据表示和数据处理，是一个渐进的过程，需注意以下三点：

　　① 数据表示任务是逐步完成的，即数据表示形式的变化过程是：机外表示 逻辑结构 存储结构。

　　② 数据处理任务也是逐步完成的，即有转化过程：处理要求 基本运算和运算 算法。

　　③ 数据表示与数据处理是密切相关的，数据处理方式总是与数据的某种相应的表示形式相联系，反之亦然。

　　2004 年 10 月全国高等教育自学考试数据结构导论试题题目中涉及本章的题目

　　选择题( 3 道，共 6 分)

　　1 .要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为( )。

　　A .逻辑结构、存储结构、机外表示

　　B .存储结构、逻辑结构、机外表示

　　C .机外表示、逻辑结构、存储结构

　　D .机外表示、存储结构、逻辑结构

　　【分析】数据表示任务是逐步完成的，即数据表示形式的变化过程是：机外表示 逻辑结构 存储结构。

　　【解答】 C

　　2 .若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常( )。

　　A .对数阶量级复杂性大于线性阶量级

　　B .对数阶量级复杂性小于线性阶量级

　　C .对数阶量级复杂性等于线性阶量级

　　D .两者之间无法比较

　　【分析】随着自变量值的增加，对数函数与线性函数相比，线性函数的函数值增加的更快。若评价算法的时间复杂性，随着问题规模的壮大，对数阶量级与线性阶量级比较，通常对数阶量级复杂性小于线性阶量级

　　【解答】 C

　　3 .下列关于线性表的基本操作中，属于加工型的操作是( )。

　　A .初始化、求表长度、插入操作 B .初始化、插入、删除操作

　　C .求表长度、读元素、定位操作 D .定位、插入、删除操作

　　【分析】加工型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；如：初始化、插入、删除、更新等操作。引用型运算，其操作不改变原逻辑结构的值，只从中提取某些信息作为运算的结果。如：查找、读取等操作。

　　【解答】 B

　　填空题( 2 道，共 4 分)

　　16 .从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和 。

　　………………

    更多信息请访问：新浪自考频道