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