按序合并链表

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
 
typedef struct student
{
 int stuno;
 int age;
 struct student *next;
};
 
int num;
student* createLink();
student* merge(student *pA, student *pB);
void sort(student *head, int num);
void print(student *head);
 
/************************************************************************/
/* main
/************************************************************************/
int main()
{    
 num = 0;
 student *head_A, *head_B, *head_C;
 head_A=head_B=head_C=NULL;
 
 head_A = createLink();
 head_B = createLink();
    
 printf("link list A:\n");
 print(head_A);
 printf("link list B:\n");
 print(head_B); 
 
 head_C = merge(head_A, head_B);
 printf("merge A with B:\n");
 print(head_C);
 
 sort(head_C, num); 
 printf("merge A with B (sort with ASC):\n");
 print(head_C); 
 return 0;    
}
/************************************************************************/
/* create link list
/************************************************************************/
student* createLink()
{
 student *head, *p1, *p2;
 head=p1=p2=NULL;
 
 printf("************************\n stuno:0 will exit:\n************************\n");
 
 while(1)
 {
  p1 = (student *)malloc(sizeof(*p1));  
  if (p1== NULL)
  {
   printf("malloc fail!");
   exit(0);
  }
  
  printf("input stuno:");  
  scanf("%d", &p1->stuno);
    
  //if (strcmp(p1->stuno, "0") == 0)
  if (p1->stuno == 0)
  {
   break;
  }
  
  printf("input age:");  
  scanf("%d", &p1->age); 
  
  if (head == NULL)
  {
   head = p1;
  }
  else
  {
   p2->next = p1;
  }
  
  p2 = p1;
  p2->next = NULL;
  
  num++;
 }
 
 return head;
}
/************************************************************************/
/*  output link list
/************************************************************************/
void print(student *head)
{
 printf("\nstuno age\n----- ----\n");
 student *p = head;
 while(p != NULL)
 {
  printf("%-5d %-4d\n", p->stuno, p->age);
  p = p->next;
 }
 printf("\n");
}
/************************************************************************/
/* merge A and B
/************************************************************************/
student* merge(student *pA, student *pB)
{
 student *pa, *pb, *pc, *pchead;
 
 pchead = pc = pA; //initial pc;
 pa = pA->next;
 pb = pB;
 while(pa != NULL)
 {
  pc->next=pa;
  pc=pa;
  pa=pa->next;
 }
 while(pb != NULL)
 {
  pc->next = pb;
  pc = pb;
  pb = pb->next;
 }
 pc->next = NULL;
 
//  while(pa!=NULL && pb!=NULL)
//  {
//   if(pa->stuno < pb->stuno)
//   {
//    pc->next=pa;
//    pc=pa;
//    pa=pa->next;
//   }
//   else
//   {
//    pc->next=pb;
//    pc=pb;
//    pb=pb->next;
//   }
//  }
//  
//  if(pa)
//   pc->next=pa;
//  else
//   pc->next=pb; 
 
 return  pchead;
}
/************************************************************************/
/* sort ASC 冒泡排序法
/************************************************************************/
void sort(student *head, int num)
{
    int i, j, t;
    student *p;

    for (i = 0; i < num - 1; i++)     //总的轮次
    {
        p = head;
        for (j = 0; j < num - i - 1; j++)     //相邻大小进行排序,大的往最后冒
        {
            if (p->stuno > p->next->stuno) 
            {
                t = p->stuno;
                p->stuno = p->next->stuno;
                p->next->stuno = t;
            }
            p = p->next;
        }
    }
}

Comments are closed.