onelink_merge.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <stdlib.h>                    //包含rand函数
#include "Onelink.h"                   //单链表类

void insert_sorted(Onelink &h1,int k); //k值插入已排序的单链表h1
void insertsort(Onelink &h1,int n);    //n个随机值插入构成已排序的单链表h1

void mergelink(Onelink &h1,Onelink &h2)
{                                      //归并两条已排序的单链表
    if(h2.head==NULL)
        return;
    if(h1.head==NULL)
    {
        h1.head=h2.head;               //h1.head指向已排序单链表
        h2.head=NULL;                  //h2为空链表返回
        return;
    }
    OnelinkNode *p,*q,*t;
    p=h1.head;                         //p在h1链表中移动
    q=h2.head;                         //q在h2链表中移动 
    if(p->data > q->data)              //比较两个单链表第1个结点的值
    {
        q=h1.head;
        p=h2.head;
        h1.head=h2.head;               //h1.head仍指向第1个结点值较小的单链表
    }
    while(p!=NULL && q!=NULL)
    {
        if(p->data <= q->data)
        {
            t=p;
            p=p->next;
        }
        else
        {
            t->next=q;
            q=q->next;
            t=t->next;
            t->next=p;
        }
    }
    if(q!=NULL)                        //另一链表中多余结点并入h1.head链表之尾
        t->next=q;
    h2.head=NULL;                      //h2中的结点已全部归并到h1中，h2为空链表
}

void main()
{
    Onelink h1,h2;                     //声明并创建空的单链表
    insertsort(h1,5);
    cout<<"h1  ";  h1.output();        //输出单链表
    insertsort(h2,4);
    cout<<"h2  ";  h2.output();

    cout<<"两链表归并后:\n";
    mergelink(h1,h2);                  //归并两条已排序的单链表
    cout<<"h1  ";  h1.output();
    cout<<"h2  ";  h2.output();
}

/*
程序运行结果如下：
insert :  41  67  34  0  69  
h1  Onelink:  0  34  41  67  69  
insert :  24  78  58  62  
h2  Onelink:  24  58  62  78  
两链表归并后:
h1  Onelink:  0  24  34  41  58  62  67  69  78  
h2  Onelink:  
*/

void insert_sorted(Onelink &h1,int k)  //k值插入已排序的单链表h1
{                                      //引用类型参数
    OnelinkNode *t=new OnelinkNode(k); //创建k值结点t
    if(h1.head==NULL)                  //空表插入
        h1.head=t;                     //改变单链表的头指针
    else
    {   
        if(k<=h1.head->data)           //表头插入
        {
            t->next=h1.head;
            h1.head=t;                 //改变单链表的头指针
        }
        else                           //表中、表尾插入
        {
            OnelinkNode *p,*q=h1.head; //查找t应插入的位置
            while(q!=NULL && k>q->data)
            {
                p=q;                   //p是q的前驱结点
                q=q->next;
            }
            t->next=p->next;           //将t插入在p结点之后
            p->next=t;
        }
    }
}

void insertsort(Onelink &h1,int n)     //n个随机值插入构成已排序的单链表h1
{
    cout<<"insert :  ";
    for(int i=0;i<n;i++)
    {
        int k=rand()%100;              //C++Builder方式为 k=random(100);
        cout<<k<<"  ";
        insert_sorted(h1,k);           //k值插入已排序的单链表
    }
    cout<<endl;
}