公共基础 数据结构与算法.doc

第一章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。算法特征：（1）可行性；（2）确定性：每个步骤必须有明确定义，不能模棱两可；（3）有穷性：在有限个步骤后终止；（4）拥有足够的情报：算法的基本要素：（1）对数据对象的运算和操作:：包括算术运算；逻辑运算；关系运算；数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序。包括顺序；选择；循环。 常用工具：传统流程图、NS图、算法描述语言。算法设计的基本方法：（1）列举法：列举所有可能；（2）归纳法：列举少量可能，经分析，找出一般规律；（3）递推法：从已知条件出发，逐步找结果；（4递归法：将问题逐层分解，再沿分解的逆过程逐步综合。 自己调用自己叫直接递归）；通过别人调用自己叫间接递归调用。（5）减半递推技术：问题规模减半，性质不变。算法复杂度： （1）时间复杂度：执行算法所需要的计算工作量。（2）空间复杂度：执行这个算法所需要的内存空间。1.2数据结构的基本概念数据结构研究的三个方面：（1）数据的逻辑结构：数据元素之间的逻辑关系（2）数据的存储结构（物理结构）：逻辑结构在计算机中的存放形式。（3）对各种数据结构进行的运算。数据结构：相互有关联的数据元素的集合。数据结构的表示方法：（1）图形；（2）二元关系。逻辑结构的两要素：（1）数据元素集合（D）（2）D上的关系（R）线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构条件：不满足线性结构条件的数据结构。1.3线性表及其顺序存储结构线性表：由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征：（1）且只有一个根结点a ，它无前件；（2）有且只有一个终端点a ，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：结点个数n（当n=0时，称为空表）。线性表的顺序存储结构的两个基本特点：（1）所有元素的存储空间是连续的；（2）所有元素在存储空间中是按逻辑顺序依次存放的。顺序表（注意：专指顺序存储的线性表）的基本操作：（1）插入：在n个长的顺序表中第i个元素前插入一个元素，需要移动n-i+1个元素，表长变为n+1。（2）删除：在n个长的顺序表中删除第i个元素，需要移动n-i个元素，表长变为n-1。1.4栈和队列栈：限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶（top），不允许插入与删除的另一端称为栈底（bottom）。栈是“先进后出”（FILO）、“后进先出”（LIFO）的线性表。栈具有记忆作用。栈类似仓库（放东西） 队列类似（按规矩）排队栈的基本运算：（1）入栈运算：在栈顶插入一个元素。（2）退栈运算：删除栈顶元素。 （3）读栈顶元素：将栈顶元素赋给某个变量。例：已知元素的入栈顺序为abcde，则下列哪种出栈顺序是不可能的（出栈和入栈操作可交叉进行）？A、edcba B、cabde C、dcbae D、bcdea 队列：是指允许在一端进入插入，而在另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 不能插队队列的基本运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。1.5线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性链表的基本运算：查找、插入、删除。循环链表的特点：（1）增加了一个头结点。 组成一个环（2）链表中最后一个结点指向头结点。循环链表中所有的结点连成一个环状链，只要指出表中的任意一个结点就能找出其他所有结点。循环链表实现了空表和非空表的统一。1.6树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。树中结点的度：结点后件的个数。度为0（后件数为0）的结点称为叶子。树的度：树中度最大（后件数最多）的结点的度。树的深度：树的层数。二叉树：度为2的树。二叉树的基本性质：（1）在二叉树的第k层上，最多有个结点；注意K-1的位置（2）深度为m的二叉树最多有个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为；（5）具有n个结点的完全二叉树的深度为；满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的二叉树具有2k-1个结点。即在满二叉树的第k层上有2k-1个结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1n的结点一一对应，则该树是完全二叉树。如图所示，为满二叉树和完全二叉树的结构比较。满二叉树 完全二叉树图满二叉树与完全二叉树结构二叉树一般采用链式存储结构，但特别的对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历： 前中后针对根接点 前：ABDECF 中：DBEACF 后：DEBFCA（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD），首先遍历左子树，然后访问遍历右子树，最后访问根结点。 抓住根不放第二次根为BABCDEF例如：写出右图所示的二叉树的遍历顺序。前后遍历可确根 中遍历可确左右子树1.7查找技术顺序查找对于长度为n的序线性表，最坏情况只需比较n次。二分法查找只适用于顺序存储的有序表，对于长度为n的序线性表，最坏情况只需比较次。1.8排序技术交换类排序法：（1）冒泡排序法，需要比较的次数为； 特点：相邻数据元素交换。（2）快速排序法。一般情况；最坏情况为。插入类排序法：（1）简单插入排序法，最坏情况需要次比较