IT104 Discrete Structures

COMPILATION OF TOPICS

Name: Aina Maree E. Siason

Instructor: Ms. Lisa Rebusa
1

Table of Contents
Topic

Page

1. Arrays
2. Statistical Array
3. Pointers
4. Functions
5. Relationship Between Pointers and Arrays
6. Passing Pointers to Functions
7. Pointers to Functions
8. Array of Functions
9. Enumeration

4
8
10
14
18
20
21
23
25

10. Character Handling Library Functions

27

Introduction
This project aims to create a simplified description of the topics discussed in our IT104
2

Discrete Structures class. Using C programming, data structures and algorithms are particularly
tackled wherein logic and theory are needed in order to create programs. Topics such as Array,
Pointers, and Functions will be discussed. Arithmetical and logical operators such +, +=, ++,
&, ~ are frequently used to solve various equations.

C programming, which is an imperative programming language, is one of the most

widely used programming languages of all time, and C compilers are available for the majority
of computer architectures and operating systems. In C, all executable codes are contained
within subroutines, which are called functions. Functional parameters are always passed by
value. Pass-by-reference is simulated in C explicitly by passing pointer values. The latter will
be discussed thoroughly as we progress further.

For each topic, the theory and the application of theory will be presented. Under the
application of theory the following will be shown: 1) problem, 2) program code, and 3) sample
output.

Arrays
Array in C programming is a data structure that can store a fixed size sequential
3

collection of elements of the same type. An array is used to store a collection of data. Thus, it is
a collective name given to a group of similar quantities. These similar quantities could be the
number of students enrolled in a university, the grades of 100 students enrolled in a class, or
the ages of employees in a company.
All arrays consist of contiguous memory locations. The lowest address corresponds to the first
element and the highest address to the last element.
First Element

Last Element

age[0]

age[1]

age[2]

age[3]

Arrays and pointers have a special relationship because arrays use pointers to reference
memory locations.

Declaration of an Array
Arrays must be declared first before they can be used in a program. The standard array
declaration is as follows:
type arrayname[arraysize];
Type specifies the variable type of the element that is going to be stored in the array. The
following are the basic variable types in C Language:

Type
char
int

Description
Typically a single octet (one byte). This is
an integer type.
The most natural size of integer for the
machine.

float

A single-precision floating value.

double

A double-precision floating value.

4

void

Represents the absence of type.

Some examples of array declaration are the following:

char name[30];
int min[10];
float width[20];
double height[15];
Arrays and pointers have a special relationship because arrays use pointers to reference
memory locations.
Arrays start at position 0 in C Language. The elements of the array occupy adjacent locations
in memory. C Language treats the name of the array as if it were a pointer to the first element,
which is important in understanding how to do arithmetic with arrays.

Single-dimensional Array
The single-dimensional array in C is the simplest form of array that contains only one row for
storing data. It has a single set of square brackets ([]).
type arrayName[arraySize];

Multi-dimensional Array
The C language supports multi-dimensional arrays. The simplest data structure for organizing
tabular data is a two-dimensional array. C compilers treat a two-dimensional array as an array
of arrays. To declare a two-dimensional integer array size x,y you would write something as
follows:
type arrayName[x][y];

Where type can be any valid C data type and arrayName will be a valid C identifier. A twodimensional array can be think as a table which will have x number of rows and y number of
columns. A 2-dimensional array a, which contains three rows and four columns can be shown
as below:

Thus, every element in array a is identified by an element name of the form a[i][j], where
a is the name of the array, and i and j are the subscripts that uniquely identify each element in
a.

Example Problem
Problem
Forty Students were asked to rate the quality of the food in the student cafeteria on a scale of 1
to 10 (1 means awful and 10 means excellent). Place the 40 responses in an integer array and
summarize the results of the poll.

Code
#include <stdio.h>
#define RESPONSE_SIZE 40
#define FREQUENCY_SIZE 11
int main()
{
6

int answer, rating, frequency[ FREQUENCY_SIZE ] = { 0 };

int responses[ RESPONSE_SIZE ] =
{ 1, 2, 6, 4, 8, 5, 9, 7, 8, 10,
1, 6, 3, 8, 6, 10, 3, 8, 2, 7,
6, 5, 7, 6, 8, 6, 7, 5, 6, 6,
5, 6, 7, 5, 6, 4, 8, 6, 8, 10 };
for ( answer = 0; answer <= RESPONSE_SIZE - 1; answer++ )
++frequency[ responses [ answer ] ];
printf( "%s%17s\n", "Rating", "Frequency" );
for ( rating = 1; rating <= FREQUENCY_SIZE - 1; rating++ )
printf( "%6d%17d\n", rating, frequency[ rating ] );
return 0;
}

Output
Rating

Frequency

11

10

Statistical Arrays
7

This uses Arrays in C programming in order to solve mathematical and statistical

problems.

Example Problem
Problem
Find maximum and minimum element in an array of 10 elements.

Code
#include<stdio.h>
int main()
{
int i;
int a[10] = { 10, 55, 9, 4, 234, 20, 30, 40, 22, 34 };
int max = a[0];
int min = a[0];
for (i = 0; i < 10; i++)
{
if (a[i] > max)
{
max = a[i];
}
else if (a[i] < min)
{
min = a[i];
}
}
printf ("Maximum element in an array: %d\n", max);
printf ("Minimum element in an array: %d\n", min);
return 0;
}

Output

Maximum element in an array: 234

Minimum element in an array: 4

Pointers
9

A pointer is a programming language object, whose value refers directly to (or "points
to") another value stored elsewhere in the computer memory using its address. A pointer
references a location in memory, and obtaining the value stored at that location is known as
dereferencing the pointer. A pointer is a simple, more concrete implementation of the more
abstract reference data type.
The basic syntax to define a pointer is as follows:
int *ptr;
This declares ptr as the identifier of an object of the following type:

pointer that points to an object of type int

This is usually stated more succinctly as ptr is a pointer to int. Because the C language
does not specify an implicit initialization for objects of automatic storage duration, care should
often be taken to ensure that the address to which ptr points is valid; this is why it is
sometimes suggested that a pointer be explicitly initialized to the null pointer value, which is
traditionally specified in C with the standardized macro NULL:
int *ptr = NULL;
Dereferencing a null pointer in C produces undefined behavior, which could be catastrophic.
However, most implementations simply halt execution of the program in question, usually with
a segmentation fault. However, initializing pointers unnecessarily could hinder program
analysis, thereby hiding bugs. In any case, once a pointer has been declared, the next logical
step is for it to point at something:
inta=5;
int*ptr=NULL;
ptr=&a;
This assigns the value of the address of a to ptr. For example, if a is stored at memory
10

location of 0x8130 then the value of ptr will be 0x8130 after the assignment. To dereference
the pointer, an asterisk is used again:
*ptr = 8;
This means take the contents of ptr (which is 0x8130), locate that address in memory and
set its value to 8. If a is later accessed again, its new value will be 8.
This example may be clearer if memory is examined directly. Assume that a is located at
address 0x8130 in memory and ptr at 0x8134; also assume this is a 32-bit machine such that
an int is 32-bits wide. The following is what would be in memory after the following code
snippet is executed:
int a = 5;
int *ptr = NULL;

Address Contents
0x8130

0x00000005

0x8134

0x00000000

(The NULL pointer shown here is 0x00000000.) By assigning the address of a to ptr:
ptr = &a;
yields the following memory values:

Address Contents
0x8130

0x00000005

0x8134

0x00008130

11

Then by dereferencing ptr by coding:

*ptr = 8;
the computer will take the contents of ptr (which is 0x8130), locate that address, and
assign 8 to that location yielding the following memory:

Address Contents
0x8130

0x00000008

0x8134

0x00008130

Clearly, accessing a will yield the value of 8 because the previous instruction modified the
contents of a by way of the pointer ptr.
In C, array indexing is formally defined in terms of pointer arithmetic; that is, the language
specification requires that array[i] be equivalent to *(array + i). Thus in C, arrays
can be thought of as pointers to consecutive areas of memory (with no gaps), and the syntax for
accessing arrays is identical for that which can be used to dereference pointers.

Example Problem
Problem
Add two numbers using pointers.

Code
#include <stdio.h>
int main()
{
int first, second, *p, *q, sum;
12

printf("Enter two integers to add\n");

scanf("%d%d", &first, &second);
p = &first;
q = &second;
sum = *p + *q;
printf("Sum of entered numbers = %d\n",sum);
return 0;
}

Output
Enter two integers to add
4
5
Sum of entered numbers = 9

13

Functions
A function is a group of statements that together perform a task. Every C program has
at least one function, which is main(), and all the most trivial programs can define additional
functions. You can divide up your code into separate functions. How you divide up your code
among different functions is up to you, but logically the division usually is so each function
performs a specific task.
A function declaration tells the compiler about a function's name, return type, and parameters.
A function definition provides the actual body of the function.
The C standard library provides numerous built-in functions that your program can call. For
example, function strcat() to concatenate two strings, function memcpy() to copy one
memory location to another location and many more functions. A function is known with
various names like a method or a sub-routine or a procedure, etc.
The general form of a function definition in C programming language is as follows:
return_type function_name( parameter list )
{
body of the function
}
A function definition in C programming language consists of a function header and a function
body. Here are all the parts of a function:

Return Type: A function may return a value. The return_type is the data type of
the value the function returns. Some functions perform the desired operations without returning
a value. In this case, the return_type is the keyword void.
14

Function Name: This is the actual name of the function. The function name and the
parameter list together constitute the function signature.

Parameters: A parameter is like a placeholder. When a function is invoked, you pass a

value to the parameter. This value is referred to as actual parameter or argument. The parameter
list refers to the type, order, and number of the parameters of a function. Parameters are
optional; that is, a function may contain no parameters.
Function Body: The function body contains a collection of statements that
define what the function does.

Function Declarations
A function declaration tells the compiler about a function name and how to call the function.
The actual body of the function can be defined separately.
A function declaration has the following parts:
return_type function_name( parameter list );
For the above defined function max(), following is the function declaration:
int max(int num1, int num2);
Parameter names are not important in function declaration only their type is required, so
following is also valid declaration:
int max(int, int);
Function declaration is required when you define a function in one source file and you call that
function in another file. In such case you should declare the function at the top of the file
calling the function.

Calling a Function
15

While creating a C function, you give a definition of what the function has to do. To use a
function, you will have to call that function to perform the defined task.
When a program calls a function, program control is transferred to the called function. A called
function performs defined task and when its return statement is executed or when its functionending closing brace is reached, it returns program control back to the main program.
To call a function, you simply need to pass the required parameters along with function name,
and if function returns a value, then you can store returned value.

Function Arguments
If a function is to use arguments, it must declare variables that accept the values of the
arguments. These variables are called the formal parameters of the function. The formal
parameters behave like other local variables inside the function and are created upon entry into
the function and destroyed upon exit. While calling a function, there are two ways that
arguments can be passed to a function:
Call Type
Call by value

Description
This method copies the actual value of an
argument into the formal parameter of the
function. In this case, changes made to the
parameter inside the function have no effect
on the argument.

Call by reference

This method copies the address of an

argument into the formal parameter. Inside the
function, the address is used to access the
actual argument used in the call. This means
that changes made to the parameter affect the
argument.

By default, C uses call by value to pass arguments. In general, this means that code within a
function cannot alter the arguments used to call the function and above mentioned example
while calling max() function used the same method.
16

Example Problem
Problem
A program to reverse a sentence input by the user.

Code
#include <stdio.h>
void Reverse();
int main()
{
printf("Enter a sentence: ");
Reverse();
return 0;
}
void Reverse()
{
char c;
scanf("%c",&c);
if( c != '\n')
{
Reverse();
printf("%c",c);
}
}

Output
Enter a sentence: Hello there
ereht elloH

17

Relationship Between Pointers and Arrays

ArraysarecloselyrelatedtopointersinCprogrammingbuttheimportant
differencebetweenthemisthat,apointervariablecantakedifferentaddressesas
valuewhereas,inthecaseofarrayitisfixed:
Consideranarray:
int arr[4];

InarraysofCprogramming,nameofthearrayalwayspointstothefirstelementofanarray.
Here,addressoffirstelementofanarrayis&arr[0].Also,arrrepresentstheaddressofthe
pointerwhereitispointing.Hence,&arr[0] is equivalent to arr.
Also,valueinsidetheaddress&arr[0]andaddressarrareequal.Valueinaddress
&arr[0]isarr[0]andvalueinaddress arris*arr.Hence,arr[0] is equivalent to
*arr.
Similarly,
&a[1] is equivalent to (a+1)
*(a+1).
&a[2] is equivalent to (a+2)

AND, a[1] is equivalent to

AND, a[2] is equivalent to
18

*(a+2).
&a[3] is equivalent to (a+1)
*(a+3).
.
.
&a[i] is equivalent to (a+i)

AND, a[3] is equivalent to

AND, a[i] is equivalent to

*(a+i).
InC,youcandeclareanarrayandcanusepointertoalterthedataofanarray.

ExampleProblem
Problem
A program to find the sum of six numbers input by the user with arrays and pointers.

Code
#include <stdio.h>
int main(){
int i,class[6],sum=0;
printf("Enter 6 numbers:\n");
for(i=0;i<6;++i){
scanf("%d",(class+i)); // (class+i) is equivalent to
&class[i]
sum += *(class+i); // *(class+i) is equivalent to
class[i]
}
printf("Sum=%d",sum);
return 0;
}

Output
Enter 6 numbers:
1
2
3
4
5
19

6
Sum = 21

Passing Pointers to Functions

C programming language allows you to pass a pointer to a function. To do so, simply
declare the function parameter as a pointer type.

Example Problem
Problem
A program to pass an unsigned long pointer to a function and change the value inside the
function which reflects back in the calling function.

Code
#include <stdio.h>
#include <time.h>
void getSeconds(unsigned long *par);
int main ()
{
unsigned long sec;
getSeconds( &sec );
/* print the actual value */
printf("Number of seconds: %ld\n", sec );
return 0;
}
void getSeconds(unsigned long *par)
{
/* get the current number of seconds */
*par = time( NULL );
return;
}

20

Output
Number of seconds: 1412869533

Pointers to Functions
Functions in C are actually just pointers to a spot in the program where some code
exists. Just like you've been creating pointers to structs, strings, and arrays, you can point a
pointer at a function too. The main use for this is to pass "callbacks" to other functions, or to
simulate classes and objects. In this exercise we'll do some callbacks, and in the next one we'll
make a simple object system.
The format of a function pointer goes like this:
int (*POINTER_NAME)(int a, int b)
A way to remember how to write one is to do this:

Write a normal function declaration: int callme(int a, int b)

Wrap function name with pointer syntax: int (*callme)(int a, int b)

Change the name to the pointer name: int (*compare_cb)(int a, int b)

The key thing to remember is, when you're done with this, the variable name for the
pointer is called compare_cb and then you use it just like it's a function. This is similar to
how pointers to arrays can be used just like the arrays they point to. Pointers to functions can
be used like the functions they point to but with a different name.
int (*tester)(int a, int b) = sorted_order;
printf("TEST:
%d
is
same
as
%d\n",

tester(2,

3),

sorted_order(2, 3));
This will work even if the function pointer returns a pointer to something:

Write it: char *make_coolness(int awesome_levels)

Wrap it: char *(*make_coolness)(int awesome_levels)

Rename it: char *(*coolness_cb)(int awesome_levels)

The next problem to solve with using function pointers is that it's hard to give them as
parameters to a function, like when you want to pass the function callback to another function.
21

The solution to this is to use typedef which is a C keyword for making new names for other
more complex types. The only thing you need to do is put typedef before the same function
pointer syntax, and then after that you can use the name like it's a type.

Example Problem
Problem
A program that defines a function func that takes two integers as inputs and returns an
integer.

Code
#include<stdio.h>
int func (int a, int b)
{
printf("\n a = %d\n",a);
printf("\n b = %d\n",b);
return 0;
}
int main(void)
{
int(*fptr)(int,int); // Function pointer
fptr = func; // Assign address to function pointer
func(2,3);
fptr(2,3);
return 0;
}

Output
a=2
b=3
a=2
22

b=3

Array of Functions
By far the most important use of pointers to functions is to have arrays of functions. We
can have arrays of pointers and pointers can be made to point at functions. So combining both
we can have array of pointers to functions put differently, we can have array of functions.
If you want to pass a single-dimension array as an argument in a function, you would have to
declare function formal parameter in one of following three ways and all three declaration
methods produce similar results because each tells the compiler that an integer pointer is going
to be received. Similar way you can pass multi-dimensional array as formal parameters.

Example Problem
Problem
A program that asks the user to input two numbers and then choose if he/she wants to add,
subtract, multiply, or divide.

Code
#include <stdio.h>
int
int
int
int

sum(int a, int b);

subtract(int a, int b);
mul(int a, int b);
div(int a, int b);

int (*p[4]) (int x, int y);

int main(void)
{
int result;
int i, j, op;
p[0]
p[1]
p[2]
p[3]

=
=
=
=

sum; /* address of sum() */

subtract; /* address of subtract() */
mul; /* address of mul() */
div; /* address of div() */
23

printf("Enter two numbers: ");

scanf("%d %d", &i, &j);
printf("0: Add, 1: Subtract, 2: Multiply, 3: Divide\n");
do {
printf("Enter number of operation: ");
scanf("%d", &op);
} while(op<0 || op>3);
result = (*p[op]) (i, j);
printf("%d", result);
return 0;
}
int sum(int a, int b)
{
return a + b;
}
int subtract(int a, int b)
{
return a - b;
}
int mul(int a, int b)
{
return a * b;
}
int div(int a, int b)
{
if(b)
return a / b;
else
return 0;
}

Output
Enter two numbers: 1
2
0: Add, 1: Subtract, 2: Multiply, 3: Divide
Enter number of operation: 0
24

Enumeration
Anenumeration is a userdefined data type consists of integral constants andeach
integralconstantisgivenaname.Keywordenumisusedtodefinedenumerateddatatype.
enum type_name{ value1, value2,...,valueN };
Here, type_name is the name of enumerated data type or tag. And value1,
value2,....,valueN are values of type type_name.
By default, value1 will be equal to 0, value2 will be 1 and so on but the programmer can
change the default value as below:
enum suit{
club=0;
diamonds=10;
hearts=20;
spades=3;
};

DeclarationofEnumeratedVariable
Abovecodedefinesthetypeofthedatabut,noanyvariableiscreated.Variableoftypeenum
canbecreatedas:
enum boolean{
false;
true;
};
enum boolean check;
25

Example Problem
Problem
A program to identify the current day of the week (wednesday) using enumeration.

Code
#include <stdio.h>
enum week{ sunday, monday, tuesday, wednesday, thursday,
friday, saturday};
int main(){
enum week today;
today=wednesday;
printf("%dth day",today+1);
return 0;
}

Output
4th day

26

Topic 10: Character Handling Library Functions

Programs that work with characters and strings often need to classify a character--is it
alphabetic, is it a digit, is it whitespace, and so on--and perform case conversion operations on
characters. The functions in the header file ctype.h are provided for this purpose.
Since the choice of locale and character set can alter the classifications of particular character
codes, all of these functions are affected by the current locale.

Classification of Characters
int islower (char c)
Returns true if c is a lower-case letter.
int isupper (char c)
Returns true if c is an upper-case letter.
int isalpha (char c)
Returns true if c is an alphabetic character (a letter). If islower or isupper is true of a character,
then isalpha is also true.
In some locales, there may be additional characters for which isalpha is true--letters which
are neither upper case nor lower case. But in the standard "C" locale, there are no such
additional characters.
int isdigit (char c)
Returns true if c is a decimal digit (`0' through `9').
int isalnum (char c)
Returns true if c is an alphanumeric character (a letter or number); in other words, if either
27

isalpha or isdigit is true of a character, then isalnum is also true.

int isxdigit (char c)
Returns true if c is a hexadecimal digit. Hexadecimal digits include the normal decimal digits
`0' through `9' and the letters `A' through `F' and `a' through `f'.
int ispunct (char c)
Returns true if c is a punctuation character. This means any printing character that is not
alphanumeric or a space character.
int isspace (char c)
Returns true if c is a whitespace character. In the standard "C" locale, isspace returns
true for only the standard whitespace characters:
''
space
'\f'
formfeed
'\n'
newline
'\r'
carriage return
'\t'
horizontal tab
'\v'
vertical tab
int isblank (char c)
Returns true if c is a blank character; that is, a space or a tab. This function is a GNU
extension.
int isgraph (char c)
28

Returns true if c is a graphic character; that is, a character that has a glyph associated with it.
The whitespace characters are not considered graphic
int isprint (char c)
Returns true if c is a printing character. Printing characters include all the graphic characters,
plus the space (` ') character.
int iscntrl (char c)
Returns true if c is a control character (that is, a character that is not a printing character).
int isascii (char c)
Returns true if c is a 7-bit unsigned char value that fits into the US/UK ASCII character set.
This function is a BSD extension and is also an SVID extension.

Case Conversion
int tolower (char c)
If c is an upper-case letter, tolower returns the corresponding lower-case letter. If c is not an
upper-case letter, c is returned unchanged.

int toupper (char c)

If c is a lower-case letter, tolower returns the corresponding upper-case letter. Otherwise c is
returned unchanged.

int toascii (char c)

This function converts c to a 7-bit unsigned char value that fits into the US/UK ASCII
character set, by clearing the high-order bits. This function is a BSD extension and is also an
SVID extension.

int tolower (char c)

29

This is identical to tolower, and is provided for compatibility with the SVID.

int toupper (char c)

This is identical to toupper, and is provided for compatibility with the SVID.

Example Problem
Problem
A program to determine if the character is an alphabet or not.

Code
#include <stdio.h>
#include <ctype.h>
int main()
{
int var1
int var2
int var3
int var4

=
=
=
=

'd';
'2';
'\t';
' ';

if( isalpha(var1)
{
printf("var1 =
}
else
{
printf("var1 =
}
if( isalpha(var2)
{
printf("var2 =
}
else
{
printf("var2 =
}
if( isalpha(var3)
{
printf("var3 =

)
|%c| is an alphabet\n", var1 );

|%c| is not an alphabet\n", var1 );

)
|%c| is an alphabet\n", var2 );

|%c| is not an alphabet\n", var2 );

)
|%c| is an alphabet\n", var3 );
30

}
else
{
printf("var3 =
}
if( isalpha(var4)
{
printf("var4 =
}
else
{
printf("var4 =
}

|%c| is not an alphabet\n", var3 );

)
|%c| is an alphabet\n", var4 );

|%c| is not an alphabet\n", var4 );

return 0;
}

Output
var1 = |d| is an alphabet
var2 = |2| is not an alphabet
var3 = | | is not an alphabet
var4 = | | is not an alphabet

31