0

私は、整数の 2 つの順序付きリストを単一の整数の順序付きリストにマージするコードに取り組もうとしています。

この関数ListNodePtr merge( ListNodePtr xPtr, ListNodePtr yPtr )は、2 つのリストのそれぞれの最初のノードへのポインターを受け取ることになっています。

マージ機能を除いて、他のすべてが機能しているようです。

問題は、短いリストの最後の要素を切り取っているようです。

//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 プログラミング言語を 1 か月半学んでいます。

4

3 に答える 3

1

コードを少し変更したところ、完璧に動作しました。

//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");
    }
}
于 2013-07-24T22:47:10.993 に答える
0 
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
于 2013-07-24T22:24:24.603 に答える
0

NEXT 値が null かどうかを確認しているため、最後の値に到達すると、マージ while ループから抜け出します。このwhileループの外では、他のリストを他のリストに追加するだけです。したがって、List1 が要素を使い果たし、List2 にさらに 3 つの要素がある場合、List2 をウォークスルーする代わりに、make (List1 の終わり)->next = (List2 で中断した場所) を作成します。

また、マージ関数で返さないでください。その必要はありません。夜リストはすでにスペースを占有しているため、ポインターが指している場所を切り替えるだけです。すべてのポインターが完了したら、関数から通常どおり List1/List2 へのアクセスを返すだけです (ただし、最初のポインターが含まれているリストを特定する必要があるため、1 または 2 を返すだけです)。

また、マージを私が思わない値に設定することはありません

于 2013-07-24T20:38:41.750 に答える