首先会有个疑问，什么是数据结构呢？
数据结构（data structure），可以概括为是互相之间存在一种或多种特定关系的数据元素的集合。
开篇配图来自网络... 那开始吧 ：）
一、数据结构起源
1968年，美国 Donald E. Knuth 教授在《计算机程序设计艺术》第一卷《基本算法》中系统阐述了数据的逻辑结构和存储结构及其操作，开创了数据结构课程体系。
70年代初，大型程序相继出现，软件也开始相对独立，结构程序设计成为程序设计方法学主要内容，人们开始认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。也就是 程序设计 = 数据结构 + 算法
现实生活中，更多的不是解决一些数值计算问题，我们需要通过表、树、图等数据结构的帮助来更好地处理问题。
所以数据结构也是一门研究非数字计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。（引用自《大话数据结构》）
二、基本概念和术语
1、数据
- 数据指的是能输入到计算机中，并能被计算机程序处理的对象。
- 对于数值类型（整型、实型等），可以进行数值计算；
对于字符数据类型（声音、图像、视频等可通过编码转化为字符数据），可以进行非数值处理。
2、数据元素
- 数据元素指组成数据的、有意义的基本单位，也被称为记录。
- 如：一部电影里面的女主就是数据元素
3、数据项
- 数据项是数据不可分割的最小单位，一个数据元素可以由若干数据项组成。
- 如：一部电影里面女主的姓名、性别等都是数据项，恩，女主性别一般是女...
4、数据对象
- 数据对象指性质相同的数据元素的集合，是数据的子集；
- 数据对象简称数据
什么是性质相同呢？
性质相同指数据元素具有相同数量和类型的数据项；
如一部电影中每个角色（数据元素）都有姓名、性别（数据项），这些角色（数据元素）构成了一部电影，那么这部电影所有人物的集合我们可以想象成是一个数据对象。
5、数据结构
- 数据结构指互相之间存在一种或多种特定关系的数据元素的集合；
- 数据结构 = 数据元素 + 关系；
还得用上面的例子，一部电影可以想象成是一个数据结构，是由一个个人物（数据元素）和一个个串联的人物情节（关系）构成，例子有点勉强，大概意思都应该理解的...
三、逻辑结构和物理结构
1、逻辑结构
- 逻辑结构指数据对象中数据元素之间的相互关系；
-
逻辑结构分为 集合结构、线性结构、树形结构 和 图形结构；
1).集合结构：其中的数据元素除同属于一个集合外，之间没有其他关系；
集合结构
2).线性结构：其中的数据元素之间是一对一的关系；
线性结构
3).树形结构：其中的数据元素之间存在一对多的层次关系；
树形结构
4).图形结构：其中的数据元素之间存在多对多的关系。
图形结构
2、物理结构
-
物理结构指数据的逻辑结构在计算机中的存储形式；
-
实际就是如何将数据元素存储到计算机存储器中。这里的存储器主要针对内存而言，像硬盘等外部存储器的数据组织通常使用文件结构来描述；
-
数据元素的存储结构形式有 顺序存储 和 链式存储 两种；
1).顺序存储结构
顺序存储结构：把数据元素存放在地址连续的的存储单元里，其数据间的逻辑关系和物理关系一致；
顺序存储结构
2).链式存储结构
链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的也可以是不连续的。数据元素的存储关系不反映其逻辑关系，用指针存放数据元素的地址，我们通过地址可以找到相关联数据元素的位置。
链式存储结构
-
两种物理结构对比来看，链式存储更为灵活
逻辑结构面向问题，物理结构面向计算机，其基本目标是将数据及其逻辑关系存储到计算机的内存中。
四、抽象数据类型
1、数据类型是什么？
数据类型指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
看起来有点模糊，接着往下看。
数据类型按照值的不同进行划分。在高级语言中，每个变量、常量、表达式都有各自取值范围。类型就用来说明变量或表达式的取值范围和所进行的操作。
计算机的内存是有限的，如果只是单纯计算 1+1 =2这样的整型数字运算，我们不需要开辟很大的内存空间，只要满足相应需求的内存空间就可以了。于是计算机领域的前辈们对数据进行分类，不同的数据类型拥有各自的取值范围。这样就可以更好利用有限的内存空间。
例如 C 语言中，数据类型可以分两类：
- 原子类型：不可再分割的基本类型。如整型、实型、字符型等基本数据类型；
- 结构类型：由若干类型组成，可再分解。如整型数组就是由若干整型数据组成的。
2、抽象数据类型
1). 上面解释了什么是数据类型，那么为什么要把数据类型抽象出来呢？
不同的计算机有不同的硬件系统，所以需要程序语言最终通过编译器或解释器转化成计算机能够识别的底层语言。然而在我们使用高级语言开发时，如计算 1+1 ，不管最终程序运行在什么计算机上，我们的目的只是为了实现 2 个整型数字的运算，不需要详细知道 CPU 为了实现 1+1 进行了几次开关操作。但无论什么计算机、什么计算机语言都会面临如整数运算这样的操作，那么可以考虑把它们抽象出来，只保留实现目标所必需的信息。
2). 什么是抽象数据类型？
抽象数据类型（Abstract Data Type, ADT）:指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于他的一组逻辑特性，与其在计算机内部如何表示和实现无关。
3). 抽象数据类型有什么意义？
"抽象"的意义在于数据类型的数学抽象特性。一个抽象数据类型定义了一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
理论的东西说起来总是那么模糊，看一个例子就会发现清晰明了了。
还是之前整数计算的例子。计算机分很多种，大型机、小型机、PC、智能手机等等，但是任何一种都有“整型数据”，也都需要进行“整型数据”运算。那么这里的整型其实就是一个抽象数据类型，它在不同计算机内的实现方法可能不同，但定义的数学特性相同，所以在我们看来是相同的。
抽象数据类型理论的东西提的比较多，概括下也就是为什么会有各种不同的数据类型，同时解释这些数据类型存在的意义是什么...
总结
直接上图吧，一图胜千言...
数据结构层次
逻辑结构与物理结构
本文参考：
戳这里 前往我的小屋：I'm Jony ：）
网友评论