利用冒泡法對單鏈表進行排序需要交換兩個相鄰結點，利用二級指針可以很方便地解決結點交換的問題
下面我們生成一個鏈表，每個結點儲存一個隨機值，然后對該鏈表進行排序。其中排序算法的實現過程也同時實現了相鄰兩個結點的交換。
#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空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
