小蝠猫学算法#2——算法概念

文章寄语

无聊的并不是时间，而是平庸无奇的我。
　　　　　　　　　　　　　　　　　　　　—— <<樱花庄的宠物女孩>>

---

引言

数据结构笔记第二篇。数据结构和算法的概念[考纲无此内容]

知识点大致按照《Hello!算法》书籍进行。因为数据结构与算法在非常多的考试中都有。

本人自知学疏才浅，一定有许多错误，恳请批评指正。

下面是几个上述提到的链接：

《Hello!算法》网页版 全国计二级官网 洛谷官网-刷题可用

星空如此灿烂，灯塔与之响应。出发吧

---

第二节 数据结构和算法的概念

数据结构的基本概念

数据结构是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法。[书上的话]

以下三者属于包含关系，关系图为数据 > 数据元素 > 数据项。数据项是最小单位。

用例子即拼装积木。一套积木，除了包含许多零件之外，还附有详细的组装说明书。我们按照说明书一步步操作，就能组装出积木模型。

Ⅰ.数据

数据是信息的载体。是计算机加工的原料，由二进制0和1组成。相当于上述的一整套积木。

Ⅱ.数据元素

数据元素是数据的基本单位，但不是最小单位。它通常是一个整体。相当于上述的未拼装积木。

Ⅲ.数据项

数据项是构成数据元素的最小单位。若干数据项组成了数据元素。相当于上述的单块积木。

Ⅳ.数据对象

数据对象是具有相同性质的数据元素的集合，为数据子集。相当于上述的同类型积木。

Ⅴ.数据类型

与程序中的数据类型不同，这里讲的是总体而不是特定的。所谓“类型”，就是相似的数据所拥有的共同特征。

书上有以下三种类型：

• 原子类型：不可以再分的数据类型。比如程序语言的内置类型整型浮点型等。
• 结构类型：可以再分的数据类型，可以由多种数据类型组成。比如自定义类型中的结构体等。
• 抽象数据类型：复杂数据类型，包含一种操作或结构形式。比如数据结构中的栈，队列，树，图等。

Ⅵ.数据结构

数据和数据之间有紧密关系，不是孤立存在的结构。有逻辑结构，存储结构和数据运算。

相当于上述的积木组织形式，包括形状、大小、连接方式等。

数据结构三要素[逻辑,存储,运算]

逻辑结构

逻辑结构揭示了数据元素之间的逻辑关系。

数据之间的逻辑关系，有线性和非线性结构。其实线性不线性的，看数据之间是不是像链条一样的一条线，是就线性，不是就非线性。

所以参照上述所说：链表，数组，栈，队列等都是线性的。其他如树，图就为非线性。非线性还可以再分：

• 集合：里面的最小单元为游离状态，仅在同一个框中罢了。
• 线性：最小单元之间仅为一对一，即逻辑关系上呈线性排列。
• 树形：最小单元之间为一对多，仅根节点和父节点可包含多个子节点。子节点和子节点之间没有关联，即使同父。
• 图或网形：最小单元之间为多对多，每一个节点均可包含多个其他节点。没有任何限制。

注意：

• 哈希表是一种特殊的数据结构，它既可以包含线性结构，又可以包含非线性结构。因为解决哈希冲突的时候，可能会使用链式地址。过长还可以转化为树。

存储结构

数据存放在内存中的位置，也为物理结构。有以下几个：

• 顺序存储：例子为数组，数组相邻的两个数存放在内存里也是相邻的。即在内存中连续存放。优点占用少；已知首元素的地址，可推算其中任意元素的内存地址。缺点使用一大块内存；碎片率高。
• 链式存储：例子为链表，不用连续存放，可以在随机的地址中存放但以指针链接，就和扣子一样。优点碎片率低。缺点因为每个链表节点都包含数值和指针两部分，占用略高；只能用遍历的方法寻找某元素。
• 索引存储：例子为字典，以”键值对”形式存放。索引，就像书的目录一样，可以快速的导航查找内容。优点是寻找元素速度快。缺点是既然是目录，当然也要几页纸，所以占用额外空间。
• 散列存储：例子为散列表，也就是哈希表。其可以用键或值直接计算出其中任意某元素的内存地址来寻找此元素，很牛皮。优点是增删查的速度都非常快。缺点是可能会出现哈希冲突，解决冲突很麻烦

关于碎片率

所谓碎片率和大小块内存，就好比有一个已经装了一点东西的抽屉：
数组大块内存像一本很大的相册，我可能勉强能塞进去。但是旁边留下的许多空隙我就不能放大东西了，我只能放一些小东西。这些空隙呢，就是碎片。
碎片率高就是空隙多，碎片率低就是空隙少。链表因为不用大块，可以在随机位置放置，所以可以”见缝插针”,放到那些空隙里，充分利用所有存储单元。
那磁盘和内存的碎片整理就类似于整理一个装满东西的抽屉。碎片就像抽屉里的空隙，碎片整理的过程就是将这些空隙尽量减少，使得空间更加紧凑，从而能够存放更多的东西。

数据运算

包括定义和实现。定义针对逻辑，指出其功能。实现针对存储，指出其操作步骤。

算法的基本概念

算法是在有限时间内解决特定问题的一组指令或操作步骤。

相当于上述的把积木拼成目标形态的一系列操作步骤。

算法的重要特性

算法的重要特性有5个，具体如下：**[大前提是特定问题必须是明确的]**

• 有穷性：算法必须在有限时间，有限步数和有限空间内完成。
• 确定性：写的每一句话都必须有实际含义。相同输入应始终返回相同的输出。
• 可行性：写的每一句话都应该可行，并可以执行该语句。
• 输入：可以没有输入(void),或者正常的一个输入，或者是多个输入。
• 输出：虽然可以没有输入，但是必须有个输出。以证明这个程序是在正常运行而不是在摸鱼的。

评价优秀算法的”得分点”

优秀算法应该拥有以下目标：

• 正确性：对于每一组输入或是函数内部处理，都能返回与预期相符合的值。即正确求解问题。
• 可读性：字面意思。可以让自己和别人理解这段代码干了什么，拥有简洁的数据表示和逻辑信息。有良好可读性。
• 健壮性：可以抵御外来病毒(一些非法数据)的侵扰，做出正确的反应来保护程序。而不是输出乱码口吐白沫。
• 高效率低储存：这是我们解决问题的核心。对于一个代码，我们总是想用时和占用空间越小越好，即高效运行。但有时候通常事与愿违。我偏向空间换时间，但是特定问题中，时间换空间也可。

数据结构和算法之间的关系

书上的话,例图如下:

• 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
• 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
• 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

数据结构与算法的关系

---

书后习题笔记

数据结构概念

选择题笔记

①数据结构包含三要素，逻辑结构，存储结构，运算。分离的基本单位算不上有三个。只有抽象数据类型里面有这三个。

②逻辑仅仅是一种关系，他不和别的有关系。但是存储他要知道是怎么放的，放在哪里，所以要逻辑告诉他。

③哈希表，单链表里面说明了存储方式是散列/链式，顺序表就是数组，里面也说明了是顺序存储。只有有序表只有”有序”，其他没有。

应用题笔记

①链表和数组，逻辑一样存储不一样。二叉树和数组/链表，逻辑不一样存储一样。

②还是数组和链表，相同逻辑不同存储。现在我在其中间部位添加或删除元素[同种运算]。数组因为是连续存储，添加时需要将某位置后的所有元素全部往后或往前推一位，以腾出/占据空间。

如果数据量大，这个操作就非常的麻烦。但是链表不是连续存储，它可以在任意部位存储。这就导致我想删除或者添加元素时，我只要把”链”断开再重新连接就好了，效率明显不同。

算法概念和时间空间复杂度

选择题笔记

①算法是在有限时间内解决特定问题的一组指令或操作步骤。剩下的只是特性罢了。

②只要是判断时间复杂度，只要抓大头即可。 如果写在循环体里，可以直接按部乘。如果写在循环条件中，反向计算。

判断技巧:

• ①第一步找出基本运算，一般为循环体返回前的最后一句话。
• ②设这个基本运算的执行次数为t。当这个循环执行t次时，将基本运算等式的右边改写为关于执行次数t的表达式。
• ③将这个表达式带回到循环条件里，得到一个t和n的不等式。
• ④解不等式，得到一个t的表达式。
• ⑤抓大头，得出结果。

递归程序中，仅考虑递归式的内部式，其他不用看。

注意：

• 如果基本运算中的操作，在循环条件中没有出现，直接无视循环条件中的操作！只关注主体语句的循环次数即可

---

总结

文章结语

我一直都在你身边 ，一直都在。
　　　　　　　　　　　　　　　　　　　　——CLANNAD

---

笔记完毕 编辑完毕时间CST 7.12 23:43

最后修改于8.15 23:07