03/11/17

Structures
• Collection of one or more variables, possibly of
different types, grouped together under a single
name for easy handling.
CS1100 • For example - a structure which represents a
Introduction to Programming point in a two dimensional plane
struct point{ A mechanism for defining
Structures compound data types
int x;
Madhu Mutyam
Department of Computer Science and Engineering int y;
Indian Institute of Technology Madras By itself it reserves
};
no storage
Course Material – SD, SB, PSK, NSN, DK, TAG – CS&E, IIT M 1 2
SD, PSK, NSN, DK, TAG – CS&E, IIT M

Point in 2D à 2 Integers Marks and Names

• Different ways of declaring structure variables struct student{
struct point{ char *name;
int x; int mark;
name could itself be a struct made up of
int y; }s1, s2; first name, middle name and last name…
} point1, point2; Nested structures are allowed

struct student s1, s2;

struct point point1, point2; struct student s1 = { “Ramesh” , 79 };
struct point point1 = {3, 2};

SD, PSK, NSN, DK, TAG – CS&E, IIT M 3 SD, PSK, NSN, DK, TAG – CS&E, IIT M 4

A Rectangle Defining New Types

struct rectangle{ • ‘typedef’ keyword is used for creating new data
struct point pt1; • types
struct point pt2; • For example:
}rect1; • typedef int Age;
• Accessing points in the rectangle Age myAge = 99;
rect1.pt1.x = 4; • typedef and Structures:
rect1.pt1.y = 5; typedef struct point pointType;
Or pointType point1, point2;
rect1.pt1 = { 4, 5 }; • This is equivalent to: struct point point1, point2;
SD, PSK, NSN, DK, TAG – CS&E, IIT M 5 SD, PSK, NSN, DK, TAG – CS&E, IIT M 6

1
 03/11/17

Operations on Structures Functions and Structures

• Structures may be copied by assignment statement • Structure as function argument
• The address of the structure (use &) can be passed
to functions and can be returned by functions int isOrigin(pointType pt){
– one can pass an entire structure if (pt.x == 0 && pt.y == 0)
– one can pass some components of a structure return 1;
– one can pass a pointer to a structure
else
• Structures may not be compared
return 0;
}

SD, PSK, NSN, DK, TAG – CS&E, IIT M 7 SD, PSK, NSN, DK, TAG – CS&E, IIT M 8

Structures and Functions A Screen and its Centre Point

• Structure as return type struct rectangle screen;
struct point middle;
pointType makePoint(int x, int y){ struct point makePoint(int, int);
pointType temp;
temp.x = x; screen.pt1 = makePoint(0, 0);
temp.y = y; Observe there is no confusion screen.pt2 = makePoint(XMAX, YMAX);
return temp; between the two occurrences middle =
of x and y
} makePoint((screen.pt1.x+screen.pt2.x)/2,
(screen.pt1.y+screen.pt2.y)/2);
SD, PSK, NSN, DK, TAG – CS&E, IIT M 9 SD, PSK, NSN, DK, TAG – CS&E, IIT M 10

Adding Two Points Point Inside a Rectangle?

/* addPoints: add two points */ • /* isPtInRect: return 1 if point p is in rectangle r,
struct point addPoints(struct point p1, struct point p2) else return 0 */
{ p1.x += p2.x;
p1.y += p2.y; int isPtInRect(struct point p, struct rectangle r){
return p1;} return (p.x >= r.pt1.x) && (p.x < r.pt2.x) &&
(p.y >= r.pt1.y) && (p.y < r.pt2.y);
• } pt2
Note that the local changes • •
to p1 would not affect the
point p1; pass by value •
•
pt1
SD, PSK, NSN, DK, TAG – CS&E, IIT M 11 SD, PSK, NSN, DK, TAG – CS&E, IIT M 12

2
 03/11/17

A Canonical Rectangle Arrays of Structures

#define min(a, b) ((a<b)?a:b) /*Macro definitions*/
#define max(a, b) ((a>b)?a:b) struct point {
struct point{ int x;
struct rectangle canonRect(struct rect r){ int x; int y;
/*canonicalize coordinates of rectangle*/ int y; }pointArray[ ] = {
struct rectangle temp; }pointArray[10]; {1, 2},
temp.pt1.x = min(r.pt1.x, r.pt2.x); {2, 3},
temp.pt1.y = min(r.pt1.y, r.pt2.y); {3, 4}
temp.pt2.x = max(r.pt1.x, r.pt2.x); };
temp.pt2.y = max(r.pt1.y, r.pt2.y);
pointType pointArray[10];
return temp;
}
SD, PSK, NSN, DK, TAG – CS&E, IIT M 13 SD, PSK, NSN, DK, TAG – CS&E, IIT M 14

Accessing Member Values Structure1 = Structure2

• Assigning values to structure elements • Structures can be assigned using the assignment
pointArray[0].x = 1; operator
pointArray[0].y = 2;
OR struct point newPoint;
newPoint = makePoint(4,4);
pointArray[i].x = 5;
pointArray[i].y = 5;
• Printing elements of Structures
printf(“(%d,%d)”, pointArray[0].x,
pointArray[0].y);
SD, PSK, NSN, DK, TAG – CS&E, IIT M 15 SD, PSK, NSN, DK, TAG – CS&E, IIT M 16

Example Structure Definition Another Definition

typedef struct student{
typedef struct book{
char name[30];
int rollNo; Components can be of char title[20];
char gender; any type - even struct
char authors[30];
char hostel[8];
int roomNo; Observe the semi-colons int accNo;
}StudentType;
char subject[25];
Creates - a new data type called StudentType }BookType;
a composite type with 5 components BookType cText; // a C textbook
Can be used in type declarations of variables BookType shelf[100]; // a shelf holds 100 books
StudentType jayanthi, vikas, mahesh;

SD, PSK, NSN, DK, TAG – CS&E, IIT M 17 SD, PSK, NSN, DK, TAG – CS&E, IIT M 18

3
 03/11/17

Using Structures Using Complex Type

• Let us create a type for complex numbers and a Dot (.) Notation:
main( ){ Accessing components
few operations on complex numbers Complex a,b,c,d; of a structure
scanf(“%f %f”, &a.real, &a.imag);
typedef struct { scanf(“%f %f”, &b.real, &b.imag);
float real; c = sum(a,b);
float imag; d = product(a,b);
}Complex; printf(“Sum of a and b is %f +i%f\n”, c.real,
Complex sum (Complex m, Complex n); c.imag);
Complex product (Complex m, Complex n); printf(“Product of a and b is %f+i%f\n”,
d.real, d.imag);
}
SD, PSK, NSN, DK, TAG – CS&E, IIT M 19 SD, PSK, NSN, DK, TAG – CS&E, IIT M 20

Sum and Product Pointers to Structures

Complex Sum(Complex m, Complex n){ pointType point1, *ptr; The brackets are necessary.
Otherwise it is taken as *(ptr.x)
Complex p;
p.real = m.real + n.real; p.imag = m.imag + n.imag; point1 = makePoint(3,4);
return (p); ptr = &point1;
} printf(“(%d,%d)”, (*ptr).x, (*ptr).y);
OR
equivalent short form
Complex Product(Complex m, Complex n){
Complex p; printf(“(%d,%d)”, ptr->x, ptr->y);
p.real = (m.real * n.real) − (m.imag * n.imag);
p.imag = (m.real * n.imag) + (m.imag * n.real); • The operator ‘->’( minus sign followed by greater than
return (p); symbol) is used to access members of structures when
} pointers are used.
SD, PSK, NSN, DK, TAG – CS&E, IIT M 21 SD, PSK, NSN, DK, TAG – CS&E, IIT M 22

Precedence and Association Recall: Precedence & Associativity of Operators

• Both . and -> associate left to right
– They are at top of precedence hierarchy
• If we have
– struct rectangle r, *rp = r;
– The following forms are equivalent
Bitwise
r.pt1.x (r.pt1).x operators

rp -> pt1.x (rp -> pt1).x

Table from
(*rp).pt1.x K & R book
2nd edn. page
53

SD, PSK, NSN, DK, TAG – CS&E, IIT M 23 SD, PSK, NSN, DK, TAG – CS&E, IIT M 24

4
 03/11/17

More Examples Dynamic Data Structures

• Given the declaration struct{int len;char *str;} *p; • How does one cater to an uncertain and changing
• ++p-> len // increments len not p; same as ++(p-> len) amount of memory requirements?
• (++p)-> len // increments p before accessing len – for example if the number of students writing an
online surprise exam is unknown
• p++-> len // increments p after accessing len
• One way is to use dynamic tables/arrays
• *p->str // fetches whatever str points to
– declare an array of some size N
• *p->str++ // increments str after accessing – if it seems to be getting full declare an array of twice
// whatever it points to the size and copy all elements into it
• (*p->str)++ // increments whatever str points to • The other is to ask for memory for a structure one
• *p++-> str // increments p after accessing whatever str at a time and link them together
// points to 25 26
SD, PSK, NSN, DK, TAG – CS&E, IIT M SD, PSK, NSN, DK, TAG – CS&E, IIT M

Self Referential Structures Creating a List of Words and Frequencies (1/2)

#include <stdio.h>
• The structure contains a pointer to a structure of We create a linked list of 10 words, read
#include <stdlib.h> from input and set their frequencies as 1.
the same type We go down the list to also print the words.
#include <string.h>
– this is in addition to the other data it stores
typedef struct node
– let student contain name and marks {char word[20]; int freq; struct node *nextWord;} wordNode;
void main( ) {
name: Ramesh
marks: 76 wordNode *firstNode, *temp, *lastNode;
nextStudent: name: Rajesh firstNode = NULL;
name: Rakesh marks: 74
marks: 77 nextStudent: for (int i = 0; i < 10; i++) { /* create a 10 word list with freq = 1 */
nextStudent: char word[20];
printf (“Input a word of max length 20 and press enter: ”);
A linked list scanf (“%s”, word);
SD, PSK, NSN, DK, TAG – CS&E, IIT M 27 SD, PSK, NSN, DK, TAG – CS&E, IIT M 28

Creating a List of Words and Frequencies (2/2) Exercise

temp = (wordNode *) malloc (sizeof(wordNode)); • Suppose we have a travel agency which stores
strcpy(temp->word, word); temp->freq = 1; information about each flight:
if (firstNode == NULL) firstNode = temp; /* add the new node*/ – Flight Number
else lastNode -> nextWord = temp; – Originating airport code (3 letters)
lastNode = temp; } /* end of for loop */ – Destination airport code (3 letters)
– Departure Time
Temp = firstNode;
– Arrival Time
Printf (“The words you gave are: \n”);
While (temp != NULL) do { • Define a structure(s) for the flight information
Printf (“%s \n”, temp->word); • Write a function to read in the flight info for all flights
Temp = temp->nextWord; } • Write a function to find the info for a given origin and
} /* end of main */ destination
SD, PSK, NSN, DK, TAG – CS&E, IIT M 29 SD, PSK, NSN, DK, TAG – CS&E, IIT M 30

5
 03/11/17

Solution: FlightInfo Structure String and Time Types

• We will start with a structure which represents • But ‘C’ does not have any ‘String’ or ‘Time’ data
flight information types.
struct FlightInfo{ – We can define them!
String flightNo; typedef char* String; //Don’t forget to allocate memory using malloc!!!
String origin; OR
String destination; //But this will allocate more memory than
Time depTime; typedef char[10] String; actually required
Time arrTime;
}; struct TimeData
{
int hour;
int minute;
};
typedef struct TimeData Time;
SD, PSK, NSN, DK, TAG – CS&E, IIT M 31 SD, PSK, NSN, DK, TAG – CS&E, IIT M 32

Reading In the Data

struct FlightInfo agency1[MAX_FLIGHTS]; void RetrieveFlight(struct FlightInfo flightList[], int numFlights){
void ReadInfo(int numFlights, struct FlightInfo flightList[ ]){ String userOrigin, userDest;
for (i=1; i< numFlights; i++){ printf (“\nEnter the origin and destination airport codes: ”);
printf(“Enter Flight Number %d”, i); scanf (“ %s, %s”, userOrigin, userDest);
scanf(“ %s”, flightList[i].flightNo);
printf(“Enter Origin (3 letter code): ”); for (int i=0; i < numFlights; i++) {
scanf(“ %s”, flightList[i].origin); if ((strcmp(flightList[i].origin, userOrigin) == 0) &&
printf(“Enter Destination(3 letter code): ”); (strcmp(flightList[i].destination, userDest) == 0)) {
scanf(“ %s”, flightList[i].destination); printf(“\nFlight Number: %s \n”, flightList[i].flightNo);
printf(“Enter Departure Time (hh:mm): ”);
printf(“Departure Time: %d: %d\n”,
scanf(“ %d%d”, &flightList[i].depTime.hour,
&flightList[i].depTime.minute); flightList[i].depTime.hour, flightList[i].depTime.minute );
printf(“Enter Arrival Time (hh:mm): ”); printf(“Arrival Time: %d: %d \n”,
scanf(“ %d%d”, &flightList[i].arrTime.hour, flightList[i]. arrTime.hour, flightList[i].arrTime.minute );
&flightList[i].arrTime.minute); }
}}
SD, PSK, NSN, DK, TAG – CS&E, IIT M 33
}
SD, PSK, NSN, DK, TAG – CS&E, IIT M 34

Storing and Accessing Elements Computer Solutions

• Linked list are accessed by following the pointers • Problem Solving
– linear time complexity – main purpose of using computers
• Search trees are traversed by comparing values at nodes • Steps
– logarithmic time complexity for balanced trees
– clear specification, understanding of the problem
• Array elements are accessed by using the index
– remove unnecessary details and retain only the
– constant time complexity
required parameters, constraints of the problem
– index value should be known (else search)
• “abstraction” - better insight, helps in thinking
• Can we store names/strings in arrays?
– find the method of solving the problem
– and find them in constant time
• “algorithm design” - “efficiency”
– Yes, in Hash tables (average complexity)
– express the solution in a programming language

SD, PSK, NSN, DK, TAG – CS&E, IIT M 35 SD, PSK, NSN, DK, TAG – CS&E, IIT M 36

6
 03/11/17

References Homework Exercise

• Peter Grogono and Sharon Nelson, Problem • Write a program to take a filename as a command
Solving and Computer Programming, Narosa, line argument, open the file and count the
1987. frequencies of the different words in the file.
• R G Dromey, How to Solve it by Computer, • Given a “-n” option it should print the words
Prentice-Hall India, 1996. preceded by their counts in an increasing order of
frequency, one word per line.
• Otherwise it should print the words in alphabetic
order

SD, PSK, NSN, DK, TAG – CS&E, IIT M 37 SD, PSK, NSN, DK, TAG – CS&E, IIT M 38