数据结构概述

一、概述

二、数组       

         数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据。

        数组是用于存储多个相同类型数据的集合。通常用Array表示，也称之为线性表。

数组的特点：

（1）数组是相同数据类型的元素的集合（int的数组不能存float，float也不能存double）

（2） 数组中各元素的存储是有先后顺序的，它们在内存中按照这个顺序连续存放到一起。内存地址（连续存储）

（3）数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如a[0]表示名字为a的数组中的第一个元素。a[1]表示名字为a的数组中的第二个元素，以此类推。

重要特性：随机访问

        数组是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了这个重要的特性：随机访问。

        优势：查找效率高（随机访问的应用）

        缺点：删除、插入（效率相对低，因为要根据插入和删除的位置决定；效率低的原因：为了保证连续性，需要做大量的数据搬移工作）

三、链表

        链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

        简单来说，「链表」 是实现线性表链式存储结构的基础。

 

        如上图所示，链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个「链节点」。为了将所有的节点串起来，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针 nextnext」。

        在链表中，数据元素之间的逻辑关系是通过指针来间接反映的。逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。

我们先来简单介绍一下链表结构的优缺点：

• 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。

• 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

四、栈

        栈（Stack）：是一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线性表。

        我们把栈中允许插入和删除的一端称为 「栈顶（top）」；另一端则称为 「栈底（bottom）」。当表中没有任何数据元素时，称之为 「空栈」。

     堆栈有两种基本操作：「插入操作」 和 「删除操作」。

• 栈的插入操作又称为「入栈」或者「进栈」。
• 栈的删除操作又称为「出栈」或者「退栈」。

        

        简单来说，栈是一种 「后进先出（Last In First Out）」 的线性表，简称为 「LIFO 结构」。

我们可以从两个方面来解释一下栈的定义：

• 第一个方面是 「线性表」。

栈首先是一个线性表，栈中元素具有前驱后继的线性关系。栈中元素按照 a1,a2,...,ana1​,a2​,...,an​ 的次序依次进栈。栈顶元素为 anan​。

• 第二个方面是 「后进先出原则」。

        根据堆栈的定义，每次删除的总是堆栈中当前的栈顶元素，即最后进入堆栈的元素。而在进栈时，最先进入堆栈的元素一定在栈底，最后进入堆栈的元素一定在栈顶。也就是说，元素进入堆栈或者退出退栈是按照「后进先出（Last In First Out）」的原则进行的。

五、队列

        队列（Queue）：一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。

        我们把队列中允许插入的一端称为 「队尾（rear）」；把允许删除的另一端称为 「队头（front）」。当表中没有任何数据元素时，称之为 「空队」。

队列有两种基本操作：「插入操作」 和 「删除操作」。

• 队列的插入操作又称为「入队」。
• 队列的删除操作又称为「出队」。

队列结构

简单来说，队列是一种 「先进先出（First In First Out）」 的线性表，简称为 「FIFO 结构」。

我们可以从两个方面来解释一下队列的定义：

• 第一个方面是 「线性表」。

队列首先是一个线性表，队列中元素具有前驱后继的线性关系。队列中元素按照 a1,a2,...,ana1​,a2​,...,an​ 的次序依次入队。队头元素为 a1a1​，队尾元素为 anan​。

• 第二个方面是 「先进先出原则」。

        根据队列的定义，最先进入队列的元素在队头，最后进入队列的元素在队尾。每次从队列中删除的总是队头元素，即最先进入队列的元素。也就是说，元素进入队列或者退出队列是按照「先进先出（First In First Out）」的原则进行的。

六、树

        树（Tree）：由 n≥0n≥0 个节点与节点之间的关系组成的有限集合。当 n=0n=0 时称为空树，当 n>0n>0 时称为非空树。

        之所以把这种数据结构称为「树」是因为这种数据结构看起来就像是一棵倒挂的树，也就是说数据结构中的「树」是根朝上，而叶朝下的。如下图所示。

 

「树」具有以下的特点：

• 有且仅有一个节点没有前驱节点，该节点被称为树的 「根节点（Root）」 。
• 除了根节点以之，每个节点有且仅有一个直接前驱节点。
• 包括根节点在内，每个节点可以有多个后继节点。
• 当 n>1n>1 时，除了根节点之外的其他节点，可分为 m(m>0)m(m>0) 个互不相交的有限集合 T1,T2,...,TmT1​,T2​,...,Tm​，其中每一个集合本身又是一棵树，并且被称为根的 「子树（SubTree）」。

        如下图所示，红色节点 AA 是根节点，除了根节点之外，还有 33 棵互不相交的子树 T1(B,E,H,I,G)T1​(B,E,H,I,G)、T2(C)T2​(C)、T3(D,F,G,K)T3​(D,F,G,K)。

七、堆

        堆(Heap)：是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值。
• 堆总是一棵完全二叉树。

        堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。

        若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2)，堆这种数据结构也可以提高入队和出队的效率。

	入队	出队
普通数组	O(1)	O(n)
顺序数组	O(n)	O(1)
堆	O(logn)	O(log)

结构图示

        二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆，如下图所示：

我们可以使用数组存储二叉堆，右边的标号是数组的索引。

假设当前元素的索引位置为 i，可以得到规律：

parent(i) = i/2（取整）

left child(i) = 2*i

right child(i) = 2*i +1

八、哈希表

        哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。

        哈希表通过「键 keykey」和「映射函数 Hash(key)Hash(key)」计算出对应的「值 valuevalue」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

        哈希表的关键思想是使用哈希函数，将键 keykey 映射到对应表的某个区块中。我们可以将算法思想分为两个部分：

• 向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
• 在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。

哈希表的原理示例图如下所示：

 

        在上图例子中，我们使用 value=Hash(key)=key//1000value=Hash(key)=key//1000 作为哈希函数。 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。

• 向哈希表中插入一个关键码值：通过哈希函数解析关键字，并将对应值存放到该区块中。
  • 比如：01380138 通过哈希函数 Hash(key)=0138//1000=0Hash(key)=0138//1000=0，得出应将 01380138 分配到 00 所在的区块中。
• 在哈希表中搜索一个关键码值：通过哈希函数解析关键字，并在特定的区块搜索该关键字对应的值。
  • 比如：查找 23212321，通过哈希函数，得出 23212321 应该在 22 所对应的区块中。然后我们从 22 对应的区块中继续搜索，并在 22 对应的区块中成功找到了 23212321。
  • 比如：查找 32143214，通过哈希函数，得出 32143214 应该在 33 所对应的区块中。然后我们从 33 对应的区块中继续搜索，但并没有找到对应值，则说明 32143214 不在哈希表中。

        哈希表在生活中的应用也很广泛，其中一个常见例子就是「查字典」。

        比如为了查找 「赞」 这个字的具体意思，我们在字典中根据这个字的拼音索引 zan，查找到对应的页码为 599599。然后我们就可以翻到字典的第 599599 页查看 「赞」 字相关的解释了。

在这个例子中：

• 存放所有拼音和对应地址的表可以看做是 「哈希表」。
• 「赞」 字的拼音索引 zan 可以看做是哈希表中的 「关键字 keykey」。
• 根据拼音索引 zanzan 来确定字对应页码的过程可以看做是哈希表中的 「哈希函数 Hash(key)Hash(key)」。
• 查找到的对应页码 599599 可以看做是哈希表中的 「哈希地址 valuevalue」。

九、图

        图（Graph）：由顶点的非空有限集合 VV （由 n>0n>0 个顶点组成）与边的集合 EE（顶点之间的关系）构成的结构。其形式化定义为 G=(V,E)G=(V,E)。

• 顶点（Vertex）：图中的数据元素通常称为顶点，在下面的示意图中我们使用圆圈来表示顶点。
• 边（Edge）：图中两个数据元素之间的关联关系通常称为边，在下面的示意图中我们使用连接两个顶点之间的线段来表示边。边的形式化定义为：e=〈u,v〉e=〈u,v〉，表示从 uu 到 vv 的一条边，其中 uu 称为起始点，vv 称为终止点。

 

• 子图（Sub Graph）：对于图 G=(V,E)G=(V,E) 与 G′=(V′,E′)G′=(V′,E′)，如果存在 V′⊆VV′⊆V，E′⊆EE′⊆E，则称图 G′G′ 是图 GG 的一个子图。在下面的示意图中我们给出了一个图 GG 及其一个子图 G′G′。特别的，根据定义，GG 也是其自身的子图。