What we have learned so far

• Straight forward statements

• Conditional statements (branching)

• Repeated statements (loops)

Adding Comments
• Why is it important to write comments?
 Some programmers are not very smart and write ugly
codes!!

1
ONE
MONTH
LATER
…

ONE
MONTH
LATER
…

2
 Two types of Comments
• Single line comment

int a=5; //initialization

• Multi-line comments

/*
Addition Of Two Numbers
By Bill Gates
© Microsoft Corporation
*/
int a=(b*c + b*d)/b; int a = c + d;

However…..

3
 Arrays
One variable many data

Problem:
Read 10 numbers from the keyboard and store them

4
 100 Problem:
Read 10 numbers from the keyboard and store them
// solution #1
int a, b, c, d, e, f, g, h, i, j;

printf(“Enter a number: “);

scanf(“%d”, &a); Two Problems

printf(“Enter a number: “); • Many Variable

scanf(“%d”, &b); • Many lines of
code
//…

printf(“Enter a number: “);

scanf(“%d”, &j);

Arrays
• An array is an ordered list of data values of similar kind

The entire array Each value has a numeric index

has a single name

0 1 2 3 4 5 6 7 8 9

a 79 87 94 82 67 98 87 81 74 91

An array of size N is indexed from zero to N-1

This array holds 10 values that are indexed from 0 to 9

5
An array with 8 elements of type double

Arrays
• The values held in an array are called array
elements

• An array stores multiple values of the same type –

the element type

• The element type can be a primitive type

• Therefore, we can create an array of int, an array
of float, an array of double or an array of
character.

6
 Declaring Arrays
data_type array_name[size];

For example:

int a[10];

a is an array of 10 integers.

float prices[3];

prices is an array of 3 floats.

char c[6];

c is an array of 6 characters.

How to assign values?

There are 3 ways.

7
 How to assign values?
First way

• It is possible to initialize an array when it is

declared:

float prices[3] = {1.0, 2.1, 2.0};

int a[3] = {3, 8};

int a[3] = {0};

How to assign values?

First way (Continue)
• Declaring an array of characters of size 3:

char letters[3] = {‘a’, ‘b’, ‘c’};

• Or we can skip the 3 and leave it to the compiler to

estimate the size of the array:

char letters[] = {‘a’, ‘b’, ‘c’};

8
 How to assign values?
Second way:

• Use assignment operator

int a[6];

a[0]=3;

a[1]=6;

How to assign values?

Third way: Array index could be
constant, integer
 Use scanf to input in the array: variable or expressions
int a[6]; that generate integers

scanf(“%d”, &a[0]);

scanf(“%d”, &a[1]); int a[6];

…….. for(i= 0; i<6; i++){

….. scanf(“%d”, &a[i]);

scanf(“%d”, &a[5]); }

9
 How to print values?
Use printf to show values in the array:

int a[6]={1,5,3,9,8,3};
int a[6]={1,5,3,9,8,3};
printf(“%d”,a);
printf(“%d”, a[0]);

printf(“%d”, a[1]);
int a[6];
……..
for(i= 0; i<6; i++){
…..
printf(“%d”, a[i]);
printf(“%d”, a[5]);
}

Arrays: Some examples

• Example 1: Take N students’ marks as input and store

them in an array. Find average mark. N will also be input.
(Do it for 5 students first)

10
 Arrays: Some examples

Example 2: Take N students marks as input and store

them in an array. Find grade of each student. The following
chart will be used for a quick grade conversion in C
programming language course:

90-100 A
80-89 B
70-79 C
60-69 D
0-59 F

• Example 3: Take N numbers as input and store them in

an array. Print all odd numbers in the array.

Example 4:
Take N students marks
as input and store them
in an array. Find
highest/lowest mark.

11
 Finding maximum
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]

4 40 30 70 60 70 88 99 10 87 91 65

Large
r?
Initially assume first element is the maximum

max = a[0]

max < a[1] max >= a[1]

Update max Do nothing

max = a[1]

find_maximum.c
#include <stdio.h>
#include <stdlib.h>

#define N 12
int main()
{
int a[N] = { 14, 21, 36, 14, 12, 9, 8, 22, 7, 81, 77, 10};
int i;

// Find The Maximum Element

int max=a[0]; // pick the first number as the current maximum

for(i=1; i< N; i++)
{
if(max < a[i])
{
max=a[i];
}
}

printf("The maxiumum value in the array is %d.\n\n", max);

}

12
 Problem:
Find the minimum number in an array
of unsorted integers

find_minimum.c

find_minimum.c
#include <stdio.h>
#include <stdlib.h>

#define N 12
int main()
{
int a[N] = { 14, 21, 36, 14, 12, 9, 8, 22, 7, 81, 77, 10};
int i;

// Find The Minimum Element

int min=a[0]; // pick the first number as the current minimum

for(i=1; i< N; i++)
{
if(a[i] < min)
{
min=a[i];
}
}

printf("The minumum value in the array is %d.\n\n", min);

}

13
 Problem:
Find the minimum number (and its index)
in an array of unsorted integers

find_minimum_and_index.c

find_minimum_and_index.c
#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
int a[N] = { 14, 21, 36, 14, 12, 9, 8, 22, 7, 81, 77, 10};
int i, min;

// Find The Minimum Element and it index

min= a[0]; // initial guess: a[0] is the minimum value
int idx=0; // initial guess: the minimum value is at index 0

for(i=0; i< N; i++)

{
if(a[i] < min)
{
min=a[i];
idx=i;
}
}
printf("The minumum value in the array is %d.\n\n", min);
printf("It is located at index: %d \n\n", idx);
}

14
 Example 5: Take N numbers as input and store them
in an array. Shift all elements of the array one place
towards left. The first element will go to the last place.

Left rotate all the elements in an array

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]

4 6 6 4 7 8 10 7 8 10 4 9

t = a[0]
Desired output:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]

6 6 4 7 8 10 7 8 10 4 9 4

15
 Code snippet
#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
int a[N] = { 4, 6, 6, 4, 7, 8, 10, 7, 8, 10, 4, 9};
int i, t;

t = a[0];
for(i=0; i < N-1; i++)
a[i] = a[i+1];

a[N-1] = t;
printf(" Array elements after left rotation……..\n");

for(i = 0; i < N; i++)

printf("%d\n", a[i]);
}

Searching

16
 Search

Linear Search
• The most basic

• Very easy to implement

• The array DOESN’T have to be sorted

• All array elements must be visited if the search fails

• Could be very slow

17
Example: Example:
Successful Successful
Linear Linear
Search Search

Example:
Failed
Linear
Search

18
 Problem:
Find the index of a number in an
unsorted array of integers

linear_search.c

Linear_Search.c
#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
int a[N] = { 4, 21, 36, 14, 62, 91, 8, 22, 7, 81, 77, 10};
int i;
int target, i, idx;
printf("What do you want to search?");
scanf("%d", &target);
idx = -1;
for(i=0; i< N; i++)
{
if(a[i] == target)
{
idx=i;
break;
}
}
if(idx == -1)
printf("Target not found.\n\n");
else
printf("Target found at index: %d \n\n", idx);
}

19
Linear Search in a Sorted Array

Target 19

21 > 19

Problem:
Find the index of a number in a
sorted array of integers

LinearSearch_InSortedArray.c

20
 LinearSearch_InSortedArray.c
#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
int a[N]= { 4, 7, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91};
int target, i, idx;
printf("What do you want to search?");
scanf("%d", &target);
idx = -1;
for(i=0; i< N; i++)
{
if(a[i] == target)
{
idx=i;
break;
}
else if(a[i]>target)
break; // we can stop here
}
if(idx == -1)
printf("Target not found.\n\n");
else
printf("Target found at index: %d. \n\n", idx);
}

Analysis

• If the list is unsorted we have to search all

numbers before we declare that the target is not
present in the array.

• Because the list is sorted we can stop as soon as

we reach a number that is greater than our target

• Can we do even better?

21
 Collecting statistics in an array

Take N students’ marks as input and store them in

array. Find and print how many of them got A, how
many of them got B, C, D and F grades respectively.
The grade chart is provided below:

Marks Grade
===== =====
90 – 100 A
80 – 89 B
70 – 79 C
60 – 69 D
<60 F

Collecting statistics in an array

#include <stdio.h>
#define N 12
int main()
{
int a[N]= { 40, 72, 86, 10, 94, 91, 56, 36, 62, 77, 81, 91};
int aCount, bCount, cCount, dCount, fCount;

aCount = bCount = cCount = dCount = fCount = 0;

for(i=0; i< N; i++)

{
if(a[i] >= 90) aCount++;
else if(a[i] >= 80) bCount++;
else if(a[i] >= 70) cCount++;
else if(a[i] >= 60) dCount++;
else fCount++;

}
printf(“Number of students getting A %d \n“, aCount);
printf(“Number of students getting B %d \n“, bCount);
printf(“Number of students getting C %d \n“, cCount);
printf(“Number of students getting D %d \n“, dCount);
printf(“Number of students getting F %d \n“, fCount);
}

22
 Some Harder Examples

• Print the number of distinct elements in an array which

is already sorted in ascending order

Number of distinct elements in a sorted array

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]

4 4 6 7 7 7 8 9 10 10 10 10

same? Number of distinct elements = 6

Initially assume all elements are distinct
Number of distinct elements = total number of elements
= 12

t = a[0]

t == a[1] t != a[1]

Decrement counter Do nothing

23
 Code snippet

#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
int a[N] = { 4, 4, 6, 6, 7, 7, 7, 8, 9, 10, 10, 10, 10};
int i, counter;

counter = N;
for(i=0; i< N-1; i++){
if(a[i] == a[i+1])
counter--;
}
printf("The number of distinct elements in the array is
%d.\n\n", counter);
}

Some Harder Examples

• Print largest and second largest element of an array.

Assume that the array has at least two elements.

24
 Largest and Second largest
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]

4 21 36 14 62 91 8 22 7 81 77 10

secL = 4 largest = 21

Third element
t = a[2]

t > largest secL < t <= largest t <= secL

secL = largest secL = t ignore

largest = t

Code Snippet
if(a[0] > a[1]){
largest = a[0];
secL = a[1];
}
else{
largest = a[1];
secL = a[0];
}

for(i=2; i< N; i++){

t = a[i];
if(t >= largest){
secL = largest;
largest = t;
}
else if (t > secL) secL = t;
}

printf("The largest: %d second largest: %d", largest, secL);

}

25
Questions?

26