首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

一个链表求集合并集交集的异常

2012-03-22 
一个链表求集合并集交集的错误请各位大侠帮我看一下怎么改:我要用单链表求两个链表的并集,交集C/C++ code/

一个链表求集合并集交集的错误
请各位大侠帮我看一下怎么改:
我要用单链表求两个链表的并集,交集

C/C++ code
//求并集的函数:void bingji(mylist*p,mylist*q,mylist*&r)//r作为并集列表的头指针,p,q是输入的两个指针{    mylist *k,*m;    r=new mylist;    m=r;    for(;p;)//把一个集合的值复制到    {        m->data=p->data;        k=new mylist;        m->next=k;        p=p->next;        m=m->next;    }            //下面要把q中有的且r中没有的元素添加到r中    for(;q;)    {        m->data=q->data;        k=new mylist;        m->next=k;        q=q->next;        m=m->next;                    }    delete k;    m->next=NULL;}//求交集的函数:void jiaoji(mylist*p,mylist*q,mylist*&r)//这样做的话会虽然能求出正确的交集,但是会导致破坏原链表{    mylist *m,*n,*k;    mylist *temp;//用于存放前一个节点的地址    r=new mylist;    m=r;    n=q;    int i=-1;    for(;p;)    {        for(;q&&-1==i;)        {            if(p->data==q->data)            {                k=new mylist;                m->data=p->data;                m->next=k;                m=m->next;                i=0;                if(q==n)                {                    q=q->next;                    n=q;                                    }                                    else                {                    temp->next=q->next;                    q=q->next;                }            }            else            {                temp=q;                q=q->next;            }        }        i=-1;        p=p->next;        q=n;    }    delete k;    m->next=NULL;}


如果我只是求两个链表的并集是正常的,原链表的输出也是正常的。

错误出现在,如果在main函数里调用
bingji(list1,list2,list3);
jiaoji(list1,list2,list4;
printlist(list3);//原链表list1,原链表list2,并集链表list3,交集链表list4
printlist(list4);
printlist(list1);
printlist(list2);
   
这时候并集输出的结果不对,交集输出的结果是正确的,链表list2也被破坏了,输出也不对。注释掉求交集函数jiaoji()之后又恢复正常。
求并集明明在求交集之前,求交集不应该影响链表list3才对啊。

求大侠解释。

[解决办法]
这样复杂度明显是O(A*B)
求交集理想的复杂度是A+B,用哈希.

热点排行