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

文章寄语

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

---

引言

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

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

本人基础较弱，可能会有许多错误，恳请批评指正。

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

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

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

---

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

数据结构的基本概念

数据结构是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法.

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

Ⅰ.数据

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

Ⅱ.数据元素

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

Ⅲ.数据项

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

Ⅳ.数据对象

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

Ⅴ.数据类型

与程序中的数据类型不同，这里是相似的数据所拥有的共同特征。

有以下三种类型：

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

Ⅵ.数据结构

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

相当于积木之间形状、大小、和连接方式等。

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

逻辑结构

数据之间的逻辑关系，有线性和非线性。其实线性不线性的，可以看数据之间是不是一条线，是就线性，不是就非线性。

所以：链表，数组，栈，队列等都是线性的。如树，图就为非线性。

非线性还可以再分：

• 集合：游离，仅在同一个框中罢了。
• 线性：仅为一对一，逻辑关系上呈线性排列。
• 树形：一对多，仅限根节点和父节点上可包含多个子节点。子节点和子节点之间没有关联。
• 图/网形：多对多，每一节点均可包含多个其他节点。

不过哈希表例外，它是一种特殊的数据结构，既可以包含线性结构，又可以包含非线性结构。

存储结构

即数据存放在内存中的位置：

• 顺序存储：如数组，相邻的两个数在内存里也是相邻的。即连续存放。优点占用少；已知首元素地址，可推算任意元素的地址。缺点使用大块内存；碎片率高。
• 链式存储：如链表，不需连续存放，可在随机地址中存放但以指针链接。优点碎片率低。缺点因节点均包含数值 + 指针，占用高；寻找节点只能遍历。
• 索引存储：如字典，以”键值对”存放。就像书的目录一样，可快速查找内容。优点寻找快。缺点占用额外空间比较多。
• 散列存储：如散列表，即哈希表。可用键或值直接计算出任意某元素的地址来寻找元素。优点增删查的速度非常快。缺点会出现哈希冲突。

关于碎片率

所谓碎片率和大小块内存，就好比一个已经装了一点东西的抽屉：
大块内存像一本大相册，勉强能塞进去。但是旁边会留下很多空隙，这些空隙只能放一些小东西了。这些空隙呢，就是碎片。
碎片率高就是空隙多，碎片率低就是空隙少。平时的碎片整理就是在整理一个装满东西的抽屉。
碎片整理的过程就是将这些空隙尽量减少，使得空间更加紧凑，从而能够存放更多的东西。

数据运算

包括定义和实现。定义是逻辑，主要是功能。实现是存储，主要是步骤。

算法的基本概念

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

相当于把积木拼成完整的，一系列操作步骤。

算法的重要特性

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

• 有穷性：算法必须在有限时间，有限步数和有限空间内完成。
• 确定性：写的每一句话都必须有实际含义。相同输入应始终返回相同的输出。
• 可行性：写的每一句话都应该可以执行。
• 输入：可以没有输入,或者一个输入，或者多个输入。
• 输出：必须有个输出。不能没有输出。

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

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

• 正确性：对于每一组输入/函数内部，返回都与预期相符合。
• 可读性：即有可读性。能让自己和别人理解这段代码干了什么，拥有简洁的数据表示和逻辑信息。
• 健壮性：可以抵御错误输入，或者是非法输入。程序有错误处理机制。
• 高效率低储存：解决问题的核心。我们总想让用时和空间越小越好。但通常事与愿违。偏向空间换时间，在特定问题中，时间换空间也可以。

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

例图如下:

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

数据结构与算法的关系

---

书后习题笔记

数据结构概念

选择题笔记

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

②逻辑仅仅是一种关系，和别的没关系。但是存储如果要知道是怎么放的，放在哪里的话，要逻辑告诉他。

③哈希表，单链表里面说明了存储方式是散列/链式。顺序表是顺序存储。只有有序表只有”有序”。

应用题笔记

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

②数组和链表，相同逻辑不同存储。现在我在两者中间均添加或删除元素[同种运算]。

数组连续存储，添加时需要将某位置后的所有元素全部往后或往前推一位，以腾出/占据空间。

数据量大时，这个操作非常的麻烦。但链表不为连续存储，其可在任意部位存储。只要把”链”断开再重新连接就好了，效率明显不同。

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

选择题笔记

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

②判断时间复杂度，只需抓大头。但是在复杂的情况下还是不太清楚。

结语

文章结语

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

---

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

最后修改于9.27 19:00