Slide 1:
arrays Slide 2:
Elementary Data Representation Elementary representation of data can be in forms of raw data, data item, data structures.
(i) Raw Data:-
Raw data are raw facts. These are simply values or set of values.
(ii) Data item:-
Data item represents single unit of values of certain type.
Data Type:-
A Data Type refers to a named group of data which share similar properties or characteristics and which have common behavior among them. For instance: name can contain only alphabets, its data type is alphabetic & age only have digits, its data type is numeric.
Data Structure:-
A Data Structure is a named grouped of data of different data types which can be processed as a single unit. Slide 3:
Primitive & Non-Primitive
Data Type The data structure can contain any of these data types:-
Primitive:-
These are those data types, which are not composed of other data types. C++ names primitive data types as standard or fundamental data types. Ex: Integer, Real, Character (i.e., int, float, double, and char).
Non-Primitive:-
These are those data types which are composed of primitive data types. Sometimes these are called user-define data types because these are defined by users. Ex: array, structure, class, enumeration, union etc.
Pointers:-
A special data type pointer data types has been introduced by some programming languages. These are of great used in some popular and efficient data structures like linked lists, stacks, queues and trees etc. Slide 4:
Different data Structures Data structures are very important in a computer system, as these not only allow the user to combine various data types in a group but also allow processing of the group as a single unit thereby making things much simpler and easier. The data structures can be classified into following two types:
Simple data Structure:-
The data structures are normally built from primitive data types like integers, reals, characters, boolean. Ex: array, structure.
2. Compound Data Structures:-
Simple data structures canbe combined in various ways to form more complex structures called compound data structures. It is classified into two types:
(i) Linear data structures- A data structure is said to be linearif its elements form a sequence. Ex. Stack, queue, linked list.
(ii) Non-Linear data structures- theseare multilevel data structures. Example of non-linear data structure is Tree. Slide 5:
Data Structure Array Structure Simple data structure compound data structure Non-linear linear Stack queue Linked list tree Following figure shows all the data structures. Slide 6:
Arrays refer to a named list of a finite number n of similar data elements. Each of the data elements can be referenced respectively by a set of consecutive numbers, usually 0, 1, 2, 3,…n. If the name of an array of 10 elements is ARY, then its elements will be referenced as shown below:
ARY[0], ARY[1], ARY[2], ARY[3], …….. ARY[9]
Arrays can be one dimensional, two dimensional or multi dimensional. Array:- Structure:- Structure refers to a named collection of variables of different data types. A structure gathers together different atoms of information that form a given entity. The elements of a structure are referenced using the dot operator. Stack:- Stack data structures refer tro the lists stored and accessed in a special way, where LIFO (last in first out) technique is followed. Slide 7:
(a) Stack of plates (b) Queue of people waiting for their turn Slide 8:
Queues:- Linked Lists:- Queues data structures are FIFO lists where insertions take place at the “rear” and of the queues and deletion take place at the “front” and of the queues. Linked lists are special lists of some data elements linked to one another. The logical ordering is represented by having each elements pointing to the next element. start start INFO INFO INFO INFO INFO INFO Slide 9:
In singly linked lists, nodes have one pointer (next) pointing to the next node, whereas nodes of doubly linked lists have two pointers (prev and next). Prev points to the previous node and next points to the node in the lists. Trees:- Tress are multilevel data structures having a hierarchical relationship among its elements called nodes. Topmost node is called the root of the tree and bottom most nodes are called leaves of the tree. Slide 10:
(a) (b) (a) General tree (b) Binary tree Slide 11:
Operations and data structure The basic operations that are performed on data structure are as follows:-
Insertion: It means addition of a new data element in a data structure.
Deletion: It means removal of a data element from a data structure. The data element is searched for before its removal.
Searching: It involves searching for the specific data element in a data structure.
Traversal: Traversal of a data structure means processing all the data elements of it.
Sorting: Arranging data elements of a data structure in a specified order is called sorting.
Merging: Combining elements of two similar data structures to form a new data structure of same type, is called merging. Slide 12:
Arrays When elements of linear structures are represented in memory by means of sequential memory location, these linear structures are called arrays. For instance,
If an array has elements numbered as -7,-6,-5,…0,1,2,…,15, then its UB is 15 and LB is -7 and array length is = 15 – (-7) + 1
= 15 + 7 + 1 = 23
(UB= Upper Bound, LB= Lower Bound) Types of Arrays:- There are different types of arrays:
One-Dimensional Array
(ii) Two-Dimensional Array Slide 13:
One - dimensional Arrays:- The simplest form of array is one-dimensional array. The array itself is given a name and its elements are referred to by their subscript. The notation of an array can be given as follows:
Array name [lower bound L, upper bound U]
Which indicates the array name’s subscript value ranges from L through U.
In C++, an array is denoted as follows:
Array name [size]
Where size specifies the no. of elements in the array and the subscript value ranges from 0 through size – 1.
Ex.: #include<iostream.h>
void main()
{ int A[10],i;
for(i=0;i<10;i++)
{ cout<<“Enter a number: “;
cin>>A[i];
}
cout<<“\n Array Contents\n”;
for(i=0;i<10;i++)
{ cout<<A[i]<<“ “;
}
} Slide 14:
Basic Operations on One-dimensional Arrays:- 1. Searching: Linear Search: In linear search, each element of array is compared with the given Item to be searched for, one by one. This method, which traverses the array sequentially to locate the given Item, is called linear search or sequential search.
Binary Search: This popular search technique searches the given ITEM in minimum possible comparisons. The binary search requires the array, to be scanned, must be sorted in any order. For instance, say ascending order. 2. Insertion: Insertion of new element in array can be done in two ways:
If the array is unordered, the new element is inserted at the end of the array,
If the array is sorted then new element is added at appropriate position without altering the order and to achieve this, rest of the elements are shifted. Slide 15:
3. Deletion: The element to be deleted is first searched for in the array using one of the search techniques i.e., either linear search or binary search. 4. Traversal: Traversal in one-dimensional arrays involves processing of all elements one by one. For instance, traversal of array would process in the following order:
X[0], X[1], X[2], X[3], ……., X[10], 5. Sorting: Sorting of an array means arranging the array elements in a specified order i.e., either ascending or descending order. These are several sorting techniques available e.g., shell sort, shuttle sort, bubble sort, selection sort, quick sort, heap sort etc. Slide 16:
(a) Selection Sort:
One family of internal sorting algorithms is the group of selection sorts. The basic idea of a selection sort is to repeatedly select the smallest key in the remaining unsorted array.
(b) Bubble Sort:
The basic idea of bubble sort is to compare two adjoining values and exchange them if they are not in proper order. For instance, following unsorted array is to be sorted in ascending order using bubble sort. 6. Merging: Merging means combining elements of two arrays to form a new array. Simplest way of merging two arrays is that first copy all the elements of one array into new array and then copy all the elements of other array into new array.