吴导有言
数据结构是一种特殊的组织和存储数据的方式，让我们能更方便地对存储的数据进行操作。数据结构在计算机科学和软件工程范畴有丰富多彩的应用。每个程序或软件系统都使用数据结构。此外，数据结构是计算机科学和软件工程的基础。当参加软件工程面试时，数据结构问题非常重要。所以，我们必须非常熟悉数据结构。
1.数组数组是大小的结构，存储的项目数据类型必须相同。项目类型可以包括整数数组，浮点数数组，字符串数组或者是数组数组（例如二维数组）。数组有索引，能够随机访问。
Fig1.VisualizationofbasicTerminologyofArrays
数组运算·遍历：遍历所有元素并打印。
·插入：将一个或多个元素插入数组。
·删除：删除数组元素
·搜索：搜索数组中元素。依照元素的值或索引搜索元素
·更新：在特定索引处更新现有元素
数组的应用·是其他数据结构的基础，例如数组列表，堆，哈希表，向量和矩阵。
·用于不同的排序算法，例如插入排序，快速排序，冒泡排序和合并排序。
2.链表链表是顺序结构，链接的线性顺序项目序列组成了它。必须顺序访问链表，不允许随机访问。链接列表是动态集的灵活的表示方法。
思考以下链表相关的名词。通过参考图2，我们会有一个清晰的认识。
·链表中的元素称为节点。
·每个节点都有钥匙和一个指向其后继节点（称为next）的指针。
·head指向链接列表的第一个元素。
·链表的最后一个元素称为尾。
Fig2.VisualizationofbasicTerminologyofLinkedLists
以下是可用的各种类型的链表。
·单链列表—仅仅允许正向遍历。
·双链表-在前进和后退方向上遍历。节点由上一个的附加指针组成，指向上一个节点。
·循环链接列表—链接列表，其中头的上一个指针指向尾部，尾号的下一个指针指向头。
链表操作·搜索：借助线性搜索在链表中找到键为k的第一个元素，并返回指向该元素的指针
·插入：在链接列表中插入一个密钥。插入的方法有三种；在列表的头插入，在列表的尾插入，或者在列表的中部插入。
·删除：从链表中删除元素x。不允许删除节点。删除的方法有三种：从列表的开头删除，从列表的末尾删除，然后从列表的中间删除。
链表的应用·设计编译器中的管理符号表。
·在使用AltTab（使用循环链表实现）的程序之间进行切换。
3.堆栈堆栈是LIFO（后进先出）结构，在编程中该结构很常见。该结构定义为"堆栈"，因为它像现实世界的堆栈-板的堆栈。
ImageSource:pixabay
堆栈操作下图给出在堆栈上执行的2个基本操作。参考图3，方便我们理解堆栈操作。
·Push推送：在堆栈顶部插入一个元素。
·Pop弹出：删除最上面的元素并返回。
Fig3.VisualizationofbasicOperationsofStacks
此外，堆栈的附加功能可以检查状态。
·Peep窥视：返回堆栈的顶部元素但不删除它。
·isEmpty：了解堆栈是否为空。
·isFull：了解堆栈是否已满。
堆栈的应用·表达式评估（例如：解析和评估数学表达式的调车场算法）。
·在递归编程中完成函数调用。
4.队列队列是FIFO（先进先出）结构，该结构。该结构被称为"队列"，因为它像队列-人们在排队。
ImageSource:pixabay
队列操作下图是在队列的2个基本操作。参考图4，方便我们理解。
·进队：元素插入队列的末尾。
·出队：从队列的开头删除元素。
Fig4.VisualizationofBasicOperationsofQueues
队列的应用·管理多线程。
·用于排队系统（例如：优先级队列）。
5.哈希表哈希表是数据结构，可以存储与键相关联的键值。此外，与值关联的键，支持查找。因此，插入和搜索无论数据大小都可以实现。
当存储在表中时，直接寻址用值和键之间映射。但是，当有键值对时，也有问题。该表记录很多，非常庞大。为避免此问题，使用哈希表。
哈希函数
名为哈希函数（h）的特殊函数用于解决直接寻址中的问题。
在直接访问中，密钥k的值存储在插槽k中。使用哈希函数，计算出每个值都指向的表（插槽）的索引。给定键的哈希函数计算的值称为哈希值，它表示该值映射到的表的索引。
·h：哈希函数
·k：应确定其哈希值的键
·m：哈希表的大小（可用插槽数）。
Fig5.RepresentationofaHashFunction
·1→1→1
·5→5→5
·23→23→3
·63→63→3
从两个示例中，当哈希函数为多个键创建一样的索引时，会出现问题。能够选择恰当的哈希函数h并使用链接和开放式寻址等方法来解决问题。
哈希表的应用·数据库索引。
·关联数组。
·"设置"数据结构。
6.树树是层次结构，数据按层次组织并链接。此结构与链接列表相差很大，而在链接列表中，顺序链接。
在过去的一段时间中，已经有丰富多样的树木，以适合某些应用。一些例子是二叉搜索树，B树，红黑树，展开树，AVL树和n元树。
二叉搜索树毋庸置疑，二进制搜索树（BST）是二进制树，数据以分层结构组织。数据结构按排序顺序存储值。
二叉搜索树中的每个节点都有一些属性。
·key：存储在节点中的值。
·left：指向左孩子的指针。
·右：指向右孩子的指针。
·p：指向父节点的指针。
二叉搜索树的属性，与其他树区分开。属性称为binary-search-tree属性。
令x为二叉搜索树中的一个节点。
·若y是x左子树中的一个节点，则y.key≤x.key
·若y是x的右子树中的节点，则y.key≥x.key
Fig6.VisualizationofBasicTerminologyofTrees.
树的应用·二叉树：表达式解析器。
·二进制搜索树：不断输入和输出数据的搜索应用程序中。
·堆：由JVM存储Java对象。
·Trap：无线网络。
7.堆堆是二叉树的一种，将父节点与其子节点的值比较，排列。
堆使用树和数组表示。图7和图8使用二叉树和数组来表示二叉堆。
Fig7.BinaryTreeRepresentationofaHeap
Fig8.ArrayRepresentationofaHeap
堆有2种类型。
·最小堆-父项的密钥小于或等于子项的密钥。称为min-heap属性。根有堆的最小值。
·最大堆数-父项的密钥大于或等于子项的密钥。称为max-heap属性。根有堆的最大值。
堆的应用·实现优先级队列，堆属性对优先级值排序。
·在O（logn）时间内用堆来完成队列功能。
·查找数组中k个最小（或最大）的值。
·堆排序。
8.图图由有限的顶点或节点连接顶点的边组成。
图的顺序是图中的顶点数。图的大小是图中的边数。
两个节点同一边彼此连接，则称它们为相邻节点。
有向图若图形G的每个边都具有方向，则称该图形为有向图。
定义（u，v）从顶点u入射或离开顶点u，然后入射到或进入顶点v。
自环：从顶点到本身的边。
无向图如果图G的所有边无方向，则为无向图。在两个顶点之间以两种方式连接。
如果顶点未图中的其他节点连接，则顶点为孤立的。
Fig9.VisualizationofTerminologyofGraphs
图的应用·表示社交媒体网络。顶点代表用户，连接时会创建一条边。
·表示搜索引擎的网页和链接。互联网上的网页因为超链接相互链接。每页是一个顶点，两页之间的超链接是一条边。
·表示GPS中的位置和路线。位置是顶点，连接位置的路线是边。可以计算两个之间的最短路径。
预览时标签不可点收录于话题#个上一篇下一篇