合并两个排序的链接列表 [英] Merge two sorted link lists
问题描述
我想通过指针操作合并两个排序的链接列表，但停留在这一点。不能找出错误。请帮帮我。我认为问题是在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<<NODE IS的大小<<< sizeof（s）<<BYTES<< endl<< endl;
while（choice =='y'）
{
cout<<输入节点信息：;
cin>> i;
ptr1-> info = i;
cout<<你想输入更多的节点吗？'y'/'n'<< endl;
cin>>选择;
if（choice =='y'）
{
ptr1-> next = new s;
ptr1 = ptr1-> next;
}
else
{
ptr1-> next = NULL;
}
}
choice ='y';
ptr2 = new s;
start2 = ptr2;
cout<<NODE IS的大小<<< sizeof（s）<<BYTES<< endl<
while（choice =='y'）
{
cout<<输入节点信息：;
cin>> i;
ptr2-> info = i;
cout<<你想输入更多的节点吗？'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-&
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<<XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX;
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（）;
}
非常对。
while（ptr1-> next！= NULL || ptr2-> next！= NULL）
很好，但仅当两个列表长度相同时才会出现！当列表长度不同时， ptr1-> next 或 ptr2-> next 将为 NULL ，你会得到一个分段错误。更改为&& 不是正确的操作，因为您将丢失其中一个列表的结尾。
使用此方法：<（ptr1！= NULL& ptr2！= NULL）&& ptr2使用这个：
;&（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或ptr2NULL：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>I wanted to merge two sorted link lists by pointer manipulation, but stuck at this point. cant find out the mistake. Help me please. I think the problem is in while loop. I want to make it space efficient and do not want to make another list.
#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(); }
解决方案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->nextorptr2->nextwill beNULL, 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->nextand
ptr2=temp; ptr2=ptr2->next;This is bad, because
tempis 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 donetemp=ptr1andtemp=ptr2respectively.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
ptr1orptr2beingNULL: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 6and1 3,2and1 4,2 3and1 3,2 3and all work as I'd expect them to.这篇关于合并两个排序的链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
