C语言链表如何排序

可以把链表设计成循环链表，用冒泡排序

在排序前设计一个交换标记，如在循环过程中有交换，则修改这个标记变量，如果在一次循环（当前节点为刚开始时节点，表示循环了一次）中，交换标记没有被修改，则表明该数列已排好序。

现在给一个双向循环链表的排序程序给你，该程序用了双向冒泡排序（也就是鸡尾酒排序法），希望对你有帮助

双向链表我用的鸡尾酒排序,也就是双向冒泡排序

#include<stdio.h>

#define LEN sizeof(struct list)

struct list//双向链表有两个指针域，一个指向前节点，一个指向后继节点

{struct list *lp //lp为前节点指针，rp为后继节点指针

int x

struct list *rp

}

int n

struct list *creat(void)

{struct list *head

struct list *p1,*p2 //两个节点指针，腊顷p1是当前新建节点指针，p2为p1的前一个节点

n=0

p1=p2=(struct list*)malloc(LEN)//申请内存空间

scanf("%d"顷并,&p1->x)

head=NULL //先把头指针设置为空

while(p1->x!=0)

{n=n+1

if(n==1){p1->lp=NULLhead=p1} //把head指向轮乎陆链表的第一个节点并把首节点的lp设为NULL

else

{p1->lp=p2新建了一个节点，把它的lp指向前一个节点p2

p2->rp=p1}把前节点的rp指针指向刚建立的节点

p2=p1 进行迭代，p1变成下一个新节点的后继节点

p1=(struct list*)malloc(LEN)//每次新建节点都要向系统申请内存空间

scanf("%d",&p1->x)

}

p2->rp=NULL 把随后的节点后继指针设为空

return(head)

}

void print(struct list *head)

{struct list *p

printf("\nNow,Thess %d records are :\n",n)

p=head

if(head!=NULL)

do

{printf("%d ",p->x)

p=p->rp//这个是个迭代过程，把p的后继节点变成下一次要输出的节点

}while(p!=NULL)

}

void sort(struct list *head) //排序用的双向排序法，提高排序效率

{struct list *p,*bottom,*top

int f,temp

p=head

if(head!=NULL)

{ f=1

bottom=NULL //bottom和top为数列左右冒泡的边界节点

top=NULL

while(f==1) //f为交换标记，如果没交换则f没变就推出循环

{f=0

do

{

if(p->x >(p->rp)->x)

{temp=p->x

p->x=(p->rp)->x

(p->rp)->x=temp

f=1

}

p=p->rp

}while(p->rp!=top)

print(head)

top=p

if((f==0)||(top==bottom))break

f=0

do

{

if(p->x<(p->lp)->x)

{

temp=p->x

p->x=(p->lp)->x

(p->lp)->x=temp

f=1

}

p=p->lp

}while(p->lp!=bottom)

bottom=p

if(top==bottom)break

print(head)

}

}

}

void main() //所有的函数都做成全局函数，可以随时调用

{struct list *head

head=creat() //建立链表

print(head) //输出链表

sort(head) //排序

print(head) //输出链表

system("PAUSE")

}

同学，给你一段代码，里面涵盖了链表的冒泡排序！

#include<stdio.h>

#include<malloc.h>

typedef struct node

{

int data/*data代表成绩分数*/

struct node *next

}LNode,*LinkList

LinkList Creat(void)/*创建链表，结束标志为当输入的数据为0!*/

{

LinkList H,p1,p2

int n

n=0

p1=p2=(LinkList)malloc(sizeof(LNode))

printf("输入数据：")

scanf("%d",&p1->data)

H=NULL

while(p1->data!=0)

{

n=n+1

if(n==1)

H=p1

else

p2->next=p1

p2=p1

p1=(LinkList)malloc(sizeof(LNode))

scanf("%d",&p1->data)

}

p2->next=NULL

return(H)

}

LinkList Sort(LinkList SL)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/

{

LinkList p,q

int temp

for(p=SLp!=NULLp=p->next)

{

for(q=p->nextq!=NULLq=q->next)

{

if(p->data>q->data)

{

temp=q->data

q->data=p->data

p->data=temp

}

}

}

return SL

}

int main()

{

LinkList L,S,K

L=Creat()

printf("初始昌谈戚化的单链表数据序列为:\n")

for(S=LS!=NULLS=S->耐陵next)

printf("%d ",S->data)

Sort(L)

printf("\n按递增顺序排侍蚂序后的序列为:\n")

for(K=LK!=NULLK=K->next)

printf("%d==>",K->data)

return 0

}

---