onelink_select.cpp

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

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

void createRand(Onelink &h1,int n)     //单链表中头插入n个随机数
{
    for(int i=0;i<n;i++)
    {
        int k=rand()%100;
        OnelinkNode *q=new OnelinkNode(k);
        q->next=h1.head;               //q结点插入head结点之前
        h1.head=q;                     //head指向新的链首结点
    }
}

void selectsort(Onelink &h1)           //单链表的直接选择排序
{
    OnelinkNode *sortedhead=NULL,*sortedrear=NULL;
    OnelinkNode *p=NULL,*q=NULL,*min=NULL,*minprior=NULL;
    do
    {
        min=h1.head;
        p=h1.head->next;
        q=h1.head;
        while(p!=NULL)
        {   
            if(p->data < min->data)    //比较,min记住最小值位置
            {
                minprior=q;            //minprior是min的前趋结点
                min=p;
            }
            q=p;                       //q是p的前趋结点
            p=p->next;
        }    
        cout<<"min="<<min->data<<"    ";
        if(min==h1.head)               //从head链表中删除min结点
            h1.head=h1.head->next;
        else
            minprior->next=min->next;
        min->next=NULL;
                                       //在已排序链表中插入min结点
        if(sortedhead==NULL)
            sortedhead=min;            //头插入
        else
            sortedrear->next=min;      //尾插入
        sortedrear=min;
        h1.output();                   //输出单链表
    }while(h1.head!=NULL);
    cout<<endl;
    h1.head=sortedhead;                //head重新指向已排序单链表
}

void main()
{
    Onelink h1(2);                     //声明并创建单链表
    createRand(h1,6);
    h1.output();                       //输出单链表
    selectsort(h1);
    cout<<"SelectSort!   ";
    h1.output();
}
/*
程序运行结果如下：
Onelink:  24  69  0  34  67  41  1  2  
min=0     Onelink:  24  69  34  67  41  1  2  
min=1     Onelink:  24  69  34  67  41  2  
min=2     Onelink:  24  69  34  67  41  
min=24    Onelink:  69  34  67  41  
min=34    Onelink:  69  67  41  
min=41    Onelink:  69  67  
min=67    Onelink:  69  
min=69    Onelink:  

SelectSort!   Onelink:  0  1  2  24  34  41  67  69  

*/