「Do.028」数据结构与算法——入门（一）

首发公众号：Android程序员日记
作者：贤榆的榆
如果喜欢，请关注、赞赏、点在看
阅读时间：2155字 5分钟

前言

先说说为什么想要写数据结构与算法这个系列文章，主要出于两方面考虑：

• 第一个是面试的需要，大厂和外企尤大多数都会问到关于算法和数据结构方面的问题，而每次都考背，那其实也很难形成长期记忆，也不能与面试官进一步深入探究。
• 其二就是工作的需要了，作为一个初级的程序员用ArrayList和HashMap可能就几乎可以解决大部分问题了，因为我们的App用户量不算大，业务逻辑不算复杂，所以浪费一点性能和手机资源也不会有太大的问题暴露出来，但是当App变得越来越大，业务逻辑也越来越复杂时，我们就需要去考虑用在某些场景下LinkedList是不是会更好，TreeMap会不会比HashMap的使用成本更低？我知道很多同学会马上说出他们之间两两的区别。但如果不知道其背后的实现原理和逻辑，还真的不太可能会考虑到使用别的去代替一个我们常用的。

数据结构入门

针对自己自学《数据结构导论》这门课程，真的是有一种感触就是——出来混的总是要还的。高中玩过去了，混过去了，现在招聘市场上也会对本科学历有要求，像我这种正在专升本的，其实以后可能也是没什么用了。因为人家可能会写明需要统招本科。那为什么我还想要自考去拿一个计算机的本科学历。可能也是因为像计算机原理、网络原理、数据机构、算法等，这些编程很底层很基础的课程，确实可能会在某个技能爬升的阶段称为我们这些半路出家的程序员的瓶颈。所以说出来混的总是要还的。下面我们先从数据结构的一些基本概念和术语开始吧。

1、数据、数据元素和数据项

• 数据：所有被计算机存储、处理的对象。包括但不限于数值、布尔值、字符串、表格、图像、声音。
• 数据元素：数据的基本单位，同事也是运算的基本单位，在程序中作为一个整体加以考虑和处理。通常具有完整且确定的实际意义。
• 数据项：它是数据的不可分割的最小标识单位。数据元素一般都由数据项组成。在数据库中数据项又称之为字段或者域。

学号	姓名	性别	成绩
1	Jack	男	98
2	Alice	女	99
3	Tony	男	90

这里举个例子比如上面这份表格，它就是可以说是一份数据，而其中的每一个记录如“1、Jack、男、98”就是一个数据元素，而这条数据元素由学号、姓名、性别和成绩这四个具体的数据项组成。我们在计算机中处理时基本都是以一条数据元素为单位进行处理的。这也就很好好理解了，因为单独拎出一个98来运算其实是没什么意义。但是在一些特殊场景下，一个数据元素也可能只由一个数据项组成，此时数据项就是数据元素自身。

2、数据的逻辑结构

数据的逻辑结构就是指数据元素之间的逻辑关系。而逻辑关系是指数据元素之间的关联方式或“邻接关系”。而多条数据元素之间逻辑关系的整体呈现称之为逻辑结构。

线性结构

• 线性结构：元素之间只存在一对一的关系

树形结构

• 树形结构：元素之间存在着一对多的关系

图结构

• 图结构：元素之间存在着多堆多的关系（呈现出来的像是网，所以也的称为网结构。）

集合

• 集合：除了这些元素同属于同一个集合之外，元素之间并没有其他关系

3、数据的存储结构

• 顺序存储：在内存中申请一块地址值连续的内存空间，依次将各个数据元素存储进去，利用了存储节点在内存中的相对位置来表示数据元素之间的逻辑关系。其优点是可以实现随机访问，且每个数据元素占用了最少的空间；但缺点也显而易见，它每次需要一整块的存储单元，容易造成内存的碎片化，无法更加充分的利用内存空间，同时插入和删除操作也需要移动元素。

• 链式存储：不要求在内存中有一块连续的存储空间，它可以通过让元素节点存储地址的指针来表示元素之间的逻辑关系。其优点自然是可以充分利用内存空间，避免了内存的碎片化，增删元素比较灵活（不用一定元素，只需要改变节点的）；缺点是元素因为存储了指针而占用了除存储元素本身以外的更多内存空间，并且它也只能实现顺序访问元素。

• 索引存储：该存储方式是在存储元素的同时还增加了一个索引表，索引表中的每一项由<关键字+地址>的形式进行存储的，关键字是能够标识一个数据元素唯一的数据项，而地址则指示了数据元素存储的地址值或者存储区域的首地址值。其优点是检索速度快，缺点是附加的索引表占用了较多的内存空间，增加和删除数据时也要修改索引表，因此增加了时间的开销。

  注：关于索引存储想更深入的了解的可以查看该链接：《快速理解索引原理》

• 散列存储：通过一个散列（哈希）函数将元素的关键字与存储的地址值建立起一种对应关系。因此每一个数据元素的具体存储位置都可以通过该算法直接计算出来。其优点是检索、增加、删除的速度都很快，缺点是一般都需要比其他结构更多的存储空间，关键字也不能重复，还需要解决hash冲突的问题。

  注：关于散列存储或散列表想了解更多的可以看该连接：哈希表知识点总结

4、数据逻辑结构与存储结构的关系

数据的存储结构其实就是数据逻辑结构在计算机里的实现。不过一种逻辑结构可以采用一种或多种数据的存储结构来表达数据元素之间的逻辑关系。

---

数据结构和算法，其实在一个程序员的生涯中，算是一个很重要的地基吧，想要起高楼，这个地基是无论如何是无法略过的。所以在10月份自考了《数据结构导论》科目之后，就一直想着把这块的东西再总结一下分享出去，下一篇”入门二“会介绍算法和算法分析（及时间和空间复杂度），如果觉得有帮助欢迎关注我或点个在看！

欢迎大家关注我的公众号