第二章：数据结构与算法基础

• 更新

25-05-18 初始记录

基本概念与三要素

数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素、数据项：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构：是相互之间存在一种或多种特定关系d 的数据元素的集合。

三要素：逻辑结构、物理结构（存储结构）、数据的运算

三要素 - 逻辑结构

集合：各个元素同属于一个集合，别无其它关系。

线性结构：数据元素之间时一对一的关系。除了第一个元素，所有的元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。

树形结构：数据元素之间是一对多的关系。

图结构：数据元素之间是多对多的关系。

三要素 - 物理结构

顺序结构：把逻辑上相邻的元素存储在屋里位置上也相邻的存储单元中

联是存储：逻辑上相邻的元素在物理位置上可以不相邻

索引存储：在存储元素信息的同时，还建立附加的索引表

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储

算法

五个特性

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。

确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定的关系的量。

算法效率的度量

时间复杂度：时间开销与问题规模 n 之间的关系

空间复杂度：空间开销（内存开销）与问题规模 n 之间的关系。

递归调用带来的内存开销：S(n) = O(n) 空间复杂度 = 递归调用的深度

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

线性表

存储结构

|- 顺序表
|- 链表 
|-- 单链表
|-- 循环链表
|-- 双向链表

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1	<1
	容量分配	事先确定	动态改变
时间性能	查找运算	O(n/2)	O(n/2)
	读运算	O(1)	O([n + 1]/2)，最好情况为 1，最坏情况为 n
	插入运算	O(n/2)，最好情况为 0，最坏情况为 n	O(1)
	删除运算	([n - 1]/2)，	O(1)

其他

算法问题直接看之前的算法笔记。

内链：[[面试-数据结构和算法]]
外链：面试-数据结构和算法