您当前的位置:首页 > 计算机 > 编程开发 > C语言

从A和B两个单链表的公共元素中产生单链表C

时间:01-03来源:作者:点击数:

问题描述:

设A和B是两个单链表(带头结点),其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C,要求不破坏A、B的结点。

问题解答:

算法思想:尾插法建立单链表C,由于算法要求不破坏A、B的结点,所以,需要通过比较复制的方式产生单链表C。

void Get_Common (LinkList A, linkList B) {
    //本算法产生单链表A和B的公共元素的单链表C
    LNode *p=A->next,*q=B->next,*r,*s;
    LinkList C=(LinkList)malloc(sizeof(LNode)) ; //建立表 C
    r=C;  //r始终指向C的尾结点
    while (p!=NULL && q!=NULL) {    //循环跳出条件
        if(p->data<q->data)
            p=p->next;  //若A的当前元素较小,后移指针
        else if(p->data>q->data)
            q=q->next;  //若B的当前元素较小,后移指针
        else{  //找到公共元素结点
            s=(LNode *)malloc(sizeof(LNode));
            s->data=p->data;  // 复制产生结点 * s
            r->next=s; r=s;  //将*s链接到C上(尾插法)
            p=p->next;  //表A和B继续向后扫描
            q=q->next;
        }
    }
    r->next=NULL;  //置C尾结点指针为空
}

 

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门