链表插入并自动排序操作思考

链表插入并自动排序操作思考

修改insert函数实现插入排序的功能，链表中的数据按从小到大排列，每次插入数据都要在链表中找到合适的位置再插入。在第 6 节 “折半查找”中我们看到，如果数组中的元素是有序排列的，可以用折半查找算法更快地找到某个元素，想一想如果链表中的节点是有序排列的，是否适用折半查找算法？为什么？

 

1、插入并排序
 64 link insert(link lnode, char ch)
 65 {
 66     link node = create_node(ch);
 67     link *head;
 68     if(lnode==NULL){
 69         return node;
 70     }
 71     if(lnode->next == NULL){
 72         if(lnode->element >= ch){
 73             node->next = lnode;
 74             return node;
 75         }
 76     }
 77     for(head=&lnode; (*head)->next; head=&(*head)->next){
 78         if((*head)->element >= ch){
 79             node->next = *head;
 80             *head = node;   
 81             return lnode;
 82         }
 83     }
 84     (*head)->next = node;
 85     return lnode;
 86 }                                                                                                         
 87
关于链表折半查找 这里讨论过https://groups.google.com/forum/?fromgroups=#!topic/pongba/zYbhezWyIhI

2、 例1中 有两个if判断,我想去掉第二个，所以有了下面改写，并干脆全去掉了，这时如果lnode为空肯定直接over了

引入了一个link tail,每次遍历是记住当前*head地址，
当没有比ch大的元素，就 tail->next = node;   
 43 link insert(link lnode, char ch)
 44 {
 45     link node = create_node(ch);
 46     link *head;                                                                                           
 47     link tail;
 48     printf("ch=%c\n", ch);
 49     for(head=&lnode; *head; head=&(*head)->next){
 50         tail = *head;
 51         if((*head)->element >= ch){
 52             printf("ch=%c\n", ch);
 53             node->next = *head;
 54             *head = node;   
 55             return lnode;
 56         }  
 57     }  
 58     tail->next = node;
 59     return lnode;
 60 }  
 61

3、例2是需要返回值的，下面是参数取地址，不需要返回值的实现
 47 void insert(link *list, char ch)
 48 {
 49     link head = malloc(sizeof(head));
 50     head->element = ch;  
 51     link *p = list;      
 52     link tail;           
 53     for(; *p; p=&(*p)->next){
 54         tail = *p;       
 55         if((*p)->element > head->element){
 56             head->next= (*p);
 57             *p = head;   
 58             return;      
 59         }
 60     }
 61     tail->next = head;
  }

4、补充更简单的写法，由liuxinyu帮助
 50 void insert(link *list, char ch)
 51 {   
 52     link head = malloc(sizeof(head));
 53     head->element = ch;
 54     link *p = list;
 55     for(; *p && (*p)->element < ch ; p=&(*p)->next);
 56     head->next = *p;
 57     *p = head;
 58 }
5、相关数据定义
  3 typedef struct node *link;
  4 struct node
  5 {
  6     char element;
  7     link next;
  8 };
  9