Definition
Data may be organized in many different ways.
The logical or mathematical model of a particular organization is called a data structure.
It can also be defined as the choice of representation of data.
The choice of a data model depends on two considerations :
It must be rich enough to mirror the actual relationship of data in the real world.
It should be simple enough that one can effectively process the data when necessary
Classification
Data structures can be classified as :
Linear
Nonlinear
A data structure is said to be linear if its elements form a sequence.
Examples for linear structure include arrays and linked lists.
Trees and graphs are examples of nonlinear structures.
Linear Data structures
The operations performed on linear structures are :
Traversal
Search
Insertion
Deletion
Sorting
Merging
Arrays
The simplest type of data structure is a one-dimensional array or list or linear array.
Linear array is a list of finite number (n) of similar data elements referenced respectively by a set of n consecutive numbers , usually 1,2…..n.
If we choose a name A for the array , then the elements of A are denoted by subscript notation
a1,a2,a3……,an
or by the parenthesis notation
A(1),A(2)………. ,A(n)
or by the bracket notation
A[1],A[2]………. , A[n]
The value K in A[K] is called a subscript and A[K] is called a subscripted variable.
The elements of an array are stored in consecutive memory locations.
Linear Array
A linear array LA can be pictured as
(LB) 1
2 1 2 3 4 5
3
4
(UB) 5
Notations :-
LB :- Lower Bound
UB :- Upper Bound
Length of an array :- UB – LB + 1
LOC(LA[K]) :- Address of the element LA[K] of the array LA
Base (LA) :- Address of the first element of LA.
LOC (LA [K]) =Base (LA) + w (K-lower bound) ,where w is the number of words per memory cell for the array LA.
Traversing Linear Arrays
Let LA be a collection of elements stored in memory of the computer. Suppose we want to print the contents of the array or to count the number of elements of LA with a given property. This can be accomplished by traversing LA ,that is by accessing and processing each element of exactly once.
Algorithm
Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation to each element of LA.
[Initialize counter] Set K = LB.
Repeat steps 3 and 4 while K<=UB
[Visit Element] Apply process to LA[K].
[Increment counter.] K = K+1.
End of step 2 loop.
Exit.
Insertion
Suppose LA is an array containing 5 names in alphabetical order
Algorithm
(Inserting into a Linear Array) INSERT(LA,N,K,ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K<=N. this algorithm inserts an element ITEM into the Kth position in LA.
[Initialize counter.] Set J=N.
Repeat steps 3 and 4 while J>=K.
[Move Jth element downward.] Set LA[J+1] = LA[J].
[Decrease Counter.] Set J = J-1.
[End of step 2 loop.]
[Insert element.] set LA[K] = ITEM.
[Reset N] Set N= N + 1.
Exit
Deletion
Suppose we want to delete an element “smith” from the array.
Deletion
(Deleting from a Linear array)DELETE(LA,N,K,ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from LA.
Set ITEM = LA[K]
Repeat for J=K to N-1:
[Move J+1 th element upward] Set LA[J] = LA[J+1].
[End of loop.]
[Reset the number N of elements in LA.] Set N=N-1
Exit .
Searching
Let A be a collection of data elements in memory and suppose a specific ITEM of information is given. Searching refers to the operation of finding the location LOC of ITEM in A or printing some message that ITEM does not appear there.
The search is said to be successful if ITEM does appear in A and unsuccessful otherwise.
Searching Techniques
There are different searching techniques
Linear Search
Binary Search
Binary search is more efficient than linear search. It take lesser time for execution.
The complexity of searching algorithms is measured in terms of the number of comparisons required to find ITEM in array .
Linear Search
Suppose A is an array with N elements.
To search for a given item in A , compare ITEM with each element of A one by one.
This method , which traverses A sequentially to locate ITEM , is called linear search or sequential search.
Algorithm
(Linear search) LINEAR(A,N,ITEM,LOC)
Here A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in DATA , or sets LOC=0 if search is unsuccessful.
[Insert ITEM at the end of A]. Set A[N+1]=ITEM.
[Initialize Counter] Set LOC=1.
[Search for ITEM]
Repeat while A[LOC] != ITEM
Set LOC=LOC+1
[End of loop]
[Successful?] If LOC=N+1 , then Set LOC=0.
Exit
Binary Search
Suppose A is an array which is sorted in increasing numerical order or alphabetically.
Then there is an extremely efficient searching algorithm, called binary search.
The algorithm compares ITEM with the middle element A[MID] where MID is obtained by
MID=((BEG+END)/2)
If A[MID]=ITEM , then search is successful and set LOC=MID. Otherwise a new segment of A is obtained as follows:
If ITEM<A[MID], then ITEM can appear only in the left half of the segment : A[BEG],A[BEG+1],…….A[MID-1]
So reset END = MID-1 and search again.
If ITEM>A[MID], then ITEM can appear only in the right half of the segment : A[MID+1],A[MID+2]……..A[END].
So reset BEG=MID+1 and search again.
Algorithm
(Binary search) BINARY(A,LB,UB,ITEM,LOC)
Here A is a sorted array with a lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG,MID and END denote, respectively the beginning, end and middle locations of a segment of elements of A. This algorithm finds the location Loc of ITEM in A or sets LOC=NULL.
[Initialize segment variables.]
Set BEG=LB,END=UB AND MID = INT((BEG+END)/2)
Repeat Steps 3 and 4 while BEG<= END and A[MID]!=ITEM
If ITEM<A[MID], then:
Set END= MID – 1
Else
Set BEG = MID + 1
[End of If.]
Set MID = INT((BEG+END)/2)
[End of step2 loop.]
If A[MID]=ITEM , then
Set LOC= MID
else
Set LOC=NULL
[End of If]
Exit
Example
Consider an array with 5 elements :
Let ITEM= 76
12 , 15 , 20 , 23 , 32 , 45 , 54 , 76 , 98 beg=1,end=9 ,mid=5
Limitations of Binary Search
Even if the binary search algorithm is so efficient it requires two conditions :
The list must be sorted and
One must have direct access to the middle element in any sub list .
This means that one must essentially use a sorted array to hold data.
But keeping data in sorted array is normally very expensive when there are many insertions and deletions.
Sorting Methods
Bubble sort
Selection sort
Quick sort
Insertion sort
Merge sort
Heap sort
Bubble Sort
Let A be a list of n numbers. Sorting A refers to the operation of rearranging the elements of A so that they are in increasing order. A[1]<A[2]…..<A[N]
Steps
Compare A[1] and A[2] and arrange them in desired order, so that A[1]<A[2]. Then compare A[2] and A[3] and arrange them so that A[2]<A[3].Continue until we compare A[N-1] with A[N]. This step involve N-1 comparisons.
Repeat step 1 with one less comparison .That is ,now we stop after we compare and rearrange A[N-2] and A[N-1]
………………….
………………..
Step N-1. Compare A[1] with A[2] and arrange them so that A[1]<A[2]
After N-1 steps , the list will be in sorted order.
Algorithm
(Bubble Sort) BUBBLE (A,N)
Here A is an array with N elements. This algorithm sorts the elements in A.
Repeat steps 2 and 3 for K=1 to N-1.
Set PTR=1[Initializes a pointer PTR.]
Repeat while PTR<=N-K [Executes pass]
If A[PTR]>A[PTR+1], then :
Interchange A[PTR] and A[PTR+1].
[End of If]
Set PTR=PTR+1.
[End of inner loop]
[End of outer loop]
Exit
Example
32 , 27 , 51 ,66 , 23, 13,85,57
Complexity of Algorithms
An algorithm is a well-defined list of steps for solving a particular problem.
The time and space it uses are two major measures of the efficiency of the algorithm.
The complexity of an algorithm is the function which gives the running time or space in terms of the input size.
Complexity of Linear Search
In linear search we read each item in the list one at a time and compare it with the item to be searched.
The time required to execute this algorithm is proportional to the number of comparisons.
The average number of comparisons required
in a list of n elements = n/2.
=> complexity of linear search , C (n)=n/2.
Multi-Dimensional arrays
Linear arrays in which each element is referenced by a single subscript is called a one – dimensional array.
Arrays in which elements are referenced by more than one subscript is called multi-dimensional arrays.
A two-dimensional array A is a collection of m*n elements such that each element is specified by a pair of subscripts A [i][j]
Representation of 2-D arrays
A 2-D array is stored in memory by a block of m*n sequential memory locations.
The programming language will store the array A either
Column by column (column-major order)
Row by row (row-major order)
2-D arrays
For a one-dimensional array computer uses the formula
LOC(A[K])=Base (A) +w(K-1)
to find the address of A[K].
For a 2-D array the address of A[J,K] is found out using the formula
LOC(A[J,K])=Base(A)+w[M(K-1)+(J-1)]
(Column major order)
LOC(A[J,K] = Base (A)+[N(J-1)+(K-1)]
Stacks and Queues
The linear lists and arrays allow one to insert and delete elements at any place in the list : at the beginning , at the end or in the middle.
But there are certain situations in computer science when one wants to restrict insertions and deletions so that they can take place only at the beginning or the end of the list , not in the middle.
Two of the data structures that are useful in such situations are stacks and queues.
Stacks
A Stack is a linear structure in which items may be added or removed only at one end.
A stack is a homogeneous collection of items of any one type, arranged linearly with access at one end only, called the top.
Formally this type of stack is called a Last In, First Out (LIFO) stack.
Data is added to the stack using the Push operation, and removed using the Pop operation.
Stacks
Consider the following example :
Operations on Stack
Two basic operations associated with stack include :
Push :- term used to indicate insertion.
Pop :- term used to indicate deletion.
Suppose the following 5 elements are to be inserted or pushed on to the stack:
a, b ,c ,d ,e
Operations on Stack
The elements from a stack are poped in the reverse order.
Elements are poped in the following order.
Array Representation of Stack
Stacks may be represented in the computer in various ways ,usually by means of a one-way list or a linear array.
Stack can be maintained by a linear array STACK, a variable TOP , which contains the location of the top element of the stack and a variable MAXSTK which gives the maximum number of elements that can be held by the stack.
The condition TOP=0 or TOP=NULL will indicate that the stack is empty.
Algorithm
PUSH(STACK,TOP,MAXSTK,ITEM)
This procedure pushes an ITEM onto stack.
[Stack already filled?]
if TOP=MAXSTK ,then Print : OVERFLOW , and Return
set TOP=TOP+1[Increases TOP by 1.]
Set STACK[TOP] =ITEM. [Inserts ITEM in new TOP position.]
Return.
Algorithm
POP(STACK,TOP,ITEM)
This procedure deletes the top element of the stack and assigns it to the variable ITEM
[Stack has an item to be removed?]
if TOP=0 , then print UNDERFLOW and Return.
Set ITEM = STACK[TOP].[ Assigns TOP element to ITEM]
Set TOP= TOP – 1 .[Decrease TOP by 1]
Return.
Queues
How do we use lists?
In many cases, we want to use a list, but we only want a limited subset of its operations
example: Use a list to store a waiting line of customers for a bookstore. As each customer arrives, place him/her at the end of the line. Serve customers in the order that they arrived.
Which list methods do we need here, and which do we not need?
Common idiom: "FIFO"
Many times, we will use a list in a way where we always add to the end, and always remove from the front (like the previous example)
The first element put into the list will be the first element we take out of the list
First-In, First-Out ("FIFO")
Let's create a new type of collection which is a limited version of List, tailored to this type of usage: a Queue
Queues
A queue is a linear list in which items may be added at one end and items may be removed only at the other end.
Deletions can take place only at one end , called the front , and insertions can take place only at the other end , called the rear.
Queues are also called first-in-first-out lists , since the first element in a queue will be the first element out of the queue. In other words , the order in which elements enter a queue is the order in which they leave.
Representation of Queues
Queues may be represented in various ways , usually by means of one-way lists or linear arrays.
Queues will be maintained by an array QUEUE and two pointer variables , FRONT, containing the location of the front element and REAR , containing the location of the rear element of the queue.
The condition FRONT=NULL indicates that the queue is empty.
offer or enqueue: add an element to the back
remove or dequeue: remove and return the element at the front
peek: return (but not remove) front element
peek on an empty queue returns null
Circular arrays
We can treat the array holding the queue elements as circular (joined at the ends)
Elements were added to this queue in the order 11, 22, 33, 44, 55, and will be removed in the same order
Use: front = (front + 1) % Queue.length; and: rear = (rear + 1) % Queue.length;
Full and empty queues
If the queue were to become completely full, it would look like this:
If we were then to remove all eight elements, making the queue completely empty, it would look like this:
Algorithm
QINSERT(QUEUE,N,FRONT,REAR,ITEM)
This procedure inserts an element ITEM into a queue.
[ Queue already filled?]
If FRONT=1 and REAR=N , or if FRONT=REAR+1, then:
Write : OVERFLOW AND Return.
[ Find new value of REAR]
if FRONT=NULL , then [Queue initially empty]
set FRONT=1 and REAR=1.
Else if REAR=N then :
set REAR=1.
Else
Set REAR=REAR+1
[ End of if structure.]
Set QUEUE[REAR]=ITEM. [This inserts new element]
return.
More Refer
http://studentbank.in/report-data-struct...2#pid61222
http://studentbank.in/report-data-struct...w-ques-ans
http://studentbank.in/report-file-organi...structures
