STRUCTURED DATA TYPE

Chapter 4

https://www.hellgeeks.com/sequential-
search/
https://www.w3schools.com/cpp/default.asp
https://www.geeksforgeeks.org/structures-in-cpp/
http://www.cplusplus.com/doc/tutorial/structures/
 Records and Records Structures.
Hierarchical records.

Tables.

OBJETIVES
Search and find schemes.

Strings
 • Arrays are used to store multiple values in a single variable, instead
of declaring separate variables for each value.
• An array in C/C++ or be it in any programming language is a
collection of similar data items stored at contiguous memory
locations and elements can be accessed randomly using indices of an
array.
• They can be used to store collection of primitive data types such as
int, float, double, char, etc of any particular type. To add to it, an
array in C/C++ can store derived data types such as the structures,
pointers etc. Given below is the picture representation of an array.

Array
Why do we
need arrays?
• We can use normal variables
(v1, v2, v3, ..) when we have
a small number of objects,
but if we want to store a large
number of instances, it
becomes difficult to manage
them with normal variables.
The idea of an array is to
represent many instances in
one variable.
How to declare an array
• To declare an array, define the variable type, specify the name of the
array followed by square brackets and specify the number of
elements it should store:

We have now declared a variable that holds an array of four strings. To insert values to it, we can
use an array literal - place the values in a comma-separated list, inside curly braces:
Access the Elements of an Array
• You access an array element by referring to the index number.
Change an Array Element
• To change the value of a specific element, refer to the index number:
Access the Elements of an Array
• You access an array element by referring to the index number.
• This statement accesses the value of the first element in cars:
Omit Array Size
• You don't have to specify the size of the array. But if you don't, it will
only be as big as the elements that are inserted into it:

• This is completely fine. However, the problem arise if you want extra
space for future elements
• If you specify the size however, the array will reserve the extra space:
Array and Loops - Loop Through an Array
• You can loop through the array elements with the for loop.
Search Vs Traversal Algorithm
Search Algorithm:
• Definition: A search algorithm is used to find a specific item or
element within a collection of data.
• Objective: The goal of a search algorithm is to determine whether a
particular item exists in the given dataset and, if so, where it is
located.
• Termination Condition: A search algorithm typically terminates when
the target item is found or when the entire dataset has been searched
without success.
Search Vs Traversal Algorithm
Traversal Algorithm:
• Definition: A traversal algorithm is used to visit or process all the
elements in a collection of data.
• Objective: The goal of a traversal algorithm is to perform an
operation on each element in the dataset, without necessarily looking
for a specific item.
• Termination Condition: A traversal algorithm continues until it has
visited all the elements in the dataset.
Search Vs Traversal
Algorithm

• In summary, a search algorithm is about

finding a specific item in a dataset, while
a traversal algorithm is about visiting and
processing all elements in a dataset.
Each type of algorithm is designed with a
specific goal in mind, and the choice
between them depends on the problem
you're trying to solve.
Searching in Arrays
• The process of finding the required data in an array is called
searching. Normally, there are two types of searching techniques
used in C++.
• Sequential search.
• Binary search (only if the array is sorted)
Sequential search
• Sequential search in C++ is also
called a linear search. This
searching technique is very simple,
to perform this technique the user
starts the loop from the zero index
of an array to the last index of an
array. It starts from the first index
and compared the required value
with the first value.
• If the required value is found it will
show the result otherwise compare
the value of next index and it will
continue until the required value is
found or loop completes without
finding any value.
Sequencial Search – with while
Sequencial Search – return the index
Linear Search
with Duplicate Element
• This program has many extra features than previous
program:
• Allows user to define the size of array
• Handles that type of inputs, when user enters a number that doesn't
exist in the array
• Prints all the index numbers, if entered number found in repeated
order

Need to check if tot>100

Search in a array with duplicate elements need
To loop throught all the array
With variations, this could have been done only
displaying the index
(no need of an extra array to keep the indexs)
 Binary Search – only for sorted array
• Given a sorted array arr[] of n elements, write a function to search a given
element x in arr[].
A simple approach is to do a linear search. Another approach to perform
the same task is using Binary Search.
Binary Search: Search a sorted array by repeatedly dividing the search
interval in half. Begin with an interval covering the whole array. If the value
of the search key is less than the item in the middle of the interval, narrow
the interval to the lower half. Otherwise, narrow it to the upper half.
Repeatedly check until the value is found or the interval is empty.

You will study this algorithm in the

next course.
Efficiency: For the moment, you just
must know that if the array is sorted,
you can start at the beginning and if
the value to search is greater than
that of the array, you can stop and
say "element not found"
 Search in sorted array (naive approach)

You will study this algorithm in the

next course.
Efficiency: For the moment, you just
must know that if the array is sorted,
you can start at the beginning and if
the value to search is greater than
that of the array, you can stop and
say "element not found"
Exercise: Find the Index of Maximum Element
• Write a C++ program that finds the index of the maximum element in a
one-dimensional array of integers. If there are multiple occurrences of the
maximum element, the program should return the index of the first
occurrence.
• Example:
Enter the size of the array: 7
Enter the elements of the array: 4 7 9 4 2 9 8
The maximum element is at index 2.
• Instructions:
1.Ask the user for the size of the array.
2.Ask the user to input the elements of the array.
3.Use a search algorithm to find the maximum element and its index.
4.If there are multiple occurrences of the maximum element, record the
index of the first occurrence.
5.Display the index of the found maximum element
In this program, the user is asked to input the size of
the array and then provide the elements. It then
iterates through the array to find the maximum
element and its index. Finally, it prints out the index
of the maximum element.

This solution uses a linear search algorithm to find

the maximum element in the array. It initializes
maxElement and maxIndex with the first element
and index, and then compares it with the rest of the
elements to find the maximum.

Please note that this solution assumes the user will

input valid integers and doesn't include extensive
error handling. Depending on the specific
requirements of your program, you might want to
add additional validation.
Exercise: Partially Filled Array Search
Write a C++ program that works with a large-sized array, but it's only partially filled. The program should allow the user to
input integers in the initial positions of the array and then perform searches up to the last valid element.
• Instructions:
1. Define an array of a fixed but sufficiently large size.
2. Allow the user to input integers into the initial positions of the array until they choose to stop.
3. Keep a counter that tracks how many elements have been entered and are valid.
4. Implement a search function that allows the user to search for a specific element in the array, up to the last valid
element.
5. If the element is found, display its position. If not, display a message indicating that it wasn't found.
• Example:
Additional Tip:
Enter a number (or enter 0 to stop): 7 Use the counter of valid
Enter a number (or enter 0 to stop): 5 elements to determine the last
Enter a number (or enter 0 to stop): 3 element entered by the user
and therefore the last valid
Enter a number (or enter 0 to stop): 0 element in the array. This will
Enter the number to search for: 5 allow you to perform searches
The number 5 is at position 2. up to that point.
Generating a random int array
Data Structures – Struct in C++
We often come around situations where we need to store a
group of data whether of similar data types or non-similar data
types.
We have seen Arrays in C++ which are used to store set of data
of similar data types at contiguous memory locations.
Unlike Arrays, Structures in C++ are user defined data types
which are used to store group of items of non-similar data
types.

• A data structure is a group of data elements

grouped together under one name. These
data elements, known as members, can
have different types and different lengths.

Once the three objects of a determined structure type are

declared (apple, banana, and melon) its members can be
accessed directly. The syntax for that is simply to insert a dot (.)
between the object name and the member name.
Struct - Direct Initialization (Using Braces)
• You also can initialize a struct variable by directly assigning values
using braces {}.
Structs in C++
Nesting structures
• Structures can also be nested in
such a way that an element of a
structure is itself another structure

After the previous declarations, all of the

following expressions would be valid
Structs in Arrays
• Because structures are types, they can also be used as the type of arrays to construct tables or databases of them: