公共基础课本总结.doc

公共基础课本总结 第1章数据结构与算法 1.1算法 算法：是指解题方案的准确而完整的描述。 算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报。 *算法的控制结构：算法中各操作之间的执行顺序。包括：顺序、选择、循环 算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法 算法的复杂度：时间复杂度（算法所需要的计算工作量，即算法所执行的基本运算次数）、空间复杂度（执行这个算法所需要的内存空间） 1.2数据结构的基本概念 数据结构：是指相互有关联的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。 在数据结构中没有前件的结点称为根结点，没有后件的结点为叶子结点（终端结点）。 数据结构研究的三个问题：1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。 2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 3）对各种数据结构进行的运算。 *数据的逻辑结构：指反应数据元素之间逻辑关系的数据结构。 *数据的存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。（常用：顺序、链接、索引等结构） 数据处理：是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析 空的数据结构：一个元素都没有的数据结构。 数据结构分类：线性结构、非线性结构。 *线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。（线性表、栈、队列、线性链表） *非线性结构：不满足线性结构特点的数据结构。树、二叉树、图 1.3线性表及其顺序存储 线性表由一组数据元素组成。 线性表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。 线性表中数据元素的个数n称为线性表的长度。线性表可以为空表：n=0。 线性表是一种存储结构，它的存储方式：顺序和链式。 线性表的顺序存储结构有两个基本特点：1. 所有元素所占的存储空间是连续的。 2.各元素在存储空间中是按逻辑顺序依次存放的，前后件两个元素在存储空间中是紧邻的。 在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，它们所需移动元素的平均个数是为n/2。 1.4栈和队列 栈是限定在一端进行插入与删除的线性表。 栈顶：允许插入与删除的一端。 栈底：不允许插入与删除的一端。 栈是按照“先进后出”或“后进先出”的原则组织数据的。 栈中元素个数：栈底-栈顶+1 栈的基本运算：入栈运算（上溢）、退栈运算（下溢）、读栈顶元素 栈的存储方式和线性表类似，也有两种：顺序栈和链式栈。 队列允许在一端进行插入、而在另一端进行删除的线性表。 队尾（rear）：允许插入的一端。 队头（front）：允许删除的一端。 队列是按照“先进先出”或“后进后出”的原则组织数据的。 队中元素个数：队尾-对头（队尾对头） 队中元素个数：队尾-对头+容量（队尾对头） 队列的基本运算：入队运算、退队运算 循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间 1.5线性链表 线性链表：线性表的链式存储结构，是一种物理存储单元上非连续、非顺序的存储结构 *在链式存储结构中，每个数据结点由两部分组成：数据域（存放数据元素的值）、指针域（存放下一结点的存储地址）。 *在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致， 而数据元素之间的逻辑关系是由指针域来确定的。 *线性链表的优点：在线性链表中插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。 *循环链表的优点：只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。 栈和队列也可采用链式存储结构 线性链表基本运算：插入、删除、合并、分解、逆转、复制、排序、查找 1.6树与二叉树 父结点：每一个结点只有一个前件，称为父结点。 根结点：没有前件的结点只有一个，称为根结点，简称为根。 子结点：每一个结点可以有多个后件，这些后件称为子结点。 叶子结点：没有后件的结点。 结点的度：一个结点所拥有的后件个数。 树的度：所有结点中的最大的度。 树的深度：树的最大层次（几层） *根结点在第1层。叶子结点没有子树。 二叉树的特点：非空二叉树只有一个根结点，每一个结点最多有2颗子树，且分别称为该结点的左子树与右子树。 二叉树的度：可以为0（叶子结点）、1（只有1颗子树）或2（有2颗子树） 二叉树的性质： 1.在二叉树的第k层上，最多有