数据结构考试重点必背

1、word可编辑第一章：绪论：数据结构课程的任务是：争辩数据的各种规律结构、在计算机中的存储结构以及各种操作的算法设计。：数据：是客观描述事物的数字、字符以及全部的能输入到计算机中并能被计算机接收的各种集合的统称。数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的根本单位。数据项：是数据元素中有独立含义的、不行分割的最小标识单位。数据结构概念包含三个方面：数据的规律结构、数据的存储结构的数据的操作。数据的规律结构指数据元素之间的规律关系，用一个数据元素的集合定义在此集合上的假设干关系来表示，数据结构可以分为三种：线性结构、树结构和图。：数据元素及其关系在计算机中的存储表示称为数据的存储

2、结构，也称为物理结构。 数据的存储结构根本形式有两种：挨次存储结构和链式存储结构。 ：算法：一个算法是一个有穷规章的集合，其规章确定一个解决某一特定类型问题的操作序列。算法规章需满足以下五个特性：输入算法有零个或多个输入数据。 输出算法有一个或多个输出数据，与输入数据有某种特定关系。 有穷性算法必需在执行又穷步之后结束。 确定性算法的每个步骤必需含义明确，无二义性。 可行性算法的每步操作必需是根本的，它们的原那么上都能够精确地进行，用笔和纸做有穷次就可以完成。 有穷性和可行性是算法最重要的两个特征。：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。 算法设计依靠数据的规律

3、结构，算法实现依靠数据结构的存储结构。：算法的设计应满足五个目标：正确性：算法应精确的满足应用问题的需求，这是算法设计的根本目标。 健壮性：即使输入数据不适宜，算法也能做出适当的处理，不会导致不行控结 高时间效率：算法的执行时间越短，时间效率越高。 果。 高空间效率：算法执行时占用的存储空间越少，空间效率越高。 可读性：算法的可读性有利于人们对算法的理解。 ：度量算法的时间效率，时间简单度，课本39页。：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：至少有一条初始定义是非递归的，如1！=1. 由函数值逐步递推计算出未知函数值，如用n-1！定义n！。 第二章：线性表线性表

4、：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,an-1,组成的有限序列,记作： LinearList = (a0,a1,a2,an-1)其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。假设n=0，那么LinearList为空表。假设n>0，那么a0没有前驱元素，an-1没有后继元素，ai0<i<n-1有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1。线性表的挨次存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的规律次序相同。线性表的数据元素数据同一种数据类

5、型，设每个元素占用c字节，a0的存储地址为Loca0，那么ai的存储地址Locai为：Locai = Loca0+ i*c 数组是挨次存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。：挨次表的插入和删除操作要移动数据元素。平均移动次数是 属数据表长度的一半。课本第50页：线性表的链式存储是用假设干地址分散的存储单元存储数据元素，规律上相邻的数据元素在物理位置上不肯定相邻，必需接受附加信息表示数据元素之间的挨次关系。它有两个域组成：数据域和地址域。通常成为节点。课本第55页及56页单链表课本56页单链表的遍历：Node<E> p = head

6、; while(p!=null) 访问p节点；p = ;单链表的插入和删除操作格外简便，只要转变节点间的链接关系，不需移动数据元素。单链表的插入操作：1：空表插入/头插入 2)中间插入/尾插入 if(head = null) Node<E> q = new Node<E>(x); head = new Node<E>(x); = ; else = q; Node<E> q=new Node<E>(x); 中间插入或尾插入都不会转变单表 = head; 的头指针head。 head = q; 单链表的删除操作：头删除：head = ;

7、中间/尾删除：if!=null) = 循环单链表：假设单链表最终一个节点的next链保存单链表的头指针head值，那么该单链表成为环形结构，称为循环单链表。课本67假设rear是单链表的尾指针，那么执行=head;语句，使单链表成为一条循环单链表。当=head时，循环单链表为空。：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点， 当=null时，双链表为空。 设p指向双链表中非两端的某个结点，那么成立以下关系：p=。双链表的插入和删除：1插入 2)删除q=new DLinkNodex； = ;=; =p; if=null) = q;=q; .prev = ;循环双链表：当=

8、head且=head时，循环双链表为空。第三章：栈和队列栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有挨次栈和链式栈。栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。栈的进出栈挨次：后进先出，先进后出。及75页的思考题。：队列：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为队尾，允许出队的一端称为对头。没有元素的队列称为空队列。队列是先进先出。第四章：串：串是一种特殊的线性表，其特殊性在于线性表中的

9、每个元素是一个字符。一个串记为： s=“s0s1s2sn-1 其中n>=0,s是串名，一对双引号括起来的字符序列s0s1s2sn-1是串值，sii=0，1，2，n-1为特定字符集合中的一个字符。一个串中包含的字符个数称为串的长度。长度为0的串称为空串，记作“，而由一个或多个空格字符构成的字符串称为空格串。子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。子串的序号是指该子串的第一个字符在主串中的序号。串比较：两个串可比较是否相等，也可比较大小。两个串子串相等的充要条件是两个串子串的长度相同，并且各对应位置上的字符也相同。两个串的大小由对应位置的第一个不同字

10、符的大小打算，字符比较次序是从头开头依次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较“大。第五章：数组和广义表：数组是一种数据结构，数据元素具有相同的数据类型。一维数组的规律结构是线性表，多维数组是线性表的扩展。：一维数组：一维数组接受挨次存储结构。一个一维数组占用一组连续的存储单元。设数组第一个元素a0的存储地址为Loca0，每个元素占用c字节，那么数组其他元素ai的存储地址Locai为： Locai= Loca0+i*c数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，所划给的时间是O1。因此数组是随机存取结构，这是数组最大的优点。：多维数组

11、的遍历：有两种次序：行主序和列主序。行主序：以行为主序，按行递增访问数组元素，访问完第i行的全部元素之后再访问第i+1行的元素，同一行上按列递增访问数组元素。 a00,a01,a0(n-1), a10,a11,a1(n-1),a(m-1)0,a(m-1)1,a(m-1)(n-1) 2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的全部元素之后再访问第j+1列的元素，同一列上按列递增访问数组元素。 多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两种。静态多维数组的挨次存储结构：可按行主序和列主序进行挨次存储。 按行主序存储时，元素aij的地址为：Locaij=

12、Loca00+i*n+j*c按列主序存储时，Locaij= Loca00+j*m+i*c动态多维数组的存储结构。 二维数组元素地址就是两个下标的线性函数。无论接受哪种存储结构，多维数组都是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除操作。第六章：树是数据元素结点之间具有层次关系的非线性结构。在树结构中，除根以外的结点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。树是由nn>=0个结点组成的有限集合树中元素通常称为结点。N=0的树称为空树；n>0大的树T；有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。除根结点之外的其他结点分

13、为mm>=0个互不相交的集合T0,T1,T3.,Tm-1，其中每个集合Ti0<=i<m本身又是一棵树，称为根的子树。树是递归定义的。结点是树大的根本单位，假设干个结点组成一棵子树，假设干棵互不相交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点组成的、结点之间具有层次关系大的非线性结构。 结点的前驱结点称为其父母结点，反之，结点大的后继结点称为其孩子结点。一棵树中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父母结点所经过大的全部结点。结点的后代是指该结点的全部孩子结点，

14、以及孩子的孩子等。结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度是指树中各结点度的最大值。结点的层次属性反响结点处于树中的层次位置。商定根结点的层次为1，其他结点的层次是其父母结点的层次加1。明显，兄弟结点的层次相同。树的高度或深度是树中结点的最大层次树。设树中x结点是y结点的父母结点，有序对x，y称为连接这两个结点的分支，也称为边。设X0,X1,.,Xk-1是由树中结点组成的一个序列，且Xi，Xi+10<=i<k-1都是树中的边，那么该序列称为从X0到Xk-1的一条路径。路径长度

15、为路径上的边数。在树的定义中，结点的子树T0，T1.,Tm-1之间没有次序，可以交换位置，称为无序树，简称树。假设结点的子树T0,T1,Tm-1从左到右是有次序的，不能交换位置，那么 称该树为有序树。森林是mm>=0棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。二叉树的性质1：假设根结点的层次为1，那么二叉树第i层最多有2 的i-1次方i>=1个结点。二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，那么n0=n2+1。一棵高度为k的满二叉树是具有2的k次方减一个

16、结点的二叉树。满二叉树中每一层的结点数目都到达最大值。对满二叉树的结点进行连续编号，商定根节点的序号为0，从根节点开头，自上而下，每层自左至右编号。一棵具有n个结点高度为k的二叉树，假设他的每个节点都与高度为k的满二叉树中序号为0n-1的结点一一对应，那么这棵二叉树为为完全二叉树。满二叉树是完全二叉树，而完全二叉树不肯定是满二叉树。完全二叉树的第1k-1层是满二叉树第k层不满，并且该层全部结点必需集中在该层左边的假设干位置上。二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n确实定值+1二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有假设i=0，那么i为根节点

17、，无父母结点；假设i>0，那么i的父母结点的序号为i-1/2。假设2i+1<n，那么i的左孩子结点序号为2i+1；否那么i无左孩子。假设2i+2<n，那么i的右孩子结点的序号为2i+2，否那么i无右孩子。二叉树的遍历二叉树的遍历是依据肯定规章和次序访问二叉树中的全部结点，并且每个结点仅被访问一次。二叉树的三种次序遍历1：先根次序；访问根节点，遍历左子树，遍历右子树。2：中根次序；遍历左子树，访问右子树，遍历右子树。3：后根次序；遍历左子树，遍历右子树，访问根节点。先根次序遍历时，最先访问根节点；后根次序遍历时，最终访问根节点；中根次序遍历时，左子树上的结点在根节点之前访问，右

18、子树上的结点在根节点之后访问。二叉树的插入和删除操作P147二叉树的层次遍历P149习题P167 610，619第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图G记为G=V,E，V是顶点A的有限集合，E是边的有限集合。即 V=A|A属于某个数据元素集合E=(A,B)|A,B属于V或E=<A,B>|A,B属于V且PathA,B其中PathA,B表示从顶点A到B的一条单向通路，即PathA,B是有方向的。无向图中的边事没有方向，每条边用两个顶点的无序对表示。有向图中的边是有方向，每条边用两个顶点的有序对表示。完全图指图的边数到达最大值。n个顶点的

19、完全图记为Kn。无向完全图Kn的边数为n*n-1/2,有向完全图Kn的边数为n*n-1。子图：设图G=(V,E),G=(V,E)，假设V包含于V且E包含于E,那么称图G是G的子图。假设G是G的真子图。连通图：在无向图G中，假设从顶点VI到Vj有路径，那么称Vi和Vj是联通的。假设图G中任意一对顶点Vi和VjVi不等于Vj都是联通的，那么称G为连通图。非连通图的极大联通子图称为该图的联通重量。强连通图：在有向图中，假设在每一对顶点Vi和VjVi不等于Vj之间都存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，那么称该图的强连通图。非强连通图的极大强连通子图称

20、为该图的强连通图重量。图的遍历遍历图是指从图G中任意一个顶点V动身，沿着图中的边前行，到达并访问图中的全部顶点，且每个顶点仅被访问一次。遍历图要考虑一下三个问题：指定遍历的第一个访问顶点由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间商定一种访问次序。由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。深度优先搜寻图的深度优先搜寻策略是，访问某个顶点v，接着查找v的另一个未被访问的邻接顶点w访问，如此反复执行，走过一条较长路径到达最远顶点；假设顶点v没有未被访问的其他邻接顶点，那么回到前一个被访问顶点，再查找其他访问路径。图的深度优先搜寻遍历算法P188 联通的无回

21、路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。各连通重量均为树的图称为森林，树是森林。由于树中无回路，因此树中必定无自身环也无重边否那么他有回路假设去掉树中的任意一条边，那么变成森林，成为非联通图；假设给树加上一条边，形成图中的一条回路，那么不是树。P191生成树和生成森林：一个连通无向图的生成树是该图的一个微小联通生成子图，它包含原图中全部顶点n个以及足以构成一棵树的n-1条边。 一个非联通的无向图，其各连通图重量的生成图组成该图的生成森林。图的生成图或生成森林不是唯一的，从不同顶点开头、接受不同遍历可以得到不同的生成树或森林。 在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。第八章折半查找算法描述 P206,P207二叉排序树及其查找：二叉排序树或者是一棵空树；或者是具有以下性质的二叉树：每个结点都有一个作为查找依据的关键字，全部结点的关键字互不相同。假设一个结点的左子树不空，那么左子树上全部结点的关键字均小于这个节点的关键字；每个结点的左右子树也分别为二叉排序树。在一棵二叉排序树中，查找值为value的结点，算法