MHB List that contains only the elements of the one of the two given lists

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Elements List
AI Thread Summary
The discussion revolves around creating an algorithm to generate a new list, M3, from two sorted lists, M1 and M2, containing only the elements from M1 that do not exist in M2. The initial attempt at the algorithm is criticized for not properly creating M3 and failing to utilize the sorted nature of the lists, leading to inefficiencies. The importance of maintaining a time complexity of O(n + m) is emphasized, where n and m are the lengths of M1 and M2, respectively. Suggestions include using pointers to traverse both lists efficiently and ensuring that new nodes are created correctly to form M3. A complete solution in C++ is provided, demonstrating how to implement the algorithm correctly while handling edge cases and maintaining the sorted order. The discussion highlights the need for careful implementation and testing of the algorithm to ensure it functions as intended.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! (Smile)

Given two sorted lists $M_1, M_2$, I want to write an algorithm, that creates a new list $M_3$, that contains the elements of $M_1$, that do not exist in $M_2$.

That's what I have tried:

Code: 
Algorithm(M1,M2){
    pointer q=M1, p=M2, M3;
    int same=0;
    if (M1==NULL) return error;
    else if (M2==NULL) return M1;

    while (q!=NULL){
            while (p!=NULL){
                    if (p->data==q->data){
                       same=1;
                    }
                    p=p->next;
            }
            if (same==0){
                M3=q;
                M3=M3->next;
            }
            q=q->next;
    }   
    return M3;

Could you tell me if it is right or if I have done something wrong? (Thinking)
Is there also a better way to do this? :confused:
 
Technology news on Phys.org
This is wrong. First, you never create a new list M3; you only assign to M3 some tail of (tail of tail of...) M1. Second, you never use comparison and therefore ignore the fact that the lists are sorted.

P.S. Don't put a comma before "that". See http://www.grammarly.com/handbook/punctuation/comma/28/comma-setting-off-restrictive-clauses/.
 
Evgeny.Makarov said:
This is wrong.
So, is it totally wrong? (Worried)

Evgeny.Makarov said:
First, you never create a new list M3; you only assign to M3 some tail of (tail of tail of...) M1. Second, you never use comparison and therefore ignore the fact that the lists are sorted.

How can we create then a new list? (Thinking)

Is it possible that we write an algorithm with time complexity $O(n+m)$, where $n$ is the number of elements of $M_1$ and $m$ is the number of elements of $M_2$?
Evgeny.Makarov said:
P.S. Don't put a comma before "that". See http://www.grammarly.com/handbook/punctuation/comma/28/comma-setting-off-restrictive-clauses/.

Ok... (Nod)
 
evinda said:
So, is it totally wrong?
I am afraid so.

evinda said:
How can we create then a new list?
For this you need to create a new record with fields [m]data[/m] and [m]next[/m]. I have not been following your other threads, so I am not sure how this is done in your programming language.

evinda said:
Is it possible that we write an algorithm with time complexity $O(n+m)$, where $n$ is the number of elements of $M_1$ and $m$ is the number of elements of $M_2$?
That's the idea. To do this, you need to use the fact that the lists are sorted.

I recommend considering several example lists and figuring out how the algorithm should work in those examples. Then formulate the general algorithm.
 
I tried this:
Code: 
Algorithm(M1,M2){
  pointer p=M1, q=NULL, M3=NULL;
  while (p!=NULL){
           q=M2;
           while (q->data<p->data and q!=NULL){
                    q=q->next;
            }
            if (q->data!=p->data){
               if (M3==NULL) M3->data=p->data;
               else{
                      M3= M3->next
                      M3->data=p->data;
               }
            }
            p=p->next;
   }
}
But now the time complexity is $O(n \cdot m)$ instead of $O(n+m)$, right?
What could I change? (Thinking)
 
Evinda,
I'm afraid you're doomed to continue making errors until you're willing to let the computer help you by implementing your ideas with a real programming language.

1. while (q->data < p->data and q != null): If q is null, this won't work in any programming language that I know. If the language has "shortcut" evaluation (C++ or Java), you need to change the order of the conditions.

2. if (M3 == null) M3->data=p->data:
This fails period.

3. M3=M3->next;
M3->data=p->data; :
Even if somehow this would make sense, at the end of your algorithm, you have no way of accessing the created difference.

Following is a complete solution in C++. Notice to test the solution, you need to have sorted lists. The testing of all possible situations is an art; I think you ought to become familiar with this testing problem.

Code: 
#include <cstdlib>
#include <cstddef>
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

/* class Node is as specified.  The linked lists are singly linked with no
 * header node.
 */

class Node {
public:
  int data;
  Node* next;
  Node():data(0),next(0){};
  Node(int x):data(x),next(0){};
};

/*  Makes a sorted linked list of nodes with "random" data fields.  This list
 * represents a multiset; i.e. not all data fields need be different.  The list
 * is created (for n != 0) by first creating a node with random data and then 
 * inserting a new node with random data into its proper position.
 */
Node* makeSortedList(int n) {
  if (n == 0) {
    return(NULL);
  }
  Node *first, *p, *q, *r;
  int x = rand() % 100, i;
  first = new Node(x);
  for (i = 1; i < n; i++) {
    x = rand() % 100;
    r = new Node(x);
    q = NULL;
    p = first;
    while (p != NULL && p->data < x) {
      q = p;
      p = p->next;
    }
    if (q == NULL) {
      r->next = first;
      first = r;
    } else {
      r->next = q->next;
      q->next = r;
    }
  }
  return (first);
}

/*  Just displays a list for debugging purposes.
 */
void printList(Node* first) {
  cout << "{";
  while (first != NULL) {
    cout << first->data << ", ";
    first = first->next;
  }
  cout << "}" << endl;
}

/* Upon entry A and B point to sorted "multiset" lists of size m and n, 
 * respectively.  This computes and returns a new list, the "multiset"
 *  difference A - B. The algorithm is "obviously" of order  m + n.
 */
Node* AminusB(Node* A, Node* B) {
  Node *first, *p = A, *q, *pB = B;
  first = NULL;
  if (A == NULL) {
    return (first);
  }
  while (pB != NULL) {
    while (p != NULL && p->data < pB->data) {
      if (first == NULL) {
        first = new Node(p->data);
        q = first;
      } else {
        q->next = new Node(p->data);
        q = q->next;
      }
      p = p->next;
    }
    if (p == NULL) {
      return (first);
    }
    if (p->data == pB->data) {
      p = p->next;
    }
    pB = pB->next;
  }
  if (first == NULL) {
    first = new Node(p->data);
    q = first;
    p = p->next;
  }
  while (p != NULL) {
    q->next = new Node(p->data);
    q = q->next;
    p = p->next;
  }
  return (first);
}

int main(int argc, char** argv) {
  Node *M1, *M2, *M3;
  M1 = makeSortedList(10);
  printList(M1);
  M2 = makeSortedList(15);
  printList(M2);
  M3 = AminusB(M1, M2);
  printList(M3);
  return 0;
}
 
johng said:
1. while (q->data < p->data and q != null): If q is null, this won't work in any programming language that I know. If the language has "shortcut" evaluation (C++ or Java), you need to change the order of the conditions.

So we could also just change the order of the conditions at a pseudocode, or not?

johng said:
3. M3=M3->next;
M3->data=p->data; :
Even if somehow this would make sense, at the end of your algorithm, you have no way of accessing the created difference.
So should the algorithm look like that?

Code: 
Algorithm(M1,M2){
  pointer p=M1, q=NULL, M3=NULL, k=NULL;
  while (p!=NULL){
           q=M2;
           while (q->data<p->data and q!=NULL){
                    q=q->next;
            }
            if (q->data!=p->data){
               if (k==NULL) k->data=p->data;
               else{
                      k= k->next;
                      k->data=p->data;
               }
            }
            p=p->next;
   }
   M3=k;
   return M3;
}

johng said:
Following is a complete solution in C++. Notice to test the solution, you need to have sorted lists. The testing of all possible situations is an art; I think you ought to become familiar with this testing problem.

Code: 
#include <cstdlib>
#include <cstddef>
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

/* class Node is as specified.  The linked lists are singly linked with no
 * header node.
 */

class Node {
public:
  int data;
  Node* next;
  Node():data(0),next(0){};
  Node(int x):data(x),next(0){};
};

/*  Makes a sorted linked list of nodes with "random" data fields.  This list
 * represents a multiset; i.e. not all data fields need be different.  The list
 * is created (for n != 0) by first creating a node with random data and then 
 * inserting a new node with random data into its proper position.
 */
Node* makeSortedList(int n) {
  if (n == 0) {
    return(NULL);
  }
  Node *first, *p, *q, *r;
  int x = rand() % 100, i;
  first = new Node(x);
  for (i = 1; i < n; i++) {
    x = rand() % 100;
    r = new Node(x);
    q = NULL;
    p = first;
    while (p != NULL && p->data < x) {
      q = p;
      p = p->next;
    }
    if (q == NULL) {
      r->next = first;
      first = r;
    } else {
      r->next = q->next;
      q->next = r;
    }
  }
  return (first);
}

/*  Just displays a list for debugging purposes.
 */
void printList(Node* first) {
  cout << "{";
  while (first != NULL) {
    cout << first->data << ", ";
    first = first->next;
  }
  cout << "}" << endl;
}

/* Upon entry A and B point to sorted "multiset" lists of size m and n, 
 * respectively.  This computes and returns a new list, the "multiset"
 *  difference A - B. The algorithm is "obviously" of order  m + n.
 */
Node* AminusB(Node* A, Node* B) {
  Node *first, *p = A, *q, *pB = B;
  first = NULL;
  if (A == NULL) {
    return (first);
  }
  while (pB != NULL) {
    while (p != NULL && p->data < pB->data) {
      if (first == NULL) {
        first = new Node(p->data);
        q = first;
      } else {
        q->next = new Node(p->data);
        q = q->next;
      }
      p = p->next;
    }
    if (p == NULL) {
      return (first);
    }
    if (p->data == pB->data) {
      p = p->next;
    }
    pB = pB->next;
  }
  if (first == NULL) {
    first = new Node(p->data);
    q = first;
    p = p->next;
  }
  while (p != NULL) {
    q->next = new Node(p->data);
    q = q->next;
    p = p->next;
  }
  return (first);
}

int main(int argc, char** argv) {
  Node *M1, *M2, *M3;
  M1 = makeSortedList(10);
  printList(M1);
  M2 = makeSortedList(15);
  printList(M2);
  M3 = AminusB(M1, M2);
  printList(M3);
  return 0;
}

I will take a look at it..
 

Similar threads

C/C++ Matrix33 in C++: Create, Add, Check & Program
Replies
25
Views
2K
MHB Algorithm for Ordering Odds & Evens in Linked List L
Replies
2
Views
2K
MHB How to Properly Implement the Delete() Algorithm for Linked Lists
Replies
7
Views
2K
MHB In which case will the command be executed?
Replies
7
Views
3K
Challenge: Find the minimum amount of draws possible for a list of integers
Replies
9
Views
2K
MHB Can Recursion Reverse a Singly Linked List in Descending Order?
Replies
8
Views
2K
C: remove recursively elements of a list
Replies
3
Views
2K
Sorting Revisited #3: Linked List Merge Sort
Replies
2
Views
1K
MHB What Are the Complexity and Operations of a Static Queue?
Replies
9
Views
2K
MHB Both fields point to the same element
Replies
29
Views
4K

Hot Threads

Recent Insights

Back
Top