【数据结构与算法】线性表

文章目录

• 一.什么是线性表？
• 二.线性表如何存储？
• 三.线性表的类型

一.什么是线性表？

1. 定义

   线性表（Linear List）是由n(n>=0)个具有相同特性的数据元素（结点）a1,a2,…an组成的有限序列。如下图所示：

• 线性起点也称首元
• 如果这个线性表没有元素，即n=0时为空表。
• 统一线性表中的元素必定具有相同的特性，数据元素间的关系是线性关系。

线性表的例子

【例1】分析26个英文字母组成的英文标：（A,B,C,D,……,Z）

数据元素都是字母；元素间关系是线性。

【例2】分析学生情况登记表

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
数据元素都是记录；元素间关系是线性

【例3】十二星座（白羊座，金牛座，双子座，……，双鱼座）

数据元素都是字符串；元素间关系是线性

2. 特点
   • 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2
   • 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a(n-1)
   • 其余的内部结点ai(2<=i<=n-1)都有且仅有一个直接前趋a(i-1)和一个直接后继a(i+1).
   • 线性表是一种典型的线性结构。

二.线性表如何存储？

即线性表在计算机里如何实现这个运算？

我们从一个案例来引出线性表的两种存储方式：

【案例2.1】一元多项式的运算（实现两个多项式加减乘运算）

我们可以把每个系数拿出来存成一个线性表，用数组来实现，变量用系数的下标隐含的表示：

这样我们可以顺利的进行两个一元多项式的加运算：

【案例2.2】多项式非零项的数组表示

很多项缺失，就不能用下标来隐含的表示指数了：

继续用顺序存储法来进行多项式的加法运算：

1. 创建一个新数组C（这就意味着需要一个新的空间）
2. 分别从头遍历比较a和b的每一项
   • 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项
   • 指数不同，则将指数较小的项复制到c中
3. 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可。

结果如下：

0	1	7	17
7	11	22	5

稀疏多项式有很多项缺失，这样存储的话会造成存储空间很大的浪费，怎么办？

我们发现顺序存储结构存在的问题：

• 存储空间分配不灵活
• 运算的空间复杂度高

下面用**链式存储法（指针）**进行上面案例的实现：

分别把系数不为0的项的系数和指数存储起来，这个线性表中的每个元素都有两个数据项，再存储下一个元素的位置，如下图所示：

我们再引入一个实际案例来理解链式结构存储：

【案例2.3】图书管理系统

在该图书管理系统中我们需要的功能有：查找，插入，删除，修改，排序和计数。

1. 首先，将图书表抽象为线性表，表中每本图书抽象为线性表中数据元素

2. 选择合适的存储结构

   • 图书顺序表
     

   • 图书链表
     

3. 实现此存储结构上的基本操作

4. 利用基本操作完成功能

三.线性表的类型

1.前面已经给出了抽象数据类型的定义，抽象数据类型线性表的定义如下：

ADT List{
    数据对象：D={ai|ai属于Elemset,(i=1,2,...n,n>=0)}
    数据关系：R={<ai-1,ai>|ai-1,ai属于D,(i=2,3,...n)}
    基本操作：
}ADT List

2.基本操作

• InitList(&L)(Initialization List)
  • 操作结果：构造一个空的线性表L.（线性表的初始化）
• DestroyList(&L)
  • 初始条件：线性表L已经存在
  • 操作结果：销毁线性表L
• ClearList(&L)
  • 作用：线性表内容的清除
  • 初始条件：线性表L已经存在
  • 操作结果：将线性表L重置为空表
• ListEmpty(L)
  • 作用：判断线性表里是否有元素
  • 初始条件：线性表L已经存在。
  • 操作结果：若线性表L为空表，则返回TURE;否则返回FALSE
• ListLength(L)
  • 初始条件：线性表L已经存在
  • 操作结果：返回线性表L中的数据元素个数
• **GetElem(L,i,&e)**替换
  • 初始条件：线性表L已经存在，1<=i<=ListLength(L)
  • 操作结果：用e返回线性表L中第i个数据元素的值
• **LocateElem(L,e,compare())**定位查找
  • 初始条件：线性表L已经存在，compare()是数据元素判定函数
  • 操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0.
• **PriorElem(L,cur_e,&pre_e)**求前驱
  • 初始条件：线性表L已经存在
  • 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义。
• **NextElem(L,cur_e,&next_e)**求后驱
  • 初始条件：线性表L已经存在
  • 操作结果：若cur_e是L的数据元素，且不是第最后个，则用next_e返回
• **ListInsert(&L,i,e)**插入
  • 初始条件：线性表L已经存在，1<=i<=ListLength(L)+1
  • 操作结果：在L的第i个位置之前插入新的数据元素e,L的长度加一
• **ListDelete(&L,i,&e)**删除
  • 初始条件：线性表L已经存在，1<=i<=ListLength(L)+1
  • 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一。
• ListTraverse(&L,visited())
  • 初始条件：线性表L已经存在
  • 操作结果：依次对线性表中每个元素调用visited()