`
langzhe
  • 浏览: 288053 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

关于单连表插入后自动从小到达排序问题

    博客分类:
  • c
 
阅读更多

原题:来自http://learn.akae.cn/media/ch26s01.html

1、修改insert函数实现插入排序的功能,链表中的数据按从小到大排列,每次插入数据都要在链表中找到合适的位置再插入。在第 6 节 “折半查找”中我们看到,如果数组中的元素是有序排列的,可以用折半查找算法更快地找到某个元素,想一想如果链表中的节点是有序排列的,是否适用折半查找算法?为什么?
 
 
1、下面是从小到大的插入函数,里面用了两个if 和 (*head)->next = node; 才实现插入自动排序功能。 我想去掉  if(lnode->next == NULL){ 判断和(*head)->next = node;两块语句实现此功能。想了好久也没有实现,请各位指点。
2、我觉得不能用折半算法查找,因为但连表是从表头开始查找元素的。
 不知道是否正确。请各位给予答案。
 
插入算法:
 44 link insert(link lnode, char ch)
 45 {  
 46     link node = create_node(ch);   
 47     link *head;           
 48     if(lnode==NULL){      
 49         return node;      
 50     }
 51     if(lnode->next == NULL){
 52         if(lnode->element >= ch){      
 53             node->next = lnode;            
 54             return node;
 55         }
 56     }
 57     for(head=&lnode; (*head)->next; head=&(*head)->next){
 58         if((*head)->element >= ch){    
 59             node->next = *head;            
 60             head = &node;    
 61             return lnode;
 62         }
 63     }
 64     (*head)->next = node;
 65     return lnode;
 66 }
 67 

格式定义:
  5 typedef struct node *link;
  6 #include <stdio.h>
  7 struct node{
  8     char element;
  9     link next;
 10 };   

根据字符创建节点
 95 link create_node(char ch)
 96 {
 97     link p = malloc(sizeof *p);
 98     p->element = ch;
 99     p->next = NULL;
100     return p;
101 }
102 
 
 
 
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics