跳到主要内容

数据结构简介

1. 基本概念​

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

2. 什么是数据​

数据是描述客观实物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

  • 数据元素

数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

  • 数据项

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

  • 数据对象

数据对象是性质相同的数据元素的集合，是数据的子集。性质相同是指数据元素具有相同数量和类型的数据项。

3. 数据结构​

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

数据结构分为逻辑结构和物理结构。

3.1 逻辑结构​

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

  • 集合结构：集合结构中的数据元素除了“同属一个集合外”，它们之间没有其他关系。

Zh1KDt.png

  • 线性结构：线性结构的数据元素之间是一对一关系。

Zh16aC.png

  • 树形结构：树形结构中的数据元素存在一种一对多的关系。

Zh18HQ.png

  • 图形结构：图形结构中的数据元素多对多的关系。

Zh1gCu.png

3.2 物理结构​

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

  • 顺序存储结构（顺序表）

数据元素存放在地址连续是存储单元里，其数据间的逻辑关系和物理关系是一致的。

Zh1k4v.png

  • 链式存储结构（链表）

把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

Zh1r0E.png

4. 常见的数据结构​

  • **栈（Stack）：**栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
  • **队列（Queue）：**队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
  • **数组（Array）：**数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
  • **链表（Linked List）：**链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
  • **树（Tree）：**树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。
  • **图（Graph）：**图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
  • **堆（Heap）：**堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
  • **散列表（Hash table）：**散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

5. 常用算法​

程序设计 = 数据结构 + 算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。

算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

  • **检索：**检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
  • **插入：**往数据结构中增加新的节点。
  • **删除：**把指定的结点从数据结构中去掉。
  • **更新：**改变指定节点的一个或多个字段的值。
  • **排序：**把节点按某种指定的顺序重新排列。例如递增或递减。
0%