0

2 つのソートされたリンク リストをポインター操作でマージしたかったのですが、この時点で行き詰まりました。間違いを見つけることができません。お願い助けて。問題はwhileループにあると思います。スペース効率を高めたいので、別のリストを作成したくありません。

#include<iostream>
#include<conio.h>
using namespace std;
struct s
{
   int info;
   s *next;
};

int main()
{
    int i;
    char choice = 'y';
    s *ptr1, *ptr2, *start1, *start2, *reversedHead, *temp;
    ptr1= new s;
    start1=ptr1;
    cout<<"SIZE OF A NODE IS "<<sizeof(s)<<" BYTES"<<endl<<endl;
    while(choice=='y')
    {
                  cout<<"Enter info for node: ";
                  cin>>i;
                  ptr1->info = i;
                  cout<<"Do you wish to enter more nodes.? 'y'/'n'"<<endl;
                  cin>>choice;

                  if(choice=='y')
                  {
                                 ptr1->next = new s;
                                 ptr1 = ptr1->next;
                  }
                  else
                  {
                      ptr1->next = NULL;
                  }
    }
    choice = 'y';
    ptr2= new s;
    start2=ptr2;
    cout<<"SIZE OF A NODE IS "<<sizeof(s)<<" BYTES"<<endl<<endl;
    while(choice=='y')
    {
                  cout<<"Enter info for node: ";
                  cin>>i;
                  ptr2->info = i;
                  cout<<"Do you wish to enter more nodes.? 'y'/'n'"<<endl;
                  cin>>choice;

                  if(choice=='y')
                  {
                                 ptr2->next = new s;
                                 ptr2 = ptr2->next;
                  }
                  else
                  {
                      ptr2->next = NULL;
                  }
    }

    ptr1=start1;
    ptr2=start2;
    while(ptr1->next!=NULL || ptr2->next!=NULL)
    {
                         if(ptr1->info < ptr2->info)
                         {
                                       if(ptr1->next->info < ptr2->info)
                                                           ptr1=ptr1->next;
                                       else
                                       {
                                           ptr2=temp;
                                           ptr2=ptr2->next;
                                           temp->next=ptr1->next;
                                           ptr1->next=temp;
                                       }
                         }
                         else
                         {
                             if(ptr2->next->info < ptr1->info)
                                                 ptr2=ptr2->next;
                             else
                             {
                                 ptr1=temp;
                                 ptr1=ptr1->next;
                                 temp->next=ptr2->next;
                                 ptr2->next=temp;
                             }
                         }
    }
    if(ptr1->next==NULL)
                    ptr1->next=ptr2;
    else
        ptr2->next=ptr1;
    cout<<"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";                    
    if(start1->info>start2->info)
    {
                             ptr2=start2;
                             while(ptr2!=NULL){
                                              cout<<ptr2->info<<"\t";
                                              ptr2=ptr2->next;}
    } 
    else
    {
                             ptr1=start1;
                             while(ptr1!=NULL){
                                              cout<<ptr1->info<<"\t";
                                              ptr1=ptr1->next;}
    }          



    getch();
}
4

2 に答える 2

2

すべてをチェックしたわけではありませんが、ここから始めましょう：

 while(ptr1->next!=NULL || ptr2->next!=NULL)

リストのいずれかの次のエントリが null の場合に比較を続行したく&&ないため、そうではない必要があります (while ループの if の 1 つでその内容を使用します)。||

于 2012-11-12T14:18:03.210 に答える
2

Your while loop condition is not quite right.

while(ptr1->next!=NULL || ptr2->next!=NULL)

is fine, but only when both lists are the same length!. When the lists are of different lengths, either ptr1->next or ptr2->next will be NULL, and you'll get a segmentation fault. Changing to to && is not the correct thing to do, because you'll lose the end of one of your lists!

Use this:

while((ptr1 != NULL && ptr2 != NULL) && (ptr1->next!=NULL || ptr2->next!=NULL))

Now, inside your loop you have tests like this:

if(ptr1->next->info < ptr2->info)

replace this with

if(ptr1 != NULL && ptr1->next->info < ptr2->info)

so that unequal length lists don't terminate early and don't segfault inside.

Next, inside your insert operations, you do things like

ptr1=temp;
ptr1=ptr1->next

and

ptr2=temp;
ptr2=ptr2->next;

This is bad, because temp is undefined as you never write any valid data to it! The bug here is that your assignments are the wrong way round. You should have done temp=ptr1 and temp=ptr2 respectively.

Finally, your cleanup operation to fix up equal length input lists needs to account for the fact that unequal length input lists can result in either ptr1 or ptr2 being NULL:

if(ptr1 != NULL && ptr1->next==NULL)
    ptr1->next=ptr2;
else if (ptr2 != NULL)
    ptr2->next=ptr1;

And all seems to be well. I've tested the resulting code on 1 3 5,2 4 6 and 1 3,2 and 1 4,2 3 and 1 3,2 3 and all work as I'd expect them to.

于 2012-11-12T14:31:29.763 に答える