全国计算机等级考试《数据结构》讲解

全国计算机等级考试《数据结构》讲解全国计算机等级考试《数据结构》讲解全国计算机等级考试《数据结构》讲解资料仅供参考文件编号：2022年4月全国计算机等级考试《数据结构》讲解版本号：A修改号：1页次：1.0审核：批准:发布日期：心之所向，所向披靡第一章数据结构与算法§1概述一、基本概念数据是对客观事物所进行的描述，这种描述是采用了计算机系统能够识别、存储和处理的形式来进行的。数据元素是数据的基本单位，即数据集合中的个体。（在不同的场合又称结点、记录等）数据项是数据的不可分割的最小单位。在数据结构学科中研究的对象是数据元素，而不讨论数据项间的构成和关系。数据对象是性质相同的数据元素的集合，即数据集合的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。抽象化地描述数据元素之间的相互关系称为数据的逻辑结构，它包含两方面的要素：一是数据元素的集合D，二是在D上的一组运算和相应的运算规则或简称为关系R。数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构（也称为存储结构），一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等形式。数据结构学科主要研究如下三个方面的内容：①数据的逻辑结构；②数据的存储结构；③对各种数据结构进行的运算，即算法的设计。二、算法算法是对特定问题求解步骤的描述，它是指令的有限序列。算法的基本特征：①有穷性；②确定性；③可行性；④0个或多个输入；⑤1个或多个输出。算法的基本要素：①对数据的运算和操作：基本运算和操作包括算术运算、逻辑运算、关系运算和数据传输；②算法的控制结构：基本的控制结构包括：顺序结构、选择结构、循环结构。算法设计的基本方法：①列举法；②归纳法；③递推；④递归；⑤半递推技术；⑥回溯法。算法复杂度（性）主要包括时间复杂度和空间复杂度。所谓时间复杂度是指执行算法所需要的计算工作量。一般选取一个标准操作，找出随着问题规模n的变化，算法所执行标准操作的运算次数与其之间的函数关系f(n)，以f(n)的数量级O(n)来表示时间复杂度T(n)。常见的时间复杂度有：线性级O(n)，平方级O(n2)，对数级O(log2n)和指数级O(2n)等。分析某算法的时间复杂度时，有时还从最好情况、最坏情况、平均情况等方面进行全面比较。所谓空间复杂度是指执行算法所需要的存储空间的大小。一般也是问题规模的一个函数，取其数量级表示为O(n)。通常分析算法所需辅助空间的最大情况。§2线性表一、线性结构与非线性结构线性结构满足：①有且仅有一个根结点；②每一个结点最多有一个直接前趋结点，也最多有一个直接后继结点；③在一个线性结构中插入或删除任何一个结点后，还是线性结构。线性结构元素之间是一对一的联系。典型的线性结构有线性表、栈、队列、字符串等。如果一个数据结构不是线性结构，则称之为非线性结构。典型的非线结构有树（一对多的联系）、图（多对多的联系）等。二、线性表线性表是由n（n>=0）个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个（首元素）外，有且只有一个前趋，除了最后一个（尾元素）外，有且仅有一个后继。即线性表或是一个空表，或可表示为：（a1,a2,……,ai,……,an）其中ai是性质相同的数据元素，也称为线性表中的一个结点。线性表的长度，即表中的元素个数n，当n=0时称为空表。三、线性表的顺序存储结构（顺序表）线性表的顺序存储结构的基本特点：①线性表中所有元素所占的存储空间是连续的（一般用数组实现）；②线性表中每个元素在存储空间中是按逻辑顺序存放的，即用物理上的相邻关系来体现逻辑上的相邻关系。线性表的随机存取地址计算公式为： ADD(ai)=ADD(a1)+(i-1)*k这里ADD(ai)是第i元素的地址，k是每个元素占用空间字节数。线性表上的主要运算：①线性表的插入；②线性表的删除；③线性表的查找；④线性表的排序；⑤线性表的分解；⑥线性表的合并；⑦线性表的复制；⑧线性表的逆转。四、线性表的插入运算在长度为n的线性表(a1,a2,…,ai,…,an)的第i元素ai之前插入一个新元素x后得到的长度为n+1的线性表为(a1,a2,…,x,ai,…,an)。实现方法：要在第i（1<=i<.n）元素之前插入一个新元素x，首先要从最后一个（即第n个）元素开始，直到第i元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，在第i位置写入新元素x。插入结束后，表长度就增加了1。插入操作算法的时间复杂度分析：如果插入的位置在第n个元素之前，则只需将第n元素后移，这是最好情况；如果插入的位置在第1个元素之前，则n个元素都要后移，这是最坏情况；在等概情况下（即在任何位置插入的机率相同）平均移动元素个数为n/2。五、线性表的删除运算在长度为n的线性表(a1,a2,…,ai,…,an)中删除第i元素ai后，变为长度为n-1的线性表(a1,a2,…,ai-1,ai+1…,an)。实现方法：要删除第i（1<=i<.n）元素，首先要从第i+1元素开始，直到最后一个（即第n个）元素之间的n-i个元素依次向前移动一个位置。删除结束后，表长度减1。删除操作算法的时间复杂度分析：与插入操作类似，平均情况下需要移动表中一半的元素。两种操作的算法时间复杂度都可记作O(n)。六、线性表顺序存储结构的适用场合线性表的顺序存储结构对于小线性表或者表中元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单且易于随机读取；但这种顺序存储方式对于元素需要变动的大线性表就不太适合了，因为插入和删除操作的效率比较低。§3栈和队列栈和队列都是运算受限的线性表，各自又有自身的特点。一、栈的概念栈（也称堆栈）是限定只能在表的一端进行插入和删除的线性表。它按照“后进先出”（LIFO）的原则组织数据。表中允许插入和删除的一端叫做栈顶，表中的固定端叫做栈底。二、栈的顺序存储方式（顺序栈）一般用一维数组S[m]作为栈的存储空间，其中m为栈的最大容量。设置栈顶指针top指向下次进栈的位置。判空条件为：top==0；判满条件为：top==m。三、栈的基本运算1、入栈：先判满，若栈满不能入栈，发生“上溢”错误；不满时将新元素插入到栈顶位置后，修改栈顶指针top++。2、出栈：先判空，若栈空不能出栈，发生“下溢”错误；非空时修改栈顶指针top--，将栈顶元素赋给一个指定的变量。3、读栈顶元素：将栈顶元素赋给一个指定的变量，栈顶指针不变。当栈为空时，读栈顶元素操作失败。四、队列的概念队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。它按照“先进先出”（FIFO）的原则组织数据。表中允许插入的一端叫做队尾，允许删除的一端叫做队头。五、队列的顺序存储方式（顺序队列）一般用一维数组Q[m]作为队列的存储空间，其中m为队列的最大容量。设置队尾指针rear指向队尾元素的位置，设置队头指针front指向队头元素的前一位置。为了克服“假溢出”现象采用循环队列，即把一维数组Q[m]想象成首尾相接的循环数组，设想Q[0]接在Q[m-1]之后。判空条件为：rear==front；判满条件为：(rear+1)modm==front。六、队列的基本运算1、入队：先判满，若队列满则不能入队，发生“上溢”错误；队列不满时，修改rear为(rear+1)modm，然后把新元素插入到rear位置；2、出队：先判空，若队列空则不能出队，发生“下溢”错误；队列非空时，修改front为(front+1)modm，然后把队头元素读入到指定的变量中；3、求队列长度：即求队列中元素的个数，(rear-front+m)modm。§4线性链表线性表的顺序存储方式有结构简单、可以随机存取等优点，但也存在两大缺点：①插入或删除操作时，需要移动大量元素，效率低；②对于长度可变的线性表，要预先分配（静态分配）足够的空间，这是很困难的。分配太大可能使部分空间长期闲置不用，分配太小会造成表的容量难以扩充。为了克服以上缺点，可以采用链式存储方式，实现动态分配。线性表的链式存储称为线性链表。线性链表中各个元素（结点）的存储空间可以连续也可以不连续，根据表的使用情况可以随时申请和撤消元素占用空间。一、结点结构datanext表中的每个元素除了存储自身信息外，增设一个指示后继元素地址的指针。在用C语言实现时可以定义为结构体类型。由于每个结点都记下了后继结点的地址（最后一个结点的指针为空指针），整个表就构成了一个链。为了找到这个链表，应设一个头指针（head）指向表头结点。要对链表进行操作，一般总要从头指针出发，所以链式结构是顺序存取结构。二、单链表表中每个结点只用一个指针，指向后继结点。又分为不带头结点的单链表和带头结点的单链表（增设表头结点，该结点不含数据域，只有一个指向第一个表结点的指针。使得以空表和非空表的操作实现了统一）。三、循环链表链表中尾结点的指针不为空，而是指向表头结点，这样从表中任何一个结点出发都可以访问到表中其它所有的结点。四、双向循环链表链表中每个结点设两个指针域（可称为左指针llink和右指针rlink），分别指向前趋结点和后继结点，表头结点的左指针指向尾结点，表尾结点的右指针指向头结点。llinkdatarlink五、链式栈栈的链式结构和单链表存储结构基本相同，单链表的头指针含义为栈的栈顶指针。插入和删除结点只能通过栈顶指针在栈顶端进行。六、链式队列队列的链式结构也和单链表的存储结构基本相同，不过链式队列有两个指针，一个队头指针，一个队尾指针。七、线性链表主要基本运算①查找结点：线性链表的查找过程是从头指针（或链式栈的栈顶指针、或链式队列的队头指针）指向的结点开始，沿指针进行扫描，直到找到下一结点的数据域为查找值x或已无后继结点为止。②插入结点：先向系统申请一个新结点（由指针p指向），并赋值；然后利用查找算法找到待插入位置的前一结点的指针q；修改两个指针即可：先将p指向q的后继结点，再将p挂接在q的后面。（与顺序存储结构的插入操作的最大区别：一是可随时申请新结点空间，无需判满；二是只修改两个指针，无需移动结点）。③删除结点：先判空，对非空表利用查找算法找到待删除位置的前一结点的指针q，用另一指针p暂时保存q的后继结点（即待删除结点），然后把p结点的后继链直接挂接在q的后面。最后释放p结点所分配的内存空间。（与顺序存储结构的删除操作的最大区别是，只修改一个指针，无需移动结点）。§5树与二叉树树型结构是非线性结构，是一种以分支关系定义的层次结构，体现数据元素之间的“一对多”的联系。一、树的基本概念1、基本术语：根结点，父结点，子结点，叶子结点，结点的度，树的度，树的深度，子树，空树，有序树，无序树，森林，树的表示法。2、树的存储结构：顺序存储，链式存储。3、树的应用：表示算术表达式，二叉排序树，哈夫曼树等。二、二叉树及其特点1、二叉树的递归定义：二叉树是结点的一个有限集合，这个集合或是空，或者是由一个根结点和两棵分别称为根结点的左子树和右子树的互不相交的二叉树组成。2、二叉树的特点：非空二叉树只有一个根结点，每一个结点最多有两棵子树（度只能是0、1、2）且严格区分是左子树还是右子树（即二叉树是有序树）。3、二叉树的五种基本形态①空二叉树②只有一个根结点③右子树为空④左子树为空⑤左、右子树均非空。三、二叉树的基本性质1、在二叉树的第i层上，最多有2i-1（i>=1）个结点。2、深度为k的二叉树中结点总数最多为2k-1（k>=1）。3、对任意的一棵二叉树，度为0的结点（即叶结点）数n0总比度为2的结点数n2多1个，即n0=n2+1。满二叉树：深度为k的二叉树共有2k-1个结点（即性质2中允许的最大值）。完全二叉树：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后一层（第k层）上结点都尽量排在靠左的位置上。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。4、具有n个结点的完全二叉树的深度为[log2n]+1。（这里的[]表示取整）5、对于具有n个结点的完全二叉树，如果从根结点开始，按层序（每层从左到右）用自然数进行编号，则对编号为k的结点（1<=k<=n）有以下结论：①若k>1，则该结点的父结点编号为[k/2]；若k=1，则它是根结点，无父结点。②若2k<=n，则该结点的左孩子结点编号为2k；若2k>n，则它无左孩子结点。③若2k+1<=n，则该结点的右孩子结点编号为2k+1；若2k+1>n，则它无右孩子结点。四、二叉树的存储结构1、顺序存储：选用一个数组T[n]，根据性质5的编号关系，各结点按编号放在相应位置上。适用于满二叉树和完全二叉树，对于一般二叉树，会造成空间浪费。lchilddatarchild2、链式存储：①二叉链表：结点结构包括三个域，数据域data，左孩指针lchild，右孩指针rchild。②三叉链表：有时为了求父结点的方便，在二叉链表的结点结构中再增设一个指向父结点的指针parent。五、二叉树的遍历1、前序遍历（DLR）：先访问根结点，再前序遍历左子树，最后前序遍历右子树。2、中序遍历（LDR）：先中序遍历左子树，再访问根结点，最后中序遍历右子树。3、后序遍历（LRD）：先后序遍历左子树，再后序遍历右子树，最后访问根结点。§６查找查找是根据给定的关键字值，在表中确定一个其关键字等于给定值的记录的过程。若表中存在这样的一个记录，则称为查找成功，输出记录的有关信息或在表中的位置；若表中不存在相应的记录，则称查找不成功，可以输出一个空记录或空指针。常用的查找方法有顺序查找、折半查找、索引顺序查找、树表查找和哈希查找。这里只介绍前两种方法。一、顺序查找1、查找方法：从表头到表尾逐个进行比较，若某个记录的关键字值与给定值相等，则查找成功，否则继续比较表中下一个记录，直到整个表都遍历完。2、适用场合：对表的结构无要求，顺序存储或链式存储的查找表都可以。3、算法分析：平均查找长度（ASL）为n/2，时间复杂度为O(n)。二、折半查找（二分查找）1、查找方法：每次把待查值和查找表中间位置的记录的关键字进行比较，若相等则查找成功；不相等时根据大于或小于关系确定在后半区间或在前半区间继续折半查找。2、适用场合：顺序存储的有序表。3、算法分析：平均查找长度为log2(n+1)-1，时间复杂度为O(log2n)。三、两种查找方法的比较顺序查找算法简单，对表的结构无要求，但时间性能不太好；折半查找以减半的方式缩小搜索范围，查找速度快，但前提是顺序存储的查找表并且已按关键字排好序。§７排序排序的功能是将一个记录的无序序列重新排列成一个按关键字有序的序列。排序的目的之一是方便查找。排序的依据是记录中能唯一识别该记录的数据项，称为关键字。可以按关键字的值从小到大排序，称为升序排序，反之称为降序排序。在记录序列中，排序前存在相同关键字的记录，经过某种排序方法排序后，这些记录的相对次序保持不变，则称这种排序方法是稳定的，反之称这种排序方法是不稳定的。在内存中就能完成对记录序列的排序过程的排序称为内部排序，若记录文件很大，还需对外存进行访问的排序过程称为外部排序。排序方法分为插入排序法、交换排序法、选择排序法、归并排序法、基数排序法等大类。一般的性能评价标准有两条：一是执行排序算法所需的时间，二是执行排序算法所需的附加空间。时间性能一般以具体排序算法执行过程中的关键字之间的比较次数和记录位置的移动次数来反映。这里只介绍前三类六种排序方法。一、插入排序1、直接插入排序基本思想是：将待排序表看做是左、右两部分，其中左边是有序区，右边是无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。2、希尔排序基本思想是：将待排序列分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后现对整个序列进行直接插入排序。关键在于如何分组，常用办法是第一轮取步长为初始长度n的一半，即间隔为[n/2]的元素为一组，以后每轮的步长为上次的一半（缩小增量法）。二、交换排序1、冒泡排序（简单交换排序）基本思想是：从表的一端开始，逐个比较相邻的两个元素的关键字值，发现倒序就交换。一轮比较的结果是关键字值最大的元素排到表尾，关键字值小的元素前移，就像在水面上的重物下沉、轻物上浮一样，故称之“冒泡”排序。2、快速排序基本思想是：选定一个元素作为中间元素，然