1 /***************************************************************2 程序作者：yin3 创建日期：-2-164 程序说明：链表冒泡，与数组冒泡不同的是交换与移动需要三个指针的协5 作，即三交换与三移动，并且交换与移动过程要验证合法性，防止指针指6 歪了。程序可做通用修改，替换sort()中节点类型Node与节点的键值data，7 外部给sort()传指针地址即可使用。8 ***************************************************************/
9 /***************************************************************10 修改作者：yin11 修改日期：-2-1712 修改说明：13 1.完善调试显示与注释14 后续改进：暂无15 ***************************************************************/
16 #include
17 #include
18 typedef structNODE19 {20 intdata;21 struct NODE *next;22 }Node;23 void sort(Node **h)24 {25 //操纵*h与head等效
26 Node* left=NULL;27 Node* cur=NULL;28 Node* right=NULL;29 //每趟冒泡都有一个变动的尾部tail
30 for(Node* tail=NULL;tail!=(*h)->next;)//(*h)->next指向的是第二元素，当tail指向第二元素整个程序终止
31 {32 //每趟冒泡排序的开始点33
34 //printf("此趟冒泡排序开始......\n");//#####调试显示#####35 //每趟冒泡起点初始化，都是从第一个点开始的
36 left=NULL;37 cur=*h;38 right=cur->next;39 while(1)40 {41 if(cur->data > right->data)//逆序,三交换
42 {43 //printf("now exchange (%2d) and (%2d)\n",cur->data,right->data);//#####调试显示#####44 //交换
45 cur->next=right->next;46 right->next=cur;47 if(left==NULL) *h=right;48 else left->next=right;;49 //纠正
50 cur=right;51 right=right->next;52 //printf("after exchange (%2d) and (%2d)\n",cur->data,right->data);//#####调试显示#####
53 }54 if(right->next!=tail)//三移动为下一次做准备
55 {56 if(left!=NULL) left=left->next;57 else left=cur;58 cur=cur->next;59 right=right->next;60 }61 else break;62 }63
64 tail=right; //一个变动的尾部65
66 //每趟冒泡排序的结束点67
68 //#####调试显示#####
69 /*printf("此趟冒泡排序的结果\n");70 for(Node *p=*h;p!=NULL;p=p->next)71 printf("(%2d) ",p->data);72 printf("\n");*/
73 }74 }75 intmain()76 {77 Node *head=NULL;78 int dataarray[10]={6,9,8,3,10,5,4,7,2,1};79
80 Node*pt=NULL;81 for(int i=0;i<10;i++)82 {83 //开空间,需要引用 stdlib.h
84 Node *temp=(Node*)malloc(sizeof(Node));85 temp->data=dataarray[i];86 temp->next=NULL;87 //连接
88 if(i==0)89 {90 head=temp;91 pt=temp;92 }93 else
94 {95 pt->next=temp;96 pt=pt->next;97 }98 }99 printf("--------------------------------------------------------------------\n");100 printf("初始数据序列：\n");101 for(Node *p=head;p!=NULL;p=p->next)102 printf("(%2d)",p->data);103 printf("\n");104 printf("--------------------------------------------------------------------\n");105
106 sort(&head);//测试sort
107
108 printf("--------------------------------------------------------------------\n");109 printf("链表冒泡结果：\n");110 for(Node *p=head;p!=NULL;p=p->next)111 printf("(%2d)",p->data);112 printf("\n");113 printf("--------------------------------------------------------------------\n");114 }
