数据结构知识点总结详细无题目.docx

《数据结构知识点总结详细无题目.docx》由会员分享，可在线阅读，更多相关《数据结构知识点总结详细无题目.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载数据结构学问点总结内容概要：基本概念 线性表 栈与队列 树与二叉树 图查找算法 排序算法可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载一、基本概念1、数据元素是数据的基本单位。2、数据项是数据不行分割的最小单位。3、数据结构的规律结

2、构（抽象的，与实现无关）物理结构（储备结构）次序映像（次序储备结构）位置“相邻”非次序映像（链式储备结构）指针表示关系 4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决详细问题，并得到正确的结果。有穷性：任何一条指令都只能执行有限次，即算法必需在执行有限步后终止。确定性：算法中每条指令的含义必需明确，不答应由二义性可行性：算法中待执行的操作都非常基本，算法应当在有限时间内执行完毕。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 16 页 - - - - - - - - - -可

3、编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出5、算法设计的要求：（ 1）正确 性：算法应能满意设定的功能和要求。（ 2）可读 性：思路清楚、层次分明、易读易懂。（ 3）健壮 性：输入非法数据时应能作适当的反应和处理。（ 4）高效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。（ 5）低储备量（空间复杂度） ：完成同一功能，占用储备空间应尽可能少。二、线性表1 、线性表 List：最常用且最简洁的数据结构。含有大量记录的线性表称

4、为文件。2 、线性表是 n 个数据元素的有限序列。线性结构的特点：“第一个”“最终一个”前驱 后继。3 、次序表 线性表的次序储备结构特点a) 规律上相邻的元素在物理位置上相邻。b) 随机拜访。可编辑资料 - - - 欢迎下载精品名师归纳总结1) typedef structDataType elemMAXSIZE;01L.elem.MAXSIZE-1L.length=0可编辑资料 - - - 欢迎下载精品名师归纳总结int length; SqList;L.elemL.elemL.length=MAXSIZE 0L.lengthnext= =null 循环单链表为空的判定条件为L.next=

5、 =L线性链表的最终一个结点的指针为NULL头结点的数据域为空，指针域指向第一个元素的指针。5 、次序表和单链表的比较可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载次序表单链表以的址相邻表示关系用指针表示关系随机拜访，取元素O1次序拜访，取元素On插入、删除需要移动元素On插入、删除不用移动元素On用于查找位置6 、次序储备：优点：储备

6、密度大，可随机储备缺点：大小固定。不利于增减节点;储备空间不能充分利用。容量难扩充链式储备：优点：易于插入删除。可动态申请空间。表容量仅受内存空间限制缺点：增加了储备空间的开销。不行以随机储备元素三、栈与队列1 、栈栈：限定仅在表尾进行插入或删除操作的线性表。栈顶：表尾端栈底：表头栈是先进后出的线性表。插入栈顶元素称为入栈，删除栈顶元素称为出栈。2 、栈分为链栈和次序栈链栈可编辑资料 - - - 欢迎下载精品名师归纳总结用不带头结点的单链表实现。次序栈Sanan-1.a1/可编辑资料 - - - 欢迎下载精品名师归纳总结类似于次序表，插入和删除操作固定于表尾。可编辑资料 - - - 欢迎下载精

7、品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载可编辑资料 - - - 欢迎下载精品名师归纳总结进栈: 进栈运算是在栈顶位置插入一个新x元。素算法思想： a判栈是否为满，如栈满，作溢出处理，并0。返回 b如栈未满，栈顶指t针op加1。 c将新元素x送入栈顶，并返1回。算法实现：出栈: 出栈运算是指取出栈顶元素，赋给某一个指x定。变量算法步骤：(a) 判栈是否为空，如栈空，

8、作下溢处理，并0。返回(b) 如栈非空，将栈顶元素赋给变x。量(c) 指针top减1，并返回1。可编辑资料 - - - 欢迎下载精品名师归纳总结int Push SeqSta*cs，k datatypex可编辑资料 - - - 欢迎下载精品名师归纳总结 if （s-top= =MAXLE1N）算法实现：可编辑资料 - - - 欢迎下载精品名师归纳总结return 。0 else s-to。p+/ 栈满不能入栈，且返0回datatypePop（SeqStac*ks）datatypxe;可编辑资料 - - - 欢迎下载精品名师归纳总结s-datas-top。=/x/ 栈不满，就压入元x素if SE

9、mptys 可编辑资料 - - - 欢迎下载精品名师归纳总结return 。1 / 进栈胜利，返回1return 。0/ 如栈空不能出栈，且返回0可编辑资料 - - - 欢迎下载精品名师归纳总结else x=s-datas-。top/ 栈不空就栈顶元素存*x入s-top-。可编辑资料 - - - 欢迎下载精品名师归纳总结return 。x/ 出栈胜利，返回1可编辑资料 - - - 欢迎下载精品名师归纳总结3 、队列先进先出的线性表。队尾入队对头出队答应插入的一端叫做队尾答应删除的一端叫做对头4 、链队列typedef struct queuenodedatatypedata;structque

10、uenode*next;queuenode;/ 链队结点的类型datatypetypedefstructqueuenode*front,*rear;linkqueue;/ 将头指针、尾指针封装在一起的链队可编辑资料 - - - 欢迎下载精品名师归纳总结frontprearA BJ图 4-6链队列示意图可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 -

11、- - - - - - - - - - -学习必备欢迎下载5 、 循环队列typedef struct DataType elemMAXSIZE;int front, rear;/队头、队尾位置 SqQueue;循环队列判定队空的条件为front=rear循环队列判定队满的条件为（rear+1）%m=front在一个循环队列中删除元素时，第一需要后移队首指针。 6 、栈与队列比较： 都是线形结构，栈的操作LIFO（后进先出），队列操 作 FIFO（先进先出）。四、树和二叉树可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共

12、16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载1. 树的定义树（ Tree ）：是 n （n0）个有限数据元素的集合。在任意一棵非空树T 中：（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点。（2）当 n1 时，除根结点之外的其余结点被分成 mm0个互不相交的集合 T1，T2， ， Tm，其中每一个集合 Ti （1 i m）本身又是一棵树，并且称为根的子树。2. 基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支

13、结点：左（右）子树均为空二叉树的结点称作树叶否就称作分支结点。结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1孩子和双亲：树的深度：树的度数：树中度数最大的结点度数叫作树的度数树林：是由零个或多个不相交的树所组成的集合。3. 二叉树性质：1) 二叉树的第i 层上至多有2i-1 个结点。2) 深度为 k 的二叉树至多有2k-1 个结点。满二叉树 ：深度为k，有 2k-1 个结点。完全二叉树 ：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1 到 n。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - -

14、- - - - - - - -第 7 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载3) 叶子结点n0 ，度为 2 的结点为n2， 就 n0 = n2+1。考虑结点个数：n = n0 + n1 + n2考虑分支个数：n-1 = 2n2 + n1可得 n0 = n2+1可编辑资料 - - - 欢迎下载精品名师归纳总结4) n 个结点的完全二叉树深度为log n1 。可编辑资料 - - - 欢迎下载精品名师归纳总结5) n 个结点的完全二叉树，结点按层

15、次编号可编辑资料 - - - 欢迎下载精品名师归纳总结有：i 的双亲是n / 2，假如 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 struc

16、t BTNode DataType data;struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree;可编辑资料 - - - 欢迎下载精品名师归纳总结lchilddatarchildlchilddataparentrchild可编辑资料 - - - 欢迎下载精品名师归纳总结在链式储备结构中，含有n 个结点的二叉链表有n+1 个空链域。5. 遍历二叉树 （先序 DLR、中序 LDR、后序 LRD）方法与 C语言描述由二叉树的递归定义可知，一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（ R）三部分组成。因此，只要依次遍历

17、这三部分，就可以遍历整个二叉树。一般有三种方法： 先序 前序 遍历 DLR（根左右） 、中序遍历 LDR（左根右）、 后序遍历LRD（左右根）。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载1 先序遍历（D LR ）的递归过程void PreorderBT*T/ 先序遍历二叉树BT if T= =NULL return;/ 递归调用的终

18、止条件 printfT-data;/ 输出结点的数据域PreorderT-lchild;/ 先序递归遍历左子树PreorderT-rchild;/ 先序递归遍历右子树2 中序遍历（L DR）的递归过程void InorderBT*T/ 中序遍历二叉树BT if T= =NULL return;/ 递归调用的终止条件 InorderT-lchild;/中序递归遍历左子树printfT-data;/ 输出结点的数据域InorderT-rchild;/ 中序递归遍历右子树可编辑资料 - - - 欢迎下载精品名师归纳总结3 后序遍历（L RD）的递归过程可编辑资料 - - - 欢迎下载精品名师归纳总结

19、void PostorderBT*T/后序遍历二叉树BT if T= =NULL return;/ 递归调用的终止条件 PostorderT-lchild;/ 后序递归遍历左子树PostorderT-rchild;/ 后序递归遍历右子树printfT-data;/输出结点的数据域6. 线索二叉树n 个结点的二叉链表中有n+1 个空指针，可以利用其指向前驱或后继结点，叫线索 ，同时需附加一个标志，区分是子树仍是线索。lchild ltagdatartag rchild 0/10/1lchild有左子树，就指向左子树，标志ltag = 0。没有左子树，可作为前驱线索，标志ltag = 1。rchi

20、ld有右子树，就指向右子树，标志rtag = 0。没有右子树，可作为后继线索，标志rtag = 1。7. 树和森林树的储备结构双亲表示法 ，孩子表示法 ，孩子兄弟表示法 。特点：双亲表示法简洁求得双亲， 但不简洁求得孩子。 孩子表示法简洁求得孩子， 但求双亲麻烦。 两者可以结合起来使用。 孩子兄弟表示法， 简洁求得孩子和兄弟， 求双亲麻烦，也可以增加指向双亲的指针来解决。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料wo

21、rd 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载树与二叉树的转换表 错误！文档中没有指定样式的文字。.1树和二叉树的对应关系树对应的二叉树根根第一个孩子左孩子下一个兄弟右孩子树的遍历树的结构：根，根的子树。先根遍历：。例：ABCDEFGHIJ。K后根遍历：。例：CEDFBHGJKI。A遍历森林森林的结构：第一棵树的根，第一棵树的根的子树森林，其余树 除第一棵外 组成的森林。先序遍历：。例：ABCDEFGHI。J中序遍历：。例：BDCEAGFIJH。注：先序遍历森林， 相当于依次先根遍历每一棵树。中根遍历森林相当于后根遍历每一棵树。AAFH可编辑资料 - - -

22、 欢迎下载精品名师归纳总结BGIBCEGIJ可编辑资料 - - - 欢迎下载精品名师归纳总结CDFHJKDE树的结构划森林的结构划分遍历树、森林与遍历二叉树的关系遍历树、森林和二叉树的关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历8. 哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树构造赫夫曼树每次取两个最小的树组成二叉树可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 -

23、 - - - - - - - - - - -学习必备欢迎下载赫夫曼编码 前缀码 向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。五、图1 完全图：有 12 nn-1条变得无向图有向完全图：具有n（n-1）条弧的有向图。 权：与图的边或弧相关的数。顶点 v 的度：和 v 相关联的边的数目。入度：以顶点 v 为头的弧的数目出度：以顶点 v 为尾的弧的数目回路或环：第一个顶点和最终一个顶点相同的路径。简洁路径：序列中顶点不重复显现的路径。2. 图的储备结构邻接矩阵：A01100B00110C00010D10000E10010邻接表：typedef struct ArcNode /弧结

24、点intadjvex;/邻接点struct ArcNode *nextarc;/下一个邻接点 ArcNode;typedef struct VexNode /顶点结点VertexTypedata;/顶点信息ArcNode *firstarc;/第一个邻接点 VexNode;const int MAX_VERTEX =最大顶点个数;typedef struct Graph /图VexNodevexsMAX_VERTEX;/顶点向量intvexnum, arcnum;/顶点和弧的个数 Graph;边弧多就需要储备空间多。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - -

25、 - - - - - - -第 11 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载0A12/1B23/2C3/3D0/4E03/十字链表：十字链表是有向图的另一种链式储备结构。可以看成是将有向图的邻接表和逆 邻接表结合起来的一种链表。 在十字链表中， 对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。邻接多重表3. 图的遍历1) 深度优先（ DFS）搜寻拜访方式：从图中某顶点v 动身： a）拜访顶点 v。b）从 v 的未被拜访的邻接点动

26、身，连续对图进行深度优先遍历，如从某点动身全部邻接点都已拜访过，退回前一个点连续上述过程，如退回开头点， 终止。2) 广度（宽度， BFS）优先搜寻 a）拜访顶点 v 。b）拜访同 v 相邻的全部未被拜访的邻接点w1,w2,kw。c）依次从这些邻接点动身， 拜访它们的全部未被拜访的邻接点; 依此类推，直到图中全部拜访过的顶点的邻接点都被拜访。4. 生成树和最小生成树每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。 因此有 DFS生成树和 BFS生成树。1) 最小生成树 Kruskal算法一句话，“不构成环的情形下，每次选

27、取最小边”。可编辑资料 - - - 欢迎下载精品名师归纳总结A532A532A532可编辑资料 - - - 欢迎下载精品名师归纳总结6B3E137CDa6B 3E137CDb6B3E137CDc可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结A5326B3EDA5326B3EDA5326B3ED可编辑资料 - - - 欢迎下载精品名师归纳总结137C(d)137C(e)137C(f)可编辑资料 - - - 欢迎下载精品名师归纳总结 普里姆算法可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -

28、第 12 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载记 V 是连通网的顶点集，U 是求得生成树的顶点集，TE 是求得生成树的边集。普里姆算法：(a) 开头时， U=v0 ，TE=。b运算 U 到其余顶点V-U 的最小代价，将该顶点纳入U，边纳入TE。c重复 b直到 U=V。普里姆算法和克鲁斯卡尔算法的比较算法普里姆算法克鲁斯卡尔算法时 间 复 杂On2Oe loge度特点只与顶点个数n 有关只与边的数目e 有关可编辑资料 - - - 欢迎下载精

29、品名师归纳总结与边的数目e 无关适用于稠密图与顶点个数n 无关适用于稀疏图可编辑资料 - - - 欢迎下载精品名师归纳总结5. AOV- 网用顶点表示活动，边表示活动的优先关系的有向图称为AOV 网。拓扑排序：对AOV 网络中顶点构造拓扑有序序列的过程。拓扑排序的方法1在有向图中选一个没有前驱的顶点且输出之2从图中删除该顶点和全部以它为尾的弧6. 关键路径AOE 网，关键路径AOE 网Activity On Edge带权的有向无环图，其中顶点表示大事，弧表示活动， 权表示活动连续时间。在工程上常用来表示工程进度方案。关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。7. 最

30、短路径(1) 迪杰斯特拉算法求一个顶点到其他各顶点的最短路径。算法： a 初始化：用起点v 到该顶点w 的直接边 弧初始化最短路径，否就设为。(b) 从未求得最短路径的终点中挑选路径长度最小的终点u：即求得 v 到 u 的最短路径。可编辑资料 - - - 欢迎下载精品名师归纳总结(c) 修改最短路径：运算u 的邻接点的最短路径，如v,u+u,wv,代替。(d) 重复 b-c，直到求得v 到其余全部顶点的最短路径。特点：总是根据从小到大的次序求得最短路径。，就以,wv,u,w可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - -

31、 - - - - - - - -第 13 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载(2) 弗洛伊德算法求每对顶点之间的最短路径。依次运算A0，A1， ，An。A0为邻接矩阵， 运算 Ak时，Aki,j=minA k-1i,j, A k-1i,k+Ak-1k,j。技巧：运算Ak的技巧。第k 行、第 k 列、对角线的元素保持不变，对其余元素，考查Ai,j 与 Ai,k+Ak,j（“行 +列”），假如后者更小就替换Ai,j，同时修改路径。六、查找1

32、. 查找分为：静态查找表、动态查找表、哈希查找表2. 静态查找表：对查找表只作查找操作的查找表。动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。3. 次序查找：次序查找又称线性查找，是最基本的查找方法之一。次序查找既适用于次序表，也适用于链表。4. 二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必需按关键字有序（按关键字递增或递减）排列。5. 索引次序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高6. 动态查找表：二叉排序树查找：二叉排序树的生成二叉排序树 二叉查找树 ：或者是一颗空树。或者如下1 如它的左子树不空，就

33、左子树上全部的结点的值均小于他的根结点的值。2 如右子树不空，就右子树全部结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。7. 哈希表： 哈希函数构造： 直接定址法、 除留余数法、 平方取中法， 随机数法， 数字分析法冲突解决方法：开放定址法、拉链法、公共溢出区法七、排序1. 插入类排序：直接插入排序每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依旧有序。直到待排序数据元素全部插入完为止。折半插入排序希尔排序基本思想：先将整个待排序记录序列分成为如干个子序列分别进行直接 插入排序，待整个序列中的记录基本有序时在对全体序列进行一次直接插入排序，子序列的构

34、成不是简洁的逐段分割，而是将像个某个增量 的记录组成一个子序列。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 14 页，共 16 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习必备欢迎下载2. 交换类排序起泡排序也称冒泡法， 每相邻两个记录关键字比大小, 大的记录往下沉 （也可以小的往上浮）。每一遍把最终一个下沉的位置登记，下一遍只需检查比较到此为止。到全部记录都不发生下沉时，整个过程终止（每交换一次，记 录削

35、减一个反序数） 。快速排序在当前无序区 R1.H 中任取一个数据元素作为比较的 基准 不妨记为 X，用此基准将当前无序区划分为左右两个较小的无序区： R1.I-1 和 RI+1.H ，且左边的无序子区中数据元素均小于等于基准元素， 右边的无序子区中数据元素均大于等于基准元素，而基准 X 就位于最终排序的位置上，即 R1.I- 1 X.KeyRI+1.H1I ，H当 R1.I-1 和 RI+1.H 均非空时， 分别对它们进行上述的划分过程，直至全部无序子区中的数据元素均已排序为止。3. 挑选类排序简洁挑选排序每一趟从待排序的数据元素中选出最小（或最大） 的一个元素， 次序放在已排好序的数列的最终，直到全部待排序的数据元素排完。堆排序堆排序是一树形挑选排序，在排序过程中，将R1.N 看成是一颗完全二叉树的次序储备结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来挑选最小的元素。