//////////////////////////////////////////////  <算法 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;}

评论