|
|
利用冒泡法對單鏈表進行排序需要交換兩個相鄰結(jié)點，利用二級指針可以很方便地解決結(jié)點交換的問題
下面我們生成一個鏈表，每個結(jié)點儲存一個隨機值，然后對該鏈表進行排序。其中排序算法的實現(xiàn)過程也同時實現(xiàn)了相鄰兩個結(jié)點的交換。
#include < stdio.h >
#include < stdlib.h >
#include < time.h >
#define FALSE 0
#define TRUE 1
typedef struct NODE{ //鏈表節(jié)點的結(jié)構(gòu)體聲明
struct NODE *link;
int value;
}Node;
int sort(register Node **head,int length); //排序函數(shù)的原型聲明
int main(void)
{
int i; //利用i控制循環(huán)次數(shù)
Node *head=(Node *)malloc(sizeof(Node)); //申請頭結(jié)點并讓頭指針指向頭結(jié)點
Node *p=head; //利用p使當(dāng)前結(jié)點與新節(jié)點相連接
srand( (unsigned)time( NULL ) );
for(i=0;i<20;i++) //單鏈表創(chuàng)建
{
p->value=rand()0+1; //生成1~100的隨機數(shù)
p->link=(Node *)malloc(sizeof(Node)); //使當(dāng)前結(jié)點與新節(jié)點相連
p=p->link; //p指向新節(jié)點
}
p->value=rand()0+1; //對尾結(jié)點賦值
p->link=NULL;
p=head;
printf("排序前儲存的數(shù)值為："); //打印排序前鏈表儲存的數(shù)值
while(p!=NULL)
{
printf("%d ",p->value);
p=p->link;
}
sort(&head,20); //調(diào)用排序函數(shù)對鏈表排序
p=head;
printf("\n排序后儲存的數(shù)值為："); //打印排序后鏈表儲存的數(shù)值
while(p!=NULL)
{
printf("%d ",p->value);
p=p->link;
}
free(head);
return 0;
}
int sort(register Node **head,int length) //定義三個二級指針實現(xiàn)結(jié)點交換
{
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; //實現(xiàn)結(jié)點交換
*prior=*current;
*current=*later;
*later=temp1;
temp2=current; //調(diào)整三個指針的位置
current=later;
later=temp2;
}
if(*later==NULL) //最后一次交換已完成，*later為NULL，不能執(zhí)行下面代碼，故結(jié)束循環(huán)
{
break;
}
later=&((*later)->link); //三個指針均向后移動一個結(jié)點
current=&((*current)->link);
prior=&((*prior)->link);
}
prior=head; //三個指針均移回鏈表起始處
current=&((*prior)->link);
later=&((*current)->link);
}
}
|
評分
-
查看全部評分
|
