数据结构---线性表的应用

• 线性表的应用
  • 线性表的合并
    • 算法思想：扩大线性表LA，将存在表LB而不存在于表LA中的数据放在表LA中
    • 即从表LB中取得每个元素，并且都和表LA中的元素进行比较，不存在就插入表LA中
  • 有序表的合并
    • ---顺序有序表的合并
      • 算法思想：用两个指针指向表LA和表LB的某个元素，比较其大小，将小的插入在表LC中，插入后指针顺序后移
    • ---链式有序表的合并
      • 算法思想：设立3个指针 pa 、 pb 和 pc, 其中 pa 和 pb 分别指向LA和LB中当前待比较插入的结点，而 pc 指向LC中当前最后一个结点（指针的初值为：pa 和 pb 分别指向LA和LB表中的第一个结点，pc 指向空表LC中的头结点。）通过比较指针 pa 和 pb 所指向的元素的值，依次从LA或LB中 “摘取“ 元素值较小的结点插入到LC最后，当其中一个表变空时，只要将另一个表的剩余段链接在 pc 所指结点之后即可

线性表的应用

线性表的合并

算法思想：扩大线性表LA，将存在表LB而不存在于表LA中的数据放在表LA中

即从表LB中取得每个元素，并且都和表LA中的元素进行比较，不存在就插入表LA中

算法步骤：

• 分别获取表LA和表LB的表长m，n
• 从表LB中获取第i个元素，将其赋值给e
• 在表LA中查找元素e，不存在则将其插在表LA后，重复上述操作执行n次

主要是用到基本操作中的获取元素，查找元素，插入元素

void Union(LinkList& LA,LinkList& LB,int m,int n)
{
int e,a;
for(int i=1;i<=n;i++)
{
e=GetElem(LB,i,e);//获取第i个元素赋给e
a=LocateElem(LA,e);//在LA中查找e，找到a为1否则为0
if(a!=1)//没有找到或者为空
ListInsert(LA,m,e);//将e插在LA表尾
}
}

时间复杂度为O(m*n)

有序表的合并

---顺序有序表的合并

表LA和表LB均是有序表，合并后得到的表LC还是有序表

算法思想：用两个指针指向表LA和表LB的某个元素，比较其大小，将小的插入在表LC中，插入后指针顺序后移

算法步骤：

• 创建空表LC(表长为m+n)

• 将指针pc，pa，pb初始化分别指向LC，LA，LB的第一个元素

• 当LA，LB均没有到达表尾，依次比较pa，pb所指向元素的值，将较小值插入LC表中

• 继续将LA或LB中的剩余结点插入表LC后

  

void Union(SqList LA,SqList LB,SqList &LC)
{
int*pa,*pb,*pc,*pa_last,*pb_last;
pa=LA.elem;
pb=LB.elem;
LC.length=LA.length+LB.length;
LC.elem=new int[LC.length];
pc=LC.elem;
pa_last=LA.elem+LA.length-1;
pb_last=LB.elem+LB.length-1;
while ((pa<=pa_last) && (pb<=pb_last))
{
if(*pa< =*pb ) *pc++=*pa++;
else *pc++=*pb++;
}
while (pa<=pa_last) *pc++=*pa++; 
while (pb<=pb_last) *pc++=*pb++;
}

时间复杂度为O(m+n)

*p++: *p;p+=1;

p++是先对p进行运算，这里是先进行*P的运算，再将p+1

---链式有序表的合并

算法思想：设立3个指针 pa 、 pb 和 pc, 其中 pa 和 pb 分别指向LA和LB中当前待比较插入的结点，而 pc 指向LC中当前最后一个结点（指针的初值为：pa 和 pb 分别指向LA和LB表中的第一个结点，pc 指向空表LC中的头结点。）通过比较指针 pa 和 pb 所指向的元素的值，依次从LA或LB中 “摘取“ 元素值较小的结点插入到LC最后，当其中一个表变空时，只要将另一个表的剩余段链接在 pc 所指结点之后即可

算法步骤：

• 指针 pa和 pb 初始化，分别指向LA和LB的第一个结点。

• LC的结点取值为LA的头结点。

• 指针 pc初始化，指向LC的头结点。

• 当指针 pa 和 pb 均未到达相应表尾时， 则依次比较 pa 和 pb 所指向的元素值， 从 LA 或LB 中 ＂摘取“ 元素值较小的结点插入到 LC 的最后。

• 将非空表的剩余段插入到 pc 所指结点之后。

• 释放 LB 的头结点。

  

void Union(LinkList &LA,LinkList &LB,LinkList &Lc)
{
struct LNode*pa,*pb,*pc;
pa=LA->next;pb=LB->next;
LC=LA;
pc=LC;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb; 
pb=pb->next;
}
}
pc->next=pa?pa:pb; 
delete LB;
}

时间复杂度为O(m+n)