线性表——(2)线性表的顺序存储及其运算的实现

归纳编程学习的感悟，
记录奋斗路上的点滴，
希望能帮到一样刻苦的你！
如有不足欢迎指正！
共同学习交流！
🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言📝
看到美好，感受美好，屏蔽阴霾！

一起加油！

一、顺序表：

二、顺序表基本运算的实现：

💦顺序表的初始化：

💦插入运算：

☘️顺序表的数据元素的插入算法：

💦删除运算：

☘️顺序表的数据元素的删除算法：

💦按值查找 :

☘️顺序表的数据元素查找算法:

三、顺序表的其他运算举例：

💦例1：

☘️顺序表的划分算法：

💦例2：

☘️顺序表的合并算法：

💦例3：

☘️两个顺序表的比较算法：

四、总结：

五、共勉：

一、顺序表：

        线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表中的各数据元素，用这种存储形式存储的线性表称为顺序表。因为内存中的地址空间是线性的，所以用物理位置关系上的相邻性实现数据元素之间的逻辑相邻关系既简单又自然。线性表的顺序存储示意图如图 A所示，设 a 的存储地址为 Loc(a)，每个数据元素占 d 个存储单元，则第 i个数据元素的地址为:

Loc(a $^{_{i}}$ )=Loc(a $^{_{1}}$ )+(i-1)*d 1<=i<=n

图A 线性表的顺序存储示意图

         这就是说，只要知道顺序表首地址和每个数据元素所占存储单元的个数就可求出第 i 个数据元素的地址，这也是顺序表具有按数据元素的序号随机存取的特点。
        在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的了。考虑到线性表有插入、删除等运算，即表长是可变的，因此，数组的容量要设计得足够大,设用 data[MAXSIZE]来表示，其中 MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据元素从 data[0]开始依次顺序存放，但当前线性表中的实际数据元素个数可能未达到 MAXSIZE 个，因此需用变量 last 记录当前线性表中最后一个数据元素在数组中的位置，即 last 具有指针的作用，始终指向线性表中最后一个数据元素，因此，表空时 last =-1。这种存储思想的具体描述可以是多样的，如可以是:
datatype data[MAXSIZE];
	int last;
这样表示的顺序表如图 A 所示，表长为 last+1，数据元素分别存放在 data[0]到 data[last]中这样使用简单方便，但有时不便于管理。

从结构性上考虑，通常将 data 和 last 封装成一个结构，作为顺序表的数据类型:
typedef struct{
	datatype data[MAXSIZE];
	int last;
}SeqList; 
定义一个顺序表:
SeqList L
这样表示的线性表如图(a) 所示。表长 = L.last+1，线性表中的数据元素 a1至 an分别存放在 L.data[0]至 L.data[L.last]中.其实有时定义一个指向 SeqList 类型的指针更为方便:
SeqList *L
L是一个指针变量，线性表的存储空间通过 L=malloc(sizeof(SeqList)运算来获得。L 中存放的是顺序表的地址，这样表示的线性表如图 (b) 所示。表长表示为(*L).last+1 或 L->last+1，线性表的存储区域为 L->data，线性表中数据元素的存储空间为:

L->data[0] ~ L->data[L->last]

二、顺序表基本运算的实现：

根据以上线性表顺序存储结构定义，确定了其存储方式之后，就可以讨论其基本运算的实现方法(即实现算法)了，同时还要对算法进行初步的分析。

💦顺序表的初始化：

顺序表的初始化即构造一个空表，这对顺序表是一个加工型的运算，因此，将L设为指针参数,首先动态分配存储空间，然后将表中 last 指针置为-1，表示顺序表中没有数据元素。算法如下:
SeqList *init_SeqList(){ 
	SeqList *L;
	L=malloc(sizeof(SeqList));
	L->last=-1;
	return L;
}
设调用函数为主函数，主函数对初始化函数的调用如下:
main(){
	SeqList *L;
	L=init_SeqList();
	…… 
} 