《军队文职-计算机类计算机类-数据结构与算法知识点总结》由会员分享，可在线阅读，更多相关《军队文职-计算机类计算机类-数据结构与算法知识点总结（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构知识点总结内容概要：基本概念线性表栈与队列树与二叉树图查找算法排序算法一、 基本概念1、数据元素是数据的基本单位。2、数据项是数据不可分割的最小单位。3、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决具体问题，并得到正确的结果。有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。确定性：算法中每条指令的含义必须明确，不允许由二义性可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执
2、行完毕。输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出5、算法设计的要求：（1）正 确 性：算法应能满足设定的功能和要求 。 （2）可 读 性：思路清晰、层次分明、易读易懂 。 （3）健 壮 性：输入非法数据时应能作适当的反应和处理。 （4）高 效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。 （5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。二、 线性表1、线性表 List：最常用且最简单的数据结构。含有大量记录的线性表称为文件。2、线性表是n个数据元素的有限序列。线性结构的特点： “第一个” “最后一个” 前驱 后继。3、顺序表线性表的顺
3、序存储结构特点a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0L.lengthnext= =null循环单链表为空的判定条件为 L.next= =L线性链表的最后一个结点的指针为NULL头结点的数据域为空，指针域指向第一个元素的指针。5、顺序表和单链表的比较顺序表单链表以地址相邻表示关系用指针表示关系随机访问，取元素O(1)顺序访问，取元素O(n)插入、删除需要移动元素O(n)插入、删除不用移动元素O(n)(用于查找位置)6、顺序存储：优点：存储密度大，可随机存储 缺点：大
4、小固定；不利于增减节点;存储空间不能充分利用；容量难扩充链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制 缺点：增加了存储空间的开销；不可以随机存储元素三、 栈与队列1、栈栈：限定仅在表尾进行插入或删除操作的线性表。栈顶：表尾端栈底：表头栈是先进后出的线性表。插入栈顶元素称为入栈，删除栈顶元素称为出栈。2、栈分为链栈和顺序栈链栈a1/anS.an-1用不带头结点的单链表实现。顺序栈类似于顺序表，插入和删除操作固定于表尾。3、队列先进先出的线性表。队尾入队 对头出队允许插入的一端叫做队尾允许删除的一端叫做对头4、链队列5、 循环队列typedef struct DataTyp
5、e 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)个互不相交的集合T
6、1，T2，Tm，其中每一个集合Ti（1 i m）本身又是一棵树，并且称为根的子树。2. 基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1孩子和双亲：树的深度：树的度数：树中度数最大的结点度数叫作树的度数树林：是由零个或多个不相交的树所组成的集合。3. 二叉树性质：1) 二叉树的第i层上至多有2i-1个结点。2) 深度为k的二叉树至多有2k-1个结点。 满二叉树：深度为k，有2k-1个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，
7、n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。3) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。考虑结点个数：n = n0 + n1 + n2考虑分支个数：n-1 = 2n2 + n1可得n0 = n2+14) n个结点的完全二叉树深度为。5) n个结点的完全二叉树，结点按层次编号有： i的双亲是，如果i = 1时为根（无双亲）； i的左孩子是2i，如果2in，则无左孩子； i的右孩子是2i + 1，如果2i + 1n则无右孩子。4. 二叉树的存储结构顺序存储结构用数组、编号i的结点存放在i-1处。适合于存储完全二叉树。链式存储结构二叉链表：typedef str
8、uct BTNode DataType data; struct BTNode *lchild, *rchild; BTNode, *BinTree;三叉链表：typedef struct BTNode DataType data; struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree;dataparentlchildrchilddatarchildlchild在链式存储结构中，含有n个结点的二叉链表有n+1个空链域。5. 遍历二叉树（先序DLR、中序LDR、后序LRD）方法与C语言描述由二叉树的递归定义可知，一棵二叉树由根结点（D
9、）、根结点的左子树（L）和根结点的右子树（R）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历DLR（根左右）、中序遍历LDR（左根右）、 后序遍历LRD（左右根）。6. 线索二叉树n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。lchildltagdatartagrchild0/10/1lchild有左子树，则指向左子树，标志ltag = 0；没有左子树，可作为前驱线索，标志ltag = 1。rchild有右子树，则指向右子树，标志rtag = 0；没有右子树，可作为后继线索，标
10、志rtag = 1。7. 树和森林树的存储结构双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。树与二叉树的转换表 Error! No text of specified style in document.1 树和二叉树的对应关系树对应的二叉树根根第一个孩子左孩子下一个兄弟右孩子树的遍历树的结构：根，根的子树。先根遍历：。例：ABCDEFGHIJK。后根遍历：。例：CEDFBHGJKIA。遍历森林森林的结构：第一棵树
11、的根，第一棵树的根的子树森林， 其余树(除第一棵外)组成的森林。先序遍历：。例：ABCDEFGHIJ。中序遍历：。例：BDCEAGFIJH。注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。ABICDFHGJKEAHBCEGFIJD树的结构划分森林的结构划分遍历树、森林与遍历二叉树的关系遍历树、森林和二叉树的关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历8. 哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树构造赫夫曼树 每次取两个最小的树组成二叉树赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。五、
12、图1完全图：有12 n(n-1)条变得无向图有向完全图：具有n（n-1）条弧的有向图。权：与图的边或弧相关的数。顶点v的度：和v相关联的边的数目。入度：以顶点v为头的弧的数目出度：以顶点v为尾的弧的数目回路或环：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。2. 图的存储结构邻接矩阵：0110000110000101000010010ABCDE邻接表：typedef struct ArcNode / 弧结点 int adjvex;/ 邻接点 struct ArcNode *nextarc;/ 下一个邻接点 ArcNode;typedef struct VexNode / 顶点结点 VertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个邻接点 VexNode;const int MAX_VERTEX = 最大顶点个数;typedef struct Graph / 图 VexNode vexsMAX_VERTEX;/ 顶点向量 int vexnum, arcnum;/ 顶点和弧的个
