2nd BSc DATA STRUCTURES USING C chapter 1
CHAPTER 1 : INTRODUCTION TO DATA STRUCTURE
Definition: Data structure can be defined as the logical or mathematical model of a particular
organization of data. DS=ORGANIZED DATA + OPERATIONS.
It deals with
1. The study of how the data is organized in memory.
2. How efficiently the data can be stored in memory.
3. Hoe efficiently the data can be retrieved and manipulated.
Primitive data structures: These are the data structures that can be manipulated directly by machine
instructions.
Eg. int, float, double, char.
Non-Primitive data structures: These are the data structures that cannot be manipulated directly by
machine instructions. Eg. Arrays, Stacks, Queues, Linked list, Graphs.
Linear data structures: It is the one which establishes the relationship of adjacency between the
elements which means all the elements are stored in memory linearly or sequentially.
Eg. Arrays, linked list, stacks, queues.
Non-Linear data structures: Any data structures which establishes the relationship other than the
adjacency relationship is called non-linear data structures. Eg. Trees and Graphs.
Arrays: It is a finite ordered set of homogeneous elements, which are stored in adjacent cells in
memory.
The data are represented by a single name identified by a subscript.
Stacks: It is a linear data structures in which data is inserted and deleted at one end called as top of the
stack that is data is stored and retrieved in last in first out (LIFO)order.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
Queues: It is defined as an ordered collection of items from which, the items may be deleted at one
end called FRONT end and into which the items may be inserted at other end called REAR end.
It is also called as FIFO.
Linked list: A list is a linear sequence of data objects of the same type. The list may be singly linked list,
doubly linked list, circular linked list.
The linked list is a linear collection of data items called as nodes.
Node is divided into two parts: 1. Information field 2. Link/pointer field.
Trees: It is a finite set of vertices that has a vertex called as root and remaining vertices are collection
of sub-trees.
Graphs: It is a finite set of points, some of which are connected by lines or arrows(edges or arcs).
OPERATIONS ON DATA STRUCTURES
1. Inserting: Adding the new element to the existing data structures.
2. Deleting: Deleting the element from a data structures.
3. Traversing: Accessing each element exactly once.
4. Searching: Searches a particular element in the list of the element.
5. Sorting: Arranging the elements in ascending or descending order.
6. Merging: Combining the two different sorted list into single sorted list.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
MEMORY ALLOCATION
Memory allocation is the process of setting aside sections of memory in a program to be used to store
variables and instances of structures and classes.
Two types of memory allocation
1. Static/compile time allocation.
2. Dynamic/Run time allocation.
Static memory allocation: It is allocated by the compiler.
Exact size and type of memory must be known at compile time.
Eg. int x,y;
Float a[5];
Dynamic memory allocation: It is the process of assigning the memory space during the execution
time or the run time.
We have functions to allocate and de-allocate memory dynamically they are
Malloc(), calloc(), realloc(), free().
Malloc(): It allocates a block of memory in bytes. It allocates and leaves the memory uninitialized.
It is like a request to the RAM of the system to allocate memory.
Syntax: malloc(number of elements*size of each element);
Example: int *ptr;
ptr=malloc(100*sizeof(int));
The above statement allocates 200 bytes of memory and the pointer variable holds the address of the
first byte in the allocated memory.
Calloc(): This function allocates memory and initializes all the bits to zero.
It needs two arguments.
Syntax: calloc(n,sizeof each element);
Example: int *ptr;
Ptr=calloc(25,sizeof(int));
The above statement allocates contiguous space in memory for 25 elements of type int.
Realloc(): If the dynamically allocated memory is insufficient or more than required, you can change
the size of previously allocated memory using realloc() function.
Syntax: ptr_var=realloc(ptr_var,new_size);
Example: ptr=realloc(ptr,n2*sizeof(int));
Here n2 is a variable taken to enter new size. So here if n2=3 then 6 bytes is newly allocated to ptr
variable.
Free(): It is used to deallocate the previously allocated memory using malloc() or calloc() functions.
Syntax: free(ptr_var);
Example: free(ptr);
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
RECURSION
It is a process in which the function calls itself indirectly or directly in order to solve the problem.
Types of recursion
1. Direct recursion.
2. Indirect recursion.
Direct recursion: The function call itself repeatedly until certain condition is satisfied.
When in the body of a method there is a call to the same method, we say that the method is directly
recursive. That means direct recursion occurs when a method invokes itself.
Example:
fact(int n)
{
If(n==1)
return 1;
else
return(n*fact(n-1));
}
There are three types of direct recursion
1. Linear recursion.
2. Binary recursion.
3. Multiple recursion.
Linear recursion: It is a function that only makes a single call to itself each time the function runs.
Binary recursion: The function calls itself twice in each run. As a result, the calculation depends on two
results from two different recursive calls to itself.
Multiple recursion: In this we make not just one or two but many recursive calls.
Indirect recursion: The function calls another function which eventually causes the same function to be
called. So the function indirectly calls itself through the another function.
Example:
fun(int a)
{
------------
fun1(b);
}
fun1(int b)
{
-------
fun(b-1);
----------
}
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
Advantages of recursion
1. It reduces the complexity of the problem.
2. It allows the user to write much simpler and more elegant programs.
3. Program implemented by recursion will be smaller in length.
4. The recursion programs can have any number of nesting levels.
5. The recursion techniques is more natural and compact.
6. It is a top-down programming tool, where the given problem is divide into smaller modules,
each module are then individually attached.
Programs to find GCD, binomial coefficient and towers of Hanoi using recursion
Program to find GCD
int gcd(int m,int n)
{
If(n==0)
return(m);
else if(n>m)
return(gcd(n,m));
else
return(gcd(n,m%n));
}
main()
{
int m,n;
clrscr();
printf(“enter m and n”);
scanf(“%d%d)=%d”,m,n,gcd(m,n));
}
Program to find binomial coefficient
int main()
{
int n,r,ncr;
printf(‘enter N and R values”);
scanf(‘%d%d”,&n,&r);
ncr=fact(n)/(fact(r)*fact(n-r));
printf(“the NCR of %d and %d is %d”,n,r,ncr);
}
int fact(int x)
{
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
int i=1;
while(x!=0)
{
i=i*x;
x--;
}
return i;
}
Towers of Hanoi Problem
It is a game where a disk is to be moved from one source pillar to a destination pillar using a temporary
pillar. Consider Ssource, Ddestination, Ttemporary pillar nnumber of disks.
We have to follow conditions that are to be checked for each movement.
1. Only one disk can be moved at a time, from one pillar to another.
2. A larger disk cannot be placed on a smaller disk.
3. Only the top disk on any pillar may be moved to any other pillar.
It can be represented as 2n-1. If n=2, 22-1=3.
For n=3 movements are shown below and sequence can be written as, (consider A as S, B as T,C as D).
SD,ST,DT,SD,TS,TD,SD.
Program for tower of Hanoi
main()
{
Char source=’s’,temp=’t’,dest=’d’;
int n,count=0;
printf(“enter the number of disks”);
scanf(“%d”,&n);
printf(“sequence is”);
toh(n,source,temp,dest);
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
printf(“the number of moves=%d”,count);
}
toh(int n,char source,char temp,char dest)
{
if(n==1)
printf(“move disk from %c to %c”, source,dest);
count++;
toh(n-1,temp,source,dest);
}
}
Comparison between iteration and recursion functions:
ITERATION RECURSION
There is a repeated execution of the set of It is the process of calling a function itself within
instructions. its own code.
In this, loops are used to execute the set of It uses selection structures such as if, if-else or
instructions repetitively until the condition is switch statement.
false(for, while, do-while).
Iteration is terminated when the loop condition Recursion is terminated when base case is
fails. satisfied.
The code size is larger. The code size is smaller.
This occurs if condition never fails. Recursion is infinite if there is no base case or if
base case never reaches.
Iterative functions execute much faster and In recursion, every time the function is called, all
occupy less memory and can be designed easily. the local variables, formal parameters and return
address will be pushed onto to the stack. So it
occupies more stack and most of the time spent in
pushing and popping. Thus recursion is expensive
in terms of processor time and memory usage.
It is faster. It is slower.
There is no utilization of stack. It uses stack.
It uses less memory. It uses more memory.
There is no overhead in iteration. There is an extensive overhead due to updating
and maintaining the stack.
ALGORITHM SPECIFICATION
Algorithm: It is defined as a finite set of instructions that, if followed, performs a particular task.
All algorithm must satisfy the following criteria:
1. Input: An algorithm has zero or more inputs, taken or collected from a specified set of objects.
2. Output: An algorithm has one or more outputs having a specific relation to the inputs.
3. Definiteness: Each step and instruction must be clearly defined.
4. Finiteness: The algorithm must always finish or terminated after a finite number of steps.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
5. Effectiveness: All operations to be accomplished must be sufficiently basic that they can be
done exactly and in finite length.
Recursive algorithms: It calls itself which generally passes the return value as a parameter to the
algorithm again.
This parameter indicates the input while the return value indicates output.
Example: int fact(int n)
{
Return n*fact(n-1);
}
PERFORMANCE ANALYSIS
There are multiple algorithms to solve a problem. When we have multiple algorithms, we need to
select the best one. Performance analysis helps us to select the best algorithm.
Definition: Performance of an algorithm means predicting the resources which are required to an
algorithm to perform it’s task.
OR
Performance analysis of an algorithm is the process of calculating space and time required by that
algorithm.
Generally, the performance of an algorithm depends on the following elements:
1. Whether that algorithm is providing the exact solution for the problem?
2. Whether it is easy to understand?
3. Whether it is easy to implement?
4. How much space it requires to solve problem?
5. How much time it takes to solve the problem? Etc.,
When we want to analyze an algorithm, we consider only the space and time required by that
particular algorithm.
Space complexity: Space required to complete the task of that algorithm. It includes program space
and data space.
Time complexity: Time required to complete the task of that algorithm.
SPACE COMPLEXITY: Total amount of computer memory required by an algorithm to complete it’s
execution is called as space complexity of that algorithm.
For any algorithm, memory is required for the following purposes:
1. To store program instructions.
2. To store constant values.
3. To store variable values.
4. Other things like function calls, jumping statements etc.,
If any algorithm requires a fixed amount of space for all input values then that space complexity is said
to be “Constant Space Algorithm”.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
If the amount of space required by an algorithm is increased with the increase of input value, then that
space complexity is said to be “Linear Space Complexity”.
TIME COMPLEXITY: The time complexity of an algorithm is the total amount of time required by an
algorithm to complete it’s execution.
The running time of an algorithm depends upon the following:
1. Whether it is running on single processor machine or multi processor machine.
2. Whether it is 32 bit machine or 64 bit machine.
3. Read and write speed of the machine.
4. The amount of time required by an algorithm to perform arithmetic operations, logical
operations, return value and assignment operations etc.,
5. Input data.
Consider only input data to find time complexity and we assume a machine with single processor 32 bit
operating system and perform sequential execution.
1 unit time for assignment and return value.
1 unit time for read and write operations.
If any program requires a fixed amount of time for all input values then it’s time complexity is said to
be “Constant Time Complexity”.
If the amount of time required by an algorithm is increased with the increase of input value then that
time complexity is said to be “Linear Time Complexity”.
There are two methods to calculate time complexity of an algorithm:
1. Asymptotic Notation.
2. Frequency/step count.
Asymptotic Notation
“Asymptotic Notation of an algorithm is a mathematical representation of it’s complexity”.
When we do performance analysis of an algorithm it does not provide the exact amount of resource
required. So instead of taking the exact amount of resource, we represent that complexity in a general
form which produces the basic nature of that algorithm which we use for analysis process.
Three types of Asymptotic Notation:
1. Big-oh(O).
2. Big-omega(Ω).
3. Big-theta(Ɵ).
By using Asymptotic Notations we can calculate below time complexity:
1. Best case: If an algorithm requires minimum time for it’s execution.
2. Worst case: If an algorithm requires maximum time for it’s execution.
3. Average case: If an algorithm requires average time for it’s execution.
Big-oh(O)
It represent upper bound of algorithm’s running time.
We can calculate maximum amount of time that an algorithm requires for it’s execution.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
It is useful for calculating worst case of time complexity.
Definition:
Let f(n),g(n) be two non-negative(+ve) functions.
Then f(n)=O(g(n)) if there exists two +ve constants c,n0 such that f(n)≤c*g(n), n>n0.
Graphical representation
Big-omega(Ω)
It represent lower bound of algorithm’s run time.
We can calculate minimum amount of time that an algorithm required for it’s execution.
It is useful for calculating best case of time complexity.
Definition:
Let f(n),g(n) be two non-negative(+ve) functions.
Then f(n)=Ω(g(n)) if there exists two +ve constants c,n0 such that f(n)≥c*g(n), n>n0.
Graphical representation
Big-theta(Ɵ)
It represent average bound of algorithm’s run time.
We can calculate average amount of time that an algorithm required for it’s execution.
It is useful for calculating average case of time complexity.
Definition:
Let f(n),g(n) be two non-negative(+ve) functions.
Then f(n)=Ɵ(g(n)) if there exists two +ve constants c,n0 such that c1*g(n)≤ f(n)≤c2*g(n), n>n0.
Compiled by: Kavyashree G J Dept. of CS KFGSC
2nd BSc DATA STRUCTURES USING C chapter 1
Graphical representation
Frequency count/step count method to calculate time complexity
It specifies number of times a statement is to be executed.
RULES:
1. For comments and declarations step count=0. Because comments are not executable
statements and declarations is not needed in algorithm.
2. Return and assignment statements step count=1. Because return is used to return the value
and assignment statement is used to assign a value to a variable.
3. Ignore lower order exponents when higher order exponents are present.
4. Ignore constant multiplier.
Compiled by: Kavyashree G J Dept. of CS KFGSC
