数据结构重点整理

数据结构重点整理1/6考点1算法的时间复杂度(不会出简单的for循环)例题.1下面程序段的时间复杂度为DO(n*log2n)。for(k=1;k=j;k++)｛inti=1;while(i=n)i=i*2;｝O(1)初始化线性表检查线性表是否为空O(n)删除线性表中的所有元素；得到线性表的长度；得到线性表中指定序号为pos的元素；遍历一个线性表；从线性表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向线性表中按给定条件插入一个元素；从线性表中删除符合给定条件的第一个元素O(n^2)对线性表进行排序2几种数据结构（数据结构定义：具有结构的数据元素的集合）逻辑结构：集合、线性结构（线性表、广义表、堆栈和队列）非线性结构（树、图）存储结构：顺序存储结构、链式存储结构、索引结构、散列结构等集合和线性结构：1：1树形结构：1：N图形结构：N:N3线性表顺序存储和链接存储的特点顺序存储：随机存取，预先定义表长；插入删除时有大量元素的移动（当下标为1开始的实话移动n-i+1，当下标为0开始的实话移动n-i），查找方便。链式存储：非随机存取，表长不需要预先定义是动态分配，插入删除不需要大量的元素移动，查找时从第一个元素开始查找。4根据线性表的常用操作，选择最合适的存储方式顺序表和链表的比较：空间方面：a当表长难估较大时，选择链式存储b当表长较小时，选择顺序存储时间方面：a插入与删除较多时选择链式存储b查找方面较多时用顺序存储语言方面：当语言没有指针，选用链式存储时选用静态链表（静态链表需要预先设定空间）某线性链表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,用仅有尾指针的单循环链表存储方式实现这两种操作6链表的特点例题：链表不具有的特点是（A）。A、可随机访问任意元素B、插入删除不需要移动元素数据结构重点整理2/6C、不必事先估计存储空间D、所需空间与线性表长度成正比7链表的插入删除8链表各操作的时间复杂度O(1)初始化链表检查链表是否为空O(n)删除链表中的所有元素；得到链表的长度；得到链表中指定序号为pos的元素；遍历一个链表；从链表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向链表中按给定条件插入一个元素；从链表中删除符合给定条件的第一个元素O(n2)对链表进行排序例题：在一个长度为n单链表；在表头插入元素的时间复杂度为O(1)；在表尾插入元素的时间复杂度为O(n)。9栈的特点：先进后出，后进先出。10栈的顺序存储、链式存储的出栈入栈时间复杂度：O(1)13根据给定递归算法和输入求输出（读递归程序）14数组上的循环队列的进队出队操作（参考期中考试最后大题）判空：rear==front满：(rear+1)%MaxSize==front进队操作：rear=(rear+1)%MaxSize;Q(rear)=x出队操作：front=(front+1)%MaxSize;X=Q(front)入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize15链队的插入O(1)voidEnQueue(LinkQueue&HQ,constElemType&item){LNode*newptr=newLNode;if(newptr==NULL){cerr“Memoryalocationfailure.endl;exit(1);}newptr-data=item;newptr-next=NULL;if(HQ.rear==NULL)HQ.front=HQ.rear=newptr;elseHQ.rear=HQ.rear-next=newptr;}17稀疏矩阵的定义：其非零元素的个数远远小于零元素的个数。稀疏矩阵的严格定义：稀疏因子=非零元素/所有元素个数通常认为0.3的矩阵为稀疏矩阵三元组表示形式：(i,j,value)i为第i行，j为第j列，value为非0元素的值18广义表的特点规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a是广义表的表头head。其余元素组成表尾tail；广义表中的数据元素有相对次序;广义表的长度定义为所含元素的个数;广义表的深度定义为括号嵌套的最大次数;注意:“空表”的深度为1;广义表可以共享;广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。例：D=(E,F)E=(a,(b,c),D),F=(d,(e))D的长度为2，深度为无穷19求广义表的长度深度广义表的深度=Max{子表的深度}+1；空表的深度=1；仅由单元素组成的表的深度=1例LS=((),(e),(a,(b,c,d)))长度为3深度为3；LD=(((a),((),b),(c)))长度1深度420树的性质1树中结点个数等于所有结点的度数加121二叉树的性质4P185书中性质4：若对具有n个结点的完全二叉树按照层次从上到下,每层从数据结构重点整理3/6左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)若编号为i的结点有左孩子,则左孩子结点的编号为2i;若编号为i的结点有右孩子,则右孩子结点的编号为2i+1.(2)除树根结点外,若一个结点的标号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子.(3)若i≦|_n/2_|,即2i≦n,则编号为i的结点为分支结点,否则为叶子结点.(4)若n为奇数,则每个分支结点都既有左孩子,又有右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有.22给定权值构造哈夫曼树求带权路径长度（参考作业题）例题1：如右图：WPL=7*1+5*2+2*3+4*3=3523哈夫曼树的特点又称最优树，是一种带权路径长度WPL最小的二叉树。由0和1组成，用哈夫曼编码传送的电文长度；传输速率最快。叶子结点的度为零；除叶子结点外的所有结点的度都为224二叉排序树求平均查找长度:K为层数，n表示最大层数，m（k）表示第k层有m结点个数，M表示所有结点个数。/（M）25有向图边数和顶点入度出度关系在有向图的邻接表中，从一顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍；在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的1倍；无向图的邻接表中结点个数的边数的2倍。向图边数=所有度之和/226无向图顶点数和最小生成树的边数关系无向图顶点数n：最小生成树的边数n-127图的邻接表P258邻接表:是图的一种链式存储结构。在邻接表中，对图中每个顶点建一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。图的邻接表是存放什么的：无权无向图：列存放所有节点，横向为结点对应邻接结点和指针指向结点对应的下一邻接点带权有向图：列存放所有节点，横向为结点的出度的所有邻接点，其中第一项为结点名称，第二项为与该结点名称对应的权值，第三项为指针指向结点对应的下一出度邻接点。28求最短路径长度P281两个顶点间可能存在多条路径，其中有一条是长度最短的路径，即最短路径若带权值要i到j中所经过边权值之和最小的路径称为最短路径，其权值称为最短路径长度。29图的边数与顶点数的关系（以下是网上找的小题）a).在一个图中,所有顶点的度数之和等于所有边数的1倍。b).在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的1倍。c).一个有n个顶点的无向图最多有n(n-1)/2条边。数据结构重点整理4/6d).具有4个顶点的无向完全图有6条边。e).具有6个顶点的无向图至少应有5条边才能确保是一个连通图。h).在一个具有n个顶点的无向图中,要连通全部顶点至少需要n-1条边。i).对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小n2g).对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为n，所有邻接表中的结点总数是2e。k).一个图中的一条路径长度为k，则该路径所含的顶点数为k-130求最小生成树:带权连通图中,总的权值之和最小的带权生成树1）布里姆算法依次在G中选择一条一个顶点仅在V中,另一个顶点在U中,并且权值最小的边加入集合TE,同时将该边仅在V中的那个顶点加入集合U.重复上述过程n-1次,使得U=V,此时T为G的最小生成树.2）克鲁斯卡尔算法将图Ｇ中的边按权值从小到大的顺序依次选取，若选取的边使生成树Ｔ形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止,此时T为G的最小生成树.31顺序查找的平均查找长度:（1+2+3……n）/N32构造二叉排序树求平均查找长度平均查找长度为：（1*1+2*2+3*4+4*1）/8=21/833二分查找给定有序表和待查元素求依次与哪些元素进行比较将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一维数组A[0..9]中，然后采用二分查找方法查找元素12，被比较过的数组元素的下标依次为4，7，5_。34冒泡排序每趟需要进行的比较次数，最多进行多少趟n-1趟35快速排序第一次划分结果快速排序（QuickSorting），又称划分排序.是目前所有排序方法中速度最快的一种（从排序区间选取一个元素为基准,从区间两端向中间顺序进行比较和交换,使得前面单元只保留比基准小的元素,后面单元保留比基准大的元素.然后把基准放到前后两部分之间.）36各排序算法空间复杂度排序方法时间复杂度空间复杂度稳定性复杂性平均情况最坏情况最好情况直接插入O(n2)O(n2)O(n)O(1)稳定简单希尔排序O(n*n1/2)O(n2)O(nlog2n)O(1)不稳定较复杂冒泡排序O(n2)O(n2)O(n)O(1)稳定简单快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定较复杂直接选择O(n2)O(n2)O(n2)O(1)不稳定简单堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定较复杂归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定较复杂基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定较复杂37二叉排序树的特点二叉排序树的中序是有序的；左孩子比根小，右孩子大于等于根38顺序查找适合的存储结构顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。39排序算法时间复杂度(见36知识点图)40双循环链表（老师忘记出什么样的了）数据结构重点整理5/641图连通需要的边数在n个顶点的无向图中，若边数=n-1，则该图必是连通图。42排序的稳定性(见36知识点图)稳定的有：直接插入、归并排序、基数排序、冒泡排序不稳定的有：快速排序、希尔排序、直接选择、堆排序43树的性质3课件：性质3深度为h的k叉树中至多有(kh-1)/(k-1)结点。满k叉树：结点个数等于(kh-1)/(k-1)的k叉树。44二叉树的定义：二叉树为度为2的有序树。递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。45二分查找最多需要比较次数：N个元素最多比较n/2次46树的深度的定义：树中所有结点层次的最大值，也称高度。每次调整至少能排除一半的个数(从x到其x-1层,x层得个数应该是所有个数的一半+1),所以复杂度是log级别比如有32个元素(为了方便取一个2的幂),第一次排除,16,第二次,8,第三次4,...2,1.以这种规律排除几次才能完呢?比如要排除a次,那么第一次2^(a-1),第二次2^(a-2)...第三次2^(a-3)....第a次2^0=1是不是总的个数-1=1+2+4+...2^(a-1)=2^a-1那么总的个数=2^a所以