双向链表的排序

核心提示：以前写过双向链表交换任意结点的程序,后来写了个双向链表排序的程序,没用边输入边排序的思想,是输入完毕后我按照选择法排序的思想对链表的结点进行交换.是地址交换.#include <stdio.h>typedef strUCt Link/*双向链表结构体*/{ int data; struct Link *li

以前写过双向链表交换任意结点的程序,后来写了个双向链表排序的程序,没用边输入边排序的思想,是输入完毕后我按照选择法排序的思想对链表的结点进行交换.是地址交换. #include <stdio.h>
typedef strUCt Link/*双向链表结构体*/
{
 int data;
 struct Link *lift;
 struct Link *right;
}linkx,*linky;
linky Init();/*建立双向链表*/
void PRLink(linky p);/*输出双向链表*/
linky Sort(linky head);/*对双向链表排序*/
linky Swap(linky head,linky one,linky two);/*任意交换双向链表两个结点的地址*/
void main(void)
{
 linky head;
 head=Init();
 head=Sort(head);
 PrLink(head);
}
linky Init()/*建立链表*/
{
 linky p,q,head;
 int n=0;
 head=p=q=(linky)malloc(sizeof(linkx));
 clrscr();
 printf("please input 10 num: ");
 scanf("%d",&p->data);/*输入数据*/
 head->lift=NULL;
 n++;
 while(n!=10)/*一直输入到规定的数字个数停止*/
 {
  q=p;
  p=(linky)malloc(sizeof(linkx));
  scanf("%d",&p->data);/*输入数据*/
  q->right=p;
  p->lift=q;
  n++;
 }
 p->right=NULL;
 return(head);
}
linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/
{linky temp;
　 if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交换*/
　 {
　  if(one->right==two)/*只有两个结点的情况下*/
　  {
　　 two->right=one;
　　 two->lift=NULL;
　　 one->lift=two;
　　 one->right=NULL;
　　 head=two;
　  }
　  else/*有间隔的首尾交换*/
　  {
　  one->right->lift=two;
　  two->lift->right=one;
　  two->right=one->right;
　  one->lift=two->lift;
　  two->lift=one->right=NULL;
　  head=two;/*尾结点成为头结点*/
　  }
　 }
　 else if(two->right==NULL)/*尾和任意一个交换*/
　  {
　　 if(one->right==two)/*交换最后两个结点*/
　　 {
　　 one->lift->right=two;
　　 two->lift=one->lift;
　　 two->right=one;
　　 one->lift=two;
　　 one->right=NULL;
　　 }
　　 else/*和前面其他结点交换*/
　　 {
　　 temp=two->lift;
　　 temp->right=one;
　　 one->lift->right=two;
　　 one->right->lift=two;
　　 two->lift=one->lift;
　　 two->right=one->right;
　　 one->lift=temp;
　　 one->right=NULL;
　　 }
　  }
　 else if(one->lift==NULL)/*头和任意一个交换*/
　 {
　 if(one->right==two)/*交换头两个结点*/
　  {
　  two->right->lift=one;
　  one->right=two->right;
　  one->lift=two;
　  two->right=one;
　  two->lift=NULL;
　  head=two;
　  }
　 else/*头结点和后面其他结点交换*/
　  {
　　 temp=one->right;
　　 temp->lift=two;
　　 one->lift=two->lift;
　　 one->right=two->right;
　　 two->lift->right=one;
　　 two->right->lift=one;
　　 two->right=temp;
　　 two->lift=NULL;
　  head=two;/*交换的结点成为头结点*/
　  }
　 }
　 else/*当中的任意两个交换*/
  {
　  if(one->right==two)/*交换连在一起的两个结点*/
　  {
　  temp=one->lift;
　  one->lift->right=two;
　  one->right->lift=two;
　  one->lift=two;
　  one->right=two->right;
　  two->right->lift=one;
　  two->right=one;
　  two->lift=temp;
　  }
　  else/*交换隔开的两个结点*/
　  {
　  one->lift->right=two;
　  one->right->lift=two;
　  one->lift=two->lift;
　  temp=one->right;
　  one->right=two->right;
　  two->lift->right=one;
　  two->right->lift=one;
　  two->right=temp;
　  two->lift=one->lift;
　  }
　 }
 return(head);
}
linky Sort(linky head)/*对链表排序*/
{
 linky i,j,t,p;
 int max;
 p=head;
 for(i=p;i->right!=NULL;i=i->right)/*用选择法的思想对这些结点排序*/
  {
　 max=i->data;
　 for(j=i->right;j!=NULL;j=j->right)
　  if(j->data<max)
　  {
　  max=j->data;
　  t=j;
　  }
　 if(max!=i->data)/*假如没有找到比i小的结点*/
　 {
　 head=Swap(head,i,t);/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/
　 i=t;
　 }
  }
 return(head);
}
void PrLink(linky p)/*输出链表*/
{
 linky q;
 printf("Now the link: ");
 do
 {
  q=p;
  printf("%d ",p->data);
  p=p->right;
  free(q);/*释放输出结点*/
 }
 while(p!=NULL);
 getch();
}