数据结构知识点总结(详细无题目).pdf

数据结构知识点总结内容概要：基本概念 线性表 栈与队列 树与二叉树 图查找算法 排序算法一、基本概念1、数据元素是数据的基本单位。2、数据项是数据不可分割的最小单位。3、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决具体问题，并得到正确的结果。有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。确定性：算法中每条指令的含义必须明确，不允许由二义性可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出5、算法设计的要求：（1）正确 性：算法应能满足设定的功能和要求。（2）可读 性：思路清晰、层次分明、易读易懂。（3）健壮 性：输入非法数据时应能作适当的反应和处理。（4）高效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。（5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。二、线性表1、线性表 List：最常用且最简单的数据结构。含有大量记录的线性表称为文件。2、线性表是 n 个数据元素的有限序列。线性结构的特点：“第一个”“最后一个”前驱 后继。3、顺序表 线性表的顺序存储结构特点a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。1)typedef struct DataType elemMAXSIZE;int length;SqList;2)表长为 n 时，线性表进行插入和删除操作的时间复杂度为O（n）插入一个元素时大约移动表中的一半元素。删除一个元素时大约移动表中的（n-1）2 4、线性表的链式存储结构1)类型定义简而言之，“数据+指针”。typedef struct LNode DataType data;struct LNode*next;LNode,*LinkList;2)不带头结点的空表判定为L=null 带头结点的空表判定为L-next=null 循环单链表为空的判定条件为L.next=L 线性链表的最后一个结点的指针为NULL 头结点的数据域为空，指针域指向第一个元素的指针。5、顺序表和单链表的比较0 1 MAXSIZE-1.L.elem L.elem L.elem L.length=0 L.length=MAXSIZE 0L.lengthtop=MAXLEN 1）return 0；/栈满不能入栈，且返回0else s-top+；s-datas-top=x；/栈不满，则压入元素xreturn 1；/进栈成功，返回1出栈:出栈运算是指取出栈顶元素，赋给某一个指定变量x。算法步骤：(a)判栈是否为空，若栈空，作下溢处理，并返回0；(b)若栈非空，将栈顶元素赋给变量x；(c)指针 top减1，并返回 1。算法实现：datatype Pop（SeqStack*s）datatypex;if (SEmpty(s)return 0；/若栈空不能出栈，且返回 0else x=s-datas-top；/栈不空则栈顶元素存入*xs-top-；return x；/出栈成功，返回13、队列先进先出的线性表。队尾入队对头出队允许插入的一端叫做队尾允许删除的一端叫做对头4、链队列typedef struct queuenodedatatypedata;struct queuenode*next;queuenode;/链队结点的类型datatypetypedefstructqueuenode*front,*rear;linkqueue;/将头指针、尾指针封装在一起的链队frontrearpABJ图4-6 链队列示意图5、循环队列typedef struct DataType elemMAXSIZE;int front,rear;/队头、队尾位置 SqQueue;循环队列判断队空的条件为front=rear 循环队列判断队满的条件为（rear+1）%m=front 在一个循环队列中删除元素时，首先需要后移队首指针。6、栈与队列比较：都是线形结构，栈的操作LIFO（后进先出），队列操作 FIFO（先进先出）。四、树和二叉树1.树的定义树（Tree）：是 n（n0）个有限数据元素的集合。在任意一棵非空树T 中：（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；（2）当 n1 时，除根结点之外的其余结点被分成m(m0)个互不相交的集合 T1，T2，Tm，其中每一个集合Ti（1 i m）本身又是一棵树，并且称为根的子树。2.基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1 孩子和双亲：树的深度：树的度数：树中度数最大的结点度数叫作树的度数树林：是由零个或多个不相交的树所组成的集合。3.二叉树性质：1)二叉树的第i层上至多有2i-1 个结点。2)深度为 k的二叉树至多有2k-1 个结点。满二叉树：深度为k，有 2k-1 个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1 到 n。3)叶子结点n0，度为 2 的结点为n2，则 n0=n2+1。考虑结点个数：n=n0+n1+n2考虑分支个数：n-1=2n2+n1可得 n0=n2+1 4)n 个结点的完全二叉树深度为1log n。5)n 个结点的完全二叉树，结点按层次编号有：i 的双亲是2/n，如果 i=1 时为根（无双亲）；i 的左孩子是2i，如果 2in，则无左孩子；i 的右孩子是2i+1，如果 2i+1n 则无右孩子。4.二叉树的存储结构顺序存储结构用数组、编号i 的结点存放在i-1处。适合于存储完全二叉树。链式存储结构二叉链表：typedef struct BTNode DataType data;struct BTNode*lchild,*rchild;BTNode,*BinTree;三叉链表：typedef struct BTNode DataType data;struct BTNode*lchild,*rchild,*parent;BTNode,*BinTree;在链式存储结构中，含有n 个结点的二叉链表有n+1 个空链域。5.遍历二叉树（先序 DLR、中序 LDR、后序 LRD）方法与 C语言描述由二叉树的递归定义可知，一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历 DLR（根左右）、中序遍历 LDR（左根右）、后序遍历LRD（左右根）。data parent lchild rchild data rchild lchild 1 先序遍历（DLR）的递归过程void Preorder(BT*T)/先序遍历二叉树BT if (T=NULL)return;/递归调用的结束条件 printf(T-data);/输出结点的数据域Preorder(T-lchild);/先序递归遍历左子树Preorder(T-rchild);/先序递归遍历右子树2 中序遍历（L DR）的递归过程void Inorder(BT*T)/中序遍历二叉树BT if (T=NULL)return;/递归调用的结束条件 Inorder(T-lchild);/中序递归遍历左子树printf(T-data);/输出结点的数据域Inorder(T-rchild);/中序递归遍历右子树3 后序遍历（L RD）的递归过程void Postorder(BT*T)/后序遍历二叉树BT if (T=NULL)return;/递归调用的结束条件 Postorder(T-lchild);/后序递归遍历左子树Postorder(T-rchild);/后序递归遍历右子树printf(T-data);/输出结点的数据域6.线索二叉树n 个结点的二叉链表中有n+1 个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。lchild 有左子树，则指向左子树，标志ltag=0；没有左子树，可作为前驱线索，标志ltag=1。rchild 有右子树，则指向右子树，标志rtag=0；没有右子树，可作为后继线索，标志rtag=1。7.树和森林树的存储结构双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。lchild ltag data rtag rchild 0/1 0/1 树与二叉树的转换表 错误！文档中没有指定样式的文字。.1 树和二叉树的对应关系树对应的二叉树根根第一个孩子左孩子下一个兄弟右孩子树的遍历树的结构：根，根的子树。先根遍历：。例：ABCDEFGHIJK。后根遍历：。例：CEDFBHGJKIA。遍历森林森林的结构：第一棵树的根，第一棵树的根的子树森林，其余树(除第一棵外)组成的森林。先序遍历：。例：ABCDEFGHIJ。中序遍历：。例：BDCEAGFIJH。注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。遍历树、森林与遍历二叉树的关系遍历树、森林和二叉树的关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历8.哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树构造赫夫曼树每次取两个最小的树组成二叉树A B I C D F H G J K E A H B C E G F I J D 树的结构划森林的结构划分赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。五、图1完全图：有 12 n(n-1)条变得无向图有向完全图：具有n（n-1）条弧的有向图。权：与图的边或弧相关的数。顶点 v 的度：和 v相关联的边的数目。入度：以顶点 v 为头的弧的数目出度：以顶点 v 为尾的弧的数目回路或环：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。2.图的存储结构邻接矩阵：邻接表：typedef struct ArcNode /弧结点intadjvex;/邻接点struct ArcNode*nextarc;/下一个邻接点 ArcNode;typedef struct VexNode /顶点结点VertexType data;/顶点信息ArcNode*firstarc;/第一个邻接点 VexNode;constint MAX_VERTEX=最大顶点个数;typedef struct Graph /图VexNode vexsMAX_VERTEX;/顶点向量intvexnum,arcnum;/顶点和弧的个数 Graph;边(弧)多则需要存储空间多。0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 A B C D E 十字链表：十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。邻接多重表3.图的遍历1)深度优先（DFS）搜索访问方式：从图中某顶点v 出发：a）访问顶点 v；b）从 v 的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束。2)广度（宽度，BFS）优先搜索a）访问顶点 v；b）访问同 v 相邻的所有未被访问的邻接点w1,w2,wk；c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；4.生成树和最小生成树每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有 DFS生成树和 BFS生成树。1)最小生成树Kruskal算法一句话，“不构成环的情况下，每次选取最小边”。普里姆算法A B C D E 1 2/0 1 2 3 4 2 3/3/0/0 3/A B C D E 2 5 3 3 1 7 6 3 A B C D E 2 5 3 3 1 7 6 3 A B C D E 2 5 3 3 1 7 6 3(a)(b)(c)A B C D E 2 5 3 3 1 7 6 3 A B C D E 2 5 3 3 1 7 6 3 A B C D E 2 5 3 3 1 7 6 3(d)(e)(f)记 V 是连通网的顶点集，U 是求得生成树的顶点集，TE是求得生成树的边集。普里姆算法：(a)开始时，U=v0，TE=；(b)计算 U 到其余顶点V-U 的最小代价，将该顶点纳入U，边纳入TE；(c)重复(b)直到 U=V。普里姆算法和克鲁斯卡尔算法的比较算法普里姆算法克鲁斯卡尔算法时 间 复 杂度O(n2)O(e loge)特点只与顶点个数n 有关与边的数目e 无关适用于稠密图只与边的数目e 有关与顶点个数n 无关适用于稀疏图5.AOV-网用顶点表示活动，边表示活动的优先关系的有向图称为AOV 网。拓扑排序：对AOV 网络中顶点构造拓扑有序序列的过程。拓扑排序的方法(1)在有向图中选一个没有前驱的顶点且输出之(2)从图中删除该顶点和所有以它为尾的弧6.关键路径AOE 网，关键路径AOE网(Activity On Edge)带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。7.最短路径(1)迪杰斯特拉算法求一个顶点到其他各顶点的最短路径。算法：(a)初始化：用起点v 到该顶点w 的直接边(弧)初始化最短路径，否则设为；(b)从未求得最短路径的终点中选择路径长度最小的终点u：即求得 v 到 u 的最短路径；(c)修改最短路径：计算u 的邻接点的最短路径，若(v,u)+(u,w)(v,w)，则以(v,u,w)代替。(d)重复(b)-(c)，直到求得v 到其余所有顶点的最短路径。特点：总是按照从小到大的顺序求得最短路径。(2)弗洛伊德算法求每对顶点之间的最短路径。依次计算A(0)，A(1)，A(n)。A(0)为邻接矩阵，计算 A(k)时，A(k)(i,j)=minA(k-1)(i,j),A(k-1)(i,k)+A(k-1)(k,j)。技巧：计算A(k)的技巧。第k 行、第 k 列、对角线的元素保持不变，对其余元素，考查A(i,j)与 A(i,k)+A(k,j)（“行+列”），如果后者更小则替换A(i,j)，同时修改路径。六、查找1.查找分为：静态查找表、动态查找表、哈希查找表2.静态查找表：对查找表只作查找操作的查找表。动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。3.顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。4.二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。5.索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高6.动态查找表：二叉排序树查找：二叉排序树的生成二叉排序树(二叉查找树)：或者是一颗空树。或者如下1 若它的左子树不空，则左子树上所有的结点的值均小于他的根结点的值。2 若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。7.哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法，数字分析法冲突解决方法：开放定址法、拉链法、公共溢出区法七、排序1.插入类排序：直接插入排序每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。折半插入排序希尔排序基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列。2.交换类排序起泡排序也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。快速排序在当前无序区R1.H 中任取一个数据元素作为比较的基准(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1 和 RI+1.H，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准 X 则位于最终排序的位置上，即 R1.I-1 X.KeyRI+1.H(1I H)，当 R1.I-1 和 RI+1.H 均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。3.选择类排序简单选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。堆排序堆排序是一树形选择排序，在排序过程中，将R1.N 看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。4.归并类排序二路归并排序5.基数类排序基数排序主要特点不需要进行关键字间的比较。多关键字排序：最高为优先（MSD法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一起成为一个有序序列。最低位优先（LSD法）从最次位关键字开始排序，在对高一位的进行排序，直到成为一个有序序列。排序方法稳定性平均时间最坏情况辅助存储直接插入排序稳定O（n*n）O（n*n）O（1）快速排序不稳定O（nlbn）O（n*n）O（lbn）归并排序稳定O(nlbn)O（nlbn）O（n）简单选择排序稳定O（n*n）O（n*n）O（1）堆排序不稳定O（nlbn）O（nlbn）O(1)基数排序稳定O（d（n+rd）O（d（n+rd）O（rd）选取排序方法需要考虑的因素：(1)待排序的元素数目n；(2)元素本身信息量的大小；(3)关键字的结构及其分布情况；(4)语言工具的条件，辅助空间的大小等。小结：(1)若 n 较小(n=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3)若 n 较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n 个关键字随机分布时，任何借助于比较的排序算法，至少需要 O(nlog2n)的时间。