雙向鏈表的排序

2019-11-17 05:47:49

字體：大中小

來源：轉載

供稿：網友

以前寫過雙向鏈表交換任意結點的程序,后來寫了個雙向鏈表排序的程序,沒用邊輸入邊排序的思想,是輸入完畢后我按照選擇法排序的思想對鏈表的結點進行交換.是地址交換.#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();
}

上一篇：陀螺

下一篇：數據結構學習C++——圖（1&2&3&4）