这个作业是用C语言完成结构体和哈希表的练习

CAB403 Practical Sheet
Practical 3 – Dynamic Data Structures
Task 1: Structures
Structures allow data of different types to be stored together. They specify how types will be laid
out in memory. The struct race below specifies that an integer is followed by a float.
Assuming a 32-bit int and float where both types are aligned to 4 byte boundaries the struct
will be 8 bytes in size and pi points to the integer value 60 and pf points to the float value 5.5.
How types are laid out in memory is machine and compiler dependent. Generally speaking,
types are aligned to boundaries that match the word size of the machine. Types can be padded
out making the size of the struct larger than you would expect (large than the addition of the
size of both types).

struct race {
int seconds;
float distance;
};
struct race r = {60, 5.5};
struct race *pr = &r;
int *pi = (int *)pr;
float *pf = (float *)((char *)pr) + 4);

A pointer is a numeric variable used to hold a memory address. When you declare a pointer
using a variable, you should specify the type of the variable that is located at the address stored
in the pointer variable. A struct is another type, therefore you can create pointers to structs.
Arrays and structures are commonly used in C. An array of structures operates just like an array
of any other data type.

The linked list data structure can be represented using structures. Each node in the list contains
the data associated with the node and a pointer to the next node. A pointer to the first element
in the list provides access to the list. The list terminates when the next pointer is NULL. When
the head pointer in NULL the list is empty.

struct node {
int data;
struct node *next;
};

struct node* head = NULL;

Download struct_list.c from Blackboard and complete the specified sections marked as
TODO.
The following are the outputs of your implementation:

$ gcc -o struct_list struct_list.c && ./struct_list
two people:
name=aaron age=52years height=154cm
name=beth age=67years height=207cm
an array of people:
name=aaron age=52years height=154cm
name=beth age=67years height=207cm
name=charlie age=44years height=188cm
name=danika age=5years height=72cm
an array of pointers to people:
name=aaron age=52years height=154cm
name=beth age=67years height=207cm
name=charlie age=44years height=188cm
name=danika age=5years height=72cm
a linked list of people:
name=danika age=5years height=72cm
name=charlie age=44years height=188cm
name=beth age=67years height=207cm
name=aaron age=52years height=154cm
searching for charlie:
name=charlie age=44years height=188cm
removing danika:
name=charlie age=44years height=188cm
name=beth age=67years height=207cm
name=aaron age=52years height=154cm
removing aaron:
name=charlie age=44years height=188cm
name=beth age=67years height=207cm
removing beth and charlie:

Task 2: Hash Tables
Hash tables are a particular implementation of the associative array Abstract Data Type (ADT).
It is composed of a collection of unique keys and a collection of values. Each key is associated
with one value. Values can be looked up by key. You may know the hash table as a HashMap
in Java or a Dictionary in C# and Python.

C does not have a hash table in the standard library or built into the language. Instead you must
construct a hash table using a hash function, arrays and structures. The hash table you will
implement consists of an array, which represents the buckets items can hash to and a linked list
in each bucket to deal with hash collisions.

A hash function produces a number that summarises the content of a larger type. In the
example code we have implemented a hash function for strings for you. There exist many
different hash functions with varying speed and quality. Quality is determined by how often hash
collisions occur.

Below is an illustration of a hash table with 4 buckets. Two items hash to bucket 0 and one item
hashes to bucket 3. Buckets 1 and 2 contain NULL pointers representing empty lists.