[数据结构与算法]线性表的应用

线性表的应用

线性表的合并

• 问题描述：
  假设利用两个线性表$L_a$和$L_b$分别表示两个集合$A$和$B$，现要求一个新集合$A=A\cup B$

$L_a=(7,5,3,11)$ $L_b=(2,6,5)$ $?>$ $L_a=(7,5,3,11,2,6)$

• 算法步骤
  依次取出$L_b$中的每个元素，执行以下操作：
  1.在$L_b$中查找该元素
  2.如果找不到，则将其插入$L_a$的最后

• 伪代码实现

void union(List &La,List &Lb){
    La_len=ListLength(La);//求出La的长度
    Lb_len=ListLength(Lb);//求出Lb的长度
    for(int i=1;i<=Lb_len;i++){//遍历Lb
        GetElem(Lb,i,e);//取出Lb中的元素
        if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);//元素不在La中则插入La
    }
}

• 时间复杂度：$O(La\_len)?O(Lb\_len)$
  
• 空间复杂度：$O(La\_len)?O(Lb\_len)$
  

有序表的合并

• 问题描述：
  已知线性表$L_a$和$L_b$中的数据元素按值非递减有序排列，现要求将$L_a$和$L_b$归并为新的线性表$L_c$，且$L_c$中的数据元素仍按值非递减有序排列。

$L_a=(1,7,8)$ $L_b=(2,4,6,8,10,11)$ $?>$ $L_a=(1,2,4,6,7,8,8,10,11)$

• 算法步骤
  1.创建一个空表$L_c$
  2.一次从$L_a$或$L_b$中“摘取”元素值较小的元素插入到$L_c$表的最后，直至其中一个表变空为止
  3.继续将$L_a$或$L_b$其中一个表的剩余结点插入在$L_c$表的最后

顺序表实现

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
  pa=LA.elem;
  pb=LB.elem;//指针指向第一个元素
  LC.length=LA.length+LB.length;//LC的长度
  LC.elem=new ElemType[LC.length];//为合并后的新表分配一个数组空间
  pc=LC.elem;//指向LC的第一个元素
  pa_last=LA.elem+LA.length-1;//找到最后一个元素，方便知道LA，LB是否已到最后
  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++;//LB为空时
  while(pb<=pb_last) *pc++=*pb++;//LA为空时
}//MergeList_sq

• 时间复杂度：$O(ListLength(La)+ListLength(Lb))$
  
• 空间复杂度：$O(ListLength(La)+ListLength(Lb))$
  

链表实现

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
  LinkList pa,pb,pc;
  pa=La->next;pb=Lb->next;
  pc=Lc=La;//用La的头结点作为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;//插入剩余段，释放Lb
}

• 时间复杂度：$O(ListLength(La)+ListLength(Lb))$
  
• 空间复杂度：$O(1)$
  

案列（2.1）一元多项式的运算

• 实现两个多项式加减乘运算

例如：
$P_a(x)=10+5x?4x^2+3x^3+2x^4$

$P_b(x)=?3+8x+4x^2?5x^4+7x^5?2x^6$

加法运算

void add_Sq(List &La,list &Lb){
  for(int i=0;i<max(La.length,Lb.length);i++){
    La.elem[i]+=Lb.elem[i];
  }
}

案例（2.2）稀疏多项式运算

线性表A=((7,0),(3,1),(9,8),(5,17))
线性表B=((8,1),(22,7),(9,8))
注：(a,b):a：系数；b：指数

顺序表实现

• 算法步骤：
  1.创建一个数组c
  2.分别从头遍历比较a和b的每一项
  指数相同，对应系数相加，若其和不为零，则在c中增加一个新项
  指数相同，则将指数较小的项复制到c中
  3.一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

实现问题：c数组空间大小、运算空间复杂度高
解决办法：链式存储

链表实现

链式存储结构创建多项式：

typedef struct PNode{
  float coef;//系数
  int expn;//指数
  struct PNode *next;//指针域
}PNode,*Polynomial;

• 算法步骤：
  1.创建一个只有头结点的空链表
  2.根据多项式的个数n，循环n次执行以下操作：
  (1).生成一个新节点s
  (2).输入多项式的系数和指数赋给新节点s的数据域
  (3).设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱
  (4).指针q初始化，指向首元节点
  (5).循环向下逐个比较链表中当前节点与输入项指数，找到第一个大于输入项指数的结点*q
  (6).将输入项结点*s插入到结点*q之前

• 代码实现

void CreatePolyn(Polynmial &P,int i){
  P=new PNode;
  p->next=NULL;
  for(int i=1;i<=n;i++){
    s=new PNode;
    cin>>s->coef>>s->expn;
    pre=P;
    q=P->next;
    while(q&&q->expn<s->expn){
      pre=q;q=q->next;
    }
    s->next=q;
    pre->next=s;
  }
}

链式多项式的相加运算

• 算法步骤
  1.指针p1和p2初始化，分别指向pa和pb的首元节点
  2.p3指向和多项式的当前节点，初值为pa的头结点
  3.当指针p1和p2均未到达表尾时，则循环比较p1和p2所指结点对应的指针值
  (p1->expn与p2->expn),有下列3种情况
  (1)当p1->expn=p2->expn时,则将两个结点中的系数相加
  若和不为零,则修改p1所指结点的系数值,同时删除p2所指结点
  若和为零,则删除p1和p2所指结点
  (2)当p1->expnexpn时,则应摘取p1所指点插入到“和多项式”链表中去
  (3)当p1->expn>2->expn时,则应摘取p2指结点插入到“和多项式”链表中去
  4.将非空多项式的剩余段插入到p3所指结点之后
  5.释放pb的头结点