搜索
计算机等级考试二级公共基础知识第1章数据结构与算法1.1算法1.1.1算法的基本概念算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。1.1.1.1算法的基本特征一般来说，一个算法应具有以下4个基本特征。（1）可行性（Effectiveness）：算法在特定的执行环境中执行，应当能够得出满意的结果，即必须有一个或多个输出。（2）确定性（Definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。（3）有穷性（Finiteness）：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。1.1.1.2算法的基本要素通常，一个算法由两种基本要素组成。对数据对象的运算和操作；算法的控制结构，即运算或操作时间的顺序。（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类，如表1-1所示。表1-14类基本的运算和操作运算类型操作实例算术运算＋、－、×、÷a＋b、3－1逻辑运算与（&）、或（‖）、非（！）！1、1‖0、1&1关系运算＞＜＝≠ab、a=c、b≠c数据传输赋值、输入、输出a=0、b=3（2）算法的控制结构一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。1.1.1.3算法设计的基本方法虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。1.1.1.4算法设计的要求通常一个好的算法应达到如下目标：（1）正确性（Correctness）正确性大体可以分为以下4个层次：①程序不含语法错误；②程序对于几组输入数据能够得出满足规格说明要求的结果；③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。（2）可读性（Readability）算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。（3）健壮性（Robustness）当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。（4）效率与低存储量需求效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。1.1.2算法的复杂度算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。算法复杂度包括算法的时间复杂度和算法的空间复杂的。1.1.2.1算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数。即算法的工作量=f（n）例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，也就是时间复杂度为n3，即f（n）=O（n3）在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为0；当初始序列为自大至小有序时，基本操作的执行次数为n（n－1）/2。对这类算法，可以采用平均性态和最坏情况复杂性两种方法来分析。1.1.2.2算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（inplace）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。1.2.1数据结构的定义数据结构是计算机科学与技术领域广泛使用的一个基本术语，用来反映数据的内部构成。在给出数据结构的定义之前，我们先弄清楚几个概念。数据（data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素（dataelement）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象（dataobject）：是性质相同的数据元素的集合，是数据的一个子集。简单地说，数据结构是指相互关联的数据元素的集合，即数据的组织形式。所谓结构，就是指数据元素之间的前后件关系（或称直接前驱与直接后继关系）。例如，在考虑一日三餐的时间顺序关系时，早餐是午餐的前件（或直接前驱），而午餐是早餐的后件（或直接后继）；同样，午餐是晚餐的前件，晚餐是午餐的后件。又例如，在考虑学历的顺序关系时，小学是初中的前件，而初中是小学的后件。同样，初中是高中的前件，高中是初中的后件。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。数据结构的两个要素--数据和结构是紧密联系在一起的，数据是有结构的数据，而不是无关联的、松散的；而结构就是数据元素间的关系，是由数据的特性所决定的。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。讨论以上问题的目的是为了提高数据处理的效率，即提高数据处理的速度以及尽量节省在数据处理过程中所占用的计算机存储空间。1.2.1.1数据的逻辑结构由数据结构的定义可知，一个数据结构应包含以下两方面信息：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。在此定义中，并没有考虑数据元素的存储，所以上述的数据结构实际上是数据的逻辑结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成B=（D，R）其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一日三餐看作一个数据结构，则可表示成B=（D，R）D={早餐，午餐，晚餐}R={（早餐，午餐），（午餐，晚餐）}数据的逻辑结构包括线性结构、树型结构图、网状结构图和集合图4种。1.2.1.2数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，而且各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。1.2.3线性结构与非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在只有一个数据元素的数据结构中，删除该数据元素，就得到一个空的数据结构；在一个空的数据结构中插入一个新的元素后变成非空。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称为线性表。由此可见，在线性结构中，各数据元素之间的前后件关系是很简单的。需要特别说明的是，在一个线性表中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂。链式结构是总常用的非线性结构。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。1.3.2线性表的顺序存储结构通常，线性表可以采用顺序存储和链式存储，本小节主要讨论顺序存储结构。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征：（1）线性表中的所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。用顺序存储结构存储的线性表称为顺序表。在顺序表中，其前、后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。如长度为n的线性表（a1，a2，…，ai，…，an）的顺序存储如图1-6所示。在顺序表中，如果每个元素占有K个存储单元，则下标为i+1的元素的存储位置与下标为i的元素的存储位置之间，满足下列关系：ADR（ai+1）=ADR（ai）+K通常把顺序表中第1个数据元素的存储地址ADR（a1）称为线性表的首地址，线性表中第i个元素ai的存储地址为：ADR（ai）=ADR（a1）+（i-1）K例如，在顺序表中存储数据（14，23，25，78，15，68，27），每个数据元素占有2个存储单元，第1个数据元素14的存储地址是200，则第3个数据元素25的存储地址是：ADR（a3）=ADR（a1）+（3-1）×2=200+4=204从这种表示方法可以看到，它是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。1.4.1栈及其基本运算1．栈的定义栈（Stack）是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。例如，枪械的子弹匣就可以用来形象地表示栈结构。如图1-9(a)所示，子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当栈中没有元素时，称为空栈。例如，没有子弹的子弹匣为空栈。通常用指针top来指示栈顶的位置，用指针bottom来指向栈底。假设栈S=（a1，a2，…，an），则称a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素an。图1-9(b)是栈的