[SOLVED] CS data structure compiler OSU CSE 2421

OSU CSE 2421
Required Reading: Pointers On C, Chapter 10, through Section 10.3
J.E.Jones

OSU CSE 2421
Recall that ANSI C has a set of default data types: char, short, int, long, float, double.
An aggregate data type is one that can hold more than one individual piece of data at a time.
Recall that ANSI C allows a programmer to define additional data types as s/he sees fit.
ANSI C has two aggregate data types, arrays and structures. An array is a collection of values that are all the same data type
A structure is a collection of values, called members, but the members of a structure may be of different types.
J. E. Jones

OSU CSE 2421
Array elements can be accessed with an index or subscript because all the elements are of the same size/type, and because they are stored at contiguous locations in memory.
The situation is different with structures. Because a structures members can be of different sizes, subscripts or indexes cannot be used to access them.
This distinction is important. A structure is not an array of its members. Unlike an array name, the name of a structure variable is not replaced with a pointer when it is used in an expression.
Subscripts/indexes cannot be used on a structure variable to access its members.
Instead, structure members are given names (identifiers), and are accessed by those names.
J. E. Jones

OSU CSE 2421
The following can all be done with structures:
1. 2.
Structures may be passed as arguments to functions;
3.
Structures of the same type may be assigned to one another
4. 5. 6.
We can declare arrays of structures.

Passed by value or passed by reference

As we have already seen this is not true of arrays in ANSI C But, if there is an array within a structure, it copies correctly. We can declare pointers to structures;
We can take the address of a structure variable;
They may be returned by functions;
J. E. Jones

OSU CSE 2421
The format of a structure declaration is:
struct tag { member-list with type of each member } variable list ;
struct is a keyword in C.
As we saw with enumerated data, the tag field* and the variable-list field are
each optional, but at least one of them is required:
If the tag is omitted, only the variables with identifiers which appear in the variable-list field are declared to be of this structure type, and no other variables of this type can be declared subsequently.
If the tag field is included, then the variable-list field can be empty or omitted. In this case, the tag can be used later to declare variables of this structure type. The tag field is required if you wish to use malloc() or calloc().
*When putting a structure declaration in a .h file, you must use a tag field because you cannot use a variable list. I highly recommend always using a tag field.
J. E. Jones

OSU CSE 2421
Consider these two structure declarations:
struct { int a;
float b; } x;
/* If these two structures are declared in the */
/* same program, x is of a different data type from */ /* the elements of y, and the data type of *z is also */ /* different from the data type of x. */
struct { int a;
float b;
} y[10], *z;
The compiler has no way of recognizing that the contents of these two structures are identical, so it considers them to be a different as an iceberg and a gerbil are to one another.
Therefore, the following are invalid:
z = &x /* Invalid compilation will fail (compiler gives an error). */ y[2] = x; /* Invalid compilation will fail (compiler gives an error). */
But, the following *ARE* valid:
x.a = y.a; /* data type of int on both sides of the assignment statement */ y.b = x.b; /* data type of float on both sides of the assignment statement */
J. E. Jones

OSU CSE 2421
If we want x, y and *z to be of the same type, we have two options:
1) Use a tag (suppose the tag is Simple):
struct Simple{ int a;
float b; };
struct Simple x, y[10], *z;
struct Simple w;
struct Simple func1(struct Simple p);
struct { int a;
float b;
} x, y[10], *z, w;
/*Notice that the keyword struct is required here*/
2) Use no tag, but declare all the variables together following the member-list:
J. E. Jones

OSU CSE 2421
Anothertechniqueistocreateanewtypeusingthetypedefkeyword: typedef struct {
float b; } Simple;
int a;
ThisstatementsayscreateanewdatatypecalledSimple(insteadofintorfloator)thatisa structure which contains an integer value a then a float value b.
Thistechniquehasalmostthesameeffectasusingastructuretag.WhatisdifferentisthatSimpleis now a data type name, rather than a structure tag, so subsequent declarations of variables of this type will look like this:
Simple x, y[10], *z; /* This declares x, the elements of y[10], */ /* and*ztobeofthesametype */
Note that the keyword struct is not used because Simple is now a defined data type no different than int or double or float.
SomeCsoftwarewritersprefernottousetypedefforstructures,inordertoimprovedocumentation. They say it is not clear from the name of the type that variables of that type are structure variables if we use typedef. Others say its cleaner to use typedefs than to have structures declared haphazardly.
J. E. Jones

OSU CSE 2421
If you want to use a particular structure type throughout a source file, you should use a typedef or a structure declaration with a tag before main (this will be necessary in lab 4); this is necessary to give file scope to the type created with typedef, or the struct tag.
If you want to use a particular structure type in more than one source file, you should put the tag declaration or typedef in a header file(e.g. lab4.h). You can then #include the header file with the declaration wherever it is needed.
Header files DO NOT allocate any space or contain any executable code; they only contain function prototypes, typedef definitions or struct definitions with a tag no variable lists.
J. E. Jones

OSU CSE 2421
These can be in a .h file:
struct Simple{
int a; or
typedef struct { int a;
float b; } ;
float b; } Simple;
These cannot be in a .h file: struct Simple x, y[10], *z;
struct { int a;
float b;
} x, y[10], *z;
J. E. Jones

OSU CSE 2421
In the examples so far, all structure members have been of primitive data (char, int, float, etc.) types.
Generally, though, any kind of variable that can be declared outside of a structure can also be used as a structure member.
Specifically, all the following are possible as members of a structure (and other derived types also):
Arrays
Pointers
Structures
And obviously, primitive data types as well
J. E. Jones

OSU CSE 2421
Important: Structure members can have identical names to members of a structure of a different type. The way that the members are accessed allows them to be referred to and accessed unambiguously.
For example: struct S_1{
struct S_2{
int member1;
int member2;
struct *S_2 member3; int member4[25];
};
};
char member1;
int member 2;
struct *S_1 member3; char member4[16];
are both legal. The structure members inside both structures have the same names, but the compiler can keep them straight.
J. E. Jones

OSU CSE 2421
typedef struct {
float tax_rate;
float gross_salary; } Tax_info;
struct Employee {
char *first_name;
char *last_name;
int id_number;
Tax_info tax; /* A structure of type Tax_info declared above */
} employees[50], *emp_ptr;
J. E. Jones

OSU CSE 2421
The members of a structure are directly accessed with the dot operator, which takes two operands:
The left operand is a structure variable (either an identifier which names a declared structure variable, or a dereferenced pointer to a structure variable).
The right operand is the name of a member of that type of structure variable.
See examples next slide.
J. E. Jones

OSU CSE 2421
Consider:
struct Employee {
char *first_name;
char *last_name; int id_number; Tax_info tax;
} emp1, emp2;
To access members of emp1:
To access members of emp2:
emp1.first_name emp1.last_name emp1.id_number emp1.tax
emp2.first_name emp2.last_name emp2.id_number emp2.tax
Question: Where are the Employee names stored??? In this structure? Somewhere else?
J. E. Jones

OSU CSE 2421
For the employee structure above, one of the members, tax, is another structure of type Tax_info.
Suppose Tax_info has been declared as follows:
typedef struct {
float tax_rate; float gross_salary;
} Tax_info;
Of course, this declaration would have to be made prior to the declaration of struct
Employee shown on the preceding slide.
To access the members of emp1.tax or emp2.tax, we use two dot operators (the dot
operator has L-R associativity):
emp1.tax.tax_rate emp1.tax.gross_salary emp2.tax.tax_rate emp2.tax.gross_salary
J. E. Jones

OSU CSE 2421
We can also access the members of a structure using a pointer to the structure.
Consider:
struct Employee *ptr;
ptr = &emp1 /* if &emp1 = 0x600030 */
Suppose we pass the structure pointer, ptr, to a function with the following prototype:
void Emp_func (struct Employee *ptr);
using this statement: Emp_func(ptr); /* Emp_func(0x600030); */
How are the members of the structure accessed inside the function?
J. E. Jones

OSU CSE 2421
The function, Emp_func, must dereference the pointer. And can use one of the two following options to do so:
1. Dereference the pointer that was passed:
(*ptr).first_name (*ptr).last_name etc.
The parentheses MUST be used, because the dot operator has higher precedence than the dereference operator. Notice that this usage requires the * within the parentheses rather then outside of them.
2. Because the above notation is a nuisance (and can be confusing), ANSI C also provides an alternate option using the arrow (->) operator*:
ptr->first_name ptr->last_name etc.
The arrow operator is typed as two characters: hyphen followed by greater than (compiler interprets these two characters as a single operator) no spaces between then are allowed.
*Same precedence as dot operator both have L-R associativity.
J. E. Jones

OSU CSE 2421
ptr->first_name
Note that the left operand of the -> operator must be a pointer to a structure. This operator is not valid with any other type of left operand.
Also notice that the left-hand operand of the arrow operator is ALWAYS dereferenced, even though no dereference operator is used; it is implied by, (i.e. built-into) the arrow operator.
J. E. Jones

OSU CSE 2421
Since the left-hand operand of the arrow operator must be a structure pointer, and, since it is always dereferenced, we can convert expressions with dereference and dot to expressions with arrow (and vice-versa) as follows:
left-operand->right-operand is equivalent to (*left-operand).right-operand
What if we have multiple arrow operators in an expression? op1->op2->op3 is equivalent to (*(*op1).op2).op3
(op1 and op2 must both be pointer data types in this example)
As you can see, writing such expressions with dereference and dot operators is very cumbersome, so the arrow operator is almost always used by experienced C programmers in these cases.
J. E. Jones

OSU CSE 2421
typedef struct {
float tax_rate;
float gross_salary; } Tax_info;
struct Employee {
char *first_name;
char *last_name; int id_number; Tax_info tax;
/* Another structure of type declared above */
} employees[50], *emp_ptr; emp_ptr = employees;
We can use emp_ptr->first_name to reference the address to each employees first name:
for(i=0; i<50; i++){printf(%s %s
, emp_ptr->first_name, emp_ptr->last_name); emp_ptr++:
}
Did you notice that we can just increment emp_ptr to get to the pointer to the next structure element in the array? We dont have to know how much space each structure takes up.
J. E. Jones

OSU CSE 2421
typedef struct {
float tax_rate;
float gross_salary; } Tax_info;
struct Employee {
char *first_name;
char *last_name; int id_number; Tax_info tax;
/* Another structure of type declared above */
} employees[50], *emp_ptr; emp_ptr = employees;
How might we reference gross_salary? You might guess:
emp_ptr->tax->gross_salary or emp_ptr->tax.gross_salary Which one?? Is tax an element or a pointer to an element???
J. E. Jones

OSU CSE 2421
test_struct1.c: test_struct2.c: int main() int main() {{
typedef struct {
float tax_rate; float gross_salary;
typedef struct {
float tax_rate; float gross_salary;
} Tax_info;
struct Employee {
} Tax_info;
struct Employee {
char *firstname; char *last_name; int id_number; Tax_info tax;
char *firstname; char *last_name; int id_number; Tax_info tax;
} employees[50], *emp_ptr;
} employees[50], *emp_ptr;
emp_ptr = employees;
emp_ptr = employees;
emp_ptr->tax.gross_salary = 1200.00;
emp_ptr->tax->gross_salary = 1200.00;
return(0); }}
return(0);
$ gcc ansi pedantic test_struct1.c o test_struct1 $ gcc ansi pedantic test_struct2.c o test_struct2 $ test_struct2.c: In function `main:
test_struct2.c:24: error: invalid type argument of `-> (have `Tax_info)
$
J. E. Jones

OSU CSE 2421
What do you think??
Is it legal for a structure to contain a member that is the same
type as the structure?
Suppose we declare a structure such as the following: struct Self_Ref1 {
};
int a;
int b;
struct Self_Ref1 c;
Can you estimate the size (in bytes) of this structure??
J. E. Jones

OSU CSE 2421
struct Self_Ref1 { int a; int b;
struct Self_Ref1 c; };
This type of self-reference is not legal in ANSI C (likely, not legal in any programming language!!) because the structure member c is another complete structure, which will contain its own member c. This second member c is yet another complete structure, and contains its own member c, and so forth.
The problem with this declaration is that it is infinitely recursive, so the compiler would have to attempt to allocate an infinite amount of storage.
Lets compare this with the self-referential declaration on the following slide.
J. E. Jones

OSU CSE 2421
This is a different self-referential structure. Can you distinguish it from the previous one?
struct Self_Ref2 { int a;
int b;
struct Self_Ref2 *c; };
Is this kind of self-referential structure legal?
Can you estimate the size (in bytes) of this structure??
J. E. Jones

OSU CSE 2421
struct Self_Ref2 { int a; int b;
struct Self_Ref2 *c; };
This self-referential structure is legal in ANSI C and is used to build linked data structures such as linked lists and trees.
The difference from the previous recursive structure which does not terminate is that in this case, the structure does not contain a member that is another structure of the same type, but rather, a pointer to a structure of the same type.
The compiler of course can allocate space for a pointer to a structure, which requires a finite amount of space. (two 4-byte integers and one 8-byte pointer)
We will see how to build a linked list with such a self-referential structure soon.
J. E. Jones

OSU CSE 2421
Structures can be initialized in much the same way as arrays. For example: struct Init_example {
};
int a[6]= {6,5,4,3,1};
}y={
int a;
short b[10]; Simple c;
/* Defined with typedef from before */
10,
{1, 2, 3, 4, 5}, {25, 1.9}
/* initialization of member a */ /* initialization of array member b */ /* initialization of struct member c */
The initial values for the members must be in the order given in the member list, and they are separated by commas.
Missing values (at the end of the list of values) cause the remaining members to be set to the default initialization.
J. E. Jones

OSU CSE 2421
Lets modify the previous example slightly, by declaring an additional structure variable x, without initialization:
struct Initialization_example { int a;
} x, y = {
short b[10]; Simple c;
/* Defined with typedef above */
10,
{1, 2, 3, 4, 5}, {25, 1.9}
/* initialization of member a */
/* initialization of array member b */ /* initialization of struct member c */
};
Because x and y have been declared to be of the same type, we can assign y to x by
saying:
x = y;
This assigns the value of each member of y to the corresponding member of x.
Of course, we can also initialize, or assign to, the members of a structure one by one, with individual assignment statements, as shown on the following slide.
J. E. Jones

OSU CSE 2421
Assignment to individual members, given the following declarations: struct Initialization_example {
} x, y = {
};
x.a = 10;
x.b = {1,2,3,4,5}; x.c = {25, 1.9};
int a;
short b[10]; Simple c;
/* Defined with typedef above */
10,
{1, 2, 3, 4, 5}, {25, 1.9}
/* initialization of member a */
/* initialization of array member b */
/* initialization of struct member c */
J. E. Jones

OSU CSE 2421
It is legal to pass a structure variable as an argument to a function, but it is rarely the best option.
In ANSI C parameters are passed by value so, if the structure is large, all of the values of the all the members in the structure will have to be copied and pushed onto the stack when the function is called.
On the other hand, if we pass a pointer to the structure as a parameter, then only the value of the pointer is passed* rather than copies of all the values in the structure.
The price for this is that dereferencing must be used inside of the function in order to access the structure members (a small price to pay for the storage space saved and the speed up in execution time).
Therefore, only structures which are not much larger than a pointer should be passed by value. All others should be passed by reference.
*how parameters are passed when there are 6 values or less differs depending upon the type of CPU and the compiler being used
J. E. Jones

OSU CSE 2421
As we have seen before, C has the keyword const, which can be used to declare constants, for example:
int const MAX_LENGTH = 1000; const int MAX_LENGTH = 1000;
This keyword can also be used when passing function arguments with pointers to prevent modification of the value(s) to which the pointer points:
int func1(int const *ptr) {
. . . . . /* func1 will not be able to change the values
}
Unless the function needs to change values using the pointer (or we implicitly trust the function being called), we should declare the parameter with const, to indicate that the value(s) pointed to by the parameter will not be changed. This will also restrict the interaction between the function and the calling environment and can also aid debugging.
This can be done with structures also: float func2 (const struct *structPtr);
in the array or structure */
J. E. Jones