2 Replies - 1206 Views - Last Post: 18 November 2012 - 09:39 AM Rate Topic: -----

#1 andre1011  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 87
  • Joined: 12-January 11

print chained hash table

Posted 17 November 2012 - 09:42 PM

Hello everyone, I ant to print out the contents of a chained hashed table that is implemented with link lists.
The table has an ordinary array that is filled with nodes (structs) so dataArray[0] contains a node and dataArray

[1] contains a node and so forth to dataArray[9]; The problem is the printTable() function prints out the link

list at dataArray[0] then crashes, the counter "i" never gets incremented.

I am on a windows 7 platform using Visual Studio 2008, here is my very long code

link2.h
#ifndef LINK2_H
#define LINK2_H
#include <stdlib.h> // Provides size_t

    template <class Item>
    struct Node
    {
        Item data;
        Node *link;
    };

    // FUNCTIONS for the linked list toolkit
    template <class Item>
    size_t list_length(Node<Item>* head_ptr);

    template <class Item>
    void list_head_insert(Node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_insert(Node<Item>*& previous_ptr, const Item& entry);

    template <class Item>
    Node<Item>* list_search(Node<Item>* head_ptr, const Item& target);
	
    template <class Item, class SizeType>

    Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position);

    template <class Item>
    void list_head_remove(Node<Item>*& head_ptr);

    template <class Item>
    void list_remove(Node<Item>* previous_ptr);

    template <class Item>
    void list_clear(Node<Item>*& head_ptr);

    template <class Item>
    void list_copy 
      (Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr);

    template <class Item>
    void list_piece
      (Node<Item>*  source_ptr, Node<Item>*  end_ptr,
       Node<Item>*& head_ptr,   Node<Item>*& tail_ptr);

#include "link2.template"  // Include the implementation
#endif




link2.template
// FILE: link2.template
// IMPLEMENTS: The ten template functions of the linked list toolkit
// (see link2.h). Note that this file is not compiled on its own.
// Instead, this file is included with an include directive at the bottom
// of link2.h.

#include <assert.h>    // Provides assert
#include <stdlib.h>    // Provides NULL and size_t

template <class Item>
size_t list_length(Node<Item>* head_ptr)
// Library facilities used: stdlib.h
{
    Node<Item> *cursor;
    size_t answer;

    answer = 0;
    for(cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        answer++;

    return answer;
}

template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& new_item)
{
    Node<Item> *insert_ptr;

    insert_ptr = new Node<Item>;
    insert_ptr->data = new_item;
    insert_ptr->link = head_ptr;
    head_ptr = insert_ptr;

//cout<<" **list_head_insert** head_ptr->data  "<< head_ptr->data<< " \n";
}

template <class Item>
void list_insert(Node<Item>* &previous_ptr, const Item& new_item)
{
    Node<Item> *insert_ptr;

    insert_ptr = new Node<Item>;
    insert_ptr->data = new_item;
//	 insert_ptr->link = NULL;
 //  previous_ptr->link = insert_ptr;
   insert_ptr->link = previous_ptr->link;
   previous_ptr->link = insert_ptr;

//   cout<<" $$list_insert$$ previous_ptr->data  "<< previous_ptr->data<< " \n";
 //     cout<<" $$list_insert$$ insert_ptr->data  "<< insert_ptr->data<< " \n";
}

template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
{
    Node<Item> *cursor;

    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        if (cursor->data == target)
            return cursor;

    return NULL;
}

template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position)
// Library facilities  assert.h, stdlib.h
{
    Node<Item> *cursor;
    size_t i;

    assert(position > 0);
    
    cursor = head_ptr;
    for(i = 1; (i != position) && (cursor != NULL); i++)
        cursor = cursor->link;
    return cursor;
}

template <class Item>
void list_head_remove(Node<Item>*& head_ptr)
{
    Node<Item> *remove_ptr;

    remove_ptr = head_ptr;
    head_ptr = head_ptr->link;
    delete remove_ptr;
}

template <class Item>
void list_remove(Node<Item>* previous_ptr)
{
    Node<Item> *remove_ptr;

    remove_ptr = previous_ptr->link;
    previous_ptr->link = remove_ptr->link;
    delete remove_ptr;
}

template <class Item>
void list_clear(Node<Item>*& head_ptr)
// Library facilities used: stdlib.h
{
    while (head_ptr != NULL)
        list_head_remove(head_ptr);
}

template <class Item>
void list_copy
(Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Library facilities used: stdlib.h
{
    head_ptr = NULL;
    tail_ptr = NULL;

    // Handle the case of the empty list
    if (source_ptr == NULL)
        return;

    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_ptr, source_ptr->data);
    tail_ptr = head_ptr;

    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (source_ptr = source_ptr->link; source_ptr != NULL; source_ptr = source_ptr->link)
    {
        list_insert(tail_ptr, source_ptr->data);
        tail_ptr = tail_ptr->link;
    }
}

template <class Item>
void list_piece
(Node<Item>* start_ptr, Node<Item>* end_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Library facilities used: assert.h, stdlib.h
{
    head_ptr = NULL;
    tail_ptr = NULL;

    // Handle the case of the empty list
    if (start_ptr == NULL)
        return;
    
    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_ptr, start_ptr->data);
    tail_ptr = head_ptr;
    if (start_ptr == end_ptr)
        return;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (start_ptr = start_ptr->link; start_ptr != NULL; start_ptr = start_ptr->link)
    {
        list_insert(tail_ptr, start_ptr->data);
        tail_ptr = tail_ptr->link;
        if (start_ptr == end_ptr) 
            return;
    }
}

/*template <class Item>
void operator =(const Node<Item>& source) 
// Library facilities used: link2.h, stdlib.h 
{
    size_t i;
  //  Node<Item>* tail_ptr; // Needed for list_copy

    if (this == &source)
        return; // Avoid self-assignment
		this=&&source;


}*/



table.h
#ifndef TABLE_H
#define TABLE_H
#include<cstdlib>
#include"link2.h"

template<class RecordType>
class Table
{


 public:  static const size_t TABLESIZE = 10;
		  Table();
		  Table(const Table& source);
		  ~Table();
		  void operator =(const Table& source);
		  void printTable();
		  

 private: size_t totalRecords;
		  Node<RecordType> dataArray[TABLESIZE];
          size_t hash(int key);
		  Node<RecordType> *head;
		  Node<RecordType> *tail;
};
#include "table.template" 
#endif




table.template

template<class RecordType>
Table<RecordType>::Table()
{  
  for(size_t i = 0; i <= TABLESIZE; i++)
  {
    dataArray[i].data = NULL;
  }
  totalRecords = 0;
  
}/* end constructor */


template<class RecordType>
Table<RecordType>::Table(const Table& source)
{
  dataArray = Node<RecordType>[source->TABLESIZE];
/*  for(size_t i = 0; i < TABLESIZE; i++)
  {
    dataArray[i]->data = source.data[i];
    dataArray[i]->link = source.link[i];
  }
 */
 list_copy(dataArray, head, tail);
 totalRecords = source.totalRecords;
}/* end copy constructor */


template<class RecordType>
Table<RecordType>::~Table()
{
  list_clear(head);
    
}/* end destructor */

template<class RecordType>
void Table<RecordType>::operator =(const Table& source)
{
  for(size_t i = 0; i < TABLESIZE; i++)
  {
    dataArray[i]->data = source.data[i];
    dataArray[i]->link = source.link[i];
  }
  totalRecords = source.totalRecords;
}/* end operator = */

template<class RecordType>
void Table<RecordType>::printTable()
{
 Node<RecordType> *cursor;
 for(size_t i = 0; i < TABLESIZE; i++)
 {
   for(cursor = &dataArray[i];  cursor->link != NULL; cursor = cursor->link) /* here is where the trouble is */
   {
     if(cursor->data == NULL)                     /* it prints the link list at dataArray[0] and crashes  */
     {
       cout<<"[( "<<i<<" )]---> NULL"<<endl;
     }
     else
     {
       cout<<"[( "<<i<<" )]---> "<<cursor->data<<" "<<endl;
     }
   } 
 }
 
}/* end printTable */





driver,
#include<iostream>
#include"table.h"
using namespace std;

int main()
{

  Table<int> first;
  first.printTable();
  return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: print chained hash table

#2 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: print chained hash table

Posted 17 November 2012 - 10:04 PM

     if(cursor->data == NULL)   


Why would data ever be NULL? I think you meant to check the next pointer of cursor.
Was This Post Helpful? 1
  • +
  • -

#3 andre1011  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 87
  • Joined: 12-January 11

Re: print chained hash table

Posted 18 November 2012 - 09:39 AM

initially there is no data when the list is created so I use NULL to signify this fact, at a later time in the life of the program, all of the lists will be filled with positive integers
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1