学步园

前文链接：http://www.cnblogs.com/pmer/archive/2012/11/22/2783672.html

【样本】 

 

　　　　——陈良乔 ，《C程序设计伴侣》，人民邮电出版社，2012年10月，p237

【评析】

　　实际上谭浩强的书讲到了链表的查找、删除和插入。这一点要实事求是，不能因为谭书有大量错误就不顾事实。

【样本】

 

　　　　——陈良乔 ，《C程序设计伴侣》，人民邮电出版社，2012年10月，p237

【评析】

　　所谓“最常见的一个处理就是对链表中的数据进行排序”纯属无稽之谈。事实上对链表排序，多半是一个没有意义的问题。因为链表在建立时可以很容易建成有序的。譬如，对前文中建立链表的代码，只要稍微修改一下insert()函数并提供一个用于比较的lessthan()函数就可以轻而易举地实现建立有序链表的功能。

int lessthan ( data_t * , data_t * );

int lessthan ( data_t *pd1 , data_t *pd2 )
{
   return pd1->score < pd2->score ;
}

void insert( node_t ** p_next ,  node_t * p_node)
{
   if( ( * p_next == NULL ) || lessthan ( &p_node -> item , &(* p_next)-> item) )
   {
      p_node->next = * p_next ;
      * p_next = p_node ;
   }
   else
   {
      insert (  &(* p_next)->next  ,  p_node ) ;
   }
}

　　既然建立链表时可以轻易地把链表建成有序的，而且相对于数组来说链表付出了额外存储链接指针的代价，那么在建立时不考虑顺序问题，而在链表建立之后再对链表排序就显得是没事找事了。因此对链表排序在很大程度上是一个没有意义的问题。所以，绝大部分讲解算法的书籍都只关注数组的排序问题，从来不考虑链表的排序问题。

　　但是考虑到结点的数据部分可能由多个数据项组成，由于在建立链表时只能根据一个数据项排序，如果问题要求在链表建立后再根据另一个数据项进行排序，那么这种链表的排序问题也许会稍微有点意义。

　　但是选择冒泡法对链表排序则属于荒谬之举。因为冒泡法排序基本上是通过反复交换数据实现的，而交换则通常是在数组排序中一种不得已的选择。在数组中数据是一个挨一个紧密排放的，有点像一排人满满登登地挤在一张大通铺上，改变任何一个元素的位置都必然涉及到其他的元素位置的改变，所以有时只能通过交换这种手段来改变元素的位置。但是链表则与数组截然不同，链表的结点可以很容易地拿出来并插入到其他位置，但是交换对于链表来说则是笨重无比的一个操作。因此选择以交换为主的算法对链表排序有点像选择用饭桶吃饭，方法也许可行但却非常不智。

【样本】

 

　　　　——陈良乔 ，《C程序设计伴侣》，人民邮电出版社，2012年10月，p237

【评析】

　　这个函数充分说明了下面这种数据结构的设计为什么非常幼稚。

 

 //定义表示学生信息结点的结构体
typedef struct _student
 {
   char name[20];
   float score;
   //定义指向链表中下一个结点的指针 
   struct _student* next;
}student;

 

　　首先swap()函数交换的是两个结点数据项部分，但却不得不把两个参数写成了指向结点的student *类型，名不副实。而如果设计成

 

typedef struct 
{
   char name[20];
   float score;
}
student_t;
  
typedef struct node
{
   student_t data;
   //定义指向链表中下一个结点的指针  
   struct node * next;
}node_t;

 

　　则可以名副其实地把swap()的两个参数写成指向结点中数据的student_t *类型。

　　其次，在后一种方案下，swap()可以简单地写为

 

void swap(student_t * ps1 , student_t * ps2)
{
   student_t temp = *ps1;
   *ps1 = *ps2 ;
   *ps2 = temp ;
}

 

 　　而且这种方案没有维护方面的后顾之忧，即使student_t类型有所改动，这个函数也不需要做任何改动。

【样本】

 

 

 

　　　　——陈良乔 ，《C程序设计伴侣》，人民邮电出版社，2012年10月，p237~238 

【评析】

　　这个函数有一个显而易见的错误，就是当head为NULL亦即对空链表排序时，因为

 

student *next = node->next ;

 

中的node->next是一个无意义的运算而可能引起程序崩溃。显然这是因为作者把while语句写成了do-while语句所致。

　　前面说过，这种交换结点数据的办法对链表来说非常笨拙，因此作者给出了另一种写法。

【样本】

 

 

　　　　——陈良乔 ，《C程序设计伴侣》，人民邮电出版社，2012年10月，p237~238

【评析】

　　这里的sort()函数居然居然用了6个变量操作链表。函数结构也极其复杂，乱作一团，惨不忍读，比前一个写法更烂。这种函数是废品，根本不值得细看。尽管如此，这里还是提一下其中明显的错误和瑕疵。

　　在这个函数的do-while语句中的

 

student *next = node->next ;

 

　　在head==NULL时是没有意义的，可能会导致严重的错误。

　　一个明显的瑕疵是内层循环中的if语句

 

if(cmp(node,next))
{
 /*……*/
 next = node->next;
}
else
{
 /*……*/
 next = node->next;
}

 

　　为什么会把代码写得如此混乱不堪呢？很大一部分原因就在于使用冒泡法对链表排序。

　　链表有很多好的性质，比如可以很方便地删除、插入一个结点而不用移动其他结点，可以很很容易地建立一个有序的链表，但是却不适宜交换结点。用冒泡法对链表排序是用链表做链表所不适宜的操作，这就像抱着饭桶吃饭一样，必然会把自己弄得手忙脚乱、狼狈不堪。

　　如果真的确实需要对链表排序的话，其实倒是把链表的结点一个一个拆下来，然后按照有序的方式重新建立链表更容易。这看起来仿佛是一种“异地”排序，但是由于链表本身的特点，这样其实并不需要额外的内存空间。

【重构】

 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//----------通用函数---------------------//
void *my_malloc( size_t );
//--------------------------------------//


//----------“数据”类型----------------//
typedef 
   struct
   {
      char name[20];
      float score;
   }
data_t;
//-----------关于“数据”的函数-----------//
int  input  ( data_t * ) ; 
void output ( data_t * ) ; 
int lessthan_score ( data_t * , data_t * );
int lessthan_name ( data_t * , data_t * );
//---------------------------------------//


//---------“结点”类型------------------//
typedef 
   struct node
   {
      data_t item ;
      struct node *next ;
   }
node_t;
//--------“链表”操作函数---------------//
void create( node_t ** , int (*) ( data_t * , data_t * ));
void insert( node_t ** ,  node_t * , int (*) ( data_t * , data_t * ) );
void print ( node_t * );
void sort( node_t ** , int (*) ( data_t * , data_t * ) );
//--------------------------------------//


int main( void )
{
   node_t *head = NULL ; //空链表
   
   puts("建立一有序链表");
   create( &head , lessthan_score ); 
   
   //测试 
   puts("输出链表");
   print( head );
   
   //按姓名排序
   sort( &head , lessthan_name ); 
   print( head );   

   return 0;
}

//-------通用函数定义-------------------//
void *my_malloc( size_t size )
{
   void *p = malloc( size );
   if( p == NULL )
   {
      puts("内存不足");
      exit(1); 
   }   
   return p;
}
//--------------------------------------//

//---------“数据”操作函数定义---------//
int input ( data_t *p_data )
{
   puts("请输入姓名、成绩：");
   if( scanf( "%20s%f" , p_data->name , &p_data->score ) != 2 ) //20很重要 
   {
      while( (getchar()) != '\n' ) //清空输入缓存 
         ;
      return 0 ;   
   }
   return !0 ;
}

void output ( data_t *p_data )
{
   printf ("姓名：%s 成绩：%.2f\n" , p_data->name , p_data->score  ) ;
}

int lessthan_name ( data_t *pd1 , data_t *pd2 )
{
   return strcmp ( pd1->name , pd2->name ) < 0 ;
}

int lessthan_score ( data_t *pd1 , data_t *pd2 )
{
   return pd1->score < pd2->score ;
}

//--------------------------------------//


//----------“链表”操作函数定义--------//

void print( node_t *p_node )
{
   if( p_node != NULL )
   {
      output ( &p_node->item ); 
      print( p_node->next );
   }
}

void sort(  node_t **p_next , int (*less) ( data_t * , data_t * ) )
{
   node_t * new_head = NULL ;
   node_t * temp  ;

   while( (temp = *p_next) != NULL )       //记录第一个结点 
   {
      *p_next = (*p_next)->next ;          //切下一个结点 
      insert ( &new_head , temp , less );  //将切下的结点插入到新链表 
   }
   
   *p_next = new_head ;
}

void insert( node_t ** p_next ,  node_t * p_node , int (*less) ( data_t * , data_t * ) )
{
   if( ( * p_next == NULL ) || less ( &p_node -> item , &(* p_next)-> item) )
   {
      p_node->next = * p_next ;
      * p_next = p_node ; 
   }
   else
   {
      insert (  &(* p_next)->next , p_node , less ) ;
   } 
}
 
void create( node_t **p_next , int (*less) ( data_t * , data_t * ))
{
   data_t data;

   if( input ( & data ) != 0 )
   {
      node_t *p_node = my_malloc( sizeof (*p_node) );
      p_node->item = data ;
      insert( p_next , p_node , less);//插入结点
      create( p_next , less );        //继续 
   }
}
//--------------------------------------//