02051311.c

用C语言实现的两路归并算法

#include<stdio.h>
#include<stdlib.h>
struct listNode
{
       int data;
       struct listNode * nextPtr;
};
typedef struct listNode LISTNODE;
typedef LISTNODE * LISTNODEPTR;

void insert(LISTNODEPTR *,int);
void printList(LISTNODEPTR);
void change(LISTNODEPTR *,LISTNODEPTR *);
main()
{
      LISTNODEPTR startPtr1=NULL,startPtr2=NULL;
      int i=0;
      printf("input list 1,-1 to end.\n");
      scanf("%d",&i);
      while(i!=-1){
         insert(&startPtr1,i);
         scanf("%d",&i);
         }
      printf("input list 2,-1 to end.\n");
      scanf("%d",&i);
      while(i!=-1){
         insert(&startPtr2,i);
         scanf("%d",&i);
         }
      printf("list 1 is:");
      printList(startPtr1);
      printf("list 2 is:");
      printList(startPtr2);
      change(&startPtr1,&startPtr2);
      printf("归并后的list 1 is:");
      printList(startPtr1);
      system("PAUSE");
      return 0;
}
void insert (LISTNODEPTR *sPtr,int n)
{
     LISTNODEPTR newPtr,previousPtr,currentPtr;
     newPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));
     if(newPtr!=NULL){
       newPtr->data=n;
       newPtr->nextPtr=NULL;
       
       previousPtr=NULL;
       currentPtr=*sPtr;
       
       while(currentPtr!=NULL&&n>currentPtr->data){
         previousPtr=currentPtr;
         currentPtr=currentPtr->nextPtr;
       }
       
       if(previousPtr==NULL){
         newPtr->nextPtr=*sPtr;
         *sPtr=newPtr;
       }
       else{
         previousPtr->nextPtr=newPtr;
         newPtr->nextPtr=currentPtr;
       }
     }
      else
      printf("%d not inserted.No memory available.\n",n);
     }
void printList(LISTNODEPTR currentPtr)
{
     if(currentPtr==NULL)
        printf("List is empty.\n\n");
     else{
        while(currentPtr!=NULL){
        printf("%d-->",currentPtr->data);
        currentPtr=currentPtr->nextPtr;
     }
     printf("NULL\n\n");
}
}
void change(LISTNODEPTR *aPtr,LISTNODEPTR *bPtr)
{
     LISTNODEPTR previousPtr=NULL,currentPtr1,currentPtr2,tempPtr;
     currentPtr1=*aPtr;
     currentPtr2=*bPtr;
     while(currentPtr2!=NULL){       
        tempPtr=currentPtr2->nextPtr;
        while(currentPtr1->data<currentPtr2->data){
           previousPtr=currentPtr1;        
           currentPtr1=currentPtr1->nextPtr;
        }
     if(previousPtr==NULL){       
        currentPtr2->nextPtr=*aPtr;
        *aPtr=currentPtr2;
        previousPtr=*aPtr;
     }
     else{
        previousPtr->nextPtr=currentPtr2;
        currentPtr2->nextPtr=currentPtr1;
     }
        currentPtr2=tempPtr;
        printList(*aPtr);
     }
}