链表插入并自动排序操作思考
修改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
相关推荐
创建链表插入删除创建链表插入删除创建链表插入删除
数据结构 作业 链表的操作 完美链表 包括链表的 构造 数值的插入 删除 几种排序。。。。
快速排序、倒序输出链表、链表插入排序、插入排序
链表结点插入算法
链表的删除、插入、查询操作,另有相关的对于链表的操作的讲解。
编写算法实现:在一个非递减有序链表中,插入一个值为x的元素,使插入后的链表仍为非递减有序。
c++用链表实现插入删除,排序,数据结构的实验,希望你能用到
链表的插入和删除源代码,配套设计报告书使用,地址为:http://download.csdn.net/detail/sinat_28157861/8695229
链表的插入删除 c语言版链表 删除 插入 c语言
很详细的链表插入与删除代码,已经调试过的
用c++实现链表的建立、插入和删除操作。希望能对刚学数据结构的同学有点帮助。
双向链表的插入删除以及判断是否对称 建立有序双向链表并有序插入
链表的基本操作插入查询删除 算法思想: 先初始化单链表,然后建立单链表。 建立输出函数,用于输出链表中各个元素的值 建立查找函数,用于查找链表中是否有这个元素 建立插入函数,用于在链表中有序地插入输入的一...
C语言 双链表 插入指定位置查证 可扩展
《数据结构》链表的插入和删除操作,功能完善,希望能给大家带来学习上的帮助!
数据结构经典算法演示,这里是链表-插入节点的代码演示
单链表的插入动画,是gif格式。很形象解释了单链表节点的插入
2、 提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、 接收键盘录入的一系列整数(例10,25,8,33,60)作为节点的元素值,创建链表。输出链表内容。 4、 输入一个整数(例33),在链表...
完整的C语言数据结构学习课件 讲的很详细 很不错哦
链表的插入,通过对链表的遍历查询来进行堆链表插入。