数据结构（一）—— 数据结构简介

一、基本概念和术语？

1.1、数据

数据是描述客观事物的符号，是计算机可以操作的对象，是能被计算机识别，并输入到计算机处理的符号集合。

（数据不仅仅包括整型、实型等数值型，还有字符、声音、图像、视频等非数值类型）

1.2、数据元素

数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也称为记录（元组、结点、顶点）。

1.3、数据项（属性、字段）

• 一个数据元素可以由若干个数据项组成。
• 数据项是数据不可分割的最小单位。

1.4、数据对象

数据对象是性质相同的数据元素的集合，是数据的子集。

1.5、数据结构

• 在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，这些关系称为结构。
• 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
• 数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

二、逻辑结构和物理结构（存储结构）

数据结构是相互间存在特定关系的数据的集合，分为逻辑结构和物理结构。

2.1、逻辑结构

1、定义

逻辑结构是指数据对象中数据元素之间相互关系（逻辑关系），即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机存储器的。

2、分类（线性结构和非线性结构）

根据数据元素之间关系的不同特征，通常有下列4类基本结构，复杂程度依次递进。

• 集合：结构中的数据元素之间除了同属于一个集合外，没有其他的关系。

• 线性结构：线性结构中的数据元素之间是一对一的关系。

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

• 图状结构或网状结构：结构中的元素之间是多对多的关系。

2、物理结构

1）定义

数据的物理结构是指数据的逻辑结构在计算机中的存储方式。又称存储结构。

它研究的是数据结构在计算机中的实现方法，包括数据元素的表示和元素之间的关系。

数据元素的存储结构形式主要有两种：顺序存储和链式存储

2）顺序存储和链式存储

1. 顺序存储结构

• 是利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑顺序。
• 顺序存储结构是把数据元素放在地址连续的存储单元中，程序设计中使用数组类型来实现。（逻辑相邻物理相邻）

2. 链式存储结构

• 利用结点中指针来表示数据元素之间的关系。
• 把数据元素存储在任意的存储单元里，这组存储单元可以是连续的，也可以是连续的，程序设计中使用指针类型来实现。（逻辑相邻物理不一定相邻）

3）其他存储方式

• 索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。

• 散列存储：通过关键字直接计算出元素的物理地址。

三、算法和抽象数据类型简介

3.1 抽象数据类型定义

1. 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

例如：C语言中数据类型分为基本类型和构造类型

基本类型：整型、浮点型、字符型等

构造类型：数组、结构、联合、指针、枚举型、自定义类型等

2. 抽象数据类型（abstract data type，ADT）：是指一个数学模型及定义在该模型上的一组操作。

3.2 算法定义

算法是特定问题求解步骤的描述，是独立存在的一种解决问题的方法和思想。

1、算法的特性

• 输入：有0个或多个输入
• 输出：至少有1个或多个输出
• 有穷性：算法在有限的步骤后应该自动结束而不会无限循环。
• 确定性：算法中的每个步骤都有确定的含义，不会出现二义性
• 可行性：算法的每一步都是可行的
• 正确性：算法对于合法数据能够得到满足要求的结果，能够处理非法输入，并得到合理的结果。
• 可读性：算法要便于阅读、理解和交流
• 健壮性：算法不应该得到莫名其妙的结果
• 性价比：利用最少的资源得到满足要求的结果

2、算法效率的度量

效率评估是工程中算法最重要的附加特性。

2.1 事后统计法

比较不同算法对同一组输入数据的运行处理时间。

缺点：

A、为了获得不同算法的运行处理时间必须编写相应程序

B、运行处理时间严重依赖硬件以及运行时环境

C、算法的测试数据选取困难

2.2 事前分析统计

依据统计的方法对算法效率进行评估

影响算法效率的主要因素：

A、算法采用的策略和方法

B、问题的输入规模

C、编译器产生的代码

D、计算机的执行速度

算法效率的简单估算：

三种求和算法的关键部分的操作数量分别为2n，n，1。随着问题规模的增大，操作数量的差异会越来越大，效率差异也会越来越大。

不同算法操作数量的对比

算法操作数量对比的实例一：

n<=3时，算法B优于算法A。随着n的规模增大，算法A优势比较明显。

算法操作数量对比的实例二：

n=1时，算法C与算法D效率相同。随着n规模的增大，算法C优势明显优于算法D。

判断算法的效率时，操作数量中的常数项和其他次阶项常常可以忽略，只需要关注最高阶项。

3、算法的复杂度

（1）算法的时间复杂度

算法时间复杂度是算法运行后对时间需求量的定性描述。

由于主要关注算法的效率问题，因此主要讨论算法的时间复杂度。

O表示法

算法的效率严重依赖于操作（Operations）数量，操作数量的估算可以作为时间复杂度的估算，在判断时首先关注操作数量的最高阶项。

O（2）==>O（1）

O（3n+3）> O（3n）>O（n）

O（3n^{2+n+4）==>O（n}2）

常见的时间复杂度：

（2）算法的空间复杂度

算法空间复杂度是算法运行后对空间需求量的定性描述。

通常使用S（n）表示算法的空间复杂度。使用时间复杂度的推导方法推导空间复杂度。

当算法所需的内存空间大小为常数时，算法的空间复杂度为S（1）。

通常情况下，算法的时间复杂度更受关注。可以通过增加额外空间降低时间复杂度。

算法是解决具体问题的步骤，数据结构是算法解决问题的载体。

4、算法实例

一个数组中存储着1——1000的数字，每个数字可能出现多次或者不出现，找出出现次数最多的数字。

void search(int array[], int len)
{//总计可能出现1000种可能值int sp[1000] = {0};int max = 0;for(int i = 0; i < len; i++){//遍历数组，数组中某个数组出现一次增加统计1次sp[array[i] - 1]++;}for(int i = 0; i < 1000; i++){if(max < sp[i]){max = sp[i];}}for(int i = 0; i< 1000; i++){if(max == sp[i]){cout << "Number:" << i + 1 << endl;cout << "Count:" << max << endl;}}
}

使用空间换时间，算法的时间效率为O（n）。