数据结构的起源

（1）数据结构前身是1968年美国的高德纳教授所写的《计算机程序设计艺术》。C语言是于1972年才产生的，而《计算机程序设计艺术》这本书是1968年就有了，所以语言不重要，主要是它的数据存储的思想。不过，我这个专栏是以C语言进行简单讲解数据结构的知识。

（2）数据结构主要是研究数据的逻辑结构和存储结构及其操作。

基本概念和术语

这部分有一个简单了解即可，之后对数据结构有了一定理解之后可以回来再看。

数据

数据：是描述客观实物的符号，计算机信息的载体。能够输入到计算机，并且被计算机识别、存储和处理的符号总称。

数据包括整型、实型等数值类型，还包括声音、图像、视频等非数值类型。首先，对于数值类型而言，比如50是一个数值，但对于计算机而言，就是字符‘5’和‘0’。所以整型是属于数据。

而声音、图像、视频等也可以以符号的形式呈现，比如声音有音符，我们可以利用数字1代表某一个音符，数字2代表另外一个音符。最后将这些数字输入到计算机，能够被计算机处理。所以声音也是数据。

数据元素

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

举个例子，人类是数据，可以用“people”这一串字符代替。而人，比如张三，李四就是属于数据元素。

数据项

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

人类是数据，人是数据元素，而每一个人都有眼睛，耳朵，鼻子，性别，年龄等数据项。虽然数据项是数据的最小单位，但是我们一般是以数据元素进行分析。

数据对象

数据对象：性质相同的数据元素的集合，数据的子集。因为一般处理的数据元素具有相同性质，所以一般都将数据对象简称为数据。

数据结构

（1）结构：不同的数据元素之间不是独立的，而是有特定的关系。

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

比如人类是数据，张三，李四，王五是数据元素。张三是李四的丈夫，王五是张三的弟弟这种夫妻关系，兄弟关系我们称之为结构。张三，李四，王五他们之间被称之为家人，所以他们三个可以被称之为数据结构。

逻辑结构与存储结构（物理结构）

逻辑结构

（1）逻辑结构：逻辑结构是指数据对象中的数据元素之间的相互关系。这个是我们需要重点关注的问题。

（2）逻辑结构分为集合结构，线性结构，树形结构，图形结构四种。

集合结构

集合结构：集合结构中的数据元素处理同属于一个集合外，没有任何其他关系。基本上不考虑这种情况。

线性结构

（1）线性结构：线性结构中的数据元素之间是一对一的关系。

（2）例如我们在超市里面，购买完东西之后，排队结账，这种一个跟着一个的队列，就是属于线性结构。

数形结构

（1）树形结构：树形结构中的数据元素之间是存在一对多的层次关系。

（2）例如如下的公司关系图，一个老板，老板下面有多个总裁，总裁下面再细分。是呈现一个对多个的关系。

图形结构

（1）图形结构：图形结构的数据元素是多对多的关系。

（2）例如甄嬛传里面，各位娘娘之间的勾心斗角，娘娘A与娘娘B，C是朋友与娘娘D是敌人。娘娘B与娘娘C是敌人，而娘娘C与D又是朋友。各位娘娘各种秀操作，最后干掉对方。这种错综复杂的多对对的结构就是图形结构。

存储结构（物理结构）

（1）存储结构：数据的逻辑结构在计算机中的存储形式，或者说具体实现方法。也称为物理结构。

（2）存储结构是通过计算机语言所编写的程序来实现的，因而是依赖于具体的计算机语言。

（3）存储结构也有四种，顺序存储，链式存储，索引存储，散列存储。不过大话数据结构里面说只有顺序存储和链式存储两种，我猜可能是后两种使用的比较少。

顺序存储

（1）顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据之间的逻辑关系和物理关系是一致的。

（2）例如C语言的数组。数组的数据都是连续的，这就是物理关系。a1后面必然是a2，当我们知道了a0的地址，那么数组的任意元素地址也知道了，他们是连续的，这就是逻辑关系。

链式存储结构（重点）

（1）链式存储结构：将数据结构中的各元素分布到存储器的不同点，用地址（或链指针）方式建立他们之间的联系。这些元素的存储单元可以是连续的，也可以是不连续的。

（2）这有什么好处呢？比如，在医院排队叫号，有1-100个号码牌。如果是按照顺序存储的方式，先到的人拿到前面的号码牌，1号看完之后来2号，2号看完之后来3号。突然，来了一个重症老年患者，需要插队，所有人往后顺延一个位置。突然，有人不愿意了，又不是我家人，重症了管我我什么事情，我得病了不是病吗？先来后到不懂吗？

按照顺序存储的方式，插队位置后面所有人进行安抚，向后顺延一个位置比较麻烦。这个时候我们是不是可以对这个结构进行调整，变成链式存储结构。

依旧是还有1-100个号码牌。只不过这一次不是按照顺序发放号码牌，比如甲先到了，但是发45号，乙后到，发34号，丙发88号。然后护士那一个记事本，记住显示45号，再34号，再88号。按照这个顺序排队，如果突然来了一个重症老人，我可以直接将45号后面变成老人，老人后面是34号。虽然需要一个护士进行做记录有点麻烦，但相比需要将后面的所有人进行顺延，安抚相比简单很多事情。

（3）虽然有好处，但是还是有缺点的。第一，需要多一个护士进行记录，对空间上增加了损耗。第二，不透明。如果是顺序存储，我一眼就可以知道前面有多少人在排队。但是如果是链式存储，我不知道前面有多少个。如果我要找到我的位置，就需要看一下记事本，从第一个人从后面依次寻找，直到找到我自己。第三，数据元素数量未知。如果护士突然想直到，今天一共来了多少个人看诊，就需要从第一个一个一个的数，一直数到最后一个号码牌。