C语言程序 单链表排序 ---- 直接插入法
1、ubuntu 14.04 linux c
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
2、#include <stdio.h>
#include <stdlib.h>
#define NUM_SIZE 20
typedef struct data_node{
int data;
struct data_node *next;
}s_link_list;
s_link_list * create_node(int value)
{
s_link_list *node = (s_link_list *)malloc(sizeof(s_link_list));
node->data = value;
node->next = NULL;
return node;
}
void add_node(s_link_list *head,s_link_list *node)
{
s_link_list *tmp = head;
while(tmp->next != NULL)
{
tmp = tmp->next;
}
tmp->next = node;
}
void print_list(s_link_list *head)
{
s_link_list *tmp = head;
printf("the single linklist:[head]->");
while(tmp->next != NULL)
{
printf("%d->",tmp->next->data);
tmp = tmp->next;
}
printf("[NULL]\n");
}
void free_list(s_link_list *head)
{
s_link_list *tmp = head,*r = NULL;
while(tmp !=NULL)
{
r = tmp->next;
free(tmp);
tmp = r;
}
}
void sort_list(s_link_list *head)
{
s_link_list *p = head->next,*q = NULL,*r = NULL; //p指向第一个数据节点
if(p != NULL) //单链表有一个或者以上的数据节点
{
r = p->next; //r 保存 *p节点信侨的直接后继节点的指针
p->next = NULL; 伟斤屈闲帽 //构造只含有一个数据节点的有序表
p = r;
while(p!=NULL)
{
r = p->next; //r 保存*p节点的直接后继节点的指针
q = head;
while(q->next != NULL && q->next->data < p->data)
q = q->next; //在有序表中查找插入*p的直接前驱节点*q的位置
p->next = q->next; //将*p插入到*q之后
q->next = p;
p = r; //扫描原单链表余下的节点
}
}
}
int main()
{
int i =0,j=0;
s_link_list *head = NULL,*tmp = NULL;
head = create_node(0);
for(i=0;i<NUM_SIZE;i++)
{
tmp = create_node(rand()%100);
add_node(head,tmp);
}
print_list(head);
sort_list(head);
printf("after insertion sort :\n");
print_list(head);
free_list(head);
return 0;
}
3、xxx@linux:~/code# gcc -o single_linklist single_linklist.c
xxx@linux:~/code# ./single_linklist
the single linklist:[head]->83->86->77->15->93->35->86->92->49->21->62->27->90->59->63->26->40->26->72->36->[NULL]
after insertion sort :
the single linklist:[head]->15->21->26->26->27->35->36->40->49->59->62->63->72->77->83->86->86->90->92->93->[NULL]