数据结构

---

⚡️数据结构-第一章
⚡️抽象数据类型案例
⚡️数据结构-第二章（1）-线性结构
⚡️数据结构-第二章（2）-线性表的顺序表示和实现
⚡️数据结构-第二章（3）-顺序表（含代码）
⚡️数据结构-第二章（4）-顺序表案例（含代码）
⚡️数据结构-第二章（5）-链式存储结构
⚡️数据结构-第二章（6）-单链表基本操作的实现
⚡️数据结构-第二章（7）-双向链表和循环链表

一、线性表的合并

问题描述：

  假设利用两个线性表La和Lb分别表示两个集合$A,B$，现要求一个新的集合$A=A\cup B$

$La=(7,5,3,11)$，$Lb=(2,6,3)->La=(7,5,3,11,2,6)$

算法步骤

依次取出$Lb$中的每个元素，执行以下操作：”

• ① 在$La$中查找该元素

• ② 如果找不到，则将其插入$La$的最后

  此算法复杂度是两线性表表长的乘积

  这里的算法是通用的与$La、Lb$的具体存储方式无关（不关心它们是用顺序表还是链表）

二、有序表的合并

  问题描述：已知线性表$La$和$Lb$中的数据元素按值非递减有序排列，现要求将$La$和$Lb$归并为一个新的线性表$Lc$且$Lc$中的数据元素按值非递减有序排列（不一定是严格递增的可能出现相等的元素）。

$La=(1,7,8)，Lb=(2,4,6,8,10,11)->Lc=(1,2,4,6,7,8,8,10,11)$

顺序表实现

算法步骤：

• ① 创建一个空表$Lc$

• ② 依次从$La$或$Lb$中“摘取”元素值较小的结点插入到$Lc$表的最后，直至其中一个表为空。

• ③ 继续将$La$或$Lb$其中一个表的剩余结点插入在$Lc$表的最后。
  
  算法主要思想

循环比较将小的值放入$Lc$并移动小的元素所在数组的指针和$Lc$指针。

链表实现

有序表链表的实现具体可以看我之前的一篇文章有序表(链表)的合并（结合力扣21题/剑指offer25题-合并两个有序链表）

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！