数据机构的概念

标签：存储机构元素概念数据结构数据节点结构

数据结构的组成由来

数据

定义：数据对客观事物的符号表示

作用：数据是计算机处理的基本对象

数据元素

定义：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。例如，在一个学生信息管理系统中，一个学生的所有信息（包括学号、姓名、年龄、成绩等）构成一个数据元素。

与数据的关系：数据是由一个或多个数据元素组成的集合。数据元素是数据的个体

数据项

定义：数据项是构成数据元素的不可分割的最小单位。例如，在学生信息这个数据元素中，学号、姓名、年龄、成绩等每一个部分都是一个数据项。数据项具有独立的含义，是描述数据元素某一特征的基本单元。

与数据元素的关系：一个数据元素可以包含多个数据项。数据项的组合完整地描述了数据元素的各种属性。

数据结构

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

目的：数据结构的主要目的是有效地组织和存储数据，以便于对数据进行访问、插入、删除、修改等操作。合理的数据结构可以提高程序的运行效率，减少存储空间的占用。

数据结构的组成

数据元素

数据元素是数据结构的基本组成单位。它们可以是简单的数据类型，如整数、字符等，也可以是复杂的对象，如包含多个属性的结构体。

数据元素之间存在着特定的逻辑关系，这些关系是数据结构的核心部分

逻辑结构

逻辑结构描述了数据元素之间的相互关系，它是数据结构的抽象层面，与数据的存储方式无关。主要分为线性结构和非线性结构。

线性结构

- 像线性表（如顺序表、链表）、栈、队列等都属于线性结构。以线性表为例，它的逻辑结构特点是数据元素依次排列，存在一对一的顺序关系。例如，在一个文本文件的存储结构中，字符按照先后顺序组成线性结构，这种顺序可以方便地进行文本的读取和编辑操作。
- 线性结构的操作通常包括插入、删除、查找等。例如，在链表这种线性结构中，插入一个新的数据元素时，需要找到合适的位置，通过修改指针来建立新元素与原有元素之间的逻辑关系。

层次结构

- 层次结构是一种数据元素之间存在分层关系的数据结构。它将数据元素组织成多个层次，每个层次中的元素与上下层次的元素具有特定的关联方式。就像是一个金字塔形状的组织形式，从顶部到底部形成一种递阶关系。

层次结构的组成部分

节点

节点是层次结构中的基本单元，代表了一个数据元素。不同的节点在层次结构中扮演不同的角色，具有不同的属性和功能。

节点可以分为内部节点和叶节点。内部节点是指除了最底层（叶层）之外的节点，它们通常有子节点。叶节点是位于最底层的节点，没有子节点。

边（关系）

边用于连接相邻层次的节点，表示它们之间的关系。在树形层次结构中，边通常表示父子关系，即一个父节点通过边与它的子节点相连。

这种关系是有向的，从父节点指向子节点，体现了层次结构中的控制或者包含的方向。

网状结构

定义：网状结构是一种数据元素之间存在复杂的多对多关系的数据结构。在这种结构中，每个数据元素（节点）可以与多个其他数据元素相连，没有像树形结构那样严格的层次和父子关系限制。

特点：节点之间的连接关系复杂多样，不存在单一的根节点或固定的层次顺序。

网状结构的的组成部分跟层次结构组成部分一样的

存储结构

存储结构决定了数据元素在计算机存储器中的存储方式，主要包括顺序存储和链式存储。

顺序存储

顺序存储是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，每个元素占用空间小

不过，顺序存储也有缺点。当需要插入或删除一个元素时，可能需要移动大量的其他元素来保持顺序关系。

链式存储

链式存储中，数据元素的存储单元可以是不连续的。每个数据元素（节点）包含数据域和指针域（或引用域），指针域用于存储下一个（或多个）数据元素的存储地址，通过指针来建立数据元素之间的逻辑关系。

链式存储的优点是插入和删除操作相对灵活，只需要修改指针即可，不需要移动大量元素。

索引存储结构

定义：

- - 索引存储结构是一种在计算机数据存储中常用的数据结构。它是在存储数据记录的同时，另外建立一个索引表。索引表中的每一项称为索引项，索引项一般形式是（关键字，地址）。关键字是能唯一标识一个数据记录的某个数据项的值，地址是指该数据记录在主存储空间中的存储位置。

优点：

提高查询效率：当需要查找特定关键字对应的记录时，首先在索引表中查找关键字。

支持多种查询方式：除了精确查找（如查找特定学号的学生记录），还可以支持范围查询。

缺点：

增加存储开销：因为除了存储数据记录本身，还需要存储索引表。

数据更新维护成本高：当数据记录发生插入、删除或修改操作时，不仅要更新数据记录本身，还要更新索引表。

散列存储结构