Transcript Structures

Final




Final on May 4 12:30pm
Includes all material
Emphasis on Structures, strings and pointers, linked lists
Pick 6 out of 7 questions





Find the output of a program
Write a function
Write a complete program
Write partial code
90 minutes
1
Structures
2
Structure Definition
struct name
{
variable declaration;
variable declaration;
.
.
};
the keyword struct announces that this is a structure
definition
3
Accessing Data Members

To access a data member use


Varname.membername
struct Rect r1 = {0,0,’r’,5,10};





r1.x
r1.y
r1.color
r1.width
r1.height
r1
0
x
0
y
r
color
5
width
height
10
4
Accessing Data Members

To access a data member
with a pointer use



varname->membername
struct Rect r1 = {0,0,’r’,5,10};
struct Rect *rptr=&r1;





rptr->x
rptr->y
rptr->.color
rptr->width
rptr->height
r1
0
x
0
y
r
color
5
width
height
10
5
Assignment operator

Assignment operator is defined for structure of the
same type.
struct rect
{
double x;
double y;
char color;
double width;
double height;
};
struct rect r1, r2
r1.x = 10.5;
r1.y = 18.99;
r1.width = 24.2;
r1.height = 15.9;
r1.color = 'r';
/* Copy all data from r1 to r2. */
r2 = r1;
6
Scope of a Structure


Member variables are local to the structure.
Member names are not known outside the structure.
7
Exercise

Write a program using structures that
manipulates pairs. Addition and multiplication
of pairs is defined below.
(a,b)+(c,d)=(a+c,b+d)
(a,b)*(c,d)=(a*c,b*d)
8
Pair Structure

Store two integers to represent the first and
second number of pair
struct pair
{
int first;
int second;
};
9
Addition
struct pair add(struct pair p1, struct pair p2)
{
struct pair temp;
temp.first = p1.first + p2.first;
temp.second = p1.second + p2.second;
return temp;
}
10
How to use the functions
struct pair mp1,mp2,mp3,mp4;
printf("Enter first pair\n");
scanf("%d%d",&mp1.first, &mp1.second);
printf("Enter second pair\n");
scanf("%d%d",&mp2.first, &mp2.second);
mp3 = add(mp1,mp2);
printf("Addition result =
(%d,%d)\n",mp3.first,mp3.second);
mp4 = multiply(mp1,mp2);
printf("Multiplication result =
(%d,%d)\n",mp4.first,mp4.second);
11
Structure Representation & Size
struct CharCharInt {
char c1;
char c2;
int
i;
};
struct CharCharInt foo;
foo.c1 = ’a’;
foo.c2 = ’b’;
foo.i = 0xDEADBEEF;
sizeof(struct …) =
sum of sizeof(field)
+
alignment padding
Processor- and compiler-specific
c1
c2
61
62
padding
i
EF
BE
AD
DE
x86 uses “little-endian” representation
Structure Representation & Size
sizeof(r1) =
sizeof
sizeof
sizeof
sizeof
sizeof
+
(double)
(double)
(char)
(double)
(double)
struct Rect
{
double x;
double y;
char color;
double width;
double height;
};
struct Rect r1 = {0,0,’r’,5,10};
alignment padding
Processor- and compiler-specific
sizeof(r1) is 36. 4 doubles (8 bytes each)+1 char (1 byte) + 3 bytes padding
Using malloc with structures
struct rect *rptr;
rptr = (struct rect*)malloc(sizeof(struct rect));
rptr->x = 10.5;
rptr->y = 18.99;
rptr->width = 24.2;
rptr->height = 15.9;
rptr->color = 'r';
print(*rptr);
free(rptr);
14
Arrays of Structures

Arrays of structures may be declared in the same way as other
C data types.
struct rect rectangles[20];

rectangles[0] references first structure of rectangles array.
rectangles[0].color = ‘r’;
x
y
color
width
height
……….......
0
1
2
3
19
15
Structures as Arguments to Functions

When a structure is passed as an argument to a function, it is a
call-by-value reference.


Changes made to the formal parameters do not change the
argument.
A pointer to a structure may also be passed as an argument to
a function.

Changes made to the formal parameters also change the
argument.
16
Call by Value Example
struct simple
{
int ival;
double dval;
};
void fun1(struct simple s)
{
s.ival = s.ival+1;
s.dval = s.dval + 2;
}
s
s1
10
10
ival
1.5
1.5
dval
int main(void)
{
struct simple s1 = {10, 1.5};
fun1(s1);
printf(“%i %lf\n”, s1.ival , s1.dval );
return 0;
}
Updated s
11
3.5
17
Call by Reference Example
struct simple
{
int ival;
double dval;
};
void fun1(struct simple *s)
{
s->ival = s->ival+1;
s->dval = s->dval + 2;
}
sptr
s1
10
ival
1.5
dval
s
int main(void)
{
struct simple s1 = {10, 1.5};
struct simple *sptr = &s1;
fun1(sptr);
printf(“%i %lf\n”, sptr->ival , sptr->.dval );
return 0;
}
Updated s1
11
3.5
18
Static Array Allocation

struct rect rectangle[100];



Allocates space for 100 rectanges
Each rectangle requires 36 bytes
Allocates 3600 bytes total
Array of Pointers

struct rect *rectptr[100];




Allocates an array of 100 pointers
Each pointer is 4 bytes
Allocates 400 bytes total
Pointers do not point to allocated space
Array of Pointers


for (i=0; i<100; i++)
rectptr[i] = NULL;
Initializes pointers to NULL
Array of Pointers



for (i=0; i<100; i++)
rectptr[i] = (struct rect*)malloc(sizeof(struct rect));
Allocate space so that each pointer points to a rectangle
You can allocate space when you need it

Allocate space for 10 rectangles if you just need 10
Array of Pointers





for(i=99; i>=0; i--)
free(rectptr[i]);
Free the space allocated using malloc
If you don’t free all the space, it will cause memory leak
Space will appear as used although it is not used
Used valgrind command to find memory leaks
Array of Pointers
void test2(struct rect *a[])
{
struct rect *temp;
temp = a[0];
a[0] = a[1];
a[1] = temp;
}


Swaps first 2 pointers
Changes are permanent since arrays are pass by
reference
Array of Pointers
void test(struct rect *a[])
{
struct rect temp;
temp = *a[0];
*a[0] = *a[1];
*a[1] = temp;
}


Swaps the rectangles pointed by first two pointers
Changes are permanent since changed through pointers
Linked Lists
26
Linked List


Group of nodes connected by pointers
A node consists of


Head
Data
Pointer to next node
6
5
3
8
Null
27
Insertion into a Linked List

Head
Insert 9 after 5
6
5
3
8
Null
9
28
Deletion from a Linked List

Head
Delete 3 from the list
6
5
Free
this
space
3
8
Null
9
29
Declaration of a node
struct node
{
int info;
struct node *next;
};
typedef struct node node;
Head
6
5
3
8
Null
30
Linked List Problems
Head
6
5
3
8
Null
Some address
In memory
Head
6
5
3
Points back to
Internal node
8
31
Dynamic allocation of a node
node *ptr;
ptr = (node *)malloc(sizeof(node));
ptr
?
free(ptr)
32
Dynamic allocation of a node
node *ptr, *ptr2, *ptr3;
ptr = (node *)malloc(sizeof(node));
ptr2 = (node *)malloc(sizeof(node));
ptr3 = (node *)malloc(sizeof(node));
ptr
?
ptr2
?
ptr3
?
33
Dynamic allocation of a node
ptr -> info = 3;
ptr2 -> info = 5;
ptr3 -> info = 7;
ptr
3
ptr2
5
ptr3
7
34
Dynamic allocation of a node
ptr -> next = ptr2;
ptr2 -> next = ptr3;
ptr3 -> next = NULL;
ptr
3
ptr2
5
ptr3
7
NULL
35
Inserting at the Head
1.
2.
3.
4.
Allocate a new node
Insert new element
Make new node point to old head
Update head to point to new node
6
Head
Head
2
5
6
3
5
8
3
Null
8
Null
36
Inserting at the Head
node *inserthead(node *head, int a)
{
node *ptr;
ptr = (node*)malloc(sizeof(node));
ptr->info = a;
ptr->next = head;
return(ptr);
}
Head
Head
2
6
6
5
5
head = inserthead(head,2);
3
3
8
8
Null
Null
37
Removing at the Head
1.
2.
Update head to point to next node in the list
Allow garbage collector to reclaim the former first node
Head
6
5
3
8
Null
Head
5
3
8
Null
38
Removing at the Head
node* deletehead(node *head)
{
node * ptr;
ptr = head;
head = head->next;
free(ptr);
return(head);
}
Head
head = deletehead(head);
6
5
3
8
Null
Head
5
3
8
Null
39
Print a linked list
void printlist (node *head)
{
while (head !=NULL)
{
printf("%d ",head->info);
head = head->next;
}
printf("\n");
}
Head
6
5
printlist(head);
6538
3
8
Null
40
Find the length of a linked list
int length(node *head)
{
int count=0;
while (head != NULL)
{
head = head->next;
count++;
}
return (count);
}
Head
6
5
x=length(head);
3
8
Null
41
Find the sum of elements in a
linked list
int sum(node *head)
{
int total = 0;
while (head !=NULL)
{
total = total + head-> info;
head = head->next;
}
return (total);
}
Head
6
5
3
8
Null
42
Find the last element in a
linked list
int last(node *head)
{
if (head == NULL)
return (-1);
else
if (head->next == NULL)
return(head-> info);
while (head->next != NULL)
head = head -> next;
}
Head
return (head->info);
6
5
3
8
Null
43
Find if an element appears in
a linked list
int exists(node *head, int x)
{
if (head == NULL)
return (0);
while (head != NULL)
{
if (head->info == x)
return (1);
head = head -> next;
}
return (0);
}
Head
6
5
3
8
Null
44