数据结构（C语言版） 第1章 绪论

事先声明，本博客的大部分内容都来自《数据结构》（C语言版）—严蔚敏

数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。

数据结构(data structure)又称逻辑结构，是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。

存储结构（物理结构）是数据结构在计算机中的表示（又称映像）。

数据类型(data type)是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型(AbstractData Type)是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

1.常用的数据结构类型：集合、线性、树形、图状。

2.数据结构：

  • 逻辑结构：数据元素之间的关系
  • 存储结构：数据结构在计算机中的表示。存储结构分为：顺序存储结构和链式存储结构。

3.算法是对特定问题求解步骤的一种描述，算法具有如下特性：有穷性、确定性、可行性、输入、输出。

4.算法的度量：

  • 时间复杂度
  • 空间复杂度

–>算法分析的两个主要方面

时间复杂度，O(1), O(n), O(logn), O(nlogn) 的区别+样例分析

衡量一个算法是否优秀，则主要从以下几点考虑：正确性，可读性，健壮性，时间复杂度，空间复杂度

1.抽象数据类型与计算机内部表示和实现无关。√

抽象数据类型 (Abstract Data Type) 是指一个数学模型以及定义在该模型上的一组操作。它的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

2.数据的逻辑结构分两大类: 1、 线性结构。 2、非线性结构。

数据的存储方法有四种: 1、顺序存储方法 。 2、 链接存储方法 。 3、 索引存储方法。 4、散列存储方法 。

3.数据结构的逻辑结构独立于其存储结构

4.数据结构在计算机内存中的表示是指

数据的存储结构

5.数据结构是计算机存储、组织数据的方式，数据对象以及存在于该对象的实例（值）和组成实例的数据元素之间的各种关系。
逻辑上：

物理上：数据元素的映像相当于值，关系有顺序存储和链式存储。

6.链式存储的存储结构所占存储空间:
分两部分,一部分存节点值,另一部分存表示节点间关系的指针

7.算法的时间复杂度取决于问题的规模和待处理数据的初态