////////////////////////////////////////////
//  <算法 i~iv>
// 
//  Exercise : 3.41  , Page : 75
//  exercise description:
//   实现程序3.11的一个使用头节点的版本
//  
//   P.S : 有时候不使用哑元节点确实麻烦
//  zhaoyg   2008.1.24
////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct node
{
    int item;
    node *next;
   
    node(int x,node *t)
    {
        item=x;
        next=t;
    }
};

int main()
{
 ofstream outf;
 outf.open("result.txt");

    node *head_a=NULL;
    node *a=NULL , *t;
    node *temp;

 srand( (unsigned)time( NULL ) );

    for (int i=0;i<50;i++)
 {
  if (head_a==NULL)
  {
   head_a=new node(rand()%100,0);
   t=head_a;
  }
  else
  {
   t=(t->next=new node(rand()%100,0));
  }
 }

 outf << "original data\n";

 for (temp=head_a ;temp != 0;temp=temp->next )
  outf << temp->item <<",";
   
    node *head_b;
    node *mark;

 head_b = head_a;
 t = head_a->next;
 head_a->next = 0;

 while ( t != 0)
 {
  mark=t->next;

  for (temp=head_b;temp->next!=0;temp=temp->next)
   if(t->item < temp->item)
    break;

  if ( t->item < temp->item )
  {
   if ( temp==head_b )
   {
    t->next=head_b;
    head_b=t;
   }
   else
   {
    node *u;
    for (u=head_b ; u->next!=temp;u=u->next) ;

    t->next=u->next;
    u->next=t;
   }
  }
  else
  {
   t->next=temp->next;
   temp->next=t;
  }

  t=mark;
 }

 outf <<"\nsorted\n";
 for (temp=head_b ; temp != 0 ; temp=temp->next )
  outf << temp->item <<",";
 outf.close();

    return 0;
}

评论