利用冒泡法对单链表进行排序需要交换两个相邻结点，利用二级指针可以很方便地解决结点交换的问题
下面我们生成一个链表，每个结点储存一个随机值，然后对该链表进行排序。其中排序算法的实现过程也同时实现了相邻两个结点的交换。
#include < stdio.h >
#include < stdlib.h >
#include < time.h >
#define FALSE 0
#define TRUE 1
typedef struct NODE{ //链表节点的结构体声明
struct NODE *link;
int value;
}Node;
int sort(register Node **head,int length); //排序函数的原型声明
int main(void)
{
int i; //利用i控制循环次数
Node *head=(Node *)malloc(sizeof(Node)); //申请头结点并让头指针指向头结点
Node *p=head; //利用p使当前结点与新节点相连接
srand( (unsigned)time( NULL ) );
for(i=0;i<20;i++) //单链表创建
{
p->value=rand()0+1; //生成1~100的随机数
p->link=(Node *)malloc(sizeof(Node)); //使当前结点与新节点相连
p=p->link; //p指向新节点
}
p->value=rand()0+1; //对尾结点赋值
p->link=NULL;
p=head;
printf("排序前储存的数值为："); //打印排序前链表储存的数值
while(p!=NULL)
{
printf("%d ",p->value);
p=p->link;
}
sort(&head,20); //调用排序函数对链表排序
p=head;
printf("\n排序后储存的数值为："); //打印排序后链表储存的数值
while(p!=NULL)
{
printf("%d ",p->value);
p=p->link;
}
free(head);
return 0;
}
int sort(register Node **head,int length) //定义三个二级指针实现结点交换
{
register Node **prior=head;
register Node **current=&((*prior)->link);
register Node **later=&((*current)->link);
Node *temp1;
Node **temp2;
int i;
for(i=0;i
{
while(later!=NULL)
{
if((*prior)->value>(*current)->value)
{
temp1=*prior; //实现结点交换
*prior=*current;
*current=*later;
*later=temp1;
temp2=current; //调整三个指针的位置
current=later;
later=temp2;
}
if(*later==NULL) //最后一次交换已完成，*later为NULL，不能执行下面代码，故结束循环
{
break;
}
later=&((*later)->link); //三个指针均向后移动一个结点
current=&((*current)->link);
prior=&((*prior)->link);
}
prior=head; //三个指针均移回链表起始处
current=&((*prior)->link);
later=&((*current)->link);
}
}
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
