认识达内从这里开始

随着互联网的不断发展，越来越多的人都在学习Java编程等互联网编程技术，而本文我们就通过案例分析来简单了解一下，数据结构常见类型与特性分享。

1.数组(Arrays)

数组是简单也是常见的数据结构。它们的特点是可以通过索引(位置)轻松访问元素。

它们是做什么用的?

想象一下有一排剧院椅。每把椅子都分配了一个位置(从左到右)，因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院(椅子的行和列)，您将拥有一个二维数组(矩阵)!

特性

元素的值按顺序放置，并通过从0到数组长度的索引访问;

数组是连续的内存块;

它们通常由相同类型的元素组成(这取决于编程语言);

元素的访问和添加速度很快;搜索和删除不是在O(1)中完成的。

2.链表(LinkedLists)

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的?

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性

它们分为三种类型：单独的、双重的和圆形的;

元素不存储在连续的内存块中;

完美的优秀内存管理(使用指针意味着动态内存使用);

插入和删除都很快;访问和搜索元素是在线性时间内完成的。

3.堆栈(Stacks)

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循LIFO(后进先出)规则。因此，添加到堆栈中的后一个元素是您从中删除的一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的?

现实生活中常见的例子是在食堂中将盘子叠放在一起。位于顶部的板先被移除。放置在底部的盘子是在堆栈中保留时间长的盘子。

堆栈有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

您一次只能访问后一个元素(顶部的元素);

一个缺点是，一旦您从顶部弹出元素以访问其他元素，它们的值将从堆栈的内存中丢失;

其他元素的访问是在线性时间内完成的;任何其他操作都在O(1)中。

4.队列(Queues)

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO(先进先出)模型组织的：队列中一个插入的元素是一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的?

这种抽象数据类型(ADT)的佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有高优先级的元素先被引入队列。这个ADT在许多图算法(Dijkstra算法、BFS、Prim算法、霍夫曼编码-更多关于它们的信息)中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque队列(双关语它的发音是“deck”)。可以从队列的两端插入/删除元素。

特性

我们只能直接访问引入的“旧”元素;

搜索元素将从队列的内存中删除所有访问过的元素;

弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。

5.Map和哈希表(HashTable)

Maps(dictionaries)是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

常见的散列函数(在众多散列函数中)是模常数函数。例如，如果常量是6，则键x的值是x%6。

理想情况下，散列函数会将每个键分配给一个的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的?

Maps著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的(其键按字母顺序排列)。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟(24小时=1440分钟)分配一个从0到1439的索引。哈希函数将为h(x)=x.小时*60+x.分钟。

特性

键是的(没有重复);

抗碰撞性：应该很难找到具有相同键的两个不同输入;

原像阻力：给定值H，应该很难找到键x，使得h(x)=H;

二个原像阻力：给定一个键和它的值，应该很难找到另一个具有相同值的键;

因为maps是使用自平衡红黑树实现的(文章后面会解释)，所以所有操作都在O(logn)内完成;所有哈希表操作都是常量。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。