数据结构-第一章-《绪论》

1.数据结构研究的内容：

? ? ? ? ? 首先我们要知道：

程序 = 算法 + 数据结构 

其中，我们的数据结构研究的内容为：

? ? ? ? 数据结构主要研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。

了解了如上知识，我们就可以开始由数据的基本概念入手，来学习数据结构。

2.基本概念以及术语：

? ? ? ? ?1.数据：所有能输入到计算机中去描述的客观事物的符号。

? ? ? ? 什么意思呢，大概可以理解为：你在电脑上看到的图形，多媒体，数字，字母，都可以理解为是数据结构中的“数据”，数据主要分为两类：

? ? ? ? 数值性数据，和非数值型数据（多媒体信息处理）

? ? ? ? 2.数据元素：数据的基本单位，也可以称为结点，或记录。

? ? ? ??

我们可以看如上图片所示，每一条数据，都是一个数据元素，例如一本书的介绍，主要有书名，作者，出版单位，出版时间和价格来组成，其中这些数据项组成了一个数据元素。

? ? ? ? 3.数据项：有独立含义的最小单位，也称为域。

? ? ? ? 我们继续看上表，其中001，002，003，004，这些数据，每一个独立的个体称为一个数据域，也可以理解为，组成一条数据元素的每一项的基本内容。

? ? ? ? 其中，三者之间的关系为：数据>数据元素>数据项

? ? ? ?例：学生表>个人纪录>学号，姓名.........

? ? ? ? 4.数据对象：具有相同性质的数据元素的集合，是数据的一个子集。

? ? ? ? 例如：整型数据对象： arr = {0，1，2，3，4....}

? ? ? ? 学生数据对象，学生记录的集合

? ? ? ? 5.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

? ? ? ? 注：数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

数据结构的两个层次：

? ? ? ? 逻辑结构： 数据元素抽象化的相互关系，与数据的存储无关，独立与计算机，它是从具体问题抽象出来的数学模型。

? ? ? ? 简单来说，逻辑结构就是数据元素之间有着怎样的逻辑关系。

? ? ? ? 存储结构（物理结构）：指数据元素及其关系在计算机中存储器中的存储方式。

? ? ? ? 简单来说，就是数据元素在内存中是怎样进行存放和使用的，研究的是内存存储方面。

逻辑结构的划分方法：

? ? ? ? 划分方法一：

? ? ? ? ? ? ? ? 1.线性结构

? ? ? ? ? ? ? ? ? ? ? ?线性结构有且仅有一个开始借点（头节点）和一个终端节点（尾节点），并且所有节点都最多只有一个直接前驱和一个直接后继。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 例如：线性表、栈、队列、串，最典型的就是我们C语言中的数组。

? ? ? ? ? ? ? ? 2.非线性结构：一个节点可能有多个直接前驱和多个直接后继。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 例如：树，图。

? ? ? ? 划分方法二：

? ? ? ? ? ? ? ? ? ? ? ? 1.集合：数据元素之间除了“同属于一个集合之外”没有其他的关系。

如图所示。

? ? ? ? ? ? ? ? ? ? ? ? 2.线性结构：一个对一个，如线性表、栈、队列。

如图所示。

? ? ? ? ? ? ? ? ? ? ? ? 3.树形结构：一个对多个，如树。

如图所示。

? ? ? ? ? ? ? ? ? ? ? ? 4.图形结构：多个对多个，如图。

如图所示。

存储结构（物理结构）分为：

? ? ? ? 1.顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。
? ? ? ? ? ? ? ? 如我们的数组，就是一个活生生的例子，它就是用顺序存储结构来实现的。

? ? ? ? 其中，顺序存储结构是开辟一个连续的地址，来存放我们的数据，所以我们只要找到首地址，就可以知道任意数据元素的地址。

? ? ? ? 其中根据数学归纳法可以表示为如下:

????????

Loc(元素i) = Loc + (i-1) * m

? ? ? ? ?我们用首地址加上要找到的元素 i 的位置，用i-1来找到下标，再乘以占用的每个元素的大小，就可以得到元素 i 的地址。

? ? ? ? 2.链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。

? ? ? ? ? ? ? ? 如我们的指针数组，就可以理解为是一个链式存储结构。

从链式存储结构，我们可以看出，我们在存储时，需要存储两个部分，一个为数据域，一个为指针域，用来指向下一个元素的位置，如上元素1的指针域指向了元素2，元素2的指针域指向了元素3，元素3的指针域指向了元素4，当元素4后没有元素的时候，它不需要指向，即指针域为空。

? ? ? ? 数据的运算：

? ? ? ? 对于一种数据结构来说，常见的运算有五种：增删改查排。

? ? ? ? 即：插入、删除、修改、查找、排序。

?

其中，数据的逻辑结构是唯一的，数据的存储结构是不唯一的，可以是顺序存储，也可以是链式存储。我们运算的实现主要依赖于存储结构。

? ? ? ? 抽象数据类型：

? ? ? ? 抽象数据类型ADT由基本的数据类型组成，并且包含一组相关的操作。

? ? ? ? 抽象数据类型可以用以下的三元组来表示：

ADT = (D,S,P)

?其中，D表示数据对象，S表示D上的关系集，P表示D上的操作，其中ADT的常用定义格式为：

ADT抽象数据类型名
{
    数据对象;<数据对象的定义>
    数据关系;<数据关系的定义>
    基本操作;<基本操作的定义>
}

?D表示数据对象，S表示数据之间的关系，P表示对数据的基本操作。

? 其中，数据元素被约定为ElemType类型。

算法描述为以下的函数形式：

函数类型 函数名(函数参数表)
{
    语句；
}

? ? ? ? 算法与算法分析：

? ? ? ? 算法的特性主要有以下五点：

1.输入        有0个或多个输入
2.输出        有1个或多个输出
3.确定性      每一步都是确切、无歧义的
4.有穷性      算法应在执行有穷的步数后结束
5.有效性      每一条运算应该足够基本

? ? ?算法的评价：

????????

正确性
可读性
健壮性
高效性（时间代价和空间代价）

设计的算法必须正确，且易读，还需拥有高的健壮性，也要综合时间大小和空间大小来审视设计出的算法的好坏。

---

如上则是数据结构绪论的知识点，感谢大家的观看，后续会继续更新C语言，数据结构相关的知识，希望大家点个关注，谢谢大家。