本节要点:线性表的基本定义以及相关术语,线性表的类型定义方式和一些基本的操作;

1. 线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列。

image-20220826090316825

线性表(Linear List):由 $n(n\ge 0)$ 个数据元素(结点)$a_1,a_2,···,a_n$ 组成的有限序列。
其中数据元素的个数 $n$ 定义为表的长度。
当 $n=0$ 时称为空表
将非空的线性表 $n>0$ 记作:$(a_1,a_2,···,a_n)$ .
这里的数据元素 $a_i(1\leq i\leq n)$ 只 是一个抽象的符号,其具体含义在不同的情况下可以不同。

例如:分析 26 个英文字母组成的英文表 (A,B,C,D,...,Z),数据元素都是字母;元素间的关系是线性;

例如:12星座:(白羊座、金牛座、双子座、巨蟹座、狮子座、处女座、天秤座、天竭座、射手座、摩羯座、水瓶座、双鱼座)

同一线性表中的元素必定具有相同特性,数据元素间的关系是线性关系

从以上例子可看出线性表的逻辑特征是:

  • 在非空的线性表,有且仅有一个开始结点 $a_1$,它没有直接前趋,而仅有一个直接后继 $a_2$;
  • 有且仅有一个终端结点 $a_n$,它没有直接后继,而仅有一个直接前趋 $a_{n-1}$;
  • 其余的内部结点 $a_i(2\leq i\leq n-1)$都有且仅有一个直接前趋 $a_{i-1}$和个直接后继 $a_{i+1}$

2. 案例引入

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

$P_n(x)=p_0+p_1x+p_2x^2+···+p_nx^n$

线性表 $P=(p_0,p_1,p_2,···,p_n)$ 每一项的指数 $i$ 隐含在其系数 $p_i$ 的序号中;

例如:$P(x)=10+5x-4x^2+3x^3+2x^4$,用数组表示:

指数(下标$i$)01234
系数$p[i]$105-432

我们只需要把指数相同的多项式进行依次相加:

$$ R_n(x)=P_n(x)+Q_m(x) $$

即为:$R=(p_0+q_0,p_1+q_1,p_2+q_2,···,p_m+q_m,p_{m+1},···,p_n)$

【案例2.2】系数多项式的运算

如果是稀疏多项式(例如 $S(x)=1+3x^{100}+4x^{1000}$)就不必这么存储,不然很浪费内存。

如:$(a): A(x)=7+3x+9x^8+5x^{17}$

下标$i$0123
系数$a[i]$7395
指数01817

$B(x)=8x+22x^7-9x^8$

下标$i$012
系数$a[i]$822-9
指数178

$$ P_n(x)=p_1x^{e_1}+p_2x^{e_2}+...+p_mx^{e_m} $$

线性表:$P=\left((p_1,e_1), (p_2,e_2), ····,(p_m,e_m)\right)$

对于上面两个系数多项式 $A(x)$ 与 $B(x)$ 相加,首先确定两个线性表:

$A=((7,0),(3,1),(9,8),(5,17))$

$B=((8,1),(22,7),(-9,8))$

然后创建一个新数组 $c$,分别从头遍历比较 $a$ 和 $b$ 的每一项:

  • 指数相同,对应系数相加,若其和不为零,则在 $c$ 中增加一个新项
  • 指数不相同,则将指数较小的项复制到 $c$ 中

一个多项式已遍历完毕时,将另一个剩余项依次复制到 $c$ 中即可

那么,数组 $c$ 的大小定义多少合适?

如果使用上面的顺序存储结构存在问题:

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

所以可以使用链式存储结构。链式存储结构不需要单独定义数组来存储结果,而是需要多少用多少。

image-20220826111023187

image-20220826111046329

总结

  • 线性表中数据元素的类型可以为简单类型,也可以为复杂类型。
  • 许多实际应用问题所涉的基本操作有很大相似性,不应为每个具体应用单独编写一个程序。
  • 从具体应用中抽象出共性的逻辑结构和基本操作(抽象数据类型),然后实现其存储结构和基本操作

3. 线性表的类型定义

ADT List{
数据对象:$D=\{a_i|a_i 属于 \mathrm{Elemset},(i=1,2,···,n,n\ge0)\}$

数据关系:

$R=\{<a_{i-1},a_i>|a_{i-1},a_i属于D,(i=1,2,···,n)\}$

基本操作:

InitList(&L); DestroyList(&L);

ListInsert(&L,i,e); ListDelete(&L,i&e);

}ADT List

  • InitList(&L)

操作结果:构造一个空的线性表 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\leq i \leq \mathrm{ListLength}(L)$。

操作结果:用e返回线性表 L 中的第 $i$ 个数据元素的值。

  • LocateElem(L,e,compare())

初始条件:线性表 L 已经存在,compare() 是数据元素判定函数。
操作结果:返回 L 中第1个与 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返回它的后继,否则操作失败,next_e 无意义。

  • ListInsert(&L,i,e)

初始条件:线性表 L 已经存在,$1 \leq i\leq \mathrm{ListLength(L)}+1$。
操作结果:在 L 的第 $i$ 个位置之前插入新的数据元素e,L 的长度加一。

  • ListDelete(&L,i,&e)

初始条件:线性表 L 已经存在,$1 \leq i\leq \mathrm{ListLength(L)}$。。
操作结果:删除 L 的第 $i$ 个数据元素,并用e返回其值,L 的长度减一。

  • ListTraverse(&L,visited())

初始条件:线性表 L 已经存在
操作结果:依次对线性表中每个元素调用 visited()

🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/86.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 02 日
赏杯咖啡