算法与数据结构【30天】集训营——线性表的定义及特点-顺序表的表示与实现及操作（03）

线性结构的定义（特点）

存在唯一一个称作“第一个”的元素。
存在唯一一个称作“最后一个”的元素
除最后一个元素外，集合中每一个元素都只有一个直接前趋
除最后一个元素外，集合中每一个元素都只有一个直接后继

注意1、2条：证明循环的序列不是线性表

线性表是$n(n>=0)$个数据元素的有限序列，它是一个最常用，最简单的数据结构。

特性：均匀性，有序性（线性序列关系）

线性表的基本操作（概念）

我们需要对这些操作有所了解并掌握，常见的增删改查使我们必须要掌握的，后续的操作是将这些分开的操作结合在一起

注意：

1)线性表从1开始,线性表第一个元素对应到数组中下标是0.

2)函数通过引用对线性表的元素进行修改即可

3)数组比较特别，它即可视为逻辑结构，又可视为存储结构。

4)每一个表元素都是不可再分的原子数据。一维数组可以视为线性表，二维数组不可以，在逻辑上它最多可以有两个直接前趋和直接后继。

5)线性表具有逻辑上的顺序性，在序列中各元素有其先后次序，各个数据元素在线性表中的逻辑位置只取决于序号。

顺序表的表示及实现和操作

线性表的表示

顺序表：是线性表的循序储存结构，以物理位置表示逻辑关系，任意元素可以随机存取。用一组地址连续的存储单元依次存储线性表中的元素。逻辑顺序和物理顺序是一致的。可以顺序访问，也可随机访问。

优点：查找方便，存储密度大，可以随机存储表中任一元素

缺点：插入，删除会造成大量的元素移动，会导致效率很低（因为它是连续的，这也是顺序表的最大的特点）

顺序表最主要的特点是随机访问， 即通过首地址和元素序号可在时间0(1)内找到指定的元素。
顺序表的存储密度高， 每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻， 所以插入和删除操作需要移动大量元素。

稀疏多项式运算的线性表思想（链式存储结构）

数据域通过存储其指数域，通过比较最开始的指数，按照下面的规则：

如果两者对比，小的移动到下一位（也就是指向小的），大的不移动

如果指数域相等，则进行指数的相加，然后两者向下移动

如果出现指数相等之后，然后系数相加等于，丢弃，也就是跳过该元素，指针指向下一个（往下移动）

那么如果上述的元素跳过之后，上下两个都有元素呢？那么就是先调整指针，然后在链表即可！！

顺序表的中的基本操作实现

初始化顺序表

销毁线性表L

void DestroyList(SqList &L){
	if (L.elem) delete[]L.elem;
}
1
2
3

清空线性表L

void ClearList(SqList &L){
	L.length=0;
}
1
2
3

求线性表L的长度

void GetLength(SqList L){
	return (L.length);
}
1
2
3

判断线性表是否为空

int IsEmpty(SqList L){
	if(L.length==0) return 1;
	else return 0;
}
1
2
3
4

顺序表的取值

顺序表的插入操作

顺序表的查找操作

碰到e就返回，返回其我们认知的数字次序

顺序表的删除操作

最好，最坏，平均时间复杂度和插入一样

查找（查找e），插入，删除的算法的平均时间复杂度为$O(n)$,显然顺序表的空间复杂度为$O(1)$

常考例题

可以取其特殊值

代码算法题（现实中可能不会让你全部写）

①从顺序表中删除具有最小值的元素（假设唯一） 并由函数返回被删元素的值。 空出的位置由最后一个元素填补， 若顺序表为空， 则显示出错信息并退出运行。

②设计一个高效算法， 将顺序表厶的所有元素逆置， 要求算法的空间复杂度为0（1）

③对长度为n的顺序表编写一个时间复杂度为0（n）、 空间复杂度为0（1）的算法， 该算法删除线性表中所有值为x的数据元素

④ 从有序顺序表中删除所有其值重复的元素， 使表中所有元素的值均不同

【重要！】将两个有序顺序表合并为一个新的有序顺序表， 并由函数返回结果顺序表

首先， 按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。 然后， 看哪个表还有剩余， 将剩下的部分加到新的顺序表后面

真题集合

每文一语

开始也是一种催化剂