数据结构复习

第一部分复习提纲《数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行复习。第1章绪论内容提要1、数据结构研究的内容2、基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型3、算法的定义和5个特征。4、算法设计要求5、算法分析、时间复杂度和空间复杂度。知识点1、数据的三个层次：数据、数据元素、数据项2、数据结构的三要素：逻辑结构、存储结构及在这种逻辑结构上所定义的操作（运算）。3、抽象数据类型的定义、表示和实现方法。4、时间复杂度，最好，最坏，平均时间复杂度。常用计算语句频度来估算算法时间复杂度。有时候要求分析语句的执行的次数，有时候要求给出语句执行次数的数量级。5、空间复杂度，算法工作所需辅助存储空间。例如，在递归算法中所需的递归工作栈等。重点掌握的内容：1.数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。2.集合结构、线性结构、树结构和图结构的特点。3.抽象数据类型的定义和表示方法。4.普通函数重载和操作符函数重载的含义，定义格式和调用格式。5.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。6.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。7.一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。8.数据结构对算法的影响。对于本章的其余内容均作一般掌握。第2章线性表内容提要1、线性表是元素间约束力最强的一类数据结构。非空线性表第一个元素无前驱之后后继，最后一个元素无后继只有前驱，其余每个元素都有唯一前驱和唯一后继。2、线性表的逻辑结构定义，对线性表的操作。3、线性表的存储结构：顺序存储结构和链式存储结构。4、线性表的操作在两种存储结构的实现。5、一元多项式的线性表表示方法、稀疏多项式的抽象数据类型定义、表示和加法的实现。知识点1、线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种逻辑关系，而在链式存储结构中，是靠指针来反映这种逻辑关系的。2、顺序存储结构用一维数据表示，给定下标，可以存取相应元素，属于随机存取的存储结构。3、尽管“只要知道某结点的指针就可以存取该元素”，但因为链表的存取都需要从头指针开始，顺链进行，故链表不属于随机存取结构。4、链表是本章学习的重点和难点。要理解头指针、头结点、首元结点和元素节点的差别。为什么要设置头结点。头结点是在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或者删除第一元素时，链表的头指针总在变化，与在其他位置插入或者删除元素的步骤是不一样的，算法写起来比较复杂）。掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作的方法。对链表（不包括循环链表）的任何操作，都要从头结点开始，头结点的指针具有标记作用，故头指针往往被称为链表的名字，如链表la既指出了链表的名字叫la也指出了链表头结点的指针是la5、链表操作中应注意不要使链表意外断开。因此若在某元素前插入一个元素或删除某元素，必须知道该元素的前驱结点的指针。指针操作时候，先勾连新的指针，再改变旧的指针。6、从时间和空间复杂度的角度综合分析比较线性表在顺序和链式两种存储结构下的特点。7、静态链表，与链表进行对比理解。例如，链表la在有头结点的情况下，第一元素可表示为la-next,而在静态链表sa中，静态链表常用下标0作“头结点”，其第一元素可是sa[0].next，相对p=p-next有I=sa[i].next来找到第i个元素的后继。，对链表用p==null来判断是否到尾，而静态链表用i==-1来判断链表是否结束。后续章节中树的双亲表示法，图的邻接表表示法、表插入排序、链式基数排序、地址排序等都是静态链表的应用。重点掌握的内容：1.线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域（T*data;intmaxSize;intlast;）的定义及作用。3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。5.单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。6.带表头附加结点的链表、循环链表、双向链表的结构特点。7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。9．Josephus问题的求解过程。10．顺序表和线性链表的性能比较及各自使用背景。对于本章的其余内容均作一般掌握。第3章栈和队列内容提要1、从数据结构角度讲，栈和队列都是线性结构。其操作是线性表操作的子集，是操作受限的线性表。但从数据类型的角度看，它们是和线性表大不同的重要的抽象数据类型。2、栈的定义和操作。栈是只准在一端进行插入和删除操作的线性表。该端成为栈的顶端。3、栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。4、栈的应用：表达式求值、过程调用、递归过程。5、队列的定义和操作，队列的删除在一端（头），而插入在另一端（尾）。因此在两种存储结构中，一般都对要队头和队尾两个指针。6、链队列空的条件是首位指针相等。而循环队列满的条件的判定，有牺牲一个单元和设置标记两种方法。知识点1、栈和队列操作在两种存储结构下的实现。注意因为栈在一端操作，通常链栈不设置头结点。2、中缀表达式转成后缀表达式，后缀表达式求值3、用递归解决问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的，掌握典型问题的算法。4、对仅剩一个元素的链队列删除元素时的处理（令队尾指针指向队头），特别是仅设尾指针的循环链队列的各种操作的实现。5、循环队列中队列空用队头指针等于队尾指针来判断，队列满则可惜正一个单元及设置标记方法两种办法。这里特别注意入队、出队和求元素个数等操作中的取模运算。6、在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。重点掌握的内容：1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。5.算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。6．给定n个栈元素,出栈可能或不可能的序列数。7.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。8.队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。9.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。10.利用栈和队列解决简单问题的算法分析和设计。11、递归算法，栈与递归，掌握递归程序的两个重要方面，一是递归终止的条件，一是递归体。递归分三种，问题的定义是递归的，数据结构的定义是递归的，解决问题的方法是递归的。理解递归工作栈的工作过程。每一层递归调用所需保存的信息构成一个工作记录，通常它包括三个方面的内容，返回地址、在本次过程调用时，为与形参结合的实参创建副本、本层的局部变量值。每进入一层递归时，系统就要建立一个新的工作记录，把上述项目压入栈中。每退出一层递归，就从递归工作栈中退出一个工作记录。理解书上P106图3.12一般掌握的内容：1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。2.队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。对于本章的其余内容均作一般了解。第4章数组、串与广义表内容提要1、数组的逻辑结构定义和存储。2、特殊矩阵的存储和运算3、稀疏矩阵的存储和运算4、广义表的定义以及存储5、广义表运算的递归算法6、串是数据元素与字符的线性表，串的定义及操作。7、串的基本操作，用串的基本操作来编写算法串的其他操作。8、串的存储结构，因为串是数据元素为字符的线性表，所以存在“结点大小”的问题，静态和动态（块链结构、堆结构）存储结构的优缺点。9、朴素模式匹配算法及改进（KMP）算法。知识点1、数组（主要是二维）在以行序优先和列序优先的存储中的地址计算方法2、特殊矩阵在压缩存储时的下标变换公式。3、稀疏矩阵的三元组表存储结构及矩阵转置的算法。4、广义表的head和tail运算符5、给定广义表画出其存储结构6、通过广义表的递归模型，掌握如何编写递归算法。7、用串的基本操作编写串的其他操作(如index和replace等)和串的模式匹配。8、了解kmp算法的推导过程，熟练掌握手工描述求匹配串的next和nextval函数值9、尽管朴素的模式匹配的时间复杂度是O(m*n),KMP算法的时间复杂度是O(m+n).但在一般情况下，前者实际执行时间近似O(m+n)，因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者快得多，其主要优点是主串不回溯。重点掌握的内容：1.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。2.多维数组的逻辑结构特征。3.多维数组的顺序存储结构及地址计算公式。4．数组是一种随机存取结构的原因。5．特殊矩阵和稀疏矩阵的概念。6．特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。7.稀疏矩阵的定义和三元组线性表表示。8.稀疏矩阵的转置运算及在三元组表存储结构上的实现。9.广义表的定义和表示，广义表长度和深度的计算。10．广义表上的求表头、表尾运算。11.广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法，它们对应的时间复杂度。12.串的模式匹配。朴素模式匹配的算法。kmp算法的推导过程，手工描述求匹配串的next和nextval函数值.第二部分部分复习题第1章绪论课本P371.2;1.3;1.7;1.8;1.13;1.14补充题目：第2章线性表还有很多算法的题目，请见文件《线性链表.PDF》第3章栈和队列栈的概念、算法练习题P1313.1(1)(2)3.33.4栈的类定义----与线性表不同的运算（方法），Push与Insert;Pop与Remove;getTop与getData;顺序栈：我们课本上顺序栈采用顺序表作为其存储结构，在顺序栈的声明中用一维数组作为栈的存储空间，存放栈元素的数组的头指针是*elements，该数组的最大允许存放元素个数为maxSize，当前栈顶位置由数组下标指针top指示，如果栈为空，top=-1;栈不为空时，elements[0]表示栈中的第一个元素。基于这种存储结构，如何实现栈的类定义中定义的那些运算，特别是，Push；Pop；getTop链式栈，采用链式栈表示一个栈，便于结点的插入和删除，特别在程序中需要同时使用多个栈的情况下，用链接表示不仅能够提高效率，还可以达到共享存储空间的目的。链式栈的栈顶在链表的表头。新结点的插入和栈顶结点的删除都是在链表的第一个元素即栈顶进行的，所以采用不带头结点的单链表来表示即可。链式栈的类定义，采用了单链表中关于单链表结点的struct定义方法来定义结点。在链式栈的类定义中，用栈顶指针top表示单链表的头指针。基于链式栈的存储结构定义，如何实现栈的类定义中的那些运算，特别是，Push；Pop；getTop栈的应用，括号匹