- /**
- * @todo c版基于链表的插入排序
- * @author Koma
- **/
- #include<stdio.h>
- #include<stdlib.h>
- typedef struct node{
- int data;
- struct node *next;
- }LNode, *LinkList;
- /**
- * 创建并初始化一个带头节点的链表
- **/
- LinkList init() {
- LinkList p, r, list;
- list = (LinkList)malloc(sizeof(LNode));
- list->next = NULL;
- int e;
- while ( scanf("%d", &e) != 0 ) {
- p = (LinkList)malloc(sizeof(LNode));
- p->data = e;
- p->next = NULL;
- if ( !list->next ) {
- list->next = p;
- } else {
- r->next = p;
- }
- r = p;
- }
- return list;
- }
- /**
- * 打印链表
- **/
- void printLink( LinkList l ) {
- LinkList q;
- q = l->next;
- while ( q->next != NULL ) {
- printf("%d ", q->data);
- q = q->next;
- }
- printf("%d\\n", q->data);
- }
- void innserSort( LinkList list1, LinkList q ) {
- int in; //标志量
- LinkList p, t, r;
- in = 0;
- r = p = list1;
- t = (LinkList)malloc(sizeof(LNode));
- t->next = NULL;
- t->data = q->data;
- if ( !p->next ) {
- p->next = t;
- } else {
- while ( p->next != NULL ) {
- r = p;
- p = p->next;
- if ( t->data > p->data ) {
- continue;
- } else {
- r->next = t;
- t->next = p;
- in = 1;
- break;
- }
- }
- //处理新链最后一个元素
- if ( !in ) {
- p->next = t;
- }
- }
- }
- /**
- * 实现插入排序
- **/
- LinkList sort( LinkList l ) {
- LinkList q, list1;
- list1 = (LinkList)malloc(sizeof(LNode));
- list1->next = NULL;
- q = l->next;
- while ( q->next != NULL ) {
- innserSort(list1, q);
- q = q->next;
- }
- //处理旧链最后一个元素
- innserSort(list1, q);
- return list1;
- }
- int main() {
- LinkList l, l1;
- l = init();
- printLink(l);
- l1 = sort(l);
- printLink(l1);
- printLink(l);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/120320149010.html
来源: http://www.codesnippet.cn/detail/120320149010.html