方法:1.创建一个含原单链表第一个节点的临时链表2.从第二个元素开始插入,在临时链表中查找该元素的直接前驱节点。3.将节点插入直接前驱节点的后面。
方法/步骤
1ubuntu 14.04 linux cgcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
2#include #include #define NUM_SIZE 20typedef 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
3xxx@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]