零基础学Python之数据结构 -- 01篇

一、数据结构的概念

1.1 数据的具体介绍

• 数据：能够被计算机识别、存储等操作，用于描述客观事物的符号
• 数据分类：                
  • 数值数据：整数、小数、字符串...
  • 非数值数据：视频、音频、图像...
• 数据的组成：数据项 ------->数据元素 --------->数据对象------>数据
• 数据项：数据项是数据的最小单位，具有独立的且不可分割的单位。（比如：学生的学号、分数...）
• 数据元素：由多个数据项组成的用于描述事物特征的基本单位。（比如：一个学生）
• 数据对象：由多个相同特征的数据元素组成的集合，称为数据对象。（比如:一个班级）
• 数据结构课程研究的是数据元素

1.2 结构的具体介绍

1.结构：用于描述数据之间的关联情况，分为逻辑结构和存储结构

2.逻辑结构: 表示数据元素之间的关联情况，根据元素之间的关联情况，可以分为以下4种：

• 集合结构：任意两个元素之间没有任何关系，只是单纯的存储在一个集合中。
• 线性结构：数据元素之间存在一对一的关系，在该结构中，除了第一个元素没有前驱，最后一个元素没有后继，其余的元素都有且只有一个前驱和一个后继
• 树形结构:   数据元素之间存在一对多的关系。（比如：族谱）
• 图形结构:   数据元素之间存在多对对的关系。（比如：社交网络、朋友、暂不重点讨论）

1.3存储结构:数据的逻辑结构在计算机中的映射存储

• 顺序存储：将逻辑上相连的数据，在物理内存上也连续存储。（比如：通信录、微信好友列表）
• 链式存储：将逻辑上相连的数据，存储在物理内存上随机位置。（比如：医院的挂号、银行柜台取票）
• 索引存储：在存储数据元素时，单独创建一个索引表来记录数据元素的位置。（比如：课本的目录）
• 散列存储：也称为哈希存储，数据元素存储的位置和数据元素本身的关键字有关。

数据结构这门课主要研究 数据的存储容器，以及在该容器上的所有操作。如：增、删、改、查

1.4 抽象数据类型（ADT）

抽象数据类型abstract data type ：把数据和对数据的处理捆在一起，进行封装，形成的类型。（类）

二、线性表

概念：由多个相同属性的数据元素组成的线性结构叫线性表。

特点：

• 数据元素的属性相同
• 数据元素之间存在一对一的关系

线性表的分类：

• 顺序表：顺序存储的线性表叫做顺序表
• 链表：链式存储的线性表叫做链表
• 栈：操作受限的线性表，插入和删除操作只能在同一端操作
• 队列：操作受限的线性表，插入和删除操作只能在异端操作