Transcript Structures

Structures and Abstract data types
Lone Leth Thomsen
Structured types
• You should be familiar with basic types in C, e.g. int,
char and double
• A structured type is a data type that is built from other
types. Two main kinds, one you already know
– Arrays are a structured type comprising a number of
elements of the same type, normally identified by an array
subscript or index
– Structures are a structured type comprising a number of
members (or fields) of possibly different types, normally
identified by a member name
March 2006
Basis-C-7/LL
2
Structures
• Structures are a way of aggregating a collection of
“things” of (maybe) different types
• The keyword struct introduces a structure
declaration, which is a list of declarations enclosed
in { }
• An optional name – a structure tag – may follow
the keyword struct
• Variable names in a structure are called members
March 2006
Basis-C-7/LL
3
struct
• A declaration containing struct defines a type
struct structure_tag {
type_1 member_1;
type_2 member_2;
…
type_n member_n;
} variable_name;
• A structure declaration not followed by a list of
variables is just a template
struct structure_tag variable_name;
March 2006
Basis-C-7/LL
4
struct 2
• A member of a structure is referred to by
structure_name.member
• It is used as a variable just as a simple
variable or an array element
– e.g. print it out, set it, use it in expressions, etc.
• The “.” is called the structure member
operator, connecting the structure name and
the member name
March 2006
Basis-C-7/LL
5
struct 3
• Declare any new struct types at the
beginning of a program file (usually before
function prototypes)
• You can make as many struct types as you
want and as many variables of that type as
you want
• You can have as many members (fields) in a
struct as you like
March 2006
Basis-C-7/LL
6
Declaring a structure
• A structure is a collection of (possibly) unlike data elements
that are related in some way
struct card{
int
pips;
char suit;
};
// Number of spots on the card
// S = Spades, H = Hearts, C = Clubs, D = Diamonds
– This statement introduces a new derived data type with
the structure tag of card. It does not reserve any storage,
instead it simply describes what a card “looks like”
– The pips and the suit of a card will now be kept in
contiguous storage
March 2006
Basis-C-7/LL
7
Declaring a structure 2
• Declarations can now use struct card as if it were
built into the language just as int and double are
struct card deck[ 52], ThreeOfSpades = { 3, ‘S’ };
– Storage is reserved for
• deck which is an array of 52 elements of data type struct card
• ThreeOfSpades which is a single initialized instance of data
type struct card
March 2006
Basis-C-7/LL
8
Declaring a structure 3
• Example
struct date {
unsigned day;
unsigned month;
unsigned year;
}; // NB. The semicolon has to be there
• This declares a type, not a variable
• In the example, date is called a structure tag, the
type is struct date
March 2006
Basis-C-7/LL
9
Declaring structure variables
• Given the previous example, we could write
struct date today;
• Alternatively, we could use a typedef
typedef struct date DATE;
and then declare the variable
DATE today;
• Either the typedef or the variable definition could
be combined with the original struct declaration
March 2006
Basis-C-7/LL
10
Members
• Any type including arrays, structures and
pointers, can be structure members
• Example
struct Employee {
int ident;
char name[30];
double pay_rate;
char *dept_name;
};
March 2006
Basis-C-7/LL
11
Structures within structures
• A structure member can be any type, so another
structure is also possible
• Example
struct Employee {
int ident;
char name[30];
double pay_rate;
date start_date; // date was defined earlier
char *dept_name;
};
March 2006
Basis-C-7/LL
12
Initialising structures
• Structures can be initialised with a list of
values, one for each member
• Initialisers can be nested in nested structures
• Example
Employee new_emp = {
99,
// ident
“A. Nonymous”, // name
100.45,
// pay_rate
{1, 4, 2003}, // start_date
“Sales”
// department
};
March 2006
Basis-C-7/LL
13
Accessing members
• Simple member access uses the “dot” or
member (.) operator, e.g.
new_emp.ident = next_number;
printf(“Enter employee name: ”);
gets(new_emp.name);
printf (“New employee’s name is %s\n”, new_emp.name);
printf (“Enter start date: ”);
scanf("%u/%u/%u",
&new_emp.start_date.day,
&new_emp.start_date.month,
&new_emp.start_date.year);
March 2006
Basis-C-7/LL
14
Assigning structures
• We can assign one structure variable to
another of the same type, meaning that all
members will be copied
• E.g., if we have already initialised today,
this is valid
new_emp.start_date = today;
• No need to assign the individual members
March 2006
Basis-C-7/LL
15
Passing structures to functions
• Unlike an array, a structure variable name is not a
pointer but represents the actual structure
• If we pass a structure to a function as a parameter,
the entire structure gets copied
• (all parameters are passed by value)
• Changes made to a structure by the called function
will be made to the copy and will not affect the
original structure
March 2006
Basis-C-7/LL
16
Pointers to structures
• We can have pointers to structures
• Example
Employee *current_emp;
• Remember that an uninitialised pointer does not
point anywhere. So we have to initialise, e.g.
Employee employee_list[100];
current_emp = employee_list;
or
current_emp = &employee_list[23];
March 2006
Basis-C-7/LL
17
Accessing members using pointers
• If we have a pointer to a structure, members
are accessed using the -> operator, e.g.
printf (“Employee name:%s\n”,
current_emp->name);
printf (“Start date: %u/%u/%u\n”,
current_emp->start_date.day,
current_emp->start_date.month,
current_emp->start_date.year);
• Note the mixing of “->” and “.”
March 2006
Basis-C-7/LL
18
The use of ->
• -> is the structure pointer operator, providing
access to members of a structure via a pointer
• Note that
current_emp->name
is equivalent to
(*current_emp).name
• But
*current_emp.name
is illegal since the member operator (.) has higher
precedence than the dereference operator (*)
• Much more convenient to use ->
March 2006
Basis-C-7/LL
19
Abstraction
• “Abstraction arises from a recognition of
similarities between certain objects,
situations or processes … and the decision
to concentrate upon these similarities and
ignore for the time being the differences”
C. A. R. Hoare
March 2006
Basis-C-7/LL
20
Introduction to ADTs
(Abstract data types)
• All built-in types are ADTs
– Consider the floating point – treated similarly
as integer yet implemented entirely differently
– All built-in types are abstractions on their
binary storage
• User-defined ADTs marked the beginning of
true data abstraction
March 2006
Basis-C-7/LL
21
ADT definition
• Representation (definition) of the type and the
operations on objects of that type are contained
within a single syntactic unit
• Other program units can create objects of this type
• Representation of the type is hidden from program
units that use the type so that only the operations
of the ADT can affect/access objects of the ADT
• ADTs increase reliability
March 2006
Basis-C-7/LL
22
ADTs
• An abstract data type is a new type that is defined in terms of
the operations that can be performed on items of that particular
type
• Creating new types with public properties allows the software
that uses those types to be insulated from the details of the
implementation (private properties) of the type
• This encourages
– clean interfaces and modularisation of software
– reuse of the ADT code by separate programs
– more maintainable code because the impact of changes is limited
March 2006
Basis-C-7/LL
23
ADTs 2
• We know a conceptual idea of a data type
• We can work with objects of this type by using a set
of predefined operations
• We do not really care (and know) how it is
implemented
• An ADT can have several (different) implementations
• Implementation details are hidden
• Interface functions are the same
• Application programs will not see any difference
March 2006
Basis-C-7/LL
24
The Employee example
• Build an ADT that implements the Employee type
• Operations might include
–
–
–
–
–
input an employee’s details
output an employee’s details
give the employee a pay rise 
specify an employee’s manager
get the employee’s name or start date or pay rate or ..
• We put the declarations of the data type and the
function prototypes in the employee.h file
• The implementation of the functions will go in the
employee.c file
March 2006
Basis-C-7/LL
25
employee.h
struct Employee {
int ident;
char name[30];
double pay_rate;
date start_date;
char *dept_name;
Employee *manager;
};
void input_employee_details(Employee *emp);
void output_employee_details(Employee *emp);
void pay_rise(Employee *emp, double percent);
void set_manager(Employee *emp, Employee *mgr);
char *get_name(Employee *emp);
double get_pay_rate(Employee *emp);
date get_start_date(Employee *emp);
March 2006
Basis-C-7/LL
26
Using the “Employee”
• A program that wants to create and perform
operations on the employee data type will
– define one or more variables of type employee
– use the supplied functions to carry out all
operations on those variables.
• E.g., if the program wants to keep track of
all the employees, it may define an array of
employees,
Employee employee_list[MAX_EMPLOYEES];
March 2006
Basis-C-7/LL
27
Self-referential structures
• Self-referential structures
– Structure that contains a pointer to a structure of the
same type
– Can be linked together to form useful data structures
such as lists, queues, stacks and trees
– Terminated with a NULL pointer (0)
struct node {
int data;
struct node *nextPtr;
};
March 2006
Basis-C-7/LL
28
Linked lists facts
• A linked list is a linear collection of self referential
nodes, connected by pointer links
• It is accessed by a pointer to the start of the list
• Subsequent nodes are accessed via the link pointer
member stored in each node
• The link pointer in the last node is set to NULL to
indicate the end of the list
• Data is stored in a linked list dynamically
– each node is created as necessary
March 2006
Basis-C-7/LL
29
Linked lists
• A list is a sequence of 0 or more elements of a
given type
• One way of implementing a list is the “linked list”
5 -> 20 -> 45 -> 2 -> 32 -> 12 -> 14
• Linked lists are like treasure trails
– They can be thought of as a chain of nodes
– Given the start of the list you can find the next node in
the list
– That then directs you to the next node etc.
March 2006
Basis-C-7/LL
30
Linked lists 2
• You cannot directly access a node in the middle of a
list
• You ‘find the next node’ by having, as part of each
node, a pointer variable containing the address of the
next node
• Each node is a structure with a least two fields
– a data value
– a pointer to the next node
• Use a linked list instead of an array when
– You have an unpredictable number of data elements
March 2006
Basis-C-7/LL
31
Linked lists 3
struct clist {
char item;
struct clist *next;
};
• The ‘next’ part of the clist structure contains
a pointer to the next clist structure
March 2006
Basis-C-7/LL
32
Linked lists 4
Address
120
Value
{‘a’,130}
{item,next}
130
140
{‘b’,140} {‘c’,NULL}
Assume that the variable ‘front’ holds the address
120
front->item is ‘a’
front
front->next = 130
March 2006
Basis-C-7/LL
a
130
33
Linked lists 5
• ‘next’ contains the address of the next clist
structure
• We are not interested in the actual address
and can show it pictorially by an arrow to
the next structure
front
March 2006
a
b
Basis-C-7/LL
c
34
Linked lists 6
front
a
b
c
• The earth (ground) symbol at the end of the list
denotes the value NULL
– NULL is conventionally used to terminate a list
– NULL is defined in stdio.h and has the value zero
– it has the special property that it is automatically
coerced to any pointer type when necessary
• front is a pointer to the start of the list
March 2006
Basis-C-7/LL
35
Inserting
• Insertion involves cutting the link between
two nodes and adding in a new node
front
a
b
new
March 2006
Basis-C-7/LL
c
z
36
Inserting 2
• Adding in the new node
front
a
b
c
z
March 2006
Basis-C-7/LL
37
Deleting
• To delete the node containing 'b', we need a
pointer p to the previous node
front
a
b
c
p
• We move the link pointer of p to by-pass the
node that is no longer required
March 2006
Basis-C-7/LL
38
Deleting 2
• The node containing b is no longer part of
the list
front
a
b
c
p
• If it is no longer required elsewhere, we could
delete it using the free() function
March 2006
Basis-C-7/LL
39
Deleting 3
• The node containing b is no longer part of
the list
front
a
c
p
• The node has been deleted
March 2006
Basis-C-7/LL
40
Linear linked lists –
dynamic storage allocation
• We can use malloc to acquire storage for structures (or
arrays for that matter) only when they are required
typedef ELEMENT * LINK;
LINK
head;
head = malloc (sizeof(ELEMENT)); // allocate instance of ELEMENT
head ->d = ‘n’; // set value of data in instance
head->next =NULL; // No other items in list
March 2006
Basis-C-7/LL
41
Now something we all know
• Bugs ….
March 2006
Basis-C-7/LL
42
Debugging
• Programming errors are called bugs
• The process of correcting them is called
debugging
– Sometimes much harder than creating the program
• To get rid of a bug, the following is needed
– Some way of reproducing the bug
– Information from the program that helps finding and
correcting the program
• Always save the old copy of your program in a
safe place before you start debugging/fiddling
March 2006
Basis-C-7/LL
43
Debugging 2
• I have mentioned using printf for debugging
before. Inserting temporary printf
statements and checking the output helps
finding “where it goes wrong”
• Remember to delete the printf statements
when everything is fine
March 2006
Basis-C-7/LL
44
Compiler messages
• Compiler messages appear when a program is
being compiled. They normally mean that
something was not correct C syntax or not
understood by the compiler
• One problem can cause many errors. This does not
always mean that you have many errors in your
program
• Two types of compiler messages
– Compiler warnings
– Compiler errors
March 2006
Basis-C-7/LL
45
Compiler messages 2
• Compiler warnings
– Indicate that something “bad” has been done
but the code can still be compiled
– You should fix whatever causes a warning since
it might lead to other (harder to find) problems
later on
– The compiler labels warnings appropriately to
distinguish them from serious errors
March 2006
Basis-C-7/LL
46
Compiler messages 3
• Compiler errors
– An error message is produced if the compiler
finds something in your source file that does
not conform to valid C syntax
– A compiler error indicates that something has to
be fixed before the code can be compiled as it
should
– The first few warnings and errors might cause
the others, so fix the first ones first!
March 2006
Basis-C-7/LL
47
Compiler messages 4
• Normally, compiler messages also include
the file and line number where a problem
has been found. However, sometimes the
error is in the line(s) just above what has
been indicated.
• Compilers do not agree! Some compilers
find errors that others call warnings, and
some won’t even complain ….
March 2006
Basis-C-7/LL
48
Compiler messages 5
• You’ve all seen “syntax error”, but what is
it?
– It is caused when you have written something
that doesn’t follow the formatting rules of C
• So – why do you get syntax errors??
– Because …..
•
•
•
•
March 2006
Missing ;
Mismatched (), {}, [] etc
Missing values in assignments
Many many more and a very long list!
Basis-C-7/LL
49
Run time errors
• A run time error is what happens when you
run the executable and something goes
wrong
– It only happens when the program is actually
run, i.e. after compilation and linking has
succeeded (no errors)
– Again there are two types
• Fatal errors
• Logical errors
March 2006
Basis-C-7/LL
50
Run time errors 2
• Fatal errors
– The executable crashes!
– Segmentation faults
• Trying to access illegal memory
• Improper use of arrays and pointers
– Stack overflow
• Infinite recursion
• Too many temporary variables
– Core dump
• Sometimes an image of the running program (core) is written
out.
• Should be deleted (maybe analysed first)
• Happens e.g. when “divide by zero”
March 2006
Basis-C-7/LL
51
Run time errors 3
• Logic errors
– A logic or semantic error in meaning
• It doesn’t make sense!
– Occurs when a program doesn’t do what you
want it to do!
– There probably won’t be any semantic errors if
the constructs are “legal” but do not make sense
March 2006
Basis-C-7/LL
52
Run time errors 4
• So – why do you get logic errors??
– Because
•
•
•
•
•
•
March 2006
Infinite loops
Misunderstood operator precedence
Iteration mistakes
Code inside a loop by mistake
Using = instead of ==
….
Basis-C-7/LL
53
Warnings and errors
• The warnings and error messages produced by the
C compiler, and by Unix, are not always especially
helpful. The main reasons for this are
– The writer of a compiler cannot anticipate all of the
reasons why certain errors might occur
– So the error messages cannot indicate anything except
the most general aspects of the reason for the problem,
but this is unlikely to be very helpful finding the cause
of a specific error
March 2006
Basis-C-7/LL
54