数据结构

一、概要

1、数据结构的基本概念

① 数据：数据是计算机程序加工的原料。
② 数据元素：是数据的基本单位。
③ 数据项：是构成数据元素的最小单位。
④ 数据对象：具有相同性质的数据元素的结合。
⑤ 数据类型：是一个值得集合和定义一组操作的总称。
⑥ 是相互之间存在一种或者多种特定关系的数据元素的集合。

2、数据结构三要素

① 数据的逻辑结构：逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。 它与数据的存储无关，是独立于计算机的。
② 数据的存储结构：存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。 它包括数据元素的表示和关系的表示。
③ 数据的运算：施加在数据上的运算包括运算的定义和实现。

二、算法及评价

1、基本概念

① 算法效率的度量：通过时间复杂度和空间复杂度来描述的。

2、时间复杂度和空间复杂度

② 时间复杂度：某个语句在该算法中被重复执行的次数。
③ 空间复杂度：为该算法所耗费的存储空间。

三、线性表

概念：具有相同数据类型的n个数据元素的有限序列。
L=(a1,a2,a3,...,an);

1.顺序存储
概念:用一组地址连续的存储单元依次存储线性表中的数据元素。

typedef struct{
        int data[];
        int n;
}

2.链式存储(单链表、双链表、循环链表)