线性表的应用

  • 线性表的合并

    • 问题描述

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

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

    • 算法步骤

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

      1. 在La中查找该元素

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


void union(List &La,List Lb){

    La_len=ListLength(La);

    Lb_len=ListLength(Lb);

    for(i=1;i<=Lb_len;i++){

        GetElem(Lb,i,e);

        if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);

    } 

}

$$\bf算法的时间复杂度是：$$ $$O(ListLength(La)*Listlength(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)$$

    • 算法步骤

      1. 创建一个空表Lc

      2. 依次从La或Lb中"摘取"元素值较小的结点插入到Lc表的最后，直至其中一个表为空为止

      3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

    
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){

    pa=LA.elem;

    pb=LB.elem;		//指针pa和pb的初值分别指向两个表的第一个元素

    LC.length=LA.length+LB.length;	//新表长度为待合并两表的长度之和

    LC.elem=new ElemType[LC.length];	//为合并后的新表分配一个数组空间

    pc=LC.elem;		//指针pc指向新表的第一个元素

    pa_last=LA.elem+LA.length-1;	//指针pa_last指向LA表的最后一个元素

    pb_last=LB.elem+LB.length-1;	//指针pb_last指向LB表的最后一个元素

    while(pa<=pa_last &pb<=pb_last){	//两个表都非空

        if(*pa<=*pb)*pc++=*pa++;	//依次“摘取”两表中值较小的结点

        else *pc++=*pb++;

    }

    while(pa<=pa_last)*pc++=*pa++;//LB表已到达表尾，将LA中剩余元素加入LC

    while(pb<=pb_last)*pc++=*pb++;//LA表已到达表尾，将LB中剩余元素加入LC

}//MergeList_Sq

    $$\bf算法的时间复杂度是： $$$$O(ListLength(La) + Listlength(Lb))$$

​ $$\bf算法的空间复杂度是： $$$$O(ListLength(La) + Listlength(Lb))$$

  • 有序表的合并——链表实现


void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){

    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的头结点

}

$$\bf算法的时间复杂度是： $$$$O(ListLength(La) + Listlength(Lb))$$

案例分析与实现

  • 一元多项式的表示及相加（顺序存储结构）

​ $$线性表A=((7,0),(3.1)(9,8)(5,17))$$

​ $$线性表B=((8,1),(22,7),(-9,8))$$

算法步骤：

  1. 创建一个新数组c

  2. 分别从头遍历比较a和b的每一项

    ①指数相同，对应系数相加，若其和不为零，则在c中增加一个新项

    ②指数不相同，则将指数较小的项复制到c中

  3. 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

顺序存储结构存在问题

  1. 存储空间分配不灵活

  2. 运算的空间复杂度高

  • 一元多项式的表示及相加（链式存储结构）


typedef struct PNode{

    float coef;		//系数

    int	expn;		//指数

    struct PNode *next;//指针域

}PNode,*Polynomial;
多项式创建算法步骤：

①创建一个只有头结点的空链表。

②根据多项式的项的个数n,循环n次执行以下操作：

  • 生成一个新结点*s;

  • ·输入多项式当前项的系数和指数赋给新结点*s的数据域；

  • ·设置一前驱指针pre,用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；

  • ·指针q初始化，指向首元结点；

  • ·循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q

  • 将输入项结点s插入到结点q之前。

    
void CreatePolyn(Polynomial &P,int n){	//输入m项的系数和指数，建立表示多项式的有序链表P

    P=new PNode;

    P->next=NULL;	//先建立一个带头结点的单链表

    for(i=1;i<=n;++i){	//依次输入n个非零项

        s=new PNode;	//生成新结点

        cin>>s->coef>>s->expn;	//输入系数和指数

        pre=P;		//pre用于保存q的前驱，初值为头结点

        q=P->next;	//q初始化，指向首元结点

        while(q&&q->expn<s->expn){	//找到第一个大于输入项指数的项*q

            pre=q;q=q->next;

        }

        s->next=q;	//将输入项s插入到q和其前驱结点pre之间

        pre->next=s;

    }

}
多项式相加算法步骤：

  1. 指针p1和p2初始化，分别指向Pa和Pb的首元结点。

  2. p3指向和多项式的当前结点，初值为Pa的头结点。

  3. 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn),有下列3种情况：

    • 当p1->expn==p2->expn时，则将两个结点中的系数相加

      • 若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点

      • 若和为零，则删除p1和p2所指结点；

    • 当p1->expn<p2 ->expn时，则应摘取p1所指结点插入到"和多项式”链表中去；

    • 当p1->expn>p2->expn时，则应摘取p2所指结点插入到"和多项式”链表中去。

  4. 将非空多项式的剩余段插入到p3所指结点之后。

  5. 释放Pb的头结点。