回 帖 发 新 帖 刷新版面

主题:两个有序链表合并问题,大家帮帮忙

解题思想:把第一个链表作为基链,结点指针p,q分别指向两个链表的头结点,           比较p->data和q->data的大小,要是p->data小的话p向后扫描,而要是q->data小的话就把结点q插入到结点p的后面.q向后扫描.最后检查第二个链表是否为空,否的话就把剩余结点插入第一个链表的结尾
template<typename Type>
void  List<Type>:: Merger( const List< Type > & hb )
{
    ListNode < Type > * p = first->link;
    ListNode < Type > * q = hb.first->link;
    ListNode < Type > * temp = first;
    ListNode < Type > * t;

    while ( p != NULL && q != NULL )
    {
        if ( p->data < q->data )
        {
            temp = p;
            p = p->link;
        }
        else
        {
            t = q;
            q->link = temp->link;
            temp->link = q;
            temp = q;
            q = t->link;
        }
    }
    while ( q != NULL )
    {
        temp->link = q;
        temp = q;
        q = q->link;
    }
        
}


int main(int argc, char* argv[])
{
    
        ListNode < float > * temp;
    List < float > flist, slist;
    float a[10];
    float b[10];
    int i;
    cout << "please enter 5 float number: " << endl;
    for ( i = 0; i < 5; i++ )
    {
        cin >> a[i];
    }
    for ( i = 0; i < 5; i++ )
    {
        temp = flist.CreateNode( a[i] );
        flist.InsertRear( temp );
    }
    flist.PrintList();

    cout << "please enter 5 other float number: " << endl;
    for ( i = 0; i < 5; i++ )
    {
        cin >> b[i];
    }
    for ( i = 0; i < 5; i++ )
    {
        temp = slist.CreateNode( b[i] );
        slist.InsertRear( temp );
    }
    slist.PrintList();

    cout << "two lists have mergered. " << endl;
    flist.Merger( slist );
    flist.PrintList();
    return 0;
}

但是执行程序后没有结果.请问这个是哪里出了问题了?(其它链表的基本操作没错,因为把这个函数注释后正常) 

回复列表 (共3个回复)

沙发

while ( p != NULL && q != NULL )
    {
        if ( p->data < q->data )
        {
            temp = p;
            p = p->link;
        }
        else
        {
            t = q;
            q->link = temp->link;
            temp->link = q;
            temp = q;
            q = t->link;
        }
    }
    while ( q != NULL )
    {
        temp->link = q;
        temp = q;
        q = q->link;
    }
        
   //应该考虑p的情况
 while ( p != NULL )
    {
        temp->link = p;
        temp = p;
        p = q->link;
    }

板凳

我是把第二个链表(q)的元素插入的第一个链表中(p),为什么还要再考虑p的情况呢?这点我有点不明白.

3 楼

不知道兄台你解决没有,
我来学习的,
我感觉有两个怀疑的地方:
1、解题思想,经我推断,你是升序排列的,而你所说“而要是q->data小的话就把结点q插入到结点p的后面.”这句话有点问题;
2、while ( p != NULL && q != NULL )// if ( p->data < q->data )//else
下“q->link = temp->link;”这句话不知道什么意思。
以上两点供参考。


我来回复

您尚未登录,请登录后再回复。点此登录或注册