17_数据结构与算法

目录

线性结构

线 性 表

顺序存储和链式存储

队列和栈

环形队列

树与二叉树

树

二叉树

二叉树的存储结构

二叉树的遍历

图

图的基本概念

图的存储

图的遍历

算法的复杂度

算法分析方法

递推和递归

分治法

回溯法

贪心法

动态规划法

---

线性结构

线 性 表

线性表是线性结构(每个元素最多只有一个出度和一个入度，表现为一条线状)的代表，线性表按存储方式分为顺序表和链表，存储形式如下图

上图中，顺序表是需要一段连续的内存空间来存放顺序表中的所有元素，这些元素在物理地址上是相邻的。

而链表又可分为单链表、循环链表、双向链表，所有元素只是逻辑上相邻，在实际物理存储时处于不同的空闲块中，元素之间通过指针域连接。

顺序存储和链式存储

顺序存储和链式存储的对比如上图所示。在空间方面，因为链表还需要存储指针，因此有空间浪费存在。在时间方面，由顺序表和链表的存储方式可知，当需要对元素进行破坏性操作(插入、删除)时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他结点位置都需要变动。

而当需要对元素进行不改变结构操作(读取、查找)时，顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头结点开始，一个个地查找下去。

队列和栈

队列和栈的结构如图所示，队列是先进先出，分队头和队尾；栈是先进后出，只有栈顶能进出。

环形队列

环形队列是一个首尾相连的先进先出(First Input First Output,FIFO)数据结构，采用数组存储，到达尾部时将转回到0位置，该转回是通过取模操作来实现的。因此环形队列逻辑上是将数组元素q[0]与q[MAX-1]连接，形成一个存放队列的环形空间。为了方便读写，还要用数组下标来指明队列的读写位置，其中head指向可以读的位置，tail指向可以写的位置，环形队列如下图所示。

环形队列是对实际编程极为有用的数据结构，它有如下特点：①它是一个首尾相连的FIFO的数据结构，采用数组的线性空间；②数据组织简单，能很快知道队列是否满或空；③能以很快的速度来存取数据。因为简单高效，甚至在硬件上都实现了环形队列。

内存上没有环形的结构，因此环形队列实际上是数组的线性空间来实现。当数据到了尾部，它将转回到0位置来处理，这个转回是通过数组下标索引取模操作(Index%MAXN)来实现的。

设环形队列数据结构定义如下：

入队操作时，如队列不满，则写入如下语句：

q->tail=(q->tail+1)%q->size;

出队操作时，如果队列不空，则从head处读出。下一个可读的位置在如下语句处：

q->head=(q->head+1)%q->size;

树与二叉树

树

树结构是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系。

树是n个结点的有限集合(n≥0),当n=0时称为空树，在任一棵非空树中，有且仅有一个根结点；其余结点可分为m(m≥0)个互不相交的有限子集T1,T2,…,Tm,其中每个Ti又都是一棵树，并且成为根结点的子树。

树的结构如下图所示。

二叉树

二叉树是n个结点的有限集合，它或者是空树，或者是由一个根结点及两棵互不相交的且分别称为左、右子树的二叉树所组成，与树的区别在于每个根结点最多只有两个孩子结点。

三种特殊的二叉树如下图所示。

由上图可知，满二叉树每层都是满的。完全二叉树的k-1层是满的，第k层结点从左到右是满的。

二叉树的存储结构

顺序存储：就是用一组连续的存储单元存储二叉树中的结点，按照从上到下，从左到右的顺序依次存储每个结点。

链式存储：一般用二叉链表来存储二叉树结点，二叉链表中除了该结点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针，即一个数据+两个指针。

二叉树的遍历

一棵非空的二叉树由根结点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整棵二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根结点顺序可变，以根结点访问的顺序为准有三种遍历方式：①先序(前序)遍历：根左右。②中序遍历：左根右。③后序遍历：左右根。

还有层次遍历方法：按层次，从上到下，从左到右。

例：有二叉树如图3-3-8所示，求前序、中序、后序遍历。

解析：前序：12457836;中序：42785136;后序：48752631。

图

图的基本概念

图也是一种非线性结构，图中任意两个结点间都可能有直接关系。相关定义如下：无向图：图的结点之间连接线是没有箭头的，不分方向。

有向图：图的结点之间连接线是箭头，区分A到B和B到A是两条线。

完全图：无向完全图中，结点两两之间都有连线，n个结点的连线数为(n-1)+(n-2)+…+1=n*(n-1)/2;有向完全图中，结点两两之间都有互通的两个箭头，n个结点的连线数为n*(n-1)。

度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。出度是以该顶点为起点的有向边的数目。入度是以该顶点为终点的有向边的数目。

路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。

图的存储

邻接矩阵：假设一个图中有n个结点，则使用n阶矩阵来存储这个图中各结点的关系，规则是若结点i到结点j有连线，则矩阵R₁=1,否则为0,示例如下图所示。

由上图可知，如果是一个无向图，肯定是沿对角线对称的，只需要存储上三角或者下三角就可以了，而有向图则不一定对称。

邻接链表：用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来，而后对此一维数组的每个顶点元素，使用链表挂上和其有连线关系的结点的编号和权值，示例如下图所示。

存储特点：图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，无论是对有向图还是无向图，边数的多少决定了单链表中的结点数，而不影响邻接矩阵的规模，因此采用何种存储方式与有向图、无向图没有区别，要看图的边数和顶点数，完全图适合采用邻接矩阵存储。

图的遍历

深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他结点出发，重复这个过程直至遍历完整个图。

广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

在实际应用中，一般给出邻接表或者邻接矩阵来求遍历，可以先画出图，再求遍历，这样最保险，当然简单的结构也可以利用存储结构特点来求。图的遍历方法如下图所示。

算法的复杂度

算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行这个算法所需要的内存空间。

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数(n),因此，算法的时间复杂度记做：T(n)=O((n))。

算法的时间复杂度是一个执行时间数量级的表示，并不是执行算法程序所需要的时间值，也与算法程序的长度无必然联系，也不能简单地认为就是算法程序中的指令条数，而是算法执行过程中所需要的基本运算次数，与模块n(规模)相关，随着n的增大，算法执行的时间的增长率和f(n)的增长率成正比。

考试中经常涉及上述的时间复杂度，需要注意的是，时间复杂度是一个大概的规模表示，一般以循环次数表示(因为程序运行时间与软硬件环境相关，不能以绝对运行时间衡量),O(n)说明执行时间是n的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度，实际变化必须小于等于O括号内的渐进变化程度。

算法分析方法

递推和递归

算法是为解决某个问题而设计的步骤和方法，有了算法，就可以据此编写程序。常用算法主要有迭代法、穷举搜索法、递推法、递归法、贪婪法、回溯法等。

解决同一个问题，不同的人(甚至是同一个人)可能会写出几种不同的算法，但算法有优劣之分。递推法是利用所解问题本身所具有的递推关系来求得问题解的一种算法。递推法与递归法的关系是，任何可以用递推法解决的问题，可以很方便地用递归法写出程序解决。反之，许多用递归法解决的问题不能用递推法解决。这是因为递归法利用递归时的压栈，可以有任意长度和顺序的前效相关性，这是递推法所不具备的。

C语言支持递归，即一个函数可以调用其自身。但在使用递归时，程序员需要注意定义一个从函数退出的条件，否则会进入死循环。

例：数的阶乘递归实现代码：

分治法

概念：对于一个规模为n的问题，若该问题可以容易地解决则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。

步骤：①分解(将原问题分解成一系列子问题);②求解(递归地求解各子问题，若子问题足够小，则直接求解);③合并(将子问题的解合并成原问题的解)。

凡是涉及分组解决的都是分治法。在分治法中，因为是分解为若干个相同的问题，因此会使用到递归技术：在函数运行过程中调用自己。

在二分查找法、归并排序等算法里，将待排序序列分解为一个个小序列先排序，后再不断扩大范围合并，就是分治法的原理(将问题规模缩小)。

回溯法

概念：有“通用的解题法”之称，可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点触发搜索解空间树。搜索至任一结点时，总是先判断该结点是否肯定不包含问题的解，如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。

可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。回溯法一般用于解决迷宫类的问题。

贪心法

概念：它所做的每一步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

局部贪心，只针对当前的步骤取最优，而非整体考虑。判断此类算法，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。

动态规划法

概念：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

动态规划法本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间不是相互独立的，并且不全都相同，常用于求解具有某种最优性质的问题。此算法会将大量精力放在前期构造表格上面，其会对每一步列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，是通过查询这张表来得到的。动态规划法不但每一步最优，全局也最优。