《2022年全国计算机等级考试四级复习纲要线性表.docx》由会员分享，可在线阅读，更多相关《2022年全国计算机等级考试四级复习纲要线性表.docx（6页珍藏版）》请在金锄头文库上搜索。
1、 2022年全国计算机等级考试四级复习纲要：线性表二、线性表 （1）线性表及其根本操作 线性表是n0个元素的一个有限序列:（a 1 ，a 2 ，a 3 ，a n- 1 ，a n ，）表中元素的个数n称为表的长度，长度n=0的表称为空表。表元素又称为结点，线性表的一个重要特性是可以根据诸元素在表中的位置确定它们在表中的先后次序。若n1，则a 1 ，为第一个元素，a n 为最终一个元素。元素a i-1 先于a i ，我们称a i-1 为a i 的前驱;a i 在a i-1 之后，a 1 为a i-1 的后继。除第一个元素外，每个元素都有一个且仅有一个直接前驱;除最终一个元素外，每个元素都有一个且仅
2、有一个直接后继，下面所列的是其中一些常用的运算。 查找运算 查找线性表的第i（0in-1）个表元; 在线性表中查找具有给定键值的表元; 插入运算 把新表元插在线性表的第i（0in）个位置上; 把新表元插在具有给定键值的表元的前面或后面; 删除运算 删除线性表的第i（0in-1）个表元; 删除线性表中具有给定键值的表元; 其他运算 统计线性表元的个数; 输出线性表各表元的值; 复制线性表; 线性表分析; 线性表合并; 线性表排序; 按某种规章整理线性表。 （2）线性表的存储 有多种存储方式能将线性表存储在计算机内，其中最常用的是挨次存储和链接存储。 线性表的挨次存储 线性表的挨次存储是最简洁的存
3、储方式。程序通常用一个足够大的数组，从数组的第一个元素开头，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i（0in-1）个元素中，用数组元素的挨次存储来表达线性表中结点的先后次序关系。用数组存储线性表的优点是能直接访问线性表中的任一结点。 用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和削减的要求相冲突;二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便。 线性表的链接存储 线性表链接存储是用链表存储线性表，最简洁的用单链表。如从链表的第一个表元开头，将线性表的结点依次存储在链表的各表元中
4、。即线性表的第i个结点存储在链表的第i（0in-1）个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是*链接指针来表达线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是线性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。 其缺点也主要有两条:一是每个表元增加了一个后继指针成分，要花费更多的存储空间;二是不便随机地直接访问线性表的任一结点。 （3）线性表上的查找 线性表上的查找运算是指在线性表中找某个链值的结点。依据线性表的存储形式和线性表本身的性质差异，
5、有多种查找算法，如:挨次查找、二分法查找、分块查找、散列查找等。 （4）线性表的新结点插入挨次存储线性表的插入: 设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0in）个位置上。完成插入主要有以下几个步骤: 检查插入要求的有关参数的合理性; 把原来第n-1个结点至第i个结点依次往后移一个数组元素位置; 把新结点放在第i个位置上; 修正线性表的结点个数。 （5）栈 堆栈的工作原理是采纳后进先出（LIFO）技术，栈顶由中心处理器中的堆栈指示器（SP）指出。在执行PUSH操作中SP减量，而在POP操作中SP增量。 下面从数据构造的角度，进一步说明堆栈的根本概念与操作
6、。需要说明的是，其工作原理与前面所介绍的是全都的，不同的是脱离了硬件背景，例如，栈顶指针不是中心处理器的某个存放器的内容，而是一个抽象的数据构造。来源： 栈是一种特别的线性表，这种线性表只能在固定的一端进展插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。由于元素是按后进先出的次序入栈和出栈的，所以栈又称后进先出表（Last In First Out），简称LIFO表。栈的根本操作有: create（s） 建立一个空栈s。 empty（s） 测试栈是否为空栈。 full（s） 测试栈是否满。 push（x
7、，s） 将元素x插入栈s的栈顶。 top（s） 取栈顶元素。 pop（s） 删除栈顶元素。 由于栈是一种特别的线性表，栈的各种操 作实际上是线性表的操作的特别情形，所以表示线性表的方法同样可以用来表示栈。 （6）队列 队列可看作是插入在一端进展，删除在另一端进展的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素。队列的最终一个元素肯定是最新入队的元素。因此队列又称先进先出表（First-In-First-Out）。 日常生活中排队购物就是队列应用的例子:新来的顾客排在队尾等待，排在队头的顾客购物后离开队伍。队列的根本操作有: create（Q）建立一个空队列。 empty（Q）测试队列是否为空队列。full（Q）测试队列是否为满。front（Q）取队头元素。 enq（X，Q）向队列中插入一个元素X。enq（Q）删除队头元素。
