大家好 这一讲我们开始学习
数据结构与算法第二章 线性表
我们会介绍线性表的基本概念
以及顺序表和链表
线性表呢
是零个或多个元素所组成的
有穷的序列
这个元素呢
也可以称为表目或者是记录
而元素在线性表里面的
一个相对的位置
我们也称为下标或者是索引
元素的个数呢
就称为表长
如果长度为0
那就是空表
线性表是非常简单
易于存储和运算的
这么一个数据结构
对于小规模的应用呢
采用线性表来实现
是非常高效的
线性表里面
我们可以看到
有一些特殊的元素
以及它们之间有些关系
我们用二元组来表达线性表
二元组里面的结点集呢
就是我们线性表里面
所有元素组成的集合
而它的关系呢
其实就是前驱/后继关系
如果ai和ai+1是直接相邻的
那我们把ai称为ai+1的前驱
而ai+1称为ai的后继
我们这里是指的直接前驱
和直接后继
在这个线性表里面
有一个特殊的开始结点
它没有前驱
只有一个唯一的直接后继
有一个终结结点
没有后继
只有一个唯一的前驱
其他的呢都是内部结点
这些内部结点呢
只有唯一的一个直接前驱
和唯一的一个直接后继
我们这个前驱后继关系呢
它是有反对称性的
也就是说如果ai是ai+1的前驱呢
那不能说ai+1也是ai的前驱
对于后继关系也是这样的
还有传递性
传递性它是一个更广义范围
我们来看这个前驱后继
那也就是说
如果ai是aj的前驱
而aj是ak的前驱
那我们可以说
ai是ak的前驱
那这个表头呢
是整个线性表其他元素的前驱
而表尾呢是所有元素的后继
线性结构它有一些特点
如果我们看内存里面
最简单的普通线性结构
每一个结点呢
我们可以说
它都是由同类型的元素组成
它的元素长度呢也是一样的
也就是说它有均匀性
另外它还有一个有序性
这个表里面的元素
它都有相应的顺序
在逻辑上有一个序的关系
在存储上
我们也要很好的表达
这样的序的关系
按照线性表它的复杂程度呢
我们分为一类简单的线性表
就是我们前几章要介绍的
线性表还有栈和队列
另外呢
我们在后面会介绍散列表
散列表是一种有效的索引结构
支持高效的检索运算
还有高级的线性结构
就是基于线性结构做的一些扩充
像广义表 多维数组等等
按照访问方式呢
我们分为三种类型
直接访问型呢
就是我们根据它的下标
就能够直接的来找到
这样的一个元素位置
像数组就是这么一种
直接访问的形式
另外呢
顺序访问型
就是我们必须在这个表里面
挨个挨个才能找到
我们要找的这个元素
像链表就是这样的
顺序访问型的
目录索引型呢
就是为了加快它的检索的速度
我们做的一些有效的索引
像字典还有散列
就属于目录索引型的线性结构
线性结构按照操作来分
它可以分为普通的线性表
以及访问限制在同一端进行的栈
还有操作限制在两端的
这样的队列
我们来看
线性表的几个因素
首先是它的逻辑结构
在我们整个线性表这一章里面
因为都是讨论的线性结构
因此它们的逻辑结构是一样的
但是我们还要考虑一下
线性表它的逻辑结构
有哪些重要的属性
根据线性表的不同的存储方式
我们可以划分为
几种类型的线性结构
另外根据它的不同的运算
也可以划分为不同的线性结构
可以说在数据结构当中
逻辑存储和运算
这三个要素
只要任何一个有所不同
我们都可以看作是不同的数据结构
首先来看一下线性表的逻辑结构
我们要考虑
整个线性表有多少个元素
这个考虑呢
对于我们后面的一些存储和操作
都是相关的
另外呢
我们需要考虑线性表的起始结点
和它的终结结点
在一些特殊的运算的时候
我们需要在表头或者是表尾
进行相应的操作
还有一个就是当前位置
因为我们的操作
很可能是相关联的
如果我前面找到了这个元素的位置
然后我在这个位置上
要进行相应的操作
这个时候呢
我们就需要记录这个当前位置
然后再进行后面的运算
我们再来看
根据不同的存储结构
我们把线性表呢
分为顺序表
也就是数组
还有链表
这两大类型
顺序表呢
它是一个非常高效的存储结构
它的这个物理的存储的关系呢
就表达了它的逻辑的关联的关系
我们就不需要额外的存储的域
来表达逻辑上相邻的关系
因此我们可以非常紧密的
来存储这些相关的数据
如果整个表里面
都存的是有效元素
那我们的存储密度可以达到1
而链表它需要通过指针链接的关系
来表达我们的逻辑的一个序的关系
因此呢
它需要有指针的
这样的额外的存储空间
它的存储的一个效率
就不如顺序表
链表呢
分为单链双链循环链等等
这样的特殊的形式
按照操作来分
我们可以分为不受任何限制的
普通的线性表
另外我可以限制插入和删除
在同一端进行的结构
就是栈
还有插入和删除分别在两端进行的
线性结构
就是队列
首先来看栈
栈呢它是限制插入和删除
在表的同一端进行
这样的话呢
最先插入的这样的一个元素
它反而最后才能够出来
那也就是后进呢反而先出
这种性质在我们深搜等等
这样的算法里面
有很好的应用
队列它是插入限制在表的一端
而删除呢在另一端
这就形成了一个先进先出的
这么一个性质
这个在宽搜里面
也有很好的应用
对于一个数据结构
我们往往考虑
怎么样建立这个结构
以及怎么样销毁这个结构
把相应的这些存储的空间
返回给内存
另外呢对整个结构里面呢
我们可以进行增删查改
这样的相应的操作
还有排序和检索
这样对整个表的相关的运算
我们在后面的章节会介绍
我们来看
对线性表这些运算的实现
我们这里呢
是编写了相关的接口
例如这里增加元素
我们可以在表尾插入
也可以在任意的
一个指定位置上插入
然后呢在相应的位置上
删除某个元素
特别重要的就是
我们可能需要给定
这样的一个元素值
我在表里面找到相关的元素
然后我们再进行插入删除等等
其他的操作
还有就是修改相关位置上的元素值
我们给大家留下思考
线性表它有哪些分类方法
在各种分类方法里面
相应的这些数据结构呢
有一些什么样的区别和联系
另外呢
线性表有各种概念
例如顺序表 链表
栈 队列等等
这些概念里面呢
它哪一些是跟存储结构相关的
哪一些是跟运算相关的
谢谢大家