数据结构与算法.docVIP

第一章数据结构与算法 1.1算法 算法：是指解题方案的准确而完整的描述。1 算法特征： （1）可行性； （2）确定性：每个步骤必须有明确定义，不能模棱两可； （3）有穷性：在有限个步骤后终止； （4）拥有足够的情报： 算法的基本要素： （1）对数据对象的运算和操作:：包括算术运算；逻辑运算；关系运算；数据传输。 （2）算法的控制结构：算法中各操作之间的执行顺序。包括顺序；选择；循环。 常用工具：传统流程图、N－S图、算法描述语言。 算法设计的基本方法： （1）列举法：列举所有可能； （2）归纳法：列举少量可能，经分析，找出一般规律； （3）递推法：从已知条件出发，逐步找结果； （4）递归法：将问题逐层分解，再沿分解的逆过程逐步综合。 自己调用自己叫直接递归；通过别人调用自己叫间接递归调用。 （5）减半递推技术：问题规模减半，性质不变。 算法复杂度： （1）时间复杂度：执行算法所需要的计算工作量。 （2）空间复杂度：执行这个算法所需要的内存空间。2 1.2数据结构的基本概念 数据结构研究的三个方面： （1）数据的逻辑结构：数据元素之间的逻辑关系 （2）数据的存储结构（物理结构）：逻辑结构在计算机中的存放形式。1 常用的有顺序、链接、索引。2 （3）对各种数据结构进行的运算。 逻辑结构与存储结构的关系：一种数据的逻辑结构根据需要可以表示成多种存储结构，而采用不同的存储结构，其数据处理的效率是不同的。2 数据结构：相互有关联的数据元素的集合。 数据结构的表示方法：（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）。2 栈是“先进后出”3（FILO）、“后进先出”（LIFO）的线性表。 栈具有记忆作用。1 栈的基本运算： （1）入栈运算：在栈顶插入一个元素。 （2）退栈运算：删除栈顶元素。 （3）读栈顶元素：将栈顶元素赋给某个变量。 队列：是指允许在一端进入插入，而在另一端进行删除的线性表。 允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列的基本运算： （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 1.5线性链表 线性表的链式存储结构称为线性链表。3 数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成： （1）用于存储据元素值，称为数据域； （2）用于存放指针，称为指针域，用于指向前一个或后一个结点。 链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。1 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。 线性链表的基本运算：查找、插入、删除。 循环链表的特点： （1）增加了一个头结点。 （2）链表中最后一个结点指向头结点。 循环链表中所有的结点连成一个环状链，只要指出表中的任意一个结点就能找出其他所有结点。循环链表实现了空表和非空表的统一。 1.6树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 树中结点的度：结点后件的个数。度为0的结点称为叶子。 树的度：树中度最大的结点的度。 树的深度：树的层数。 二叉树：度为2的树。 二叉树的基本性质： （1）在二叉树的第k层上，最多有个结点；2 （2）深度为m的二