Data Structures and Algorithms

CHAPTER 3
ARRAY AND STRING
MAIN CONTENTS

One dimensional array

Processing an array

Two-dimensional array

String
One dimensional array
• An array is a collection of the same type of data items,
which are stored in consecutive memory locations under
a common name.
• The size of an array signifies the number of elements of
the array. That number should be a positive integer
number.
• An one-dimensional array is one in which only one
subscript is needed to specify a particular element of
the array.
• Arrays in programming are similar to vectors or matrices
in mathematics
One dimensional array - Declaration
• Syntax:
data_type array_name [size];
• Example:
int a[10];

• The subscript will be used to specify a single element

of an array in form of

array_name [index]
One dimensional array
Array in Memory
int a[6];

• Size of One-
Dimensional Array:
sizeof(data_type)*size
or
sizeof(array_name)
One dimensional array - Initialization

• Can not assign values to all elements of an array at

once using an assignment expression
• Can initialize some or all elements of an array when
the array is defined:
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int children[4] = {2, 12};
float b[] = {5.5, 12.1, 11.3};
One dimensional array
Reading array elements
• Can not assign values to all elements of an array at
once using an assignment expression.
• Assign values for each element in the array
• Example
int a[10];
for(i = 0; i < 10; i++)
scanf (“%d”, &a[i]);
One dimensional array
Reading array elements
• Example:
int a[10];
for(i = 0; i < 10; i++)
printf (“%d”, a[i]);
Operations Perform on Arrays
Operations Perform on Arrays
Traversing a Linear Array

• Traversing: Accessing and processing each element of

the array
• Example: Write the algorithms to complete these tasks:
+ Count the number of even elements of the array with 10
elements (integer).
+ Find the max value of given array
Operations Perform on Arrays
Traversing a Linear Array

Algorithm: Traverse (A, N)

[A is the name of the array and N = 10 is the number of elements of the array]
1. Set I=0, count =0;
2. Repeat steps 3 and 4 while I < N
3. If(A[I]%2 == 0) count++;
4. Set I=I+1
[End of loop]
5. Return the value of count
Operations Perform on Arrays
Inserting an Element into a Linear Array
Inserting an Element to a Specific Inserting an Element in a sorted
Position Array
• Move each element from • Find the correct position to
the back up one position insert the key element.
until getting the specified • When the position cannot
position be found, then insert at the
• Insert a key element end.
into a given position. • Otherwise, insert the key
• Increase array size by one element to the found
position (Same as previous
case).
Operations Perform on Arrays
Inserting an Element into a Linear Array (Specific Position)

Algorithm: Insert (A, N, P, KEY)

[A is an array of N elements; P is the position of the inserted item,
KEY is the inserted item]
1. Set I=N-1;
2. Repeat steps 3 and 4 while I>=P
3. Set A[I+1]=A[I]
4. Set I=I-1;
[End of loop]
5. Set A[P]=KEY
6. Set N=N+1
7. Return
 Operations Perform on Arrays
Inserting an Element into a Linear Array (in a sorted Array)
• Example: Insert 50 to the sorted array with 5 elements: 14,
21, 40, 77, 84
1. Find the correct position of key element (50):
Since 50 is greater than 2nd element, the correct position is 3rd
position.
2. Insert 50 to 3rd position

Merge two
steps into
one?
Operations Perform on Arrays
Inserting an Element into a Linear Array (in a sorted Array)

Algorithm: Insert (A, N, KEY)

[A is the sorted array of N elements and KEY is the inserted item]
Set I = N – 1
2. Repeat steps 3 and 4 while A[I]>KEY
3. Set A[I+1]=A[I]
4. Set I=I-1
[End of loop]
5. Set A[I+1]=KEY
6. Set N=N+1
7. Return
Operations Perform on Arrays
Deleting an element from a Linear Array

• Deleting an element from a specific position

• Deleting an element by value

Operations Perform on Arrays
Deleting an element from a Linear Array

• Examples: Delete an element from 2rd position of the

array with 6 elements:
Operations Perform on Arrays
Deleting an element from a Linear Array

Algorithm to delete an element from a specific position

Operations Perform on Arrays
Deleting an element from a Linear Array

Algorithm to delete an element using by value

Operations Perform on Arrays
Deleting an element from a Linear Array

Algorithm to delete an element using by value

Example: Write the algorithm to solve these:
- Input a float array (10 elements) and the value of a
float variable X.
- Delete all the elements that equal to X from given
array
Time complexity of operations performing on arrays

Traversing: O(n).
Inserting:
- The best case is O (1),
- The worst case is O (n),
- The average case is O (n).
Deleting: The best case is O (1),
- The worst case is O (n),
- The average case is O (n).
Applications of Array

 Linear array representation: mainly used for primitive

data types (Representation of polynomials)
 Array of Structure representation: used for structure
data types (information of students, array of strings)
 Multi-Dimensional Arrays
• Multi–dimensional array is nothing but Array of Arrays.
• A two-dimensional array is an array of one-dimensional array.
• A three-dimensional array is an array of two-dimensional
arrays.
• Similarly, any d dimensional array is an array of (d-1)
dimensional arrays.
• Generally, when we talk about multi-dimensional arrays, we
generally talk of two-dimensional arrays since more than two-
dimensional is rarely needed.
Multi-Dimensional Arrays
• There is a need to store and manipulate two-dimensional
data structure such as matrices and tables.
• A two-dimensional array is one in which two subscript
specifications are needed to specify a particular element of
the array.
• One subscript denotes the row and the other the column
Some concepts related to Multi-Dimensional Arrays

• Declaration of Two-Dimensional Array

• Address Calculation in two-dimensional Array
• Row-major Implementation
• Column-major Implementation
• Reading and Writing a two-dimensional array
• Operations Perform on two-dimensional Arrays
• Sparse matrix and Dense Matrix
Some concepts related to Multi-Dimensional Arrays

• Example: Write the algorithms to solve these following

problems
- Input a two-dimensional array A (size of 3x3).
- Display given two-dimensional array A in the form of matrix
- Find the max values of each column in given two-
dimensional array.
STRINGS
• A string is a sequence of characters
• In C language, the end of the string is marked with a
special character, the null character
• The null or string terminating character is represented
by a character escape sequence ‘\0‘
• Any sequence or set of characters defined by double
quotation symbols is a constant string.
• Strings are stored in memory as ASCII codes of
characters that make up the string appended with ‘\0‘
STRINGS – ASCII code
STRINGS -
• A string is a sequence of characters
• In C language, the end of the string is marked with a
special character, the null character
• The null or string terminating character is represented
by a character escape sequence ‘\0‘
• Any sequence or set of characters defined by double
quotation symbols is a constant string.
• Strings are stored in memory as ASCII codes of
characters that make up the string appended with ‘\0‘
STRINGS - Declaring and Initializing Strings
• Syntax: char string_name [size];
• Examples:
char name[30];
char city[25];
char class[20] = “BDA2022A”;
STRINGS – Operations on strings
• Input and display a string (in C):
scanf(“%s”, name); or gets(name);
printf(“\n %s”, name);
• Input and display a string (in C++):
cin>>name; or getline(cin,name);
cout<<name;
STRINGS – Operations on strings
STRINGS – Operations on strings
• Length of a String: The length of a string returns the
total number of characters of the string
• String Copy: Copy the current value of the string into
another string that has the same value as the original
string. One cannot copy a string using the assignment
operator.
• Concatenation of two Strings: appends the contents
of one string at the end of another string.
STRINGS – Operations on strings

• Comparison of two Strings: Comparison of two strings

to decide whether they represent a same string or not by
comparing the characters in two strings one by one.
• String Reversal: The reverse of a string is a string with
the same characters, but in the reverse order. a string is
the reverse of itself is called a palindrome.
• String Matching: String matching (or string searching) is
an operation to find the position of all occurrences of a
pattern within a given string or text.
STRINGS – Operations on strings

• Example:
Write the algorithms to solve these problems
- Input a string str1.
- Find the length of str1.
- Input another string str2.
- Check if two these strings are the same. Display the
result.
- Concatenate str2 to str1
Summary
 An array is a collection of variables of the same data type
that are stored in consecutive memory location under a
common name.
 An array can be an integer, character or floating-point data
type can be initialized only during declaration.
 An array name is an address of the first element of the array.
 A matrix is said to be Sparse Matrix if most of its elements
are having a relatively small number of non-zero elements.
 The string is a sequence of characters.
Exercises
1. Complete the Exercises on pages 3.31, 3.32
2. Write the algorithms to solve following problems
2.1 Input an one dimensional integer array with N elements
(0<N<10) and an integer X. Find the position of X in given
array.
2.2. Input a string and check if this string is palindrome
3. Write the algorithms to use an array of strings (size
0<=N<=6) (you can use the library “string”)
- Input the data for each element in the array
- Show the shortest string in this array