Слияние двух упорядоченных связанных списков в один упорядоченный связанный список

Question

Я пытался работать над кодом, который объединит два упорядоченных списка целых чисел в один упорядоченный список целых чисел.

Предполагается, что функция ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr) получит указатели на первый узел каждого из двух списков.

Все остальное работает, за исключением функции слияния.

Проблема заключается в том, что она разрезает последний элемент более короткого списка.

//12.7 merge two ordered lists into one ordered list 
#include <stdio.h> 
#include <stdlib.h> 

struct listNode 
{ 
    int data; 
    struct listNode *nextPtr; 
}; 

    typedef struct listNode ListNode; 
    typedef ListNode *ListNodePtr; 

    void insert(ListNodePtr *sPtr, int value); 
    ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr); 
    int isEmpty(ListNodePtr currentPtr); 
    void printList(ListNodePtr currentPtr); 
    void instructions(void); 

int main(void) 
{ 
    ListNodePtr startPtr1 = NULL; 
    ListNodePtr startPtr2 = NULL; 

    unsigned int choice; 
    int item; 

    instructions(); 
    printf("\n?"); 
    scanf("%u",&choice); 

    while (choice != 4) 
    { 
     switch (choice) 
     { 
     case 1: 
      printf("Enter a character into list 1:\n"); 
      scanf("\n%d",&item); 
      insert(&startPtr1, item); 
      printList(startPtr1); 
      break; 
     case 2: 
      printf("Enter a character into list 2:\n"); 
      scanf("\n%d",&item); 
      insert(&startPtr2, item); 
      printList(startPtr2); 
      break; 
     case 3: 
      if (isEmpty(startPtr1) && isEmpty(startPtr2)) 
      { 
       puts("Both lists are empty."); 
      } 
      else if (isEmpty(startPtr1)) 
      { 
       puts("List 1 is empty."); 
      } 
      else if (isEmpty(startPtr2)) 
      { 
       puts("List 2 is empty."); 
      } 
      else 
      { 
      printList(startPtr1); 
      printList(startPtr2); 
      puts("Merged list:"); 
      printList(merge(startPtr1, startPtr2)); 
      } 
      break; 
     default: 
      printf("Invalid choice.\n"); 
      instructions(); 
      break; 
     } 
     printf("\n?"); 
     scanf("%u",&choice); 
    } 
     puts("End of run."); 
} 

void instructions(void) 
{ 
    printf("Enter your choice:\n" 
    " 1 to insert an number into list 1.\n" 
    " 2 to insert an number into list 2.\n" 
    " 3 to merge and order list 1 and list 2.\n" 
    " 4 to end."); 
} 

void insert(ListNodePtr *sPtr, int value) 
{ 
    ListNodePtr newPtr; 
    ListNodePtr previousPtr; 
    ListNodePtr currentPtr; 

    newPtr = (ListNodePtr)malloc(sizeof(ListNode)); 

    if (newPtr != NULL) 
    { 
     newPtr->data = value; 
     newPtr->nextPtr = NULL; 

     previousPtr = NULL; 
     currentPtr = *sPtr; 

     while (currentPtr != NULL && value > 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.", value); 
    } 
} 

ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr) 
{ 
    ListNode merge; 
    ListNodePtr mergePtr = &merge; 

    //PROBLEM: merge.nextPtr will be missing second to last element 
    //in final merged list 

    while (xPtr->nextPtr != NULL && yPtr->nextPtr != NULL) 
    { 
     if (xPtr->data < yPtr->data) 
     { 
      mergePtr->nextPtr = xPtr; 
      xPtr = xPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 

     }//end if 
     if (yPtr->data < xPtr->data) 
     { 
      mergePtr->nextPtr = yPtr; 
      yPtr = yPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 
     }//end if 
    }//end of while 
    if (xPtr->nextPtr == NULL) 
    { 
     mergePtr->nextPtr = yPtr; 
    } 
    if (yPtr->nextPtr == NULL) 
    { 
     mergePtr->nextPtr = xPtr; 
    } 
    return merge.nextPtr; 
}//end of function merge 


int isEmpty(ListNodePtr sPtr) 
{ 
    return sPtr == NULL; 
} 

void printList(ListNodePtr currentPtr) 
{ 
    if (isEmpty(currentPtr)) 
    { 
     puts("List is empty"); 
    } 
    else 
    { 
     while (currentPtr != NULL) 
     { 
      printf("%d --> ", currentPtr->data); 
      currentPtr = currentPtr->nextPtr; 
     } 
     puts("NULL"); 
    } 
} 

Может кто-нибудь исправить эту проблему? Я изучаю язык программирования C в течение полутора месяцев.

Answer 1

Поскольку вы проверяете, имеет ли значение NEXT значение NULL, когда вы нажмете свое последнее значение, вы выйдете из цикла слияния во время цикла. Вне этого цикла while вы должны просто добавить другой список на другой. Поэтому, если в List1 не хватает элементов, а List2 имеет еще 3, вместо того, чтобы ходить через List2, просто сделайте (конец List1) -> next = (где вы остановились в List2).

Кроме того, не возвращайтесь в функцию слияния. Вам не нужно. поскольку списки yoru уже занимают пространство, вы просто переключаетесь туда, куда указывают указатели. Как только все указатели будут выполнены, просто вернитесь из функции в список List1/List2, как обычно, (за исключением того, что вам нужно выяснить, в каком списке содержится первый указатель, так что просто верните 1 или 2).

также, вы надеваете я никогда не думал о слиянии со стоимостью Не думаю, что

Answer 2

ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr) 
{ 
    ListNode merge; 
    ListNodePtr mergePtr = &merge; 

    while (xPtr != NULL && yPtr != NULL) 
    { 
     if (xPtr->data < yPtr->data) 
     { 
      mergePtr->nextPtr = xPtr; 
      xPtr = xPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 

     } else if (yPtr->data < xPtr->data)//need else because 1 loop 2 ecxecute merge 
     { 
      mergePtr->nextPtr = yPtr; 
      yPtr = yPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 
     }//end if 
     //nothing case of (yPtr->data == xPtr->data) 
    }//end of while 
    if (xPtr == NULL) 
    { 
     mergePtr->nextPtr = yPtr; 
    } 
    if (yPtr == NULL) 
    { 
     mergePtr->nextPtr = xPtr; 
    } 
    return merge.nextPtr; 
}//end of function merge 

Answer 3

Я немного модифицировал код, и он отлично работает!

//12.7 merge two ordered lists into one ordered list 
#include <stdio.h> 
#include <stdlib.h> 

struct listNode 
{ 
    ! int data; 
    struct listNode *nextPtr; 
}; 

    typedef struct listNode ListNode; 
    typedef ListNode *ListNodePtr; 

    void insert(ListNodePtr *sPtr, int value); 
    ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr); 
    int isEmpty(ListNodePtr currentPtr); 
    void printList(ListNodePtr currentPtr); 
    void instructions(void); 

int main(void) 
{ 
    ListNodePtr startPtr1 = NULL; 
    ListNodePtr startPtr2 = NULL; 

    unsigned int choice; 
    int item; 

    instructions(); 
    printf("\n?"); 
    scanf("%u",&choice); 

    while (choice != 4) 
    { 
     switch (choice) 
     { 
     case 1: 
      printf("Enter a character into list 1:\n"); 
      scanf("\n%d",&item); 
      insert(&startPtr1, item); 
      printList(startPtr1); 
      break; 
     case 2: 
      printf("Enter a character into list 2:\n"); 
      scanf("\n%d",&item); 
      insert(&startPtr2, item); 
      printList(startPtr2); 
      break; 
     case 3: 
      if (isEmpty(startPtr1) && isEmpty(startPtr2)) 
      { 
       puts("Both lists are empty."); 
      } 
      else if (isEmpty(startPtr1)) 
      { 
       puts("List 1 is empty."); 
      } 
      else if (isEmpty(startPtr2)) 
      { 
       puts("List 2 is empty."); 
      } 
      else 
      { 
      printList(startPtr1); 
      printList(startPtr2); 
      puts("Merged list:"); 
      printList(merge(startPtr1, startPtr2)); 
      } 
      break; 
     default: 
      printf("Invalid choice.\n"); 
      instructions(); 
      break; 
     } 
     printf("\n?"); 
     scanf("%u",&choice); 
    } 
     puts("End of run."); 
} 

void instructions(void) 
{ 
    printf("Enter your choice:\n" 
    " 1 to insert an number into list 1.\n" 
    " 2 to insert an number into list 2.\n" 
    " 3 to merge and order list 1 and list 2.\n" 
    " 4 to end."); 
} 

void insert(ListNodePtr *sPtr, int value) 
{ 
    ListNodePtr newPtr; 
    ListNodePtr previousPtr; 
    ListNodePtr currentPtr; 

    newPtr = (ListNodePtr)malloc(sizeof(ListNode)); 

    if (newPtr != NULL) 
    { 
     newPtr->data = value; 
     newPtr->nextPtr = NULL; 

     previousPtr = NULL; 
     currentPtr = *sPtr; 

     while (currentPtr != NULL && value > 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.", value); 
    } 
} 

ListNodePtr merge(ListNodePtr xPtr, ListNodePtr yPtr) 
{ 
    ListNode merge; 
    ListNodePtr begin, mergePtr = &merge;   //here 
    begin = mergePtr;        //here 
    //PROBLEM: merge.nextPtr will be missing second to last element 
    //in final merged list 

    while (xPtr != NULL && yPtr != NULL)  //here 2 now I deal with the last of short link! 
    { 
     if (xPtr->data < yPtr->data) 
     { 
      mergePtr->nextPtr = xPtr; 
      xPtr = xPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 

     }//end if 
     else// (yPtr->data < xPtr->data)  //here for yPtr->data == xPtr->data 
     { 
      mergePtr->nextPtr = yPtr; 
      yPtr = yPtr->nextPtr; 
      mergePtr = mergePtr->nextPtr; 
     }//end if 
    }//end of while 
    if (xPtr != NULL)       //here 2 
    { 
     mergePtr->nextPtr = xPtr; 
    } 
    if (yPtr != NULL)       //here 2 
    { 
     mergePtr->nextPtr = yPtr; 
    } 
    return begin->nextPtr;       //here 
}//end of function merge 


int isEmpty(ListNodePtr sPtr) 
{ 
    return sPtr == NULL; 
} 

void printList(ListNodePtr currentPtr) 
{ 
    if (isEmpty(currentPtr)) 
    { 
     puts("List is empty"); 
    } 
    else 
    { 
     while (currentPtr != NULL) 
     { 
      printf("%d --> ", currentPtr->data); 
      currentPtr = currentPtr->nextPtr; 
     } 
     puts("NULL"); 
    } 
}