引入
之前我们都在学习什么是数据结构以及如何评价一个算法的时间、空间复杂度，今天开始，我们学习一个最简单的数据结构，线性表。
感受数据结构
还记得小时候，排队去参加升旗仪式，老师们会按照高矮个将同学们分好位置，全班50多个人，怎么记住自己的位置呢？
1号小红
2号小明
3号小强
…
55号小美
56号小力
老师肯定不能告诉你，Bliner 你在32位，那你站队的时候还要从1数到32…如果8号没来..你还少数了…这样肯定不行。
所以，老师们一般都会这么告诉你，记住你前面的同学，下次你就站在这儿。
并且，如果有谁不在，也可以一下子就知道，因为肯定有同学会说，我前面的 XX 没来。
线性表
线性表就像刚才排队一样，具有线一样的性质。
**定义:**由 0 个或者多个数据元素组成的有限序列，就称为线性表。
- **必须是序列：**线性表是一个序列，元素之间有
先来后到的关系。 - **多个元素：**如果存在多个元素，那么
第一个元素无前驱，最后一个元素无后继，其他的元素只有一个前驱和后继。（类似 C 学指针时候的双链表） - **有限：**线性表强调的是
有限，事实上无论计算机发展到多强大，处理的数据一定是有限的。
**数学表达：**若将线性表记为（a1,…ai-1,ai,ai+1,….an），则表中 ai-1 领先于 ai , ai 领先于 ai+1。
称 ai-1 是 ai 的直接前驱元素，ai+1 是 ai 的直接后继元素。
- **元素个数：**所以
线性表的元素个数 n (n>=0) 定义为线性表的长度，n=0时，称为空表。（即：有多少个数据，则线性表就有多长，线性表可以为空）
例题
例1： 公司的组织架构属于线性关系吗
- 答： 不是。因为一个CEO 对应多个总监，一个总监对应多个经历，一个经理对应多个员工，这是一对多的关系。
- **讲解：**线性关系的条件是，如果存在多个元素，则第一个元素无前驱，最后一个元素无后继，
其他元素只能有一个前驱和后继。不符合最后一句。
**例2：**一个班级同学之间的友谊是线性关系吗？
- **答：**不是。因为我们每个人都可以跟其他人建立友谊。
**例3：**一个班级里面的点名册是线性关系吗？
- **答：**是的。因为我们的点名册是根据学号来排序的。
- **分析：**点名册根据学号排序，有限、有序列、有先来后到，我的学号前后只对应两个学生，我的直接前驱和我的直接后继，所以是线性表。
抽象数据类型
下一节，我们会说线性表的抽象数据类型，我们先来铺垫一下什么是抽象数据类型。
什么是数据类型？
**定义：**是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
例如：整形、字符型、浮点型，这些都是数据类型。
为什么要用数据类型呢？
因为不同的数据在内存中占中不同的长度。
例如，int i=3 跟 float j = 3.1415926 ，在内存中占用的空间肯定是不一样的。
给 int 类型放：3.1415926 就会放不下
给 float 类型放：3 就会浪费内存空间
所以，我们在声明变量前，首先要声明数据类型，告诉系统你要多少内存空间。
数据类型分类
在 C 语言中，数据类型可以分为两大类：
- **原子类型：**整型、浮点型、字符型等等；
- **结构类型：**由原子类型和结构类型组成的，可以对该类型进行分解，如结构体、共用体、枚举体等等。
抽象
我们知道了什么是数据类型，那么抽象数据类型又是什么呢？
**抽象定义：**指的是抽取出事物具有的普遍性本质。它要求抽出问题的特征，忽略非本质细节。是对具体事物的一个概括。抽象是一种思考方式，他隐藏了繁杂的细节。
那么，根据抽象的定义，我们对已有的数据类型进行抽象，就有了抽象数据类型。
抽象数据类型
**定义：**抽象数据类型（Abstract Data Type）是指一个数学模型及定义在该模型上的一组操作。
- 抽象数据类型的定义，仅
取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 - 抽象的意义，在于数据类型的
数学抽象特性。 - 抽象数据类型，不仅仅指那些已经定义并实现的数据类型，还
可以是计算机编程者在设计软件程序时自己定义的类型。
描述抽象数据类型：
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作
endADT
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
评论