C数据结构之双链表详细示例分析

复制代码 代码如下:

 typedef struct node
{
      struct node *prior;
      struct node *next;
       int num;
}NODE;
/*******双向链表的初始化********/
NODE *Init_link(void)
{
     int i;
     NODE *phead,*pb,*pi;
     phead = (NODE *)malloc(sizeof(NODE));
     printf("please input num:\n");
     scanf("%d",&(phead->num));
     phead->prior = NULL;
     phead->next = NULL;
     pb = phead;
     for(i=0; i<3; i++)
     {
          pi = (NODE *)malloc(sizeof(NODE));
          printf("please input num:\n");
              scanf("%d",&(pi->num));
          pi->next = NULL;
          pb->next = pi;
          pi->prior = pb;
          pb = pi;
     }
     return phead;
}
/******链表的输出******/
void print_link(NODE *phead)
{
 while(phead != NULL)
 {
  printf(" %d,",phead->num);
  phead = phead->next;
 }
 printf("\n");
}
/******链表的逆序******/
NODE *reverse_link(NODE *phead)
{
 NODE *pb,*pf,*temp;
 pb = phead;
 pf = pb->next;
 while(pf != NULL)
 {
  temp = pf->next;
  pf->next = pb;
  pb->prior = pf;
  pb = pf;
  pf = temp;
 }
// phead->prior = pf->prior;
 phead->next = NULL;
 phead = pb;
 return phead;
}
/*****链表的排序*****/
NODE *Order_link(NODE *phead)
{
     NODE *pb,*pf,*ptr,temp;
     pb = phead;
     while(pb->next != NULL)
     {
          pf = pb->next;
          while(pf != NULL)
          {
               if(pb->num > pf->num)
               {
                     temp = *pb;
                    *pb = *pf;
                    *pf = temp;
                     ptr = pb->next;
                     pb->next = pf->next;
                     pf->next = ptr;
                     ptr = pb->prior;
                     pb->prior = pf->prior;
                     pf->prior = ptr;
              }
             pf = pf->next;
        }
        pb = pb->next;
    }
    return phead;
}
/******链表的有序插入*****/
NODE *insert_link(NODE *phead,NODE *pi)
{
 NODE *pb,*pf;
 pb = phead;
 if(pi == NULL)
  return phead;
 if(phead == NULL)
 {
  phead = pi;
  pi->prior = NULL;
  pi->next =NULL;
 }
 else
 {
  while( (pi->num > pb->num)&&(pb->next!=NULL))
  {
   pf = pb;
   pb = pb->next;
  }
  if(pi->num <= pb->num)
  {
   if(pb == phead)
   {
    pi->next = phead;
    pi->prior = NULL;
    phead->prior = pi;
    phead = pi;
   }
   else
   {
    pi->next = pb;
    pb->prior = pi;
    pi->prior = pf;
    pf->next = pi;
   }
  }
  else
  {
   pi->next = NULL;
   pi->prior = pb;
   pb->next = pi;
  }
 }
 return phead;
}
/******链表的删除*****/
NODE *delete_link(NODE *phead, NODE *pi)
{
 NODE *pb,*pf;
 pb = phead;
 while(pb != NULL)
 {
  if(pb == pi)
  {
   if(pb == phead)
    phead = phead->next;
   else if(pb->next == NULL)
    pf->next = NULL;
   else
   {
    pf->next = pb->next;
    //pb->next->prior = pf;
   }
  }
  pf = pb;
  pb = pb->next;
 }
 return phead;
}
/*******链表的释放******/
void free_link(NODE *phead)
{
 NODE *pb;
 while(phead != NULL)
 {
  pb = phead->next;
  free(phead);
  phead = pb;
 }
 printf("released link success!\n");
}
/*******测试程序******/
int main(void)
{
 NODE *phead,*pi;
 phead = Init_link();
 printf("init link:\n");
 print_link(phead);

 pi = (NODE *)malloc(sizeof(NODE));
 printf("plaese input insert num:");
 scanf("%d",&(pi->num));
 phead = insert_link(phead,pi);
 printf("after insert link：\n");
 print_link(phead);
 phead = Order_link(phead);
 printf("after sort link:\n");
 print_link(phead);

 printf("after reverse link:\n");
 phead = reverse_link(phead);
 print_link(phead);
 phead = delete_link(phead, pi);
 printf("after delete link:\n");
 print_link(phead);
 free_link(phead);
 return 0;
}