1.数据结构概述

1.1什么是数据结构?

几个概念需要记住

  • 数据(data):是对客观事物的符号表示。在计算机科学中是指所有能够输入到计算机并被计算机程序识别和处理的符号的集合。数字、字符,图像、声音等也可通过编码归之于数据。
  • 数据元素(data element):是数据的基本单位。可由若干数据项组成。一个班级的每个学生记录都是班级信息数据的数据元素。每个学生记录可包含姓名、年龄、学号、成绩等数据项。
  • 数据对象(data object):性质相同的数据元素的集合,是数据的一个子集。整数数据,包含了正整数、负整数和零三个数据对象。

 

在任何一个具体的问题中,数据元素之间总是存在着某种关系,这种数据元素之间存在的关系(指逻辑关系)称之为结构(structure),也称作逻辑结构。

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

 

而计算机科学中讨论数据结构,目的是为了在计算机中实现对它的操作,因此得将数据结构在计算机中表示出来。数据结构在计算机中的表示(又称映像)称为数据的物理结构,又称存储结构。

 

总结起来,数据结构 = 数据的逻辑结构 + 物理结构 + 操作 。

 

  • 逻辑结构,指数据元素之间的关系。分为四类:
    • 集合:结构中的数据元素除了同属于一个集合,没有其他任何关系。在中国,有许多的人你不认识她,她也不认识你,大家除了都是中国人这个关系,没有其他任何关系。
    • 线性结构:结构中的数据元素之间存在一对一的关系。排队买火车票时,除了第一个人,每一个队伍中的人紧挨着前面一个人;除了最后一个人,每个人后面紧跟着一个人。
    • 树形结构:结构中的数据元素之间存在一对多的关系。家族族谱中,一对父母可能生有多个儿女。
    • 图状结构或网状结构:结构中的数据元素之间存在多对多的关系。小红的朋友圈,小红有许多朋友,她的几个朋友相互之间也是朋友。

 

  • 存储结构:包括数据元素的表示和关系的表示。分为四类:
    • 顺序存储:逻辑上相邻的元素存储在物理位置上也相邻的存储单元内,元素之间的关系由存储单元的邻接关系来体现。
    • 链式存储:不要求逻辑上相邻的元素在物理位置上也相邻,通过指针指示元素之间的关系。
    • 索引存储。
    • 散列存储。

 

  • 操作,也叫运算。包括运算的定义和实现。运算的定义针对逻辑结构,指出运算实现什么样的功能;运算的实现针对存储结构,指出运算的具体步骤。

 

顺序存储的优点:可随即存取数据元素,每个元素占用最少的存储空间。缺点:只能用一整块相邻的存储单元,可能产生较多的外部碎片。

链式存储的优点:不会出现碎片现象,充分利用所有存储单元。缺点:每个元素因存储指针而占用额外的存储空间,并且只能顺序存取。

 

1.2有哪些常用数据结构?

  • 数组
  • 链表
  • 队列
  • 二叉树(二叉链表)
  • 散列表