MHB Help Me Fix My Program: What Is Wrong?

[needOfHelpCMath]

What is wrong with my program? I am so close to finish it. May anyone tell me what is wrong and how to fix it.

#include <iostream>
#include <cstdlib>
using namespace std;

class Node {
   public:
   
   Node(); 
   
   Node* prev;
   
   string key;
   
   Node* next;
};

Node::Node(){
   prev = 0;
   next = 0;
}

class LinkedList {
   public:
   LinkedList();
   void Insert(string key);
   void Print();
   Node* Find(string key);
   void Delete(Node* x);
   
   Node* head;
};
LinkedList::LinkedList(){
   head=0;
}
void LinkedList::Insert(string key) {
   Node* n;
   
    n=new Node;
     n->key= key;
      
      n->next = head;
      
      head=n;
      
      return;
}
void LinkedList::Print() {
   
 Node* n;
 cout <<"Print"<<endl;
 n=head;
 
 
 while (n!=0){
      cout << n->key << endl;
      n=n->next;
   }
   return;
   }
   
/*void LinkedList::Find() {
   
 Node* n;
 cout <<"Print"<<endl;
 n=head;
 
 
 while (n!=0){
      cout << n->key << endl;
      n=n->next;
   }
   return;
   }
   */
   
int main(){
  
   string line;
   LinkedList l;
   
while (true){
   
   getline(cin, line);
   if (line.empty()){
      break;
   }
    l.Insert(line);
   
}
l.Print();
/*
   
   
   n = l.Find("test3");
   cout << "found key "<< n->key << endl; 
*/

return 0;
}

*What I got correct*
1. Unit test
1/1
Code Compiles

2. Compare output:
1/1
Input
100
200

Your output	:
Print
200
100

3. Unit test
1/1

Test Node Class
4. Unit test
1/1

Test Linked List Insert Function
5. Unit test
1/1

Insert Twice
6. Unit test
0/1
Find Node Test

 

[johng1]

1. Your Node class has prev and next pointers. So it seems like your linked list would be a doubly linked list. However, in your insert function, you do not update the prev pointers.

2. Your find method should return a pointer to a node. Here's one possibility for the body of find:

Node *n = head;
while (n) {
  if (n->key == key) {
    return(n);
  }
  n = n->next;
}
return(NULL);  // key not in list has return of 0

3. Presumably, you are to also write method delete. Post again if you need help for this method.

 

[needOfHelpCMath]

Okay thank you! ill post again here if i need help. Thank you very much

 

[needOfHelpCMath]

okay now i need help for the "Delete" method

#include <iostream>
#include <cstdlib>
using namespace std;

class Node {
   public:
   
   Node(); 
   
   Node* prev;
   
   string key;
   
   Node* next;
};
Node:: Node(){
   prev=0;
   next=0;

}
class LinkedList {
   public:
   LinkedList();
   void Insert(string key);
   void Print();
   Node* Find(string key);
   void Delete(Node* x);
   
   Node* head;
};
LinkedList::LinkedList(){
   head=0;
}
void LinkedList::Insert(string key) {
   Node* n;
   
    n=new Node;
     n->key= key;
      
      n->next = head;
      
      head=n;
      
      return;
}
void LinkedList::Print() {
   
 Node* n;
 cout <<"List:"<<endl;
 n=head;
 
 
 while (n!=0){
      cout << n->key << endl;
      n=n->next;
   }
   return;
   }
   
Node* LinkedList::Find(string key){
   Node* n;
 cout <<""<<endl;
 n=head;
 while (n!=0){
     if(n->key==key){
         cout << n->key << endl;
         return n;
     }
      n=n->next;
      
   }
   return 0;
}
   

   
int main(){
   
  
   LinkedList l;
 //  Node* n;
   
   
   string line;
   while(true){
      
      getline(cin, line);
      if(line.empty()){
         break;
         
      }
      
      l.Insert(line);
      
      
   
   }
   l.Print();
/*
n=l.Find("Test 1");
if(n==0){
   cout << "ERROR";
}
*/
return 0;

}

what i got right so far:

1. Unit test
1/1
Code Compiles
2. Compare output
2/2
Input
Input Test 1
Input Test 2
Input Test 3
Your output	
List:
Input Test 3
Input Test 2
Input Test 1
3. Unit test
2/2
Test Node Class
4. Unit test
2/2
Test Linked List Insert Function
5. Unit test
2/2
Insert Twice
6. Unit test
2/2
Find Node Test
Your output

test2

test1

7. Unit test
0/1
 Delete Node For a bonus question you can add the LinkedList member function Delete to delete a node: ``` void LinkedList::Delete(Node* n); ```

 

[johng1]

First comment. In your implementation of Find, you print the key of the sought node. Normally, you don't want to do this. Unless the specification of a method calls for output (printing), don't have print statements in the method. I wouldn't think Find should have any printing.

Here's most of the body of a Delete method:

if (x==NULL || head==NULL) {
  return; // do nothing for empty list or removal of NULL pointer
}
if (x==head) {
  // you write the updates of the pointers
  return;
}
Node *p=head->next, *q=head;
while (p != NULL) {
  if (p==x) {
    // you update the pointers
    return;
  }
  q=p;
  p=p->next;
}

Comments:
Assuming x!=NULL and head!=NULL, for x==head, you just need to change head appropriately; otherwise you need to find the node *x in the list and also the node that precedes x in the list. For x!=head, you do this by sending two pointers p and q down the list with always q==p->prev. Then one assignment removes x from the list. Finally, it's a good idea to set x->next to NULL before a return.

Rather than Delete a void function, I would probably make it a boolean method, returning true for a successful removal and false otherwise. There is also the question of whether Delete should deallocate the storage for node x. If the specification says to do this, you need to include a call delete(x) before you return. I would think a reasonable Delete would leave this deallocation to the caller.

Finally, Delete is much "easier" for a doubly linked list. You might try to implement a doubly linked list and modify all the methods.

 

[needOfHelpCMath]

First comment. In your implementation of Find, you print the key of the sought node. Normally, you don't want to do this. Unless the specification of a method calls for output (printing), don't have print statements in the method. I wouldn't think Find should have any printing.

Here's most of the body of a Delete method:

if (x==NULL || head==NULL) {
  return; // do nothing for empty list or removal of NULL pointer
}
if (x==head) {
  // you write the updates of the pointers
  return;
}
Node *p=head->next, *q=head;
while (p != NULL) {
  if (p==x) {
    // you update the pointers
    return;
  }
  q=p;
  p=p->next;
}

Comments:
Assuming x!=NULL and head!=NULL, for x==head, you just need to change head appropriately; otherwise you need to find the node *x in the list and also the node that precedes x in the list. For x!=head, you do this by sending two pointers p and q down the list with always q==p->prev. Then one assignment removes x from the list. Finally, it's a good idea to set x->next to NULL before a return.

Rather than Delete a void function, I would probably make it a boolean method, returning true for a successful removal and false otherwise. There is also the question of whether Delete should deallocate the storage for node x. If the specification says to do this, you need to include a call delete(x) before you return. I would think a reasonable Delete would leave this deallocation to the caller.

Finally, Delete is much "easier" for a doubly linked list. You might try to implement a doubly linked list and modify all the methods.

Thank you very much for your guidance appreciate it! Thank you.