双向链表排序C语言程序

// 双向链表排序.cpp : 定义控制台应用程序的入口点。

//

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define len sizeof(struct node)

struct node

{

int data;

struct node *next;

struct node *last;

};

struct list

{

struct node *head,*tail;

int l;

};

void main()

{

struct list a;

printf("请输入A链表的元素个数\n");

scanf("%d",&a.l);

int i,x=1;

struct node *p1,*p2,*p3;

printf("请输入A链表的第1个数据\n");

p1=p2=(struct node*)malloc(len);

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

a.head=p1;

p1->last=NULL;

for(i=2;i<=a.l;i++)

{

p2=(struct node*)malloc(len);

p1->next=p2;

p2->last=p1;

p1=p2;

printf("请输入A链表的第%d个数据\n",i);

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

}

p1->next=NULL;

a.tail=p1;//链表A生成完毕//

for(p2=a.tail;p2->last->last;p2=p2->last)//考虑第一个链点进行交换的情况//

{

if(p2->data<p2->last->data)

{

p3=p2->last;

if(p2->next)

{

p3->last->next=p2;

p2->last=p3->last;

p2->next->last=p3;

p3->next=p2->next;

p3->last=p2;

p2->next=p3;

p2=p3;

}

else

{

p3->next=NULL;

p2->last=p3->last;

p3->last->next=p2;

p2->next=p3;

p3->last=p2;

p2=p3;

a.tail=p2;//考虑最后两个链点交换的情况//

}

}

}

if(p2->last->data>p2->data)

{

p3=p2->last;

p2->last=NULL;

p3->next=p2->next;

p2->next->last=p3;

p3->last=p2;

p2->next=p3;

p2=p3;

a.head=p2->last;

}

p1=a.head;

while(p1->next)

{

for(p2=a.tail;p2->last!=p1;p2=p2->last)

{

if(p2->data<p2->last->data)

{

p3=p2->last;

if(p2->next)

{

p3->last->next=p2;

p2->last=p3->last;

p2->next->last=p3;

p3->next=p2->next;

p3->last=p2;

p2->next=p3;

p2=p3;

}

else

{

p3->next=NULL;

p2->last=p3->last;

p3->last->next=p2;

p2->next=p3;

p3->last=p2;

p2=p3;

a.tail=p2;//考虑最后两个链点交换的情况//

}

}

}

p1=p1->next;

}

p1=a.head;

printf("%d\t",p1->data);

do

{

p1=p1->next;

printf("%d\t",p1->data);

}

while(p1->next);//新链表输出//

}

本文来源：https://www.wddqw.com/doc/b3b42c87de3383c4bb4cf7ec4afe04a1b171b051.html