文档介绍：第2章数据结构与算法
【考点一】基本概念
数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。数据对象是具有相同性质的数据元素的集合。通常,一个数据对象中的数据元素不是孤立的,而是彼此之间存在着一定的联系,这种联系就是数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来,因此,数据结构概念一般包括三方面的内容:数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的运算的集合。
(1)数据的逻辑结构数据的逻辑结构只抽象地反映数据元素之间的逻辑关系,它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构两大类。线性结构的逻辑特征是:有且仅有一个开始结点和一个终端结点,并且所有的结点都最多有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是:一个结点可能有多个直接前驱和直接后继。树、图等都是非线性结构。
(2)数据的存储结构数据的存储结构是数据的逻辑结构在计算机存储器里的实现(亦称为映象)。它是依赖于计算机的,并有四种基本的存储映象方法。它们是:
①顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元内,结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方法主要用于线性的数据结构,非线性的数据结构也可以通过某种线性化方法来实现顺序存储
②链接存储方法在链接存储方法中,逻辑上相邻的结点在物理位置上未必相邻,结点间的逻辑关系是由附加的指针字段表示的。
③索引存储方法该方法通常是在存储结点信息的同时,还建立一个附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:关键字,地址。关键字是能唯一标识一个结点的那些数据项。
④散列存储方法在散列存储方法中,结点的存储地址是根据结点的关键字值直接计算出来的。上述四种基本的存储方法也可以组合起来对数据结构进行存储映象。
(3)数据的运算数据的运算定义在数据的逻辑结构之上,每种逻辑结构都有一个运算的集合。常用的运算有:查找、插入、删除、更新、排序等。显然,对数据运算的具体实现方法只有在确定了存储结构之后才能加以考虑。
(1)算法及其特征简单地说,一个算法就是一种解题方法,更严格地说,算法是由若干条指令组成的有穷序列,它必须具有以下特征:
①有穷性一个算法必须在执行有穷步后结束。
②确定性算法的每一步必须是确切地定义的,无二义性。
③可行性算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷次运算后完成。
④输入一个算法具有0个或多个输入的外界量,它们是算法开始前对算法最初给出的量。
⑤输出一个算法至少产生一个输出,它们是与输入有某种关系的量。算法的含义与程序十分相似,但二者又有区别。一个程序不一定满足有穷性,操作系统就是如此,只要整个系统不被破坏,操作系统就永远不会停止,所以操作系统程序不是一个算法。另外,程序中的指令必须是机器可以执行的,而算法中的指令则无此限制。但是,一个算法如果用机器可执行的语言书写,则它就是一个程序。对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。
(2)算法的分析求解同一个问题可以有多种不同的算法,评价一个算法的优劣除了正确性和简明性外,主要考虑两点:一是执行算法所耗费的时间,二是执行算法所耗费的存储空间,特别是辅助存储空间的耗费。就这两者而言,前者显得比后者更为重要,在数据结构中往往更注重对算法执行时间的分析。一个算法所耗费的时间是该算法中每条语句的执行时间之和,而每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间,则一个算法的时间耗费就是该算法中所有语句的频度之和
【考点二】线性表
(1)线性表及其基本操作线性表是n≥0个元素的一个有限序列:(a1,a2,a3,…,an- 1 ,an)表中元素的个数n称为表的长度,长度n=0的表称为空表。表元素又称为结点,线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若n≥1,则a1,为第一个元素,an为最后一个元素。元素ai-1先于ai,我们称ai-1为ai的前驱;ai在ai-1之后,则ai为ai-1的后继。除第一个元素外,每个元素都有一个且仅有一个直接前驱;除最后一个元素外,每个元素都有一个且仅有一个直接后继。下面所列的是其中一些常用的运算。
①查找运算·查找线性表的第i(0≤i≤n-1)个表元;·在线性表中查找具有给定键值的表元;
②插入运算·把新表元插在线性表的第i(0≤i≤n)个位置上;·把新表元插在具有给定键值的表元的前面或后面;
③删除运算·删除线性表的第i(0≤i≤