标题

[笔试经验]C++实现单链表的排序

责任编辑:admin
日期:2012-12-03

面试题中对单链表的考察非常多,基本的问题都要自己实现一遍,比如需要对单链表的排序。

因为单链表不能按照下表索引访问元素,因此不能够进行远程交换排序、或者动态分治法排序,能想到的只是相邻元素交换的冒泡排序。

代码:

  1. #include <iostream> 
  2. using namespace std; 
  3.  
  4. /* 
  5. * 编程实现单链表的排序 
  6. */ 
  7. typedef struct Student{ 
  8.     int data; 
  9.     struct Student *next; 
  10. }node; 
  11.  
  12. //获取单链表的长度 
  13. int lenList(node* head){ 
  14.     if(head==NULL) return 0; 
  15.     node *p = head; 
  16.     int sum=0; 
  17.     while(p!=NULL){ 
  18.         sum+=1; 
  19.         p=p->next; 
  20.     } 
  21.     return sum; 
  22.  
  23. //对单链表排序,因为单链表不能随机访问,只能相邻交换 
  24. void sortList(node* head){ 
  25.     int len = lenList(head); 
  26.     cout<<"len:"<<len<<endl; 
  27.     if(len==0) return
  28.     node *p = head; 
  29.     for(int i=1; i<len; ++i){ 
  30.         //i表示冒泡的次数,共len-1次 
  31.         p = head; 
  32.         for(int j=0; j<len-i; j++){ 
  33.             //j表示下落的数目 
  34.             if(p->data < p->next->data){ 
  35.                 int tmp = p->data; 
  36.                 p->data = p->next->data; 
  37.                 p->next->data = tmp; 
  38.             } 
  39.             p=p->next; 
  40.         } 
  41.     } 
  42.  
  43. void printList(node* head){ 
  44.     node *p = head; 
  45.     cout<<"List:"<<endl; 
  46.     while(p!=NULL){ 
  47.         cout<<p->data<<" "
  48.         p=p->next; 
  49.     } 
  50.     cout<<endl; 
  51.  
  52. void main(){ 
  53.     int arr[10] = {3,4,9,1,5,2,8,0,6,7}; 
  54.     node* head = (node*)malloc(sizeof(node)); 
  55.     head->data = arr[0]; 
  56.     head->next = NULL; 
  57.  
  58.     node *p = NULL; 
  59.     for(int i=1; i<10; ++i){ 
  60.         p = (node*)malloc(sizeof(node)); 
  61.         p->data = arr[i]; 
  62.         p->next = head->next; 
  63.         head->next = p; 
  64.     } 
  65.     printList(head); 
  66.     sortList(head); 
  67.     printList(head); 
  68.     system("pause"); 

运行结果:

 

阅读:

相关新闻:
评论