Solved

Segmentation Core Dump -> doubly linked list -> dlist.h() { & int main() { algorithm

Posted on 2004-10-24
329 Views
Last Modified: 2010-05-18
/*      Filename:      dlist.h
      programmer: Enrique De Los Santos
        Project:      Hw #5
        Date:            10/23/2004
        Purpose:      doubly linked list */

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   bool full() const;
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
/*  if (!empty()){
    Node< Entry_type > *currentPtr = head;
//    Node< Entry_type > *temp;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
    }
  }
*/
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
void List< Entry_type >::clear()
{
  if (!empty()){
    Node< Entry_type > *currentPtr = head;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
      delete head;
      head = NULL;
    }
  }
  count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
  if (count == 0)
    return true;
  return false;
}

template< class Entry_type >
bool List< Entry_type >::full() const
{
  return false;
}

template< class Entry_type >
int List< Entry_type >::size() const
{
  return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  if (head == NULL)
    return;
  Node< Entry_type > *currentPtr = head;
  while ( (*currentPtr).next != NULL){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).next;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != head){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).back;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
  if (empty())
    throw "Underflow, cannot retrieve";
  if (pos > count)
    throw "Range Error, cannot retrieve";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  return (*currentPtr).entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
  if (empty())
    throw "Underflow, cannot replace";
  if (pos > count)
    throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = (*currentPtr).next;
  (*currentPtr).entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
  if (full())
    throw "Overflow, cannot insert";
  if (pos > count+1)
    throw "Range Error, cannot insert";
  if (pos == 1)
    head = new Node< Entry_type>(usrEntry);

  else {
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *newPtr = new Node< Entry_type >;
   for (int i = 1; i < pos-1; i++)
     currentPtr = (*currentPtr).next;
   (*newPtr).next = (*currentPtr).next;
   (*newPtr).entry = usrEntry;
   (*currentPtr).next = newPtr;
   (*newPtr).back = currentPtr;
   currentPtr = head;

   if ((*currentPtr).next != NULL){
    while ( (*(*currentPtr).next).next != NULL)
     currentPtr = (*currentPtr).next;
    rear = (*currentPtr).next;
   }
  }

 count++;
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos > count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  Node< Entry_type > *tempPtr = (*(*currentPtr).next).next;
  delete (*currentPtr).next;
  (*currentPtr).next = tempPtr;

  if ((*currentPtr).next != NULL){
   while ( (*(*currentPtr).next).next != NULL)
    currentPtr = (*currentPtr).next;
   rear = (*currentPtr).next;
  }
  count--;
}

#endif

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

using namespace std;

int main() {
 
   int data;
   data = 1;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   //int data = 1;
   the_list.retrieve(data);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}


out:

m[edeloss2@pegasus part1]$ main
Segmentation fault (core dumped)

0
Question by:edelossantos
    5 Comments
     
    LVL 3

    Assisted Solution

    by:Indrawati
    in void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry):

    Node< Entry_type > *currentPtr = head;
    Node< Entry_type > *newPtr = new Node< Entry_type >;
    for (int i = 1; i < pos-1; i++)
       currentPtr = (*currentPtr).next;
    (*newPtr).next = (*currentPtr).next;

    What would happen ifhead is NULL (i.e. the list is empty)?
    0
     
    LVL 3

    Assisted Solution

    by:Indrawati
    You should change the

    if (pos == 1)

    in void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry) to

    if(pos == 0)
    0
     

    Author Comment

    by:edelossantos
    I am getting:

    [edeloss2@pegasus part1]$ main
    The List:
    10000
    1 retrieved at position 1



    should be:

    The List:
    1 2 3 4 5
    2 retrieved at position 1
    The_List after removing positions 0 2 5 and inserting 2,2:
    2 3 2 5
    A copy of The_List after inserting 2,9:
    2 3 9 2 5
    A copy of The_List displayed in reverse:
     5 2 3 2

    0
     
    LVL 3

    Accepted Solution

    by:
    Some pointers:

    1. I see there's some indexing error in the code, e.g.:

    in Entry_type List< Entry_type >::retrieve(const int pos) const:

    for (int i = 1; i < pos; i++)

    should be

    for (int i = 0; i < pos; i++)

    in void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry):

    for (int i = 1; i < pos-1; i++)

    should be

    for (int i = 0; i < pos-1; i++)


    2. In int main():

    the_list.retrieve(data)
    cout << data << " retrieved at position 1" << endl;

    should be

    cout << the_list.retrieve(data) << " retrieved at position 1" << endl;


    3. In int main():

    When you execute

    the_list.remove(4);

    an exception WILL be thrown, since the size of the list is now < 4 (you have removed two elements in the last two lines).
    0
     
    LVL 39

    Assisted Solution

    by:itsmeandnobodyelse
    Del, you shouldn't post two (or more) questions to the same issue.

    Look at

    http:Q_21180697.html

    Regards, Alex


    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    6 Surprising Benefits of Threat Intelligence

    All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

    Suggested Solutions

    Title # Comments Views Activity
    Help to find mistake. c++ 2 68
    why "." vs "->" 23 104
    add elements to existing standard structure 2 83
    Writing a parser for java language 4 42
    In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
    Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
    The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
    The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

    877 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now