期末考试信管数据结构小抄.docx

动态内存分配就是设计人员可以根据问题的具体需要，在程序运行时再确定数据的个数或占用内存单元的大小，从而在程序运行时具体确定所需要的内存空间。数据是人们利用文字符号、数学符号以及其他规定的符号对现实世界的十五及其活动所作的抽象描述。数据元素：表示一个事物的一组数据。数据项：构成数据元素的数据。队列：只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表.顺序队列：顺序存储结构的队列。抽象数据类型：指一个逻辑概念上的类型和这个类型上的操作集合。二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。由给定的n个叶结点权值可以构造很多棵形态不同的二叉树，WPL值最小的二叉树称为哈夫曼树。设计哈夫曼树的结点存储结构为双亲孩子存储结构无向完全图：在有n个顶点的无向图中，有n(n-1)/2条边，即任意两个顶点之间有且只有一条边。有向完全图：在有n个顶点的有向图中，有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边结点的度= 入度+ 出度。即进来的边条数加指出去的边条数路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和数据操作。数据的存储结构:数据元素在计算机中的存储方式。有两种基本形式：顺序和链式存储结构。描述算法语言的三种形式：文字、伪码、程序设计语言形式。算法的时间复杂度有： O(1)， O(log2n)， O(n)，O(nlog2n)， O(n2)， O(n3 )， O(2n)。算法的时间复杂度是衡量一个算法好坏的重要指标。n的越大，时间复杂度越大，算法的执行效率越低。程序运行时要求系统分配空间的函数：malloc()函数、free()、calloc()、realloc()线性表的表示方法：顺序表、链表。（抽象数据类型的存储结构）串的顺序存储结构：静态数组结构、动态数组结构。串的链式存储结构：单字符结点链、块链。单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。链表：单链表、单循环链表、双向循环链表堆栈：限定只能在固定一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。堆栈，后进先出表。线性表，先进后出表。树的定义具有递归性树的表示方法：直观表示法、形式化表示法、凹入表示法树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法深度为k的二叉树至多有2k+1-1个结点具有n个结点的完全二叉树的深度k为log2(n+1)-1二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉树的遍历算法分为前序遍历（DLR）、中序遍历（LDR）、后序遍历、层序树的遍历算法：先根遍历算法、后根遍历算图的遍历算法：深度优先、广度优先图的存储结构：邻接矩阵、邻接表排序分为内部排序和外部排序。常用的插入排序：直接插入排序、希尔排序。常用的选择排序算法：直接选择排序、堆排序算法思想：括号匹配问题。算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号；（4）左右括号匹配正确。具体方法：顺序扫描算术表达式（表现为一个字符串），当遇到三种类型的左括号时让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左右括号配对次序不正确；若字符串当前为某种类型右括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空（即堆栈中尚有某种类型左括号），则说明左括号多于右括号；否则，左右括号匹配正确。算法思想：回文。设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。算法思想：堆排序。循环执行如下过程直到数组为空：（1）把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换；（2）最大堆元素个数减1；（3）由于第（1）步后根结点不再满足最大堆的定义，所以调整根结点使之满足最大堆的定义。Brute-Force算法的设