Transcript Structures - Indian Institute of Technology Kharagpur

Structures
Heterogeneous Structures



Collection of values of possibly different types.
Name the collection.
Name the components.
Example : Student record
Singhal
name
rollno
classtest
midterm
final
grade
"V Singhal"
"00CS1001"
14
78
73
‘B
Structure : terminology




A struct is a group of items (variables) which
may be of different types.
Each item is identified by its own identifier,
each of which is known as a member or field
of the structure.
A struct is sometimes called a record or
structure.
Structs are the basis of classes in C++ and
Java.
Structure declaration
struct {
char first[10];
char midinit;
char last[20];
} sname, ename;
This declaration creates
two structure variables,
sname and ename, each
of which contains 3
members.
We can use
sname.first,
ename.midinit,
etc.
Members

To access the members of a structure,
we use the member access operator “.”.
strcpy (sname.first, “Sudeshna”);
sname.midinit = ‘K’;
strcpy (sname.last, “Sarkar”) ;
Tagged structure
struct nametype {
char first[10];
char midinit;
char last[20];
};
struct nametype sname,
ename;
typedef struct nametype NTYPE;
NTYPE aname, bname;
This definition creates
a structure tag nametype
containing 3 members:
first, midinit, last.
Variables may be declared
of type struct <tagname>.
typedef is normally used
to give names to a
struct type.
typedef
typedef struct {
char first[10];
char midinit;
char last[20];
} NAMETYPE;
NAMETYPE sname,ename;
Another example
#define MAX_NAME 40
typedef struct
{
char name[MAX_NAME+1];
char rollno[10];
int classtest;
int midterm;
int final;
char grade;
} StudentRecord;
Defines a new data type called StudentRecord. Does
not declare a variable.
Declaring struct variables
/* typedef structs go at top of program */
...
int .....
float ....
StudentRecord s1;
StudentRecord singhal ;
/* StudentRecord is a type; s1 and singhal are variables*/
struct nametype aname;
/* struct nametype is a type; aname is a variable
*/
Things you can and can't do

You can
Use = to assign whole struct variables

You can


You cannot


Have a struct as a function return type
Use == to directly compare struct variables;
can compare fields directly
You cannot

Directly scanf or printf structs; can read
fields one by one.
Struct initializers
/* typedef structs go on top */
StudentRecord s1 = {"V Singhal", "00CS1002", 15,
78, 73, 'B'};
Using components of struct
variables
s1.classtest = 46;
s1.midterm = 78;
scanf ("%d", &s1.rollno) ;
Assigning whole structs
s1 = singhal;
is equivalent to






strcpy(s1.name, singhal.name) ;
strcpy(s1.rollno, singhal.rollno;
s1.classtest = singhal.classtest;
s1.midterm = singhal.midterm;
s1.final = singhal.final;
s1.grade = singhal.grade;



Within a given structure, the member names
must be unique.
However, members in different structures
may have the same name.
A member is always accessed through a
structure identifier.
struct fruit {
char name[20];
int calories;
};
struct vegetable {
char name[30];
int calories;
};
struct fruit mango;
struct vegetable potato;
It is clear that we can
access mango.calories and
potato.calories without
any ambiguity.
Complicated structures

A member of a structure can be an array or
another structure.
struct grocerylist {
struct fruit flist[10];
struct vegetable vlist[20];
};

You can have an array of structures.
struct card {
int pips;
char suit;
} deck[52] ;
A function using struct array
int fail (StudentRecord slist []) {
int i, cnt=0;
for (i=0; i<CLASS_SIZE; i++)
cnt += slist[i].grade == ‘F’;
return cnt;
}
Using structures with functions




Structures can be passed as arguments to functions.
Structures can be returned from functions.
Call by value is used if a structure is a function
parameter, meaning that a local copy is made for use
in the body of the function. If a member of the
structure is an array, then the array gets copied as
well.
If the structure is large, passing the structure as an
argument can be relatively inefficient. An address of
th structure may be used as the parameter.
Union


A union is like a structure, except that the members
of a union share the same space in memory.
union int_or_float {
int i;
float f;
};
It is the programmer’s responsibility to know which
representation is currently stored in a union
variable.
Arrays of Structures
A struct represents a single record.
 Typically structs are used to deal with
collections of such records
 Examples : student records, employee
records, book records, ...
 In each case we will hav multiple instances of
the struct type.
Arrays of structs are the natural way to do this.

Arrays of structs : declaration & use
Each declaration below declares an array, where
each array element is a structure:
point corner_points[10] ;
StudentRecord btech01[MAXS] ;
We access a field of a struct in an array by specifying
the array element and then the field :
btech01[i].name
corner_points[4].x
Naming in struct Arrays
point pentagon[5];
pentagon : an array of points
x
y
x
y
pentagon[1] : a point structure
x
y
x
y
x
y
pentagon[4].x : a double
Using Arrays of structs
StudentRecord class[MAXS];
...
for (i=0; i<nstudents; i++) {
scanf (“%d%d”, &class[i].midterm,
&class[i].final);
class[i].grade =
(double)(class[i].midterm+class[i].final)/50.0;
}
struct Array elements as parameters
void draw_line (point p1, point p2) { ... }
...
point pentagon[5];
...
for (i=0;i<4;i++)
draw_line (pentagon[i], pentagon[i+1]);
draw_line (pentagon[4], pentagon[0]);
structs as Parameters

A single struct is passed by value.

all of its components are copied from the
argument (actual parameter) to initialize
the (formal) parameter.
point set_midpt (point a, point b) { ... }
int main (void) {
point p1, p2, m;
...
m = set_midpt(p1, p2);
}
Passing Arrays of structs


An array of structs is an array.
When any array is an argument (actual parameter), it
is passed by reference, not copied [As for any array]
 The parameter is an alias of the actual array
argument.
int avg (StudentRec class[MAX]) { ... }
int main (void) {
StudentRec bt01[MAX];
int average;
...
average = avg_midpt(bt01) ;
}
Dynamic Memory Allocation,
Structure pointers
Basic Idea


Many a time we face situations where data is
dynamic in nature.
 Amount of data cannot be predicted
beforehand.
 Number of data item keeps changing
during program execution.
Such situations can be handled more easily
and effectively using dynamic memory
management techniques.

C language requires the number of
elements in an array to be specified at
compile time.


Often leads to wastage or memory space
or program failure.
Dynamic Memory Allocation


Memory space required can be specified
at the time of execution.
C supports allocating and freeing memory
dynamically using library routines.
Memory Allocation Process in
C
Local variables
Stack
Free memory
Heap
Global variables
Instructions
Permanent
storage area



The program instructions and the global
variables are stored in a region known
as permanent storage area.
The local variables are stored in another
area called stack.
The memory space between these two
areas is available for dynamic allocation
during execution of the program.


This free region is called the heap.
The size of the heap keeps changing
Memory Allocation Functions




malloc: Allocates requested number of bytes and
returns a pointer to the first byte of the allocated
space.
calloc: Allocates space for an array of elements,
initializes them to zero and then returns a pointer
to the memory.
free : Frees previously allocated space.
realloc: Modifies the size of previously allocated
space.
Dynamic Memory Allocation

used to dynamically create space for
arrays, structures, etc.
int main () {
int *a ;
int n;
....
a = (int *) calloc (n, sizeof(int));
....
}
a = malloc (n*sizeof(int));


Space that has been dynamically
allocated with either calloc() or malloc()
does not get returned to the function
upon function exit.
The programmer must use free()
explicitly to return the space.


ptr = malloc (...) ;
free (ptr) ;
void read_array (int *a, int n) ;
int sum_array (int *a, int n) ;
void wrt_array (int *a, int n) ;
int main () {
int *a, n;
printf (“Input n: “) ;
scanf (“%d”, &n) ;
a = calloc (n, sizeof (int)) ;
read_array (a, n) ;
wrt_array (a, n) ;
printf (“Sum = %d\n”, sum_array(a, n);
}
void read_array (int *a, int n) {
int i;
for (i=0; i<n; i++)
scanf (“%d”, &a[i]) ;
}
void sum_array (int *a, int n) {
int i, sum=0;
for (i=0; i<n; i++)
sum += a[i] ;
return sum;
}
void wrt_array (int *a, int n) {
int i;
........
}
Arrays of Pointers

Array elements can be of any type


array of structures
array of pointers
int main (void) {
char word[MAXWORD];
char * w[N];
/* an array of pointers */
int i, n;
/* n: no of words to sort */
for (i=0; scanf(“%s”, word) == 1); ++i) {
w[i] = calloc (strlen(word)+1, sizeof(char));
if (w[i] == NULL) exit(0);
strcpy (w[i], word) ;
}
n = i;
sortwords (w, n) ;
wrt_words (w, n);
return 0;
}
Input : A is for apple or alphabet pie which
all get a slice of come taste it and try
w
0
A \0
1
i s \0
2
f o r \0
3
a p p l e \0
17
t r y \0
void sort_words (char *w[], int n) {
int i, j;
for (i=0; i<n; ++i)
for (j=i+1; j<n; ++j)
if (strcmp(w[i], w[j]) > 0)
swap (&w[i], &w[j]) ;
}
void swap (char **p, char **q) {
char *tmp ;
tmp = *p;
*p = *q;
*q = tmp;
}
Before swapping
w
w[i]
f o r \0
a p p l e \0
w[j]
After swapping
w
w[i]
f o r \0
a p p l e \0
w[j]
Pointers to Structure
Pointers and Structures

You may recall that the name of an array stands
for the address of its zero-th element.


Also true for the names of arrays of structure
variables.
Consider the declaration:
struct stud {
int roll;
char dept_code[25];
float cgpa;
} class[100], *ptr ;



The name class represents the address of the
zero-th element of the structure array.
ptr is a pointer to data objects of the type
struct stud.
The assignment
ptr = class ;


will assign the address of class[0] to ptr.
When the pointer ptr is incremented by one
(ptr++) :
 The value of ptr is actually increased by
sizeof(stud).
 It is made to point to the next record.

Once ptr points to a structure variable,
the members can be accessed as:
ptr –> roll ;
ptr –> dept_code ;
ptr –> cgpa ;

The symbol “–>” is called the arrow
operator.
Warning

When using structure pointers, we should take
care of operator precedence.

Member operator “.” has higher precedence than “*”.



ptr –> roll and (*ptr).roll mean the same thing.
*ptr.roll will lead to error.
The operator “–>” enjoys the highest priority
among operators.


++ptr –> roll will increment roll, not ptr.
(++ptr) –> roll will do the intended thing.
Program to add two complex
numbers using pointers
typedef struct {
float re;
float im;
} complex;
main() {
complex a, b, c;
scanf (“%f %f”, &a.re, &a.im);
scanf (“%f %f”, &b.re, &b.im);
add (&a, &b, &c) ;
printf (“\n %f %f”, c,re, c.im);
}
void add (complex * x, complex * y, complex * t) {
t->re = x->re + y->re ;
t->im = x->im + y->im ;
}
Structure and list processing
Dynamic allocation: review

Variables in C are allocated in one of 3 spots:
the run-time stack : variables declared local to
functions are allocated during execution
 the global data section : Global variables are
allocated here and are accessible by all parts of a
program.
 the heap : Dynamically allocated data items
malloc, calloc, realloc manage the heap region of the
mmory. If the allocation is not successful a NULL value
is returned.


Bad Pointers




When a pointer is first allocated, it does not have a
pointee.
The pointer is uninitialized or bad.
A dereference operation on a bad pointer is a serious
runtime error.
Each pointer must be assigned a pointee before it can
support dereference operations.


int * numPtr;
Every pointer starts out with a bad value. Correct code
overwrites the bad value.
Example pointer code.
int * numPtr;
int num = 42;
numPtr = &num;
*numPtr = 73;
numPtr = malloc (sizeof (int));
*numPtr = 73;
int a=1, b=2, c=3;
int *p, *q;
a
1
b
2
xxx p
xxx q
c
3
p = &a ;
q = &b ;
a
1
b
2
p
q
c
3
c = *p ;
p=q;
*p = 13 ;
a
1
p
b 13
q
c
1
Bad pointer Example
void BadPointer () {
int *p;
*p = 42;
}
int * Bad2 () {
int num, *p;
num = 42;
p = &num;
return p;
}
p
xxx
X




A function call malloc(size) allocates a block of mrmory
in the heap and returns a pointer to the new block.
size is the integer size of the block in bytes. Heap
memory is not deallocated when the creating function
exits.
malloc generates a generic pointer to a generic data
item (void *) or NULL if it cannot fulfill the request.
Type cast the pointer returned by malloc to the type of
variable we are assigning it to.
free : takes as its parameter a pointer to an allocated
region and de-allocates memory space.
Dynamic memory allocation: review
typedef struct {
int hiTemp;
int loTemp;
double precip;
} WeatherData;
main () {
int numdays;
WeatherData * days;
scanf (“%d”, &numdays) ;
days=(WeatherData *)malloc (sizeof(WeatherData)*numdays);
if (days == NULL) printf (“Insufficient memory”);
...
free (days) ;
}
Self-referential structures

Dynamic data structures : Structures with
pointer members that refer to the same
structure.
 Arrays and other simple variables are
allocated at block entry.
 But dynamic data structures require
storage management routine to explicitly
obtain and release memory.
Self-referential structures
struct list {
int data ;
struct list * next ;
};
The pointer variable next is called a link.
Each structure is linked to a succeeding structure
by next.
Pictorial representation
A structure of type struct list
data next
The pointer variable next contains either
• an address of the location in memory of the
successor list element
• or the special value NULL defined as 0.
NULL is used to denote the end of the list.
struct list a, b, c;
a.data = 1;
b.data = 2;
c.data = 3;
a.next = b.next = c.next = NULL;
a
b
1
NULL
data next
c
2
NULL
data next
3
NULL
data next
Chaining these together
a.next = &b;
b.next = &c;
a
b
1
data next
c
2
3
data next
What are the values of :
• a.next->data
• a.next->next->data
NULL
data next
2
3
Linear Linked Lists



A head pointer addresses the first
element of the list.
Each element points at a successor
element.
The last element has a link value NULL.
Header file : list.h
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct list {
DATA d;
struct list * next;
};
typedef struct list ELEMENT;
typedef ELEMENT * LINK;
Storage allocation
LINK head ;
head = malloc (sizeof(ELEMENT));
head->d = ‘n’;
head->next = NULL;
creates a single element list.
head
n
NULL
Storage allocation
head->next = malloc (sizeof(ELEMENT));
head->next->d = ‘e’;
head->next->next = NULL;
A second element is added.
head
n
e
NULL
Storage allocation
head->next=>next = malloc (sizeof(ELEMENT));
head->next->next->d = ‘e’;
head->next->next-> = NULL;
We have a 3 element list pointed to by head.
The list ends when next has the sentinel value NULL.
head
n
e
w
NULL
List operations
Create a list
 Count the elements
 Look up an element
 Concatenate two lists
 Insert an element
 Delete an element

Produce a list from a string
(recursive version)
#include “list.h”
LINK StrToList (char s[]) {
LINK head ;
if (s[0] == ‘\0’)
return NULL ;
else {
head = malloc (sizeof(ELEMENT));
head->d = s[0];
head->next = StrToList (s+1);
return head;
}
}
list from a string
#include “list.h”
LINK SToL (char s[]) {
(iterative
version)
LINK head = NULL, tail;
int i;
if (s[0] != ‘\0’) {
head = malloc (sizeof(ELEMENT));
head->d = s[0];
tail = head;
for (i=1; s[i] != ‘\0’; i++) {
tail->next = malloc(sizeof(ELEMENT));
tail = tail->next;
tail->d = s[i];
}
tail->next = NULL;
}
return head;
}
1. A one-element list
head
A
4. after assigning NULL
?
head
tail
2. A second element is attached
head
A
?
?
tail
3. Updating the tail
head
A
B
tail
?
A
B NULL
tail
/* Count a list recursively */
int count (LINK head) {
if (head == NULL)
return 0;
return 1+count(head->next);
}
/* Count a list iteratively */
int count (LINK head) {
int cnt = 0;
for ( ; head != NULL; head=head->next)
++cnt;
return cnt;
}
/* Print a List */
void PrintList (LINK head) {
if (head == NULL)
printf (“NULL”) ;
else {
printf (“%c --> “, head->d) ;
PrintList (head->next);
}
}
/* Concatenate two Lists */
void concatenate (LINK ahead, LINK bhead) {
if (ahead->next == NULL)
ahead->next = bhead ;
else
concatenate (ahead->next, bhead);
}
Insertion

Insertion in a list takes a fixed amount of
time once the position in the list is found.
Before Insertion
p2
p1
C
A
q
B
Insertion
/* Inserting an element in a linked list. */
void insert (LINK p1, LINK p2, LINK q) {
p1->next = q;
q->next = p2;
}
After Insertion
p2
p1
C
A
q
B
Deletion
Before deletion
p
1
2
3
p->next = p->next->next;
p
garbage
After deletion
1
2
3
Deletion
Before deletion
p
1
2
3
q = p->next;
p->next = p->next->next;
p
After deletion
1
2
q
3
free (q) ;
Delete a list and free memory
/* Recursive deletion of a list */
void delete_list (LINK head) {
if (head != NULL) {
delete_list (head->next) ;
free (head) ; /* Release storage */
}