公共基础 数据结构与算法

《公共基础 数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。算法特征：（1）可行性；（2）确定性：每个步骤必须有明确定义，不能模棱两可；（3）有穷性：在有限个步骤后终止；（4）拥有足够的情报：算法的基本要素：（1）对数据对象的运算和操作:：包括算术运算；逻辑运算；关系运算；数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序。包括顺序；选择；循环。常用工具：传统流程图、N－S图、算法描述语言。算法设计的基本方法：（1）列举法：列举所有可能；（2）归纳法：列举少量可能，经分析，找出一般规律；（3）递推法：从已知条件出发，

2、逐步找结果；（4递归法：将问题逐层分解，再沿分解的逆过程逐步综合。自己调用自己叫直接递归）；通过别人调用自己叫间接递归调用。（5）减半递推技术：问题规模减半，性质不变。算法复杂度：（1）时间复杂度：执行算法所需要的计算工作量。（2）空间复杂度：执行这个算法所需要的内存空间。1.2数据结构的基本概念数据结构研究的三个方面：（1）数据的逻辑结构：数据元素之间的逻辑关系（2）数据的存储结构（物理结构）：逻辑结构在计算机中的存放形式。（3）对各种数据结构进行的运算。数据结构：相互有关联的数据元素的集合。数据结构的表示方法：（1）图形；（2）

3、二元关系。逻辑结构的两要素：（1）数据元素集合（D）（2）D上的关系（R）线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构条件：不满足线性结构条件的数据结构。1.3线性表及其顺序存储结构线性表：由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征：（1）且只有一个根结点a，它无前件；（2）有且只有一个终端点a，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：结点个数n（当n=0时

4、，称为空表）。线性表的顺序存储结构的两个基本特点：（1）所有元素的存储空间是连续的；（2）所有元素在存储空间中是按逻辑顺序依次存放的。顺序表（注意：专指顺序存储的线性表）的基本操作：（1）插入：在n个长的顺序表中第i个元素前插入一个元素，需要移动n-i+1个元素，表长变为n+1。（2）删除：在n个长的顺序表中删除第i个元素，需要移动n-i个元素，表长变为n-1。1.4栈和队列栈：限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶（top），不允许插入与删除的另一端称为栈底（bottom）。栈是“先进后出”（FILO）、“

5、后进先出”（LIFO）的线性表。栈具有记忆作用。栈类似仓库（放东西）队列类似（按规矩）排队栈的基本运算：（1）入栈运算：在栈顶插入一个元素。（2）退栈运算：删除栈顶元素。（3）读栈顶元素：将栈顶元素赋给某个变量。例：已知元素的入栈顺序为abcde，则下列哪种出栈顺序是不可能的（出栈和入栈操作可交叉进行）？A、edcbaB、cabdeC、dcbaeD、bcdea队列：是指允许在一端进入插入，而在另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列是“先进先出”（FIFO）或“后进后出”

6、（LILO）的线性表。不能插队队列的基本运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。1.5线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性链

7、表的基本运算：查找、插入、删除。循环链表的特点：（1）增加了一个头结点。组成一个环（2）链表中最后一个结点指向头结点。循环链表中所有的结点连成一个环状链，只要指出表中的任意一个结点就能找出其他所有结点。循环链表实现了空表和非空表的统一。1.6树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。树中结点的度：结点后件的个数。度为0（后件数为0）的结点称为叶子。树的度：树中度最大（后件数最多）的结点的度。树的深度：树的层数。二叉树：度为2的树。二叉树的基本性质：（1）在二叉树的第k层上，最多有个结点；注意K-1的位置（2

8、）深度为m的二叉树最多有个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为；（5）具有n个结点的完全二叉树的深度为；满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度