《最新最新军队文职-计算机类计算机类-数据结构与算法知识点总结》由会员分享，可在线阅读，更多相关《最新最新军队文职-计算机类计算机类-数据结构与算法知识点总结（24页珍藏版）》请在金锄头文库上搜索。
1、精品文档数据结构学问点总结内容概要：基本概念 线性表 栈与队列 树与二叉树 图查找算法 排序算法精品文档精品文档一、基本概念1 、数据元素是数据的基本单位；2 、数据项是数据不行分割的最小单位；3 、数据结构的规律结构（抽象的，与实现无关）物理结构（储备结构）次序映像（次序储备结构）位置“相邻”非次序映像（链式储备结构）指针表示关系4 、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决具体问题，并得到正确的结果；有穷性：任何一条指令都只能执行有限次，即算法必需在执行有限步后终止；确定性：算法中每条指令的含义必需明确，不答应由二义性可行性：算法中待执行的操
2、作都特别基本，算法应当在有限时间内执行完毕；输入：一个算法的输入可以包含零个或多个数据；精品文档精品文档输出：算法有一个或多个输出5 、算法设计的要求：（ 1）正确 性：算法应能中意设定的功能和要求；（ 2）可读 性：思路清晰、层次分明、易读易懂；（ 3）健壮 性：输入非法数据时应能作适当的反应和处理；（ 4）高效 性（时间复杂度） ：解决问题时间越短，算法的效率就越高；（ 5）低储备量（空间复杂度）：完成同一功能，占用储备空间应尽可能少；二、线性表1 、线性表List：最常用且最简洁的数据结构；含有大量记录的线性表称为文件；2 、线性表是n 个数据元素的有限序列；线性结构的特点：“第一个”“
3、最终一个”前驱后继；3 、次序表 线性表的次序储备结构特点a) 规律上相邻的元素在物理位置上相邻；b) 随机拜望；1) typedef structDataType elemMAXSIZE;01L.elem.MAXSIZE-1L.length=0int length; SqList;L.elemL.elemL.length=MAXSIZE 0L.lengthnext= =null 循环单链表为空的判定条件为L.next= =L线性链表的最终一个结点的指针为NULL头结点的数据域为空，指针域指向第一个元素的指针；5 、次序表和单链表的比较datanext次序表单链表地址相邻表示关系指针表示关系机
4、拜望，取元素O1序拜望，取元素On入、删除需要移动元素On入、删除不用移动元素On用于查找位置 6 、次序储备：优点：储备密度大，可随机储备缺点：大小固定；不利于增减节点;储备空间不能充分利用；容量难扩充精品文档精品文档链式储备：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制缺点：增加了储备空间的开销；不行以随机储备元素三、栈与队列1 、栈栈：限定仅在表尾进行插入或删除操作的线性表；栈顶：表尾端栈底：表头栈是先进后出的线性表；插入栈顶元素称为入栈，删除栈顶元素称为出栈；2 、栈分为链栈和次序栈链栈用不带头结点的单链表实现；次序栈类似于次序表，插入和删除操作固定于表尾；Sanan-1
5、.a1/进栈: 进栈运算是在栈顶位置插入一个新x元；素算法思想： a判栈是否为满，如栈满，作溢出处理，并0；返回 b如栈未满，栈顶指t针op加1； c将新元素x送入栈顶，并返1回；算法实现：出栈: 出栈运算是指取出栈顶元素，赋给某一个指x定；变量算法步骤：(a) 判栈是否为空，如栈空，作下溢处理，并0；返回(b) 如栈非空，将栈顶元素赋给变x；量(c) 指针top减1，并返回1；int Push SeqSta*cs，k datatypex if （s-top= =MAXLE1N）算法实现：return ；0 else s-top；+/ 栈满不能入栈，且返0回datatypePop（SeqSta
6、c*ks）datatypxe;s-datas-top；=/x/ 栈不满，就压入元x素if SEmptys return ；1 /进栈成功，返回1return ；0/ 如栈空不能出栈，且返回0else x=s-datas-；top/ 栈不空就栈顶元素存*入xs-top-；-return ；x/ 出栈成功，返回13 、队列先进先出的线性表；队尾入队对头出队答应插入的一端叫做队尾答应删除的一端叫做对头4 、链队列精品文档精品文档typedefstruct queuenodedatatypedata;structqueuenode*next;queuenode;/ 链队结点的类型datatypetyp
7、edefstructqueuenode*front,*rear;linkqueue;/ 将头指针、尾指针封装在一起的链队frontprearABJ图4-6链队列示意图5 、 循环队列typedef struct DataType elemMAXSIZE;int front, rear;/队头、队尾位置 SqQueue;循环队列判定队空的条件为front=rear循环队列判定队满的条件为（rear+1） %m=front在一个循环队列中删除元素时，第一需要后移队首指针；6 、栈与队列比较：都是线形结构，栈的操作LIFO（后进先出） ，队列操作FIFO（先进先出） ；四、树和二叉树精品文档精品文档
8、1. 树的定义树（ Tree ）：是 n （ n 0）个有限数据元素的集合；在任意一棵非空树T 中：（ 1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；（ 2）当 n1 时，除根结点之外的其余结点被分成mm0个互不相交的集合T1， T2， Tm，其中每一个集合Ti （ 1 i m）本身又是一棵树，并且称为根的子树；2. 基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否就称作分支结点；结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1孩子和双亲：树的深度：树的度数：树中度数最大的结点度数叫
9、作树的度数树林：是由零个或多个不相交的树所组成的集合；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 = 2n 2 + n1可得 n 0 = n2+14) n 个结点的完全二叉树深度为log n1 ；精品文档精品文档5) n
10、 个结点的完全二叉树，结点按层次编号有：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 struct BTNode DataType data;struct BTN
11、ode *lchild, *rchild, *parent; BTNode, *BinTree;lchilddatarchildlchilddataparentrchild在链式储备结构中，含有n 个结点的二叉链表有n+1 个空链域；5. 遍历二叉树 （先序 DLR、中序 LDR、后序 LRD）方法与C语言描述由二叉树的递归定义可知，一棵二叉树由根结点（ D）、根结点的左子树（ L）和根结点的右子树（ R）三部分组成；因此，只要依次遍历这三部分，就可以遍历整个二叉树；一般有三种方法：先序 前序 遍历 DLR（根左右）、中序遍历 LDR（左根右）、 后序遍历 LRD（左右根） ；精品文档精品文档1 先序遍历（DLR ）的递归过程void PreorderBT*T/ 先序遍历二叉树BT if
