Chapter 5

Pointers and Arrays

Contents

5.1. Concepts of pointers

5.2. Pointer declarations
5.3. Pointer operators
5.4. Concepts of arrays
5.5. One dimensional arrays
5.6. Operations on one dimensional arrays
5.7. Multi-dimensional arrays
5.1. Concepts of pointers

• Powerful, but difficult to master

• Simulate call-by-reference for functions
• Close relationship with arrays and strings
Pointers and Addresses

• One variable always has two properties:

• The address of the variable
• The value of the variable.
• Example:
int i, j;
i = 3;
j = i;

A pointer is a variable that contains the address of a variable

Directly and indirectly referencing a variable
5.2. Pointer declaration

• A pointer is a special type of variable that can hold an

address
• Pointer declaration
type * name ;
• Example:
1. #include <stdio.h>
2. main()
3. {
4. int a=5;
5. int *p=&a;
6. printf("%x %d", p,a);
7. }
Graphical representation of a pointer variable
Pointer Operators

& (address operator)

• Returns address of operand
int y = 5;
int *yPtr;
yPtr = &y; /* yPtr gets address of y */
yPtr “points to” y
Pointer Operators

* (indirection/dereferencing operator)
• Returns a synonym/alias of what its operand points to
• *yptr returns y (because yptr points to y)
• * can be used for assignment
• Returns alias to an object
*yptr = 7; /* changes y to 7 */
• Dereferenced pointer (operand of *) must be an lvalue (no
constants)
Example

If aPtr points to a, then &a and

aPtr have the same value.

a and *aPtr have the same value

&*aPtr and *&aPtr have the same value

Result of the program on previous slide

The address of a is 0012FF7C

The value of aPtr is 0012FF7C

The value of a is 7
The value of *aPtr is 7

Showing that * and & are complements of each other.

&*aPtr = 0012FF7C
*&aPtr = 0012FF7C
Arrays

• Problem solving often requires information be

viewed as a list or a matrix.
• C provides a mechanisms: Array structure
• One-dimensional or multidimensional
• Traditional and important because of legacy
libraries
• Restrictions on its use
Array Terminology

• An array is composed of elements

• Elements in an array have a common name
• The list as a whole is referenced through the
common name
• In the scope of the course elements of an array are
of the same type — the base type
• Elements of an array are referenced by subscripting
or indexing the common name
One dimensional array declaration

BaseType Id [ SizeExp ] ;

Type of Bracketed constant

values in expression
list Name indicating number
of list of elements in list

double X [ 100 ] ;
Restrictions

• Subscripts are denoted as expressions within

brackets: [ ]
• Base type can be any standard, library-defined, or
programmer - defined type
• The index type is integer and the index range must
be 0 ... n-1 where n is a programmer-defined
constant expression.
Examples of array declaration

• Suppose
const int N = 20;
const int M = 40;
const int MaxStringSize = 80;
const int MaxListSize = 1000;

• The following are all correct array declarations

int A[10]; // array of 10 ints
char B[MaxStringSize]; // array of 80 chars
double C[M*N]; // array of 800 floats
int Values[MaxListSize]; // array of 1000 ints
Rational D[N-15]; // array of 5 Rationals
int F[5]={0,1,2,3,4}
Subscripting
• Suppose
• int A[10]; // array of 10 ints A[0], … A[9]
• To access individual element must apply a subscript to list name A
• A subscript is a bracketed expression also known as the index
• First element of list has index 0
A[0]
• Second element of list has index 1, and so on
A[1]
• Last element has an index one less than the size of the list
A[9]
• Incorrect indexing is a common error (in several C compilers)
A[10] // OK in DevC
Basic Operations on one dimensional arrays

• Input data
• Print the list
• Find smallest (greatest) value, indexes of smallest
elements of the list
• Search the list with a key
• Sort the list in ascending (descending) order
• Insert an element
• Delete an element

18
Input data into an array
int A[10];

int n;//actual size of A

int i ;// control variable

//Input array size

do {

printf("Enter array size:");

scanf("%d",&n);

while (n<1||n>10) ;

//Input elements

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

printf("\nA[%d]=",i);// Remind the user to enter correct element

scanf("%d",&A[i]);

} }

}
19
Display an array

// List A of n elements has already been set

puts("\nYour List");
for(i=0;i<n;i++)
printf("%d ", A[i]);
Result of the program

21
Smallest Value

• Problem
• Find the smallest value in a list of integers
• Input
• a value indicating the number of elements and a list of
number
• Output
• Smallest value in the list
• Note
• List remains unchanged after finding the smallest value!
Necessary Information

• Information to be maintained
• Number of values in array
• Array with values to be inspected for smallest value
• Index of current element being considered
• Smallest value so far
A More Detailed Design

• Solution
• Initialize smallest value so far to first element
• For each of the other elements in the array in turn
• If it is smaller than the smallest value so far, update the
value of the smallest value so far to be the current
element
• Print smallest value
Program

int min;
min=A[0];
for(i=1;i<n;i++)
if(A[i]<min)min=A[i];
printf("\nThe smallest value in the list
is:%d",min);
Indexes of smallest elements

puts("\nIndexes of smallest elements:\n");

for(i=0;i<n;i++)
if(A[i]== min)printf("%d ",i);

26
Searching

• Problem
• Determine whether a value key is one of the element
values.
• Two possible answer: Found/Not Found
• Does it matter if
• Element values are not necessarily numbers
• Element values are not necessarily unique
• Elements may have key values and other fields
Sequential Searching

//Search a key value using for statement

int key;
printf("\nEnter the key:");
scanf("%d",&key);
for (i = 0; i < n; i++)
if (A[i] == key) break;
if (i<n) printf("\nFound");
else printf("\n Not Found");
Sequential Searching

//Search a key value using while statement

int found=0,key1;
printf("\nEnter the key:");
scanf("%d",&key1);
i=0;
while(i<n &&found==0)
if (A[i] == key1) found=1;
else i++;
if (found)printf("Found"); else printf("Not
found");
Sorting

• Problem
• Arranging elements so that they are ordered according to
some desired scheme
• Standard is non-decreasing order
• Why don't we say increasing order?

• Major tasks
• Comparisons of elements
• Updates or element movement
Common Sorting Techniques

• Bubble sort
• Iteratively pass through the list and examining adjacent
pairs of elements and if necessary swap them to put them
in order. Repeat the process until no swaps are necessary
• Selection sort
• Sorts an array by repeatedly finding the minimum element
(considering ascending order) from unsorted part and putting it
at the beginning
Selection sort

• The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
• In every iteration of selection sort, the minimum element
(considering ascending order) from the unsorted
subarray is picked and moved to the sorted subarray.

32
Sorting (ascending order) Selection sort algorithm

List Step A Step B Step C Step D

3 3
2
1 1 1 1 1
5 5 3
2
5 2 2 2
2 2
3 5
3 5
3 3 3
6 6 6 6 6
5 5
1 1
2 3
2 3
5 5
6 6
33
Example of selection sort

• Assume array A contains 5 elements: 3 5 2 6 1

• Step A: Find the minimum element in A[0]...A[4] and place it
at the beginning of the list
15362
• Step B: Find the minimum element in A[1]...A[4] and place it
at the beginning of unsorted list A[1] ..A[4]
12563
• Step C: Find the minimum element in arr[2...4] and place it at
the beginning of unsorted list A[2]...A[4]
12365
• Step D: Find the minimum element in arr[3...4] and place it at
beginning of A[3] and A[4]
12356

34
Selection Sort

Note: Index starts

from 1, not like in
C programming
Selection Sort

for (i = 0; i <n-1; i++)

for (j = i + 1; j < n; j++)
if (A[j] < A[i])
{temp=A[i];
A[i]= A[j];
A[j]=temp;}
Other Sorting Techniques

• Insertion sort
• On ith iteration place the ith element with respect to the i-
1 previous elements

• Quick sort
• Divide the list into sublists such that every element in the
left sublist  to every element in the right sublist. Repeat
the Quick sort process on the sublists
Insert an element into the array at specified position

for(i = n; i > k; i--)

2
A[i] = A[i-1];
5
k A[k] = a;
8
7 7
n++;
4
8
Note:
9
4 n = INT_MAX: cannot insert;
k > n  Insert at position n;
?
9
k< 0  Insert at position 0;
Delete an element at desired position from an array

(kth element 0  k < N)

2
5 for(i = k+1; i < N; i++)
k A[i-1] = A[i];
8
3 N --;
3
9
N 4
9
4
Multiple dimensional array declaration

Basetype id [SizeExp1] [SizeExp2]… [SizeExpn]

Example
int disp [10][10]

40
Multiple dimensional array declaration

Basetype id [SizeExp1] [SizeExp2]… [SizeExpn]

Example
int disp [10][10]

41
Example: Read and display elements of a matrix
#include<stdio.h> //Displaying array elements
int main(){
printf(“The matrix:\n");
/* 2D array declaration*/
for(i=0; i<m; i++) {
int M[5][5];
for(j=0;j<n;j++)
int m,n; // actual size of matrix
printf("%4d ", M[i][j]);
int i,j; //Counter variables for the loop
//Reading the matrix printf("\n");

printf("Number of rows:");
scanf("%d",&m); }
printf("Number of columns:"); return 0;
scanf("%d",&n);
}
for(i=0; i<m; i++) {
for(j=0;j<n;j++) {
printf(“M[%d][%d]=", i, j);
scanf("%d", &M[i][j]);
}
}

42