数据结构绪论

1.数据与数据结构的概念

---

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

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

​

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

​ 比如，在人类中，什么是数据元素？当然是人啦。

​ 数据项：一个数据元素可以由若干个数据项组成。

​ 其实就是对数据元素所具有属性的描述，比如人这样的数据元素，可以有眼睛、耳朵、鼻子、嘴巴和手脚这些数据项，还可以有姓名、年龄、性别、家庭地址、联系电话和邮政编码等数据项。

​ 数据项是数据不可分割的最小单位。但是真正讨论问题的时候，是讨论数据元素，而不是讨论数据项。

​ 数据对象：是性质相同的数据元素的集合，是数据的子集。

​ 什么叫性质相同呢？是指数据元素具有相同数量和类型的数据项，就比如人，中国人和外国人都是人，都有诸如姓名、性别、年龄等数据项。

数据结构

​ 结构，简单来说就是关系，严格点说就是指各个组成部分相互搭配和排列的方式。在现实生活中，不同数据元素之间不是独立的，而是存在特定的关系，我们就将这些关系称为结构。

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

​ 也可以这么说：数据结构是计算机中数据的存储和组织形式。

---

​

2.逻辑结构与物理结构

---

2.1逻辑结构

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

2.1.1集合结构

​ 集合结构中的数据元素除了同属于一个集合外，并没有其他关系。

2.1.2线性结构

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

2.1.3树形结构

​ 树形结构中的数据元素之间催在一种一对多的层次关系。

2.1.4图形结构

​ 图形结构的数据元素是多对多的关系。

2.2物理结构（存储结构）

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

2.2.1顺序存储结构

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

​ 最简单的例子就是数组，比如你要建立一个带有九个整形数据的数组时，计算机就在内存中找了块空闲内存按照一个整型所占的大小乘以9，开辟出一段连续的空间，然后第一个数据放在第一位，第二个放在第二位…这样一次排放。

2.2.2链式存储结构

​ 如果结构涉及到了变化，顺序存储结构就很不方便了，比如去掉数组中某个元素，通常是要移动数组中的元素的，要是数组很大的话就会很麻烦。这是因为逻辑关系和物理关系相统一，逻辑关系一发生变动，物理关系也要变动，那要是逻辑关系和物理关系并不一致是不是改变逻辑关系时就不用改变物理关系了呢？不，还是要改变的，只是更容易改变物理关系了。

​ 链式存储结构：是把数据元素存放在任意的内存单元里，这组存储单元可以是连续的，也可以是不连续的。

​ 此时，数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样一来通过地址就可以找到相关数据元素的位置。

​ 显然，链式存储就灵活多了，数据存在哪压根不重要，只要有一个指针存放了相应的地址就能找到它了。

---

3.数据类型

​ 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。。

3.1数据类型定义

​ 数据类型是按照值的不同来划分的，类型就是用来说明变量或表达式的取值范围和能进行的操作。

​ 为什么以前的人会考虑到数据结构呢？

​ 举个生活中的例子先：大家都需要房子住对吧，那根据贫富情况每个人住的房子各有不同，像是商品房、公寓、别墅等等，房子里面的结构设计以及面积大小也有很多种类，为什么会有这么多房屋类型呢？就是为了满足不同人群的需求。

​ 同样的道理，在计算机中，内存也不是无限大的，你要计算一个如1+2=3之类的整型数字的四则运算，显然也不需要开辟很大的空间来进行，而要是你要计算很大数字的复杂运算，开辟之前整型数字的空间也显然不够用，也就是说，要对数据进行分类，以此来满足不同情景下的计算需求。

​ 比如，在C语言中声明变量 int a, b ，意味着在给变量a和b赋值时不能超出int的取值范围，同时变量a和b之间的运算只能是int类型所允许的运算。

3.2抽象数据类型

​ 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。

​ 就是将事物的普遍特性抽离出来，仅仅关心逻辑特性，并不关心具体在计算机中如何表示和实现的。

间的运算只能是int类型所允许的运算。

3.2抽象数据类型

​ 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。

​ 就是将事物的普遍特性抽离出来，仅仅关心逻辑特性，并不关心具体在计算机中如何表示和实现的。