数据结构学习笔记（一）first day

石油大学数据结构30讲

抽象数据类型 ADT

数据模型 + 一组操作（数据结构 + 一组操作）

数据结构包含两个内容 D + S

数据类型的实现

一个问题抽象成一个抽象数据类型后，仅仅是形式上的抽象定义，并没有达到解决问题的目的，要实现这个目标，就要把抽象的编程具体的，也就算在计算机上实现，变为一个具体的数据类型

一个数据类型的实现一般分为三个阶段：

1.ADT阶段，又被称为定义阶段 （建模，建造数学模型）

2.虚拟数据类型阶段，又称为表示阶段

3.物理数据类型阶段，又称为物理实现阶段

物理数据类型阶段是和硬件有关，和计算机打交道，这个并不用研究，我们只需要明白 1 和2阶段就好，使用高效语言（类c语言）来表示出来

例如：

抽象的抽象数据类型：用整数来表示

虚拟的虚拟数据类型：用c语言整数来表示

物理的物理数据类型：用机器整数表示

具有一种或者多种关系的数据元素的集合

数据结构、抽象数据类型、数据类型、存储结构的关系

算法的基础知识

一、算法的定义及特性

解决问题的一种方法，即它给出了求解问题的步骤描述

1、算法的特性或要素 ：5个

• 有穷性
• 确定性
• 可行性
• 输入量
• 输出量

有穷性

是有限的算法，也就是这个算法必须能结束，不能一直无限循环

确定性

必须要确定，不能有二义性的

可行性

在计算机上可以运行，如果是错误的算法或不能在计算机上运行，那么可用价值就是0了

输入量

像算法中输入的内容，可以有0个，也可以有多个

输出量

至少要一个输出，因为算法是要解决一个问题，要是没有输出，我们就不清楚它是否解决了这个问题

2.算法与数据类型的关系

算法对应的是操作，而数据结构对应的是存储的结与数据的逻辑结构构

算法是用来计算的方法，是关于问题在求解的过程中方法的描述

3.算法与程序的区别

算法是不严谨的，程序是严谨的，算法 + 数据结构 = 程序

不严谨只是对于程序来讲的，根据算法的5个要素，其实算法是严谨的，但是它不用苛刻于语言的要求，而程序必须要严格的按照编程语言的格式来写

二、算法的描述

1. 自然语言描述：容易，就是啰嗦，有二义性，就是我们在聊天时说的话
2. 图示：用流程图之类的来实现，思路清晰，第八下机（不容易实现）
3. 算法语言（类c语言，伪代码）：严谨简洁易于程序实现，通常使用英语
4. 程序设计语言：可以直接运行，但是太严格了