专升本数据结构复习
数据结构知识点总汇
主要参考书⽬：
1. 程海英⽼师的《数据结构（C语⾔版）》教材
2. 严蔚敏，李冬梅，吴伟民．《数据结构（C语⾔版）》
推荐视频：
说明：这是本⼈专升本上岸⼀年后写的，本篇包含知识点和例题总结。因为是当时⾃⼰⼿码的，所以知识点有冗余和顺序错位。如果发现有错误之处，欢迎评论区留⾔，看到后及时改正，谢谢！最后祝⼤家好好学习，积极向上，早⽇上岸！
① 数据结构(逻辑结构)其4类基本结构：集合、线性结构、树形结构、图状结构 和 ⽹状结构。
② 物理结构(存储结构)其4种存储结构：顺序存储结构、链式存储结构、索引存储结构 和 散列存储结构。
③ 算法5个重要特性：有穷性、确定性、可⾏性、输⼊ 和 输出。
  通常从四个⽅⾯评价算法的质量：正确性、易读性、强壮性 和 ⾼效率。
④ 线性表是由n≥0个数据元素组成的 有限序列。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻。
⑤ 在顺序表中实现的基本运算：
  插⼊：平均移动结点次数为 n/2；平均时间复杂度均为O（n）。
  删除：平均移动结点次数为 （n-1）/2；平均时间复杂度均为O（n）。
⑥ 存储位置计算：每个元素需占⽤L个存储单元第⼀个单元的存储地址作为数据元素的存储位置线性表的第i个数据元素ai的存储位置
为LOC(ai)=LOC(a1)+(i-1)*L ，a1的存储位置，通常称做线性表的起始位置或基地址。
⑦ 线性表的链式存储结构：数据元素ai的存储映像称为结点，包括2个域：存数据的 数据域、存后继存储位置的 指针域。
⑧ 线性链表(单链表)特点：每个结点只包含1个指针域。在单链表的第⼀个结点之前附设的⼀个结点，称之为 头结点。
⑨ 假设L是LinkList型变量，则L为单链表的头指针，它指向表中第⼀个结点。
  L->next 为第⼀个结点地址，L->next=NULL为 空表。
  回收结点：free(q)。
二叉树的基本性质
⑩ 栈：是限定仅在 栈顶(表尾)进⾏插⼊或删除操作 的线性表。表头端称为栈底，不含有元素的空表称为空栈；栈⼜称为 后进先出 的线性表。
队列：是⼀种 先进先出 的线性表，它只允许在表的⼀端进⾏插⼊，⽽另⼀端删除元素。允许插⼊的⼀端叫做队尾，允许删除的⼀端则称为队头。
链队列：⽤链表⽰的队列。⼀个队列需要头指针和尾指针才能确定唯⼀。
⑩ 栈：是限定仅在 栈顶(表尾)进⾏插⼊或删除操作 的线性表。表头端称为栈底，不含有元素的空表称为空栈；栈⼜称为 后进先出 的线性表。
队列：是⼀种 先进先出 的线性表，它只允许在表的⼀端进⾏插⼊，⽽另⼀端删除元素。允许插⼊的⼀端叫做队尾，允许删除的⼀端则称为队头。
链队列：⽤链表⽰的队列。⼀个队列需要头指针和尾指针才能确定唯⼀。
循环队列：两个指针front指⽰队列头元素和rear指⽰队列尾元素的位置。初始化建空队列时，令front = rear = 0，每当插⼊新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。
串：是由零个或多个字符组成的有限序列。
数组的存储位置计算：假设每个数据元素需占⽤L个存储单元，则⼆维数组A中任⼀元素A[ij]的存储位置可由下式确定：
  以⾏序为主序的存储结构：LOC(i,j)=LOC(0,0)+(n*i+j)*L;(n为⾏数)
  以列序为主序的存储结构：LOC(i,j)=LOC(0,0)+(n*j+i)*L;(n为列数)
⼴义表：是线性表的推⼴，在⼴义表的定义中，ai可以是单个元素，也可以是⼴义表，分别称为⼴义表LS的原⼦和⼦表。
⼆叉树的性质：
  性质1：在⼆叉树的第K层上⾄多有 2k-1 个结点(K≥1)。
  性质2：深度为k的⼆叉树⾄多 2k-1 个结点(k≥1)。
      深度为k的⼆叉树⾄少有k个结点(k≥1)。
      深度为k的完全⼆叉树⾄少有 2k-1 个结点(k≥1)。
  性质3：对任何⼀棵⼆叉树T，如果其终端结点数为N0，度为2的结点数为N2，则 N0=N2+1。总结点个数 N=N0+N1+N2。  性质4：具有n个结点的完全⼆叉树的深度为 [log2n]+1。
满⼆叉树：⼀颗深度为k且有 2的k次⽅减1个结点的⼆叉树。
完全⼆叉树：深度为k的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1⾄n的结点⼀⼀对应。
树转换成⼆叉树：连兄弟，留长⼦，删孩⼦。
  注意：由于树根没有兄弟结点，固树转换为⼆叉树后，⼆叉树根结点的右⼦树必为空。
① 森林转换成⼆叉树：连树根及兄弟，留长⼦，删孩⼦。
② ⼆叉树转换成树：连左孩⼦的右孩⼦及其右孩⼦…，删原树右孩⼦。
③ 赫夫曼树：⼜称最优树，是⼀类带权路径长度最短的树。
WPL=23+43+52+71=35
④ 赫夫曼编码：在赫夫曼树上，左分⽀代表0，右分⽀代表1。由根结点到指定结点的路径(从上到下把0、1连起来)，就是该结点的赫夫曼编码；如上图(d)中a为0，b为10，c为110，d为111。
⑤⽆向完全图：有 n(n-1)/2 条边的⽆向图。
 有向完全图：有 n(n-1) 条边的有向图。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。