I am trying to concatenate two lists based on array (in c ), empty the first over the second, and if the insertion failed (maximum size reached) it will keep each list as it was before insertion. therefor, the code works well, but the problem is that it execute the list in a wrong sequence like, the first list contains 10 20 30 40 50 the second 100 200 300 when it is concatenated with the second it would be as 100 200 300 10 30 50 20 40 but I want it to be 100 200 300 10 20 30 40 50 the code I wrote :
using namespace std;
const int maxsize=100;
template<class T>
class list{
T entry[maxsize];
int count;
public:
list(){
count=0;
}
bool empty(){
return count==0;
}
bool insert(int pos, T item){
if(pos<0 || pos>count) return 0;
if(count>=maxsize) return 0;
for(int i=count-1; i>=pos; i--)
entry[i 1]=entry[i];
entry[pos]=item;
count ;
return 1;
}
bool remove(int pos){
if(pos<0 || pos>=count) return 0;
for(int i=pos; i<count-1; i )
entry[i]=entry[i 1];
count--;
return 1;
}
bool retrieve(int pos, int &item){
if(pos<0 || pos>=count) return 0;
item=entry[pos];
return 1;
}
bool replace(int pos, int item){
if(pos<0 || pos>=count) return 0;
entry[pos]=item;
return 1;
}
int size(){
return count;
}
};
void print(list<int>L){
int item;
for(int i=0;i<L.size();i ){
L.retrieve(i,item);
cout<<item<<" ";
}
cout<<endl;
}
void fill(list<int>&L, int n){
for(int i=1; i<n; i )
L.insert(L.size(),rand()0);
}
bool concat (list<int>&l1,list<int>&l2){
int item;
int c=l2.size();
while(!l1.empty()) {
for(int i=0; i<l1.size(); i ){
l1.retrieve(i,item);
if(l2.insert(l2.size(),item)==0){
for(int j=c; j>l2.size()-1; j--){
l2.retrieve(j,item);
l1.insert(l1.size(),item);
l2.remove(j);
}
return 0;
}
else {
c ;
l1.remove(i);
}
}
}
return 1;
}
main(){
list<int>L1, L2;
L1.insert(0,10);
L1.insert(1,20);
L1.insert(2,30);
L1.insert(3,40);
L1.insert(4,50);
L2.insert(0,123);
L2.insert(1,143);
L2.insert(2,345);
L2.insert(3,545);
L2.insert(4,536);
print(L1);
print(L2);
cout<<"<<1: succeeded, 0: failed>> "<<concat(L1,L2)<<endl;
cout<<"First List: ";
print(L1);
cout<<"Second List: ";
print(L2);
}```
CodePudding user response：
First some nagging:
- Stop lying. This is not a list. It's a vector.
- 0 is not a bool, use true/false
- if you are going to return a bool to say if something failed then actually check the return value
- don't use out parameters
- use exceptions, std::optional or std::expected for error handling with return values
- retrieve and replace should be named
operator[]oratand have a const and not-const flavour int maxsize? Seriously? I can't have lists with more than 2 billion items?maxsizecould be a template parameter- your indentation is broken
Lets look at your code line by line:
bool concat (list<int>&l1,list<int>&l2){
So you want to concat l1 l2 into a single list.
int item;
Don't declare variables before you need them.
int c=l2.size();
while(!l1.empty()) {
Wait, if you want to add l2 to l1 then why are you looping till l1 is empty? Did you implement adding l1 to l2 instead of l2 to l1? So in your concat the arguments are reversed?
for(int i=0; i<l1.size(); i ){
And now you loop a second time, this time over all elements of l1. So for some reason this loop won't make l1 empty so you have to try over and over with the while?
l1.retrieve(i,item);
Get the i-th item of l1.
if(l2.insert(l2.size(),item)==0){
And insert it at the end of l2. If it fails:
for(int j=c; j>l2.size()-1; j--){
Starting with the old size of the list, as long as it's the last element, so actually just for the last element at position c:
l2.retrieve(j,item);
Retrieve the item one past the end of the list. So this fails and item is still the i-th element of l1.
l1.insert(l1.size(),item);
Add the i-th element of l1 to the end of l1 and ignore if it fails.
l2.remove(j);
Remove the element one past the end of l2 from the list. So this too just fails.
}
return 0;
Tell everyone we failed and now l1 and l2 are both possibly changed and maybe some item was lost.
} else {
If inserting the element in l2 succeeded:
c ;
Update the index for the end of l2 so we can't actually restore l2 to it's original state if things fail later on.
l1.remove(i);
and remove the item to complete the move.
That means item 1 is now item 0. But next loop i = 1, which is item 2 in the original list. So the for loop actually only moves every second item
to l2, which is the reason for the while.
Too bad that will scramble l1 as you append it to l2.
}
}
}
return 1;
But hey, success. We didn't overflow l2 and loose an item.
}
The list has a count. Use it to check at the start if there is enough space. No undo when things break mid way, that way lies madness.
Then use either the while with remove every loop or the for and set l1.count = 0; at the end. The later is obviously faster (O(n) vs. O(n^2)).
CodePudding user response：
this is a basic list concatenating function that satisfies order and size as you required, you could alter it to your needs.
int concat(list<int> l1, list<int> l2)
{
int item;
int l1s = l1.size();
int l2s = l2.size();
if((l1s l2s) > maxsize){
return 0;
}
while (!l2.empty())
{
item = l2.front(); // returns the first element of the list
l2.pop_front(); // removes the first element and shifts elements left
l1.push_back(item);
}
return 1;
}
int main()
{
list<int> L1, L2;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
L1.push_back(50);
L2.push_back(123);
L2.push_back(143);
L2.push_back(345);
L2.push_back(545);
L2.push_back(536);
// print(L1);
// print(L2);
cout << "<<1: succeeded, 0: failed>> " << concat(L1, L2) << endl;
cout << "First List: ";
// print(L1);
cout << "Second List: ";
// print(L2);
}