数据结构复习资料

数据结构的定义数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构：是指数据以及数据元素相互之间的联系,可以看作是相互之间存在着某种特定关系的数据元素的集合。对数据结构的内容包括以下几个方面：①数据的逻辑结构，指数据元素之间的逻辑关系。②数据的存储结构，指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。③数据运算，指施加在数据上的操作。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中，每一条指令表示一个或多个操作。粗略地说，算法是为了求解问题而给出的一个指令序列，程序是算法的一种具体实现。一个算法必须满足以下五个重要特性：1.有穷性2.确定性3.可行性4.有输入5.有输出算法的重要特征(1)有穷性:算法在有穷步之后结束，每一步在有穷时间内完成。(2)确定性:算法中的每一条指令有明确的含义，无二义性。(3)可行性:可通过已经实现的基本运算执行有限次来实现算法中的所有操作。算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法的执行时间主要与问题的规模有关。问题规模是一个与输入有关的量。语句频度是指算法中该语句被重复执行的次数。算法中所有语句的频度之和记作Ｔ(n)，是该算法所求解问题规模的函数。当问题规模趋向无穷大时，Ｔ(n)的数量级称为渐进时间复杂度，简称时间复杂度，记作Ｔ(n)=O(f(n))。通常采用算法中表示基本运算的语句的频度来分析算法的时间复杂度。例题：1.数据结构中的逻辑结构是指()，物理结构是指（）。2.算法的基本特征包括有穷性、()、()、有输入和输出。3.算法的有穷性是指（）。4.算法的确定性是指（）。5.算法的可行性是指（）。6.算法分析的两个主要方面是分析算法的（）和空间复杂度。7.语句频度是指（算法中该语句被重复执行的次数）。8.设n为正整数，对下面的程序段，写出语句①、②、③的频度及该程序段的时间复杂度。for(i=1;i=n;i++){s=0;①nfor(j=1;j=n;j++)s=s+i×j;②n2if(s%2)③nprint(s);}第二章线性表本章内容：2.1线性表的基本概念一个线性表是有n个数据元素的有限序列：(a1，a2，…，ai，…，an)2.2线性表的顺序存储结构线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点：存储单元地址连续（需要一段连续空间）逻辑上相邻的数据元素其物理位置也相邻存储密度大（100%）随机存取，元素的存储位置存在如下关系：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)2.3线性表的链式存储结构线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来表示。这称为链表。头指针是指向链表第一个结点的指针。头结点是链表中的第一个结点但是头结点中不存放数据元素。单链表、循环链表的类型定义typedefstructLNode{ElemTypedata;/*存储数据元素*/structLNode*next;/*指向后继结点*/}SLink,*LinkList;LinkListhead,tail;例题1.顺序表中，逻辑上相邻的数据元素在物理位置上(也相邻)。线性表L=(a1,a2,...,an)采用顺序存储，假定在不同的n+1个位置上的插入概率相同，则插入一个新元素平均需要移动的元素个数是(n/2)。2.在一个长度为n的顺序表中,在第i个元素(1in)之前插入一个新元素时,需向后移动(n-i+1)个元素。3.在表长为n的单链表中,取得第i(1in)个数据元素必须从(头指针)出发开始寻找。4.在一个具有n个结点的有序单链表中，插入一个新结点并保持链表有序的算法时间复杂度为(O(n))。5.解释头指针和头结点。6.请对线性表进行顺序存储和链式存储的特点作比较。基于空间的考虑：顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。因此，当线性表的长度变化较大，难以估计其存储空间规模时，宜采用动态链表作为存储结构。反之，则采用顺序表作为存储结构。另外，存储密度越大，则存储空间的利用率越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。因此，当线性表的长度变化不大，易于事先确定其大小时，为了节省空间，采用顺序表为宜。基于时间的考虑：顺序表是由向量实现的，它是一种随机存取结构，而链表是一种顺序存储结构。因此，若线性表的操作主要是进行查找，很少进行插入和删除操作时，采用顺序表作存储结构为宜。反之，则采用链表作为存储结构。7.编写算法，将一个带头结点的单链表就地逆置。（请先说明算法思路，再用类高级语言编写算法。）将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分。设置两个指针p和s，p指向已完成逆置部分链表的第一个结点，s指向未逆置部分的第一个结点。初始时令指针p指向第一个元素结点，s指向p所指结点的后继。将第一个元素结点的指针域置为空。将未逆置部分的结点逐个插入到头结点之后。p=head-next;if(p)s=p-next;p-next=NULL;p=s;s=s-next;p-next=head-next;head-next=p;p=s;s=s-next;p-next=head-next;head-next=p;将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分。设置两个指针p和s，p指向已完成逆置部分链表的第一个结点，s指向未逆置部分的第一个结点。初始时令指针p指向第一个元素结点，s指向p所指结点的后继。将第一个元素结点的指针域置为空。将未逆置部分的结点逐个插入到头结点之后。算法：voidreverse(LinkListhead){//带头结点的单链表逆置p=head-next;if(!p)return;s=p-next;p-next=NULL;while(s){p=s;s=s-next;p-next=head-next;head-next=p;}}第三章栈和队列栈是后进先出的线性表，队列是先进先出的线性表；在应用中，栈和队列都是容器，因此需要判断是否“栈空”或“队空”；采用顺序存储结构时，栈和队列都可能存在“溢出”问题，分别称为“栈满”、“队满”；采用顺序结构的队列常见形式是循环队列。栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。例题1.用S、X分别表示入栈、出栈操作，若元素入栈顺序为1、2、3、4，为得到出栈序列1、3、4、2，则相应的S和X操作串是（SXSSXSXX）。2.若push、pop分别表示入栈、出栈操作，初始栈为空且元素a、b、c依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为(bac)。3.如果进栈的序列为1、2、3,则不能得到的出栈序列为（312）。令队列空间中的一个单元闲置，使得在任何时刻，保持Q.rear和Q.front之间至少间隔一个空闲单元MAXSIZE=8队列满(full)：(Q.rear+1)%MAXSIZE==Q.front队列空：Q.rear==Q.front队列长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE例题1.在循环队列结构中（队列空间容量为M），Ｑ.rear指向队尾元素所在位置，Ｑ.front指向队头元素所在位置，则队列的长度为((Q.rear-Q.front+1+M)%M)。2.用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（O(1)）和（O(n)）；若只设尾指针，则出队和入队的时间复杂度分别是（O(1)）和（O(1)）。1.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。#defineMAXSIZE100//最大队列长度typedefstruct{Qelemtype*base;//base为队列所在存储区域的首地址intlength;//队列长度intrear;//队尾元素位置}SqQueue；1.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。#defineMAXSIZE100//最大队列长度typedefstruct{Qelemtype*base;//base为队列所在存储区域的首地址intlength,rear;//队列长度和队尾元素位置}SqQueue；StatusEnQueue（SqQueue&Q,Qelemtypee）｛//将元素e插入队列Qif（（1））returnERROR；//队列满，无法插入Q.rear＝（2）;//计算元素e的插入位置（3）＝e;//在队尾加入新的元素Q.length++；//队列长度加1returnOK;｝//(1)Q.length＝MAXSIZE(2)（Q.rear+1）％MAXSIZE(3)Q.base[Q.rear]第四章串1.了解串的基本运算2.了解串的模式匹配算法第六章树和二叉树二叉树或者是一棵空树；或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成满二叉树中所有分支结点都有左孩子和右孩子，叶结点都集中在二叉树的最后一层。满二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。完全二叉树中，最多只有最下面两层的结点的度数可以小于2，最下面一层的叶结点都排列在该层最左边的位置上。完全二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。例题1.一棵满二叉树中共有n个结点，其中有m个叶子结点，则n和m的关系为（n=2m-1）。2.在完全二叉树中，若一个结点没有左孩子子结点，则它一定没有(B)。A．父结点B．右孩子结点C．左兄弟结点D．右兄弟结点性质1非空二叉树上第i层上至多有2i-1个结点i≥1。性质2高度为h的二叉树至多有2h-1个结点(h≥1)。性质3非空二叉树上叶结点数(度为0)等于双分支结点数(度为2)加1。性质4对完全二叉树中编号为i的结点(1≤i≤n，n≥1，n为结点数)，可以算出其左孩子结点、右孩子结点和父结点的编号（若这些结点存在）。性质5具有n个(n＞0)结点的完全二叉树的高度为log2(n+1)或log2n+1。二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.一般用二叉链表存储二叉树(每个结点有两个指针域)ABCDEHIJKFGLMNO123456789101511121314满二叉树ABCDEHIJKFG1234567891011完全二叉树树的遍历是访问树中每个结点仅一次的过程。可以认为遍历是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。先序遍历DLR、中序遍历LDR、后序遍历LRD层序遍历先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点先序遍历：访问根结点、先序遍历左子树、先序遍历右子树。下图的先序遍历序列为ABDEGCF。中序遍历：中序遍历左子树、访问根结点、中序遍历右子树。下图的中序遍历序列为DBGEACF。后序遍历：后序遍历左子树、后序遍历右子树、访问根结点。下图的后序遍历序列为DGEBFCA。层序遍历：先根后子树、先左子树后右子树。下图的层序遍历序列为ABCDEFG。例题1.在有n个结点的二叉树的二叉链表中必定存在（n+1）个空链域。2.前序遍历序列与中序遍历序列相同的二叉树为（D）。A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树3.已知一棵二叉树的先序遍历序列为ABDG