大话数据结构11-查找1
搜索是互联网时代非常重要的一个技术。作者举了搜索引擎的例子,正是通过搜索引擎,使得人们能够更好的利用存储在互联网上的海量的数据。为了更好的抽象搜索的概念,我们引入以下几个定义:
搜索是互联网时代非常重要的一个技术。作者举了搜索引擎的例子,正是通过搜索引擎,使得人们能够更好的利用存储在互联网上的海量的数据。为了更好的抽象搜索的概念,我们引入以下几个定义:
上节中,我们介绍了图的基本概念以及他的基本操作:存储、遍历方法。这一节,我们更加深入的探讨一些图的相关的实际应用,包括:最小生成树,最短路径 和 有向无环图 的拓扑排序和关键路径问题。每一个应用下,都介绍了几种算法,在这一过程中,我们可以更加深入的了解图的结构及它的相关操作。
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的,通常表示为 $G(V,E)$, 其中,$G$ 表示一个图,$V$ 是图 $G$ 中顶点的集合,$E$ 是图 $G$ 中边的集合。
队列在我们生活中也很常见,例如客服人员接听电话,会将打电话的人按顺序进行排队,时间上最先打入的最早接听。抽象一下,我们定义数据结构:
队列(queue) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
栈(stack)是一种后进先出的数据结构,实际上,这种结构运用非常普遍,例如浏览网页时,我们使用”后退”按键,word,PS 等软件的撤销操作,都是栈的应用。
除了使用线性存储结构外,还可以使用链式结构存储线性表。链表的思想就是不再固定元素的位置,而是让每个元素知道它的上一个元素和下一个元素分别在哪里,也就是每个元素不仅存储数据信息,还存储地址信息。我们把存储数据元素信息的域称为 数据域,存储指针元素的域称为 指针域,指针域中存储的信息称为 指针 或者 链,数据域与指针域结合,称为 结点(Node)。
线性表是一种元素的有限序列。它的数据对象集合为 ${a_1,a_2,…,a_n}$, 每个元素的类型都相同。其中,除第一个元素$a_1$ 外,每个元素都有且只有一个直接前驱元素,除了最后一个元素 $a_n$ 外,每个元素都有且只有一个直接后继元素。