计算机公共基础知识
2021-06-14 15:57:57
供稿：网友
1.3.1 基本数据结构与算法
1．算法的基本概念及特征
算法的概念是考试的重点，是指解题方案的准确而完整的描述，它由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
算法具有可行性、确定性、有穷性、拥有足够的情报等特征。其中，确定性和有穷性是考试的重点。
算法的确定性，是指算法中的每一步骤都必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
2．算法复杂度的概念和意义
一个算法质量的好坏可从算法的时间复杂度和空间复杂度两个方面来衡量。算法的复杂度也是每次考试的重点，要注意明确有关概念。
算法的时间复杂度是指算法所需要的计算工作量；算法的空间复杂度是指执行这个算法所需要的内存 空间。
3．数据结构的定义
数据结构主要研究和讨论以下三个方面的问题：
① 数据集合中各元素之间所固有的逻辑关系，即数据的逻辑结构。
② 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
③ 对各种数据结构进行的运算。
要注意数据的逻辑结构与存储结构的区别与联系。
4．线性结构与非线性结构
根据数据结构中各元素之间前后件关系的复杂程度，一般数据结构分为两大类型：线性结构与非线性结构。要注意这两种结构的特征、它们之间的区别以及常见的有关结构。
（1）线性结构（或称线性表）有以下主要特征：
① 有且只有一个根结点，它无前件。
② 有且只有一个终结点，它无后件。
③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数称为线性表的长度，当结点个数为0时，该线性表为空表。
常见的线性结构有：线性表、栈、队列等。
（2）如果一个数据结构不是线性结构，则称之为非线性结构，常见的非线性结构有：树、二叉树、图等。
5．线性表的顺序存储结构（顺序表）及其插入与删除运算
线性表既可以采用顺序存储结构，又可以采用链式存储结构进行存储。要注意掌握二者在存储数据方面的方式与特点。
（1）线性表的顺序存储结构的特点
① 线性表中所有元素所占的存储空间是连续的。
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由此可见，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（2）线性表在顺序存储结构下的插入与删除运算
线性表在顺序存储结构下，若在第i（1in，n为线性表中元素的个数）个位置上插入一个新元素，则首先从最后一个（即第n个）元素开始，直到第i个元素之间共有n–i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i个位置。插入结束后，线性表的长度增1。
显然，在最好的情况下，插入位置在线性表的末尾进行，即在第n个元素之后插入运算，此时，不需要移动表中的元素。而在最坏的情况下，插入位置在第1个元素上，此时需要移动表中所有的元素。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。
同理，线性表在顺序存储结构下的删除运算，也需要移动表中的元素，只不过是向前移动，在最好的情况下，删除运算在线性表的末尾进行，即删除第n个元素，此时，不需要移动表中的元素。而在最坏的情况下，删除位置在第1个元素上，此时需要移动表中所有的元素。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。
线性表的顺序存储结构的特点，以及在顺序存储结构下插入与删除运算的效率是考试的重点。
6．栈与队列
要深刻领会二者的概念，以及对二者进行插入、删除运算的特点，这是考试的重点。
栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。允许插入与删除运算的一端称为栈顶，而不允许插入与删除运算的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”（First In Last Out，FILO）或“后进先出”（Last In First Out，LIFO）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。对栈常可以进行进栈、出栈、读取栈顶元素的运算。
队列是指允许在一端进行插入运算、而在另一端进行删除运算的线性表。允许插入运算的一端称为队尾，通常用一个称为队尾指针的指针指向队尾元素，即队尾指针总是指向最后被插入的元素。允许删除运算的一端称为队头，通常也用一个队头指针指向队头的元素。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”（First In First Out，FIFO）或“后进后出”（Last In Last Out，LILO）的线性表。对队列可以进行入队、退队运算。
