数据结构3-----线性表

例1

设计算法，将两个安置递增有序的单链表合并成一个安置递增有序的单链表。

代码实现

void ListMerge(LinkList LA,LinkList LB,LinkList &LC){
    LinkList lc=LC,la=LA->next,lb=LB->next;

    while(la&&lb){
        if(la->date<lb->date){
            lc->next=la;
            lc=la;
            la=la->next;
        }
        else{
            lc=lb->next;
            lc=lb;
            lb=lb->next;
        }
        if(la)
            lc->next=la;
        if(lb)
            lc->next=lb;
    }
}

例2

设L为一带有头结点的循环单链表，链表中存储一组无序的整数，设计算法，将链表中的结点分成分别由P,Q指向的带有头结点的一个奇数循环单链表和一个偶数循环单链表。

代码实现

void ListSplit(LinkList L,LinkList &P,LinkList &Q){
    LinkList pre1,pre2,pre3;
    pre1=L->next;
    pre2=P;
    pre3=Q;

    while(pre1!=L){
        if(pre1->date%2){
            pre2->next=pre1;
            pre2=pre1;
        }
        else{
            pre3->next=pre1;
            pre3=pre1;
        }
        pre1=pre1->next;
    }

    pre2->next=P;
    pre3->next=Q;
}

例3

设计算法，将带有头结点的链表就地逆置。

代码实现

void ListReverse1(LinkList &L){  //method one
    LinkList p=L->next,q;
    L->next=NULL;

    while(p){
        q=p;
        p=p->next;
        q->next=L->next;
        L->next=q;
    }
}

void ListReverse2(LinkList &L){  //method two
    LinkList p,q,r;
    p=L->next;
    q=NULL;

    while(p){
        r=q;
        q=p;
        p=p->next;
        q->next=r;
    }
    L->next=q;
}