单链表实现冒泡排序
[cpp] view plain copy print ? /************************************************************************/ /* 用单链表实现冒泡排序，输入为0-9的数字字符 */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> #define PR printf //定义一个单链表结构体 typedef struct node{ long data; struct node * next; }lklist; //快速排序，小的数据往前排，后的数据往后排 lklist* sort(lklist * head) { if (head == NULL) return NULL; lklist* p = head->next; lklist* p_pre = p; bool flag = false; //用于标记是否有交换，当数组有序的时候，提高判断效率 while(p_pre->next != NULL) { long temp = p_pre->data; p = p->next; while (p) { if(temp <= (p->data)) { p = p->next; continue; } else { long temp_change; temp_change = p->data; p->data = p_pre->data; p_pre->data = temp_change; p = p->next; flag = true; } if (flag == false) { return head; } } p_pre = p_pre->next; p = p_pre; } return head; } //向含有一个头节点的单链表中插入数据 lklist* create_lklist(lklist *head) { PR("please input the number of the data and end with q(Q):\n"); while(1) { char ch[2]; scanf("%s",ch); if(ch[0] == 'q' || ch[0] == 'Q') //输入为q(Q)时停止输入 break; else { long intData = strtol(ch,0,10); lklist* temp = NULL; temp = (lklist*)malloc(sizeof(struct node)); temp->data = intData; temp->next = NULL; temp->next = head->next; head->next = temp; } } return head; } //打印单链表中的数据信息 void printf_lklist(lklist* head) { if (NULL == head) { return; } lklist * p = head->next; PR("the sorted number is:\n"); while (p) { PR("%d ",p->data); p = p->next; } PR("\n"); } //释放有数据的链表中的节点 void free_lklist(lklist* head) { if (NULL == head) { return; } lklist * p = head->next; lklist *pre; while (p) { pre = p; p = p->next; free(pre); } } void main() { lklist *head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; //头节点不存放数据 head = create_lklist(head); head = sort(head); printf_lklist(head); free_lklist(head); free(head); //释放申请的头节点 } /************************************************************************/ /* 用单链表实现冒泡排序，输入为0-9的数字字符 */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> #define PR printf //定义一个单链表结构体 typedef struct node{ long data; struct node * next; }lklist; //快速排序，小的数据往前排，后的数据往后排 lklist* sort(lklist * head) { if (head == NULL) return NULL; lklist* p = head->next; lklist* p_pre = p; bool flag = false; //用于标记是否有交换，当数组有序的时候，提高判断效率 while(p_pre->next != NULL) { long temp = p_pre->data; p = p->next; while (p) { if(temp <= (p->data)) { p = p->next; continue; } else { long temp_change; temp_change = p->data; p->data = p_pre->data; p_pre->data = temp_change; p = p->next; flag = true; } if (flag == false) { return head; } } p_pre = p_pre->next; p = p_pre; } return head; } //向含有一个头节点的单链表中插入数据 lklist* create_lklist(lklist *head) { PR("please input the number of the data and end with q(Q):\n"); while(1) { char ch[2]; scanf("%s",ch); if(ch[0] == 'q' || ch[0] == 'Q') //输入为q(Q)时停止输入 break; else { long intData = strtol(ch,0,10); lklist* temp = NULL; temp = (lklist*)malloc(sizeof(struct node)); temp->data = intData; temp->next = NULL; temp->next = head->next; head->next = temp; } } return head; } //打印单链表中的数据信息 void printf_lklist(lklist* head) { if (NULL == head) { return; } lklist * p = head->next; PR("the sorted number is:\n"); while (p) { PR("%d ",p->data); p = p->next; } PR("\n"); } //释放有数据的链表中的节点 void free_lklist(lklist* head) { if (NULL == head) { return; } lklist * p = head->next; lklist *pre; while (p) { pre = p; p = p->next; free(pre); } } void main() { lklist *head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; //头节点不存放数据 head = create_lklist(head); head = sort(head); printf_lklist(head); free_lklist(head); free(head); //释放申请的头节点 }