A data structure is a means of grouping a number of variables of different data types together into a single unit. Here is a very simple data structure:
struct simple
{
int x;
char ch;
};
A definition of a data structure consists of the key word struct followed by a name for the data structure type, simple in this case. This is followed by the open brace (curly bracket) "{", then a list of all the variables to be enclosed within the data structure. To end the definition use the closing brace, "}", and a semicolon, ";".
This definition of the data structure does not allocate any memory, it only gives the compiler the "floor plan" of what one of these structures will look like with you declare one as in this line of code:
struct simple S1;
Using typedef: It is common practice among C programmers
to use the special definition identifier typedef (short for
type define) when defining a data structure. This allows you
to create a new data type definition using the syntax:
typedef DataType NewTypeName;
typedef int Integer; typedef float Real;
If you used these two typedefs you could then declare int and float variables using the Pascal names for these data types, thus:
Integer x; // Equivalent to int x Real f; // Equivalent to float f
If you use typedef to define the simple data structure
type it would look like this:
typedef struct
{
int x;
char ch;
}simple;
Now you can declare data structures of type simple without using
the keyword struct:
simple S1;
struct simple
{
int x;
char ch;
};
It is automatically "typdefed" so you can then declare structures of this
type without using the keyword struct. Thus:
simple S1;
The variables included in a data structure are referred to as fields.
To access one of those fields you use the name of the data structure
(the one you declare not the type name) and the name of the field, separated
by a period:
S1.x = 6; /* Set the x field in the data structure S1 to 6 */
S1.ch = 'a'; /* Set the ch field in the data structure S1 to 'a' */
It is also possible to include one data structure inside of another. If
you first define a data structure, like simple above, then you can
define another data structure that contains a simple data structure.
Assume that the simple structure has been defined (Note: assuming
C++ syntax, i.e. automatic typedef).
struct Complex
{
char label[20];
float av;
simple sim1;
};
Complex com1;
strcpy(com1.label, "Test Struct");
com1.av = 2.5;
com1.sim1.x = 12;
com1.sim1.ch = 'z';
Note that to access the fields in sim1 inside com1 you use the
name of the outer data structure, then the name of the field (sim1)
to access the inner data structure, finally the name of the field inside the
simple data structure. All are separated by periods.
To declare an array of data structures use the same syntax you use to declare arrays of other data types. Again assume that simple has been defined.
simple sims[5];
sims[3].x = 32; /* Set the x field of the 4th data structure in the array to 32 */
sims[3].ch = 'A' /* Set the ch field of the 4th data structure in the array to 'A' */
You can declare pointers to data structures just as you can declare pointers to other data types. Again assume that simple has been defined.
simple *sptr; /* Declare a pointer to a simple data structure */
simple sim1; /* Declare a data structure of type simple */
sptr = &sim1; /* Set sptr pointing to sim1 */
sptr->x = 64; /* Set the x field in sim1 to 64 */
sptr->ch = 'Z'; /* Set the ch field in sim1 to 'Z' */
simple *sptr;
simple sim1;
sptr = &sim1;
SomeFunction(sptr); /* Call function and pass the address stored in sptr */
SomeFunction(&sim1); /* Call function and pass the address of sim1 */
void SomeFunction(simple *s) /* Note: argument to the function is a pointer */
{
int i_var;
char c_var;
printf("Enter an int and a character\n");
scanf("%d %c", &i_var, &c_var);
s->x = i_var; /* Set the x field of the structure to the value stored in i_var */
s->ch = c_var; /* Set the ch field of the structure to the value stored in c_var */
}
void SomeFunction(simple& s) // Note the address operator & after the type
{
int i_var;
char c_var;
cout << "Enter an int and a character\n";
cin >> i_var >> c_var;
s.x = i_var; /* Set the x field of the structure to the value stored in i_var */
s.ch = c_var; /* Set the ch field of the structure to the value stored in c_var */
}
typedef struct simpletype
{
int x;
char ch;
struct simpletype *next;
} simple2;
struct simple2
{
int x;
char ch;
simple2 *next;
};
In all of the abstract data types you will study in this course you do not know ahead of time how many data structures you will need in the abstract data type. Therefore you will need to dynamically allocate the memory for each data structure as it is needed. To do this you use the C function malloc() which means "memory allocation, or the C++ function new.
This function takes one argument, the number of bytes to allocate, and returns the starting address of the block of memory. The prototype for this function l ooks like this:
void *malloc(int size);
This function returns a void pointer. This means it has no data type assigned to it. It is just a "raw" memory address. In order to use this block of memory as a data structure we must use a process called typecasting to convert this untyped void pointer into a pointer to our data structure type. Here is what a call to malloc() would look like to allocate a block of memory the size of a simple2. Note the use of the sizeof() function to get the number of bytes in a simple2 data structure. This saves having to count them.
simple2 *spt; /* Declare a pointer to a struct simple2 type */
spt = (simple2 *)malloc(sizeof(simple2));
spt->x = 32;
spt->ch = 'a';
spt->next = NULL; /* Set the pointer in the structure to NULL */
free(spt);
spt = new simple2();
delete spt;