程序员的进阶-深入了解数据结构数据结构与算法qq43629857的博客-

什么是数据结构？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

基本概念和术语

✍ 数据（Data）

数据是对客观事物的 符号 表示。

在计算机科学中是指所有能 输入 到计算机中并 能被计算机程序处理 的符号的总称。

✍ 数据元素（Data Element）

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也被称为记录。

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

✍ 数据对象（Data Object）

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

把一个班的学生看作一种数据对象，每个学生就是数据元素，学生的姓名，性别等就作为该数据元素的数据项。

学生表

课程表

学生表、课程表，这两张表就是 数据。

而单独的一张表就称为数据对象，即学生表是一个 数据对象，课程表也是一个 数据对象。

而每张表中的每一行就称为 数据元素。

而学号，姓名，性别，课程编号，课程名就称为 数据项。

✍ 数据结构（Data Structure）

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

数据是一个抽象的概念。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。

数据结构可以分为两种：逻辑结构 和 物理（存储）结构。

1.逻辑结构

是指数据对象中数据元素之间的相互关系。

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

• 线性结构
  数据元素之间为 1:1 的关系。

• 树形结构
  数据元素之间为 1:N 的关系。

• 图形结构
  数据元素之间为 M:N 的关系。

因此对于逻辑结构，我们通过 是否为线性 可将其分为 线性结构 和 非线性结构。

线性结构： 通常有且仅有一个开始和一个终端结点，并且所有的结点都最多只有一个前驱和一个后继，结点之间是一对一的关系。典型代表：线性表、栈、队列、串。

非线性结构： 一个结点可能有多个直接前驱和直接后继，结点之间是一对多，或者多对多的关系。典型代表：树、图。

2.物理（存储）结构

是指数据的逻辑结构在计算机中的存储形式。

• 顺序存储结构
  把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  数组就是以这种方式进行存储的。
• 链式存储结构
  把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
  数据间的物理关系并不能反映其逻辑关系，因此在链式存储结构中，有一个指针存放数据元素的地址
  这样就 可以通过指针找到相关联的数据元素位置。

✍ 数据类型和抽象数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型，如：int num, float price, char c等。

数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的统称。

抽象数据类型(Abstract Data Type，简称 ADT) 是指一个数学模型以及定义在该模型上的一组操作的统称。

即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型的形式定义:

抽象数据类型可用三元组(D、S、P)表示，其中：

• D代表数据对象
• S代表D上的关系集
• P代表对D的基本操作集

抽象数据类型具体实现：

C语言举例

#include "stdio.h" typedef struct rect{ int x; // 矩形的横坐标 int y; // 矩形的纵坐标 float width; // 矩形的宽 float height; // 矩形的高 }rect; // 初始化矩形 void init_rect(rect &r, int x, int y, int w, int h); double area(rect &r); // 计算矩形的面积 double perimeter(rect &r); // 计算矩形的周长 

性质、概念类的知识点也许非常枯燥，但也是我们非常容易忽略的知识点。可以磨炼一下自己的耐心。