第11章 数据结构与算法.pptVIP

第十一章数据结构与算法 [主要内容] 11.1 算法 11.2 数据结构的基本概念 11.3 线性表 11.4 栈与队列 11.5 树与二叉树 11.6 查找技术 11.7 排序技术 11.1 算法 定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题的方法和步骤。 特征： 有穷性 确定性 有效性 零个或多个输入 一个或多个输出 例如：一元二次方程求根算法。 算法复杂度 评价一个算法优劣的主要标准是： 算法的执行效率与存储需求 算法的效率：指的是时间复杂度（Time Complexity） 存储需求：指的是空间复杂度（Space Complexity ） 一般情况下，算法中的基本操作重复操作执行的次数是问题规模n的某个函数f(n)，算法的时间复杂度记做：T(n)=O(f(n)) 11.2 数据结构的基本概念 数据与数据结构 数据: 是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。 数据元素: 是数据的基本元素，即数据集合中的个体。 数据项: 具有独立意义的最小数据单位。 数据对象: 具有相同特性的数据元素的集合，是数据的子集。 数据结构:互相之间存在着一种或多种关系的数据元素的集合。 数据的逻辑结构 集合 线性结构 树形结构 图状或网状结构 数据的存储结构 一、顺序存储结构 主要特点： 所有元素所占的存储空间是连续的； 各个元素在存储空间中是按逻辑顺序依次存放的； 元素可随机存取，但插入、删除运算不便，会引起大量结点的移动。 二、链式存储结构 主要特点： 存储数据结构的存储空间可以不连续； 各结点的存储顺序与元素之间的逻辑关系可以不一致，元素之间的逻辑关系由指针域来确定； 插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。 数据的运算 检索：在数据结构里查找满足一定条件的结点 插入：往数据结构里增加新的结点 删除：把指定的结点从数据结构里去掉 更新：修改指定结点的一个或多个域的值 排序：保持线性结构的结点序列里结点数不变，将结点按某种指定的顺序重新排列 11.3 线性表 线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列。 （a1，a2，…，an） 顺序表：指用顺序存储结构存储的线性表。 链表：用链式存储结构存储的线性表。 栈和队列：是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表。 顺序表 各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表。 若顺序表中结点个数为n，则： 插入一个结点平均需要移动之结点个数为 n/2，算法的时间复杂度是O(n)； 删除一个结点平均需移动结点个数为 （n-1）/2，算法的时间复杂度是O(n)。 链表 线性链表（单链表）：删除算法的时间复杂度为O(n)，其主要执行时间是有哪些信誉好的足球投注网站删除位置。 循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）。 11.4 栈和队列 栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。 表中无元素即空栈。 栈中有元素a1,a2,…,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则; 栈的物理存储可以用顺序存储结构或链式存储结构; 栈的运算还有取栈顶元素，检查栈是否为空，清除等。 栈的插入和删除 队列 队列：是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。进行删除的一端叫队头，进行插入的一端叫队尾，如下页图所示。 在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则。 队列的物理存储可以用： 顺序存储结构，也可用链式存储结构。 队列的示意图 队列的插入和删除示例 11.5 树与二叉树 树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构。 树（Tree）:是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，…，Tm，每个子集又是一棵树，称作这个根的子树（subtree）。 树形结构的常用术语 结点的度（Degree）：一