paixu.cpp

双向连表的基本操作 适合初学者

#define NUM 6
#include<stdio.h> 
#include<malloc.h>
typedef struct Link/*双向链表结构体*/ 
{ 
int data; 
struct Link *left; //前驱指针
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  nums: "); 
scanf("%d",&p->data);/*输入数据*/ 
head->left=NULL; 
n++; 
while(n!=NUM)/*一直输入到规定的数字个数停止*/ 
{ 
q=p; 
p=(linky)malloc(sizeof(linkx)); 
scanf("%d",&p->data);/*输入数据*/ 
q->right=p; 
p->left=q;       
n++; 
} 
p->right=NULL; 
return(head); 
} 
linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/ 
{linky temp; 
if(one->left==NULL&&two->right==NULL)    /* 1  首结点和尾结点的交换 */ 
{ 
  if(one->right==two)/*只有两个结点的情况下*/ 
  { 
   two->right=one; 
   two->left=NULL; 
   one->left=two; 
   one->right=NULL; //直接交换两结点
   head=two; 
  } 
  else/*有间隔的首尾交换*/ 
  { 
   one->right->left=two; 
   two->left->right=one; 
   two->right=one->right; 
   one->left=two->left; 
   two->left=one->right=NULL; 
   head=two;/*尾结点成为头结点*/ 
  } 
} 
else if(two->right==NULL)               /* 2 尾和任意一个交换*/ 
{ 
  if(one->right==two)/*交换最后两个结点*/ 
  { 
  one->left->right=two; 
  two->left=one->left; 
  two->right=one; 
  one->left=two; 
  one->right=NULL; 
  } 
  else/*和前面其他结点交换*/ 
  { 
  temp=two->left; 
  temp->right=one; 
  one->left->right=two; 
  one->right->left=two; 
  two->left=one->left; 
  two->right=one->right; 
  one->left=temp; 
  one->right=NULL; 
  } 
} 
else if(one->left==NULL)               /*  3 头和任意一个交换*/    
{ 
   if(one->right==two)/*交换头两个结点*/ 
   { 
   two->right->left=one; 
   one->right=two->right; 
   one->left=two; 
   two->right=one; 
   two->left=NULL; 
   head=two; 
   } 
  else/*头结点和后面其他结点交换*/ 
  { 
   temp=one->right; 
   temp->left=two; 
   one->left=two->left; 
   one->right=two->right; 
   two->left->right=one; 
   two->right->left=one; 
   two->right=temp; 
   two->left=NULL; 
   head=two;/*交换的结点成为头结点*/ 
  } 
} 
else                                  /* 4  当中的任意两个交换*/           
{ 
  if(one->right==two)/*交换连在一起的两个结点*/ 
  { 
 temp=one->left; 
 one->left->right=two; 
 one->right->left=two; 
 one->left=two; 
 one->right=two->right; 
 two->right->left=one; 
 two->right=one; 
 two->left=temp; 
  } 
  else/*交换隔开的两个结点*/ 
 { 
 one->left->right=two; 
 one->right->left=two; 
 one->left=two->left; 
 temp=one->right; 
 one->right=two->right; 
 two->left->right=one; 
 two->right->left=one; 
 two->right=temp; 
 two->left=one->left; 
 } 
} 
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); 

}