数据结构

数据结构笔记——线性表的应用

线性表的合并

问题描述

解题思路

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

  1. 在La中查找该元素

  2. 如果找不到，则将其插入到La的最后

代码

void unionList(SqList *La,SqList *Lb){
    int La_lenth=GetLength(La);
    int Lb_lenth=GetLength(Lb);

    for(int i=0;i<Lb_lenth;i++){
        ElemType e;
        GetElem(Lb,i,e);
        if(LocateElem(La,e)!=0){
            ListInsert(La,La_lenth+1,e);
        }
    }
}

有序表的合并

顺序表实现

void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc){
    ElemType *pa =La->elem;
    ElemType *pb =Lb->elem;
    Lc->length=Lb->length+Lc->length;
    Lc->elem=(ElemType *)malloc(Lc->length * sizeof(ElemType)); 
    ElemType *pc=Lc->elem;
    ElemType *pa_last=La->elem+La->length-1;//pa_last 指向La的最后一个元素 地址=基地址+偏移量-1
    ElemType *pb_last=La->elem+La->length-1;

    while(pa<=pa_last && pb<=pb_last){//两个表都非空
        if(*pa<=*pb){
            *(pc++)=*(pa++);
        }else{
            *(pc++)=*(pb++);
        } 
    }

    while(pa<pa_last){ //看看La还有没有剩余，有剩余直接添加
        *(pc++)=*(pa++);
    }
    while(pb<pb_last){
        *(pc++)=*(pb++);
    }

}

链表实现

void Merge_LinkedList(LinkList *La, LinkList *Lb, LinkList *Lc)
{
    *Lc = *La;                                   // 让Lc使用La的头节点进行合并
    LinkList pa = (*La)->next, pb = (*Lb)->next; // pa, pb分别表示合并时所指节点
    LinkList pc = *Lc;                           // 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;
        }
    }
    if(pa!=NULL){
        pc->next=pa;
    }else{
        pc->next=pb;
    }

    // pc->next不需要NULL,因为合并时一定会剩下一串节点，只需指向该剩下的节点就OK
    free(*Lb);
    *La = *Lb = NULL;
}

Comment