C++

Forum

 
Trouble with Hash Table Sorting

mattrowe84 (6)
HI I am having an issue with my sort function. This is one part of the Hash table program. The main issue is that I am trying to sort the pointer table after all of the values have been entered. The ptr_sort function is not a class function and so I am therefore unable to use the class variables psize and pTable. Is there another way I should be trying this? it is a Vector should I use the sort() function from the vector class in STL? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include "/home/onyuksel/courses/340/progs/13f/p9/util9.h"
#include "/home/onyuksel/courses/340/progs/13f/p9/hTable.h"

#ifndef H_TABLE1
#define H_TABLE1


void ptr_sort ( );


HT::HT (  const unsigned& s )
{
        hTable.resize(s);
        pTable.resize(s);
        psize = 0;
        hsize = TBL_SZ;
        for (unsigned int i = 0; i != s; i++)
        {
                hTable[i].key = FREE;
        }
}


HT::~HT()
{
        //delete [] hTable;
        //delete [] pTable;
}


void HT::insert ( const Entry& e )
{
        int index = hash(e.key);
        unsigned int i;
        for (i = 0; i < hsize; i++)
        {
                if (hTable[(index+i)%hsize].key == FREE)
                {
                        // use open addressing: linear probing for collision resolution
                        cout << " entry = " << (index + i) % hsize << endl;
                        hTable[(index+i)%hsize] = e;
                        pTable[psize] = &hTable[(index+i)%hsize];
                        psize++;
                        break;
                }
                if (hTable[(index+i)%hsize].key == e.key)
                {
                        cout << " not inserted - duplicate key!!!" << endl;
                        break;
                }
        }
        if (i == hsize)
                cout << " not inserted - table full!!!" << endl;



}

       int index = hash(s);
        unsigned int i;
        for (i = 0; i < hsize; i++)
        {
                if (hTable[(index+i)%hsize].key == s)
                {
                        cout << " ==> number: "
                        << setw(4) << hTable[(index+i)%hsize].num
                        << " - item: " << hTable[(index+i)%hsize].desc
                        << endl;
                        break;
                }
        }
        if (hTable[(index+i)%hsize].key != s)
                cout << " not in table!!" << endl;
}


void HT::hTable_print ( )
{
        bool lastEmpty = false;
        for ( unsigned int i = 0; i < hsize; i++ )
        {
                if ( hTable[i].key != FREE )
                {
                        if ( lastEmpty ) cout << endl;
                        cout << setw(4) << i << ":  " << hTable[i].key << " - "
                        << setw(5) << hTable[i].num << "   -  " << hTable[i].desc << endl;
                        lastEmpty = false;
                }
                else lastEmpty = true;
        }
        cout << endl;
}


void HT::pTable_print ( )
{
        ptr_sort();
        for (unsigned int i = 0; i < psize; i++ )
        {
                cout << "   " << pTable[i]->key
                << " - " << right << setw(4) << pTable[i]->num
                << " - " << left << pTable[i]->desc << endl;
        }
        cout << endl;
}


void ptr_sort ( )
{
        unsigned int i, j;
        Entry* bucket;
        for (i = 1; i < psize; i++)
        {
                bucket = pTable[i];
                for (j = i; (j > 0) && (pTable[j-1]->key > bucket->key); j--)
                            pTable[j] = pTable[j-1];

                pTable[j] = bucket;
        }
}


#endif
naraku9333 (2163)
Do you have to use the ptr_sort function?
1
2
3
4
5
6
7
8
9
10
11
 
void HT::pTable_print ( )
{
        std::sort(pTable.begin(), pTable.end());//ptr_sort();
        for (unsigned int i = 0; i < psize; i++ )
        {
                cout << "   " << pTable[i]->key
                << " - " << right << setw(4) << pTable[i]->num
                << " - " << left << pTable[i]->desc << endl;
        }
        cout << endl;
}
Topic archived. No new replies allowed.