5 Replies - 928 Views - Last Post: 13 January 2013 - 07:27 PM Rate Topic: -----

#1 Prdmama  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 26-November 11

Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 12:12 PM

I'm workng on a project that I thought I understood and it turns out that I have no idea what I'm doing. The program is supposed to list different set of numbers out of an existing set, implemeting union and intersection. The program builds with no errirs and partially runs but then crashes. If someone can point out what I've done wrong and how to fit it I would be much obliged. Here is my code so far.

// list.cpp
// simple linked list program

#include <stdlib.h>
#include <string>
#include <iostream>

using std::cout;
using std::string;

// node object for the linked list
struct Node {
    int data;
    Node* link;
};

// implement a singly linked list
class LinkedList {protected:
    Node* front;        // pointer to the front of the linked list
    Node* back;         // pointer to the last node in the linked list

public:
    // constructs an empty list
    LinkedList() {
        front = back = NULL;
    }

	// search the list for a target value
    // return index if found or -1 if not found
    int Search(int targetVal) {
        Node* p;
        int count = 0;
        for (p = front; p != NULL; p = p->link) {
            if (p->data == targetVal) {
                return count;
            }
            count++;
        }
        return -1;
    }
	
    // deletes the list
    ~LinkedList() {
        // remove objects from the list as long as list is not empty
        while(Length() > 0) {
            RemoveFront();
        }
    }

    // inserts a node at the front of the list
    void InsertFront(int newValue) {
        Node* newNode = new Node;
        newNode->data = newValue;
        if (front == NULL) {
            // list must be empty so make front & back point to new node
            front = back = newNode;
            newNode->link = NULL;
        } else {
            // list is not empty so insert between front and first node
            newNode->link = front;
            front = newNode;
        }
    }

    // removes a node from the front of the list
    int RemoveFront() {
        int returnVal;
        Node *temp;
        if (front != NULL) {
            // list is not empty so remove & return first node
            returnVal = front->data;
            temp = front;
            front = front->link;
        } else {
            // list is empty just return 0
            returnVal = 0;
        }
        return returnVal;
    }

    // returns the length of the list
    int Length() {
        Node* p;
        int count = 0;
        // loop through each node in the list until we find a null value
        for (p = front; p != NULL; p = p->link) {
            count++;
        }
        return count;
    }

    // outputs a string containing all the data values in the list
    void Output() {
        Node* p;
        // loop through each node in the list until we find a null value
        for (p = front; p != NULL; p = p->link) {
            cout << p->data << ", ";
        }
    }
};

// use inheritance to create a Set class from the LinkedList class
class Set : public LinkedList {
public:
    // insert a new value only if it is unique (not already in the set)
    void Insert(int newValue) {
		int duplicate = Search(newValue);
		if (duplicate == -1)
			InsertFront(newValue);
    }

    // make this the union of two sets
    void Union(Set& a, Set& B)/> {
		Node*p;
		for(p = a.front; p != NULL; p = p->link)
		{
			Insert(p->data);
		}
		for(p = b.front; p != NULL; p = p->link)
		{
			Set::Insert(p->data);
		}
	}

    // make this the intersection of two sets
    void Intersection(Set& a, Set& B)/> {
		Node*p;
		Node*q;
		for(p = a.front; p != NULL; p = p->link)
		{
			for(q = b.front; p != NULL; p = p->link)
			{
				if (p == q)
				{
					Insert(p->data);
				}
			}
		}
	}
};


int main() {
    Set setA, setB, setUnion, setIntersection;

    setA.Insert(5);
    setA.Insert(2);
    setA.Insert(3);
    setA.Insert(5);
    setA.Insert(2);

    cout << "Contents of setA: ";
    setA.Output();
    cout << "\n\n";

    setB.Insert(1);
    setB.Insert(2);
    setB.Insert(4);

    cout << "Contents of setB: ";
    setB.Output();
    cout << "\n\n";

    setUnion.Union(setA, setB);
    cout << "Contents of setA union setB: ";
    setUnion.Output();
    cout << "\n\n";

    setIntersection.Intersection(setA, setB);
    cout << "Contents of setA intersection setB: ";
    setIntersection.Output();
    cout << "\n\n";
}





Is This A Good Question/Topic? 0
  • +

Replies To: Using Search, Union and Intersection in a Linked List, Program Crash

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 3848
  • View blog
  • Posts: 11,775
  • Joined: 25-December 09

Re: Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 12:54 PM

Have you tried running this program thru your debugger? The debugger should be able to show you exactly where the problem is being detected. Then you should be able to view the variables at the time of the crash and start backtracking the problem.

Jim
Was This Post Helpful? 0
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 01:02 PM

Quote

(gdb) run
Starting program: /home/knowles/code/cpp/dichelp/union/a.out
Contents of setA: 3, 2, 5,

Contents of setB: 4, 2, 1,

Contents of setA union setB: 1, 4, 5, 2, 3,


Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e00 in Set::Intersection (this=0x7fffffffde80, a=..., b=...) at list.cpp:129
129 for(p = a.front; p != NULL; p = p->link)
(gdb) bt
#0 0x0000000000400e00 in Set::Intersection (this=0x7fffffffde80, a=..., b=...) at list.cpp:129
#1 0x00000000004009b3 in main () at list.cpp:169
(gdb) inspect p
$1 = (Node *) 0x0
(gdb) inspect a
$2 = (Set &) @0x7fffffffdeb0: {<LinkedList> = {front = 0x602050, back = 0x602010}, <No data fields>}


Ta da! Time to step through and see how you to that state.
Was This Post Helpful? 0
  • +
  • -

#4 Prdmama  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 26-November 11

Re: Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 01:16 PM

View Postjimblumberg, on 13 January 2013 - 12:54 PM, said:

Have you tried running this program thru your debugger? The debugger should be able to show you exactly where the problem is being detected. Then you should be able to view the variables at the time of the crash and start backtracking the problem.

Jim

I'm still learning how to code and I have to admit that I don't know how to use the debugger, how to understand what has been written or how to fix the bugs it finds.

View PostKYA, on 13 January 2013 - 01:02 PM, said:

Quote

(gdb) run
Starting program: /home/knowles/code/cpp/dichelp/union/a.out
Contents of setA: 3, 2, 5,

Contents of setB: 4, 2, 1,

Contents of setA union setB: 1, 4, 5, 2, 3,


Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e00 in Set::Intersection (this=0x7fffffffde80, a=..., b=...) at list.cpp:129
129 for(p = a.front; p != NULL; p = p->link)
(gdb) bt
#0 0x0000000000400e00 in Set::Intersection (this=0x7fffffffde80, a=..., b=...) at list.cpp:129
#1 0x00000000004009b3 in main () at list.cpp:169
(gdb) inspect p
$1 = (Node *) 0x0
(gdb) inspect a
$2 = (Set &) @0x7fffffffdeb0: {<LinkedList> = {front = 0x602050, back = 0x602010}, <No data fields>}


Ta da! Time to step through and see how you to that state.

Thanks KYA...but I don't actually understand what you've written. I'd like to. I'm still learning from the ground up. Embarrassing as it is to admit I was rather proud to get this far. But even masters have to be apprentices first huh?
Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg  Icon User is offline

  • member icon


Reputation: 3848
  • View blog
  • Posts: 11,775
  • Joined: 25-December 09

Re: Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 01:27 PM

KYA's message is telling you that your program is crashing on line 129, which should be: for(p = a.front; p != NULL; p = p->link).

Now you need to figure out what is wrong with that line.

Jim
Was This Post Helpful? 0
  • +
  • -

#6 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1276
  • View blog
  • Posts: 4,401
  • Joined: 19-February 09

Re: Using Search, Union and Intersection in a Linked List, Program Crash

Posted 13 January 2013 - 07:27 PM

Looks likely the problem is line 131.

131      for(q = b.front; p != NULL; p = p->link)


This post has been edited by #define: 13 January 2013 - 07:39 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1