Transcript Structures - CS Course Webpages

Structures
1
Derived Data Type
• C gives you several ways to create a
custom data type.
– The structure, which is a grouping of
variables under one name and is called an
aggregate data type.
– The “typedef” keyword, allow us to define a
new user-defined type.
2
Structures
• A structure is a collection of variables
referenced under one name, providing a
convenient means of keeping related
information together.
• It allows us to organize related data of
different types in one structure.
3
Structure Declaration
• A structure declaration forms a template that
can be used to create structure objects
(instances of a structure).
• The variables that make up the structure are
called members.
• Usually, the members of a structure are
logically related.
4
General Form
struct tag {
type member-name;
type member-name;
type member-name;
.
.
.
} structure-variable(s);
5
keyword
structure tag name
struct addr
{
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
};
Terminated by a semicolon
No variable has actually been created.
6
Structure Variable Declaration
struct addr addr_info;
declares a variable of type struct addr called
addr_info.
The compiler automatically allocates
sufficient memory to accommodate all of
its members.
7
Memory allocated for addr_info
Name
30 bytes
Street
40 bytes
City
20 bytes
State
3 bytes
Zip
4 bytes
Assume 4-byte long integers
8
You can declare one or more
objects when declare a struct type
struct addr {
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
} addr_info, binfo, cinfo;
9
Initialization of Structures
All, Extern and Static Variables including
structure variables that are not explicitly
initialized, are automatically initialized to
0.
10
Accessing Structure Members
• Individual members of a structure are
accessed through the use of the Dot
Operator (“.”).
• General form:
object-name.member-name
11
See slide 9: Created 3 Struct vars.
e.g., addr_info.zip = 12345;
printf("%lu", addr_info.zip);
gets(addr_info.name);
for(t=0; addr_info.name[t]; ++t)
putchar( addr_info.name[t] );
12
Structure Assignments
#include <stdio.h>
int main(void)
{
struct {
int a;
Do not need to assign
int b;
the value of each
} x, y;
member separately
x.a = 10;
y = x; /* assign one structure to another */
printf("%d", y.a);
return 0;
}
13
Array of Structs
WHY?
What does an array of structs allow us to do
that is not possible with any other single
structure?
14
Arrays of Structures
• To declare an array of structures, you must
first define a structure and then declare
an array variable of that type.
struct addr
addr_list[100];
printf("%lu", addr_list[2].zip);
addr_list[2].name[0] = 'X';
15
Passing Structures to
Functions
• Passing Structure Members to Functions.
• Passing Entire Structures to Functions
16
Passing Structure Members to Functions
• When you pass a member of a structure to
a function, you are passing the value of
that member to the function. It is
irrelevant that the value is obtained from a
member of a structure.
struct friend
{ char x;
int y;
float z;
char s[10];
} mike;
17
func(mike.x);
/* passes character value of x
func2(mike.y); /* passes integer value of y
func3(mike.z); /* passes float value of z
func4(mike.s); /* passes address of string s
func(mike.s[2]); /* passes character value of s[2]
*/
*/
*/
*/
*/
func(&mike.x); /* passes address of character x */
func2(&mike.y); /* passes address of integer y */
func3(&mike.z); /* passes address of float z */
func4(mike.s);
/* passes address of string s */
func(&mike.s[2]);/* passes address of character s[2]
*/
18
Passing Entire Structures to
Functions
• Call-by-value:
#include <stdio.h>
struct Example_type {
int a, b;
char ch;
};
19
void f1(struct Example_type parm);
int main(void)
{
struct Example_type
arg;
arg.a = 1000;
f1(arg);
return 0; struct_type
}
must match
void f1(struct Example_type parm)
{
printf(''%d", parm.a);
}
20
In Header File:
cl_info.h
#define CLASS_SIZE 100
struct student {
char *last_name;
int student_id;
char grade;
};
e.g.: To count the
number of failing
students in a given
Class.
In Program File :
#include “cl_info.h”
MAIN( )
{
struct student temp, class [CLASS_SIZE];
…..
}
21
Structure Pointers
• When a pointer to a structure is passed to a
function, only the address of the
structure is pushed on the stack. This
makes for very fast function calls.
• Passing a pointer makes it possible for the
function to modify the contents of the
structure used as the argument via call-byreference.
22
Declaring a Structure Pointer
• Like other pointers, structure pointers are
declared by placing * in front of a
structure variable's name.
struct addr *addr_pointer;
23
Using Structure Pointers
• To pass a structure to a function using call
by reference.
• To create linked lists and other dynamic
data structures that rely on dynamic
allocation.
24
struct bal {
float balance;
char name[80];
} person;
struct bal *p; /* declare a structure pointer */
p = &person;
25
The Structure Pointer Operator
–>
Used to access the members of a structure via a
pointer.
p–>balance
Forms:
(*pointer-To-Struct). member
or
pointer-To-Struct
member
26
struct student
temp, *p = &temp;
temp.grade = ‘A’;
temp.last_name = “Bushker”;
temp.student_id = 590017;
struct student {
char
*last_name;
int
student_id;
char
grade;
};
27
Expression
Equivalent
temp.grade
p –> grade
temp.last_name p –> last_name
temp.student_id p –> student_id
Value
A
Bushker
590017
(*p).student_id
590017
Parenthesis are necessary
(dot) has higher priority than *
28
Arrays and Structures Within
Structures
• A member of a structure can be either a
single variable or an aggregate type. In C
aggregate types are arrays and structures.
29
Arrays Within Structures
struct x {
int a[10] [10]; /* 10 x 10 array of ints */
float b;
} y;
To reference element [ 3,7] in member a of
Structure y.
y.a[3][7]
30
Structures within Structures
struct emp {
struct addr address; /* nested structure */
float wage;
} worker;
worker.address.zip = 93456;
The C89 standard specifies that structures
can be nested to at least 15 levels.
31
Using sizeof to Ensure Portability
Type Size in Bytes
char
1
int
4
double
8
struct s {
char ch;
int i;
double f;
} s_var;
sizeof(s_var) is 13 (8+4+1).
struct s *p;
p = malloc(sizeof(struct s));
32
typedef
• You can define new data type names by using
the keyword typedef
– You are not actually creating a new data type.
– You define a new name for an existing type.
• The primary advantage of the type definition is
that it allows you to replace a complex name,
such as a pointer declaration, with a mnemonic
that makes the program easier to read and follow.
33
• General Form:
typedef type newname;
typedef float BALANCE;
BALANCE
over_due;
34
E.g.,
The declaration for an array of
pointers to strings.
Char * stringPtrAry[20];
Typedef char * STRING;
STRING StrPtrAry[20];
35
Typedef with Structures
typedef struct
{ char id[10];
char name[26];
int gradepts;
} STUDENT;
STUDENT
A typename not
a variable.
pupil;
void printstudent (STUDENT Stu);
36
LINKED LIST
DATA STRUCTURE
• A Linked List is an ordered collection of data in
which each element contains 2 parts: data and
link.
• The data part holds info fields and the link is
used to chain the data together. It contains a
pointer that identifies the in next node the list.
• A Pointer variable points to the first node
(HEAD) in the list.
• Memory for each node is allocated
dynamically.
37
Head
Data
Data
Data
Data
The Head ptr gives acess to the LINKED LIST which is a
sequence of linked nodes.
38
Self-Referential Structures
• The node in a linked list are called selfreferential structures: Each instance of the
structure contains a pointer member to
another instance of the same type.
• This gives us the ability to create our
linked list structure in which one instance
of a node structure points to another
instance of the node structure.
39
Type Definition for a Linked List
typedef int KEY_TYPE;
typedef struct
{ KEY_TYPE key;
…
/* other data fields */
} DATA;
typedef struct nodetag
{ DATA
data;
struct nodetag *link;
} NODE;
A TYPE for EACH NODE
40
Pointers to Linked Lists
• One of the attributes of a linked list is that its data
are NOT stored with physical adjaceny- like
array data is.
• We need to identify the first logical node in the
list which we do with a pointer variable
designated as the HEAD POINTER.
• A linked list MUST always have a head ptr and
will likely have other pointers which will be
used for implementing LL activities (e.g.,
insertions, deletions, searches …).
41
Primitive List Functions
• To work with a linked list we need some
basic operations that manipulate the nodes.
INSERT a Node: At the beginning.
At the end.
Anywhere in the list.
DELETE a Node: At the beginning.
At the end.
Anywhere it is.
SEARCH for a
Find the location for
node.
above activities.
42
Inserting a New Node
• Steps to insert a new node:
1. Allocate memory for the new node.
2. Determine the insertion point. Implies
a search function. We need to know
the new nodes logical predecessor.
3. Point the new node to its successor.
4. Point the predecessor to the new node.
43