onelink_insert.cpp

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

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

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;
}

void main()
{
    Onelink h1;                        //声明并创建空的单链表
    insertsort(h1,8);
    h1.output();                       //输出单链表
}
/*
程序运行结果如下：
insert :  41  67  34  0  69  24  78  58  
Onelink:  0  24  34  41  58  67  69  78  
*/