嗨客网搜索
数据结构教程

数据结构来源

1968 年,美国 Donald E. Knuth 教授在《计算机程序设计艺术》第一卷《基本算法》中系统阐述了数据的逻辑结构和存储结构及其操作,开创了数据结构课程体系。

70 年代初,大型程序相继出现,软件也开始相对独立,结构程序设计成为程序设计方法学主要内容,人们开始认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。也就是 “程序设计 = 数据结构 + 算法”。

什么是数据结构

在计算机科学中,数据结构是一种数据组织、管理和存储的格式,它可以帮助我们实现对数据高效的访问和修改。更准确地说,数据结构是数据值的集合,可以体现数据值之间的关系,以及可以对数据进行应用的函数或操作。

通俗点来说,在针对一些非数值计算的问题,我们需要数组,链表,树,图等数据结构来帮助我们解决它们。它是一个集合,里面包含了互相之间存在各种关系的数据元素。

可以说,数据结构 = 数据元素 + 元素之间的关系。

基本专业术语

术语 描述
数据(data) 所有能被计算机接受并处理的被操作对象的集合。
数据项(data item) 是数据中的最小单位;也被称为域(field),代表数据表中的字段。
数据元素(data element) 由若干个数据项组成的数据基本单元,也称结点,元素,顶点或记录。
数据对象(data object) 由性质相同的数据元素组成的集合,是数据的一个子集。举个例子,整数的数据对象{-3, -2, -1, 0, 1, 2, 3}。
数据结构(data structure) 由互相之间存在着一种或多种关系的数据元素组成的集合;这些数据元素之间的关系称为结构。

常见的数据结构

常见的四种基本数据结构包括:

结构 描述 代表结构
集合结构 数据结构中的元素之间除了 “同属一个集合” 的相互关系外,别无其他关系。
线性结构 数据结构中的元素存在一对一的相互关系 数组
树形结构 数据结构中的元素存在一对多的相互关系 二叉树
图状结构 数据结构中的元素存在多对多的相互关系 无向图

分类

数据结构有很多种,一般来说,按照数据的逻辑结构对其进行简单的分类,包括线性结构和非线性结构两类。

线性结构

简单地说,线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述,线性结构应该包括如下几点:

  1. 线性结构是非空集。
  2. 线性结构有且仅有一个开始结点和一个终端结点。
  3. 线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。

线性表就是典型的线性结构,还有栈、队列和串等都属于线性结构。

非线性结构

简单地说,非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述,非线性结构应该包括如下几点:

  1. 非线性结构是非空集。
  2. 非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

在实际应用中,数组、广义表、树结构和图结构等数据结构都属于非线性结构。

研究对象

数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后间关系,而与他们在计算机中的存储位置无关。

数据的物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示(又称映像),它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示(映像方法): 用二进制位(bit)的位串表示数据元素。通常称这种位串为节点(node)。当数据元素有若干个数据项组成时,位串中与各个数据项对应的子位串称为数据域(data field)。因此,节点是数据元素的机内表示(或机内映像)。

关系的机内表示(映像方法):数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像,常用两种存储结构:顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针(pointer)来表示数据元素之间的逻辑关系。

数据存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说,一种数据结构的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。 [4]

数据的顺序存储结构的特点是:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;非顺序存储的特点是:借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

数据结构教程总结

程序设计 = 数据结构 + 算法,同时,数据结构 = 数据元素 + 元素之间的关系。

嗨客网顶部