Name: Anonymous 2011-05-09 10:55
So I started a project for my programming class that I thought was due on Friday since projects are always due Friday, however I checked the due date and apparently it's today at midnight, so if anyone could help me with some of this id be eternally grateful.
I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table. The preliminary description of the program is as follows (this is being programmed in C):
_____________________________________________________________
"In this project, you will build a hash table abstract data type. Your ADT will permit
users to insert and search for data records in the hash table; it will also allow users to sort
data records within the hash table, and to examine them in sorted order. Your ADT will
be polymorphic, permitting the data record type to be defined by the user, and permitting
the user to control hashing and sorting by user-provided functions accessed from the ADT
via function pointers. In addition to building the hash table ADT, you will also rewrite
the parse.c example from lecture to use your new ADT. Lastly, you will also write test
vectors to test part of the ADT interface.
1 Hash Table
You are to implement a hash table as an abstract data type. As described in lecture, a
hash table allows users to insert and search for data in the hash table efficiently. Hash
table operations require the user to provide a “key” that uniquely identifies the data the
user is referring to. In this project, the hash table keys are strings. Hence, all data stored
in the hash table must be associated with a string that uniquely identifies the data. A
“hash function” is applied on the key to specify a bucket (linked list) within the hash table
where the data is located. For insert operations, the data is added to the hashed linked
list; for search operations, a linear search through the hashed linked list is performed to
find the data.
1.1 Polymorphism
Your hash table ADT will be polymorphic, allowing users to define their own data records
stored in the hash table. Your ADT will not place any constraints on the size or composition of the user’s data records. (This will permit your ADT to be very flexible, and
usable in a large number of applications). To facilitate this, the per-bucket linked lists
will employ self-referencing structures defined in your ADT. However, rather than embed
the user’s data in these structures, your linked list structures will instead point to the
user-defined data records through generic pointers.
Figure 1 illustrates the use of generic pointers. In Figure 1, user-defined structures are
denoted by shaded boxes while ADT structures are denoted by white boxes. Furthermore,
normal pointers are denoted by arrows with filled arrowheads while generic pointers are
denoted by arrows with white arrowheads. Figure 1 illustrates the structures of the ADT,
including the main “hash table” struct which contains a pointer to a buckets array. Each
element in the buckets array points to a linked list consisting of “hash entry” structs.
_____________________________________________________________
tl;dr: I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table, except I have no idea how to make an abstract data type. This is being programmed in C.
I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table. The preliminary description of the program is as follows (this is being programmed in C):
_____________________________________________________________
"In this project, you will build a hash table abstract data type. Your ADT will permit
users to insert and search for data records in the hash table; it will also allow users to sort
data records within the hash table, and to examine them in sorted order. Your ADT will
be polymorphic, permitting the data record type to be defined by the user, and permitting
the user to control hashing and sorting by user-provided functions accessed from the ADT
via function pointers. In addition to building the hash table ADT, you will also rewrite
the parse.c example from lecture to use your new ADT. Lastly, you will also write test
vectors to test part of the ADT interface.
1 Hash Table
You are to implement a hash table as an abstract data type. As described in lecture, a
hash table allows users to insert and search for data in the hash table efficiently. Hash
table operations require the user to provide a “key” that uniquely identifies the data the
user is referring to. In this project, the hash table keys are strings. Hence, all data stored
in the hash table must be associated with a string that uniquely identifies the data. A
“hash function” is applied on the key to specify a bucket (linked list) within the hash table
where the data is located. For insert operations, the data is added to the hashed linked
list; for search operations, a linear search through the hashed linked list is performed to
find the data.
1.1 Polymorphism
Your hash table ADT will be polymorphic, allowing users to define their own data records
stored in the hash table. Your ADT will not place any constraints on the size or composition of the user’s data records. (This will permit your ADT to be very flexible, and
usable in a large number of applications). To facilitate this, the per-bucket linked lists
will employ self-referencing structures defined in your ADT. However, rather than embed
the user’s data in these structures, your linked list structures will instead point to the
user-defined data records through generic pointers.
Figure 1 illustrates the use of generic pointers. In Figure 1, user-defined structures are
denoted by shaded boxes while ADT structures are denoted by white boxes. Furthermore,
normal pointers are denoted by arrows with filled arrowheads while generic pointers are
denoted by arrows with white arrowheads. Figure 1 illustrates the structures of the ADT,
including the main “hash table” struct which contains a pointer to a buckets array. Each
element in the buckets array points to a linked list consisting of “hash entry” structs.
_____________________________________________________________
tl;dr: I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table, except I have no idea how to make an abstract data type. This is being programmed in C.