合并两个排序后的链接列表

我想通过指针操作来合并两个排序后的链接列表，但在这一点上仍然存在。不能找出错误。请帮帮我。我认为问题出现在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(); 
}

来源

2012-11-12 cheeseRoot

究竟是什么问题？你尝试过调试吗？ –

如果您提供了您在应用程序中尝试过的输入，您获得的输出以及您期望的输出，它将会有所帮助。另外，有什么特别的原因，你不使用'std :: list'？ – Rook

如果你只是想让代码工作，使用'std :: list'，然后使用方法'std :: list :: merge（）';快速简单。如果你还有其他的理由（例如学习），你会有更具体的，而不仅仅是*它不工作*。 – Gorpik

while while循环条件不太正确。

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

是好的，但只有当这两个列表的长度相同！当列表长度不同时，ptr1->next或ptr2->next将为NULL，您将得到分段错误。更改为&&不是正确的做法，因为您将失去一个列表的结尾！

使用此：

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

现在，你的循环里面你有测试这样的：

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

与

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

使不等长列表不替换此提前终止，不要在内部发生故障。

接下来，你的插入操作里面，你不喜欢的东西

ptr1=temp; 
ptr1=ptr1->next

和

ptr2=temp; 
ptr2=ptr2->next;

这是不好的，因为temp是不确定的，你从来不写任何有效数据吧！这里的错误是你的任务是错误的。你应该分别完成temp=ptr1和temp=ptr2。

最后，你的清理操作来修复相等长度的输入列表中需要考虑的事实，不等长度的输入列表可以导致主要是ptr1或ptr2是NULL：

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

而且一切似乎很好。我已经测试了1 3 5,2 4 6和1 3,2和1 4,2 3和1 3,2 3的结果代码，所有代码都如我所预期的那样工作。

来源

2012-11-12 14:31:29 Rook

狗屎。我怎么能不注意到这样的错误。感谢@rook。 :)：p – cheeseRoot

FIRST LIST-> 3,5 SECOND LIST-> 4,6 现在输出来了3-> 4-> 5（不是6）:(:( – cheeseRoot

@SudhanshuSingh done。还有3个我发现的问题;-) – Rook

没有检查这一切还是让我们从这里开始：

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

应该&&，而不是||，因为你不希望继续进行比较时，在列表中的一个的下一个项为无效（你可以在while循环中的ifs之一中使用它的内容）

来源

2012-11-12 14:18:03 giorashc

哦，是的。谢谢。但执行仍然突然停止。 – cheeseRoot

我会建议你使用调试器，并看看@ Rook的回答 – giorashc

合并两个排序后的链接列表

回答

相关问题