数据结构的基本概念

1.什么是数据结构？

数据元素：是数据（集合）的一个个体，它是数据的基本单位。

数据项：用来描述数据元素，数据的最小单位。

数据对象：具有相同性质的若干个数据元素的集合，如整数数据对象是所有整数的集合。

eg.下表就是学生为数据对象，数据项包括学号、姓名，班级，性别，班号。而数据元素就是数据对象的基本单位，即每一个学生

的数据。比如“1号张斌，性别男，班号9901”，这就是一个数据元素。

数据对象：学生；

数据项：学号，姓名，性别，班号；

数据元素：一个学生的所有数据项下的所有数据的集合。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。（集合中的数据元素可按照数据项分类，数据元素的集合有构成了数据对象）。

数据结构=数据对象+数据元素结构

数据结构的构成：逻辑结构（面向程序员的数据之间的结构）、存储结构（面像机器存储的实际物理结构）、数据运算（施加在该数据的运算）。

2.数据结构的基本构成

2.1逻辑结构

主要类型：线性结构、树型结构、图型结构。

1.线性结构：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前趋元素和一个后继元素。

2.树型结构

3.图型结构：所有元素都可能有多个前趋元素和多个后继元素

数据的逻辑表示：二元组表示

例如，如下数据为一个矩阵：

对应的二元组表示为B=(D，R) ，其中：

D={2,6,3,1,8,12,7,4,5,10,9,11}

R={r1，r2}

其中，r1 表示行关系，，r2表示列关系

r1={<2,6>，<6,3>，<3,1>，<8,12>，<12,7>，<7,4>，<5,10>, <10,9>，<9,11>}

r2={<2,8>，<8,5>，<6,12>，<12,10>，<3,7>，<7,9>, <1,4>， <4,11>}

2.2存储结构（物理结构）

主要类型：顺序存储结构、链式存储结构、索引存储结构、哈希（散列)存储结构。

1.顺序存储结构（结构体）：所有元素占用一整块内存空间，逻辑上相邻的元素、物理上也相邻。

2.链式存储结构（链表）：一个逻辑元素用一个节点存储，每个节点单独分配，所有节点的地址不一定是连续的。用指针来表示

逻辑关系。

此外还有索引存储结构、哈希（散列)存储结构。

2.3数据运算

数据运算是对数据的操作，分为：运算描述和运算实现。

3.数据类型和抽象数据类型

1.数据类型，是一个值的集合和定义在此集合上的一组操作的总称。

数据类型就是已经实现类的数据结构。

2.抽象数据类型=逻辑结构+抽象运算

抽象数据类型（（ADT））指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑

计算机的具体实现。

4.算法概述

4.1 什么是算法

数据元素之间的关系有逻辑关系和物理关系，对应的运算有基于逻辑结构的运算描述和基于存储结构的运算实现。

通常把基于存储结构的运算实现的步骤或过程称为算法。

算法的特性：有穷性、确定性、可行性、有输入、有输出。

4.2 算法分析

4.2.1 算法时间复杂度分析

一个算法是由控制结构( 顺序、分支和循环三种）和原操作（指固有数据类型的操作，如如+、-、 * 、/ 、++和和 -- 等）构

成的。算法执行时间取决于两者的综合效果。

分析算法的执行时间：

求出算法所有原操作的执行次数（也称为频度），它是问题规模n的函数，用T(n) 表示。
算法执行时间大致=原操作所需的时间（分析过程中可简化为次数）×T(n) 。所以T(n)与算法的执行时间成正比。为此用T(n) 表示算法的执行时间。
比较不同算法的T(n) 大小得出算法执行时间的好坏。

算法中执行时间T(n) 是问题规模n 的某个函数f(n)，记作：

T(n) = O(f(n))

记“O”读作 “大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同，即f(n)与T(n)同阶。

一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。

一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。

其余常用的算法时间复杂度还有平方阶O( $n^{2}$ )、立方阶O( $n^{3}$ )、 n^{3} 对数阶O()、指数阶O( ) 等。

4.2.2 算法空间复杂度分析

空间复杂度：用于量度一个算法在运行过程中临时占用的存储空间大小。一般也作为问题规模n的函数，采用数量级形式描述，

记作：

S(n) = O(g(n))

若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。

eg.下列函数的空间复杂度为多少？

答：O(1)。算法中分配的变量i、j、k、s等与问题规模n无关，所以空间复杂度为O(1)。