Data Structure using C by Dr. K Adisesha .ppsx

Data Structure using C ppt by Dr. K. Adisesha

1. Data Structures using C
Prof. Dr. K ADISESHA

2. Please bring to class
each day
Introduction
Types of Data structures
Arrays
Stacks and Queues
Linked lists
2
Data Structures
Trees

3. Introduction
Prof. Dr. K. Adisesha
3
Data Structures:
Data
Dataisacollectionoffacts,numbers,lettersorsymbolsthatthecomputerprocessinto
meaningfulinformation.
Datastructure
Datastructureisrepresentationofthelogicalrelationshipexistingbetweenindividual
elementsofdata.
Datastructureisaspecializedformatfororganizingandstoringdatainmemorythat
considersnotonlytheelementsstoredbutalsotheirrelationshiptoeachother.

4. Introduction
Prof. Dr. K. Adisesha
4
Why to Learn Data Structure:
Asapplicationsaregettingcomplexanddatarich,therearethreecommonproblems
thatapplicationsfacenow-a-days
DataSearch−Consideraninventoryof1million(106)itemsofastore.Ifthe
applicationistosearchanitem,ithastosearchanitemin1million(106)itemsevery
timeslowingdownthesearch.Asdatagrows,searchwillbecomeslower.
Processorspeed−Processorspeedalthoughbeingveryhigh,fallslimitedifthedata
growstobillionrecords.
Multiplerequests−Asthousandsofuserscansearchdatasimultaneouslyonaweb
server,eventhefastserverfailswhilesearchingthedata..

5. Introduction
Prof. Dr. K. Adisesha
5
Data Structures:
Datastructuresareessentialcomponentsthathelporganizeandstoredataefficiently
incomputermemory.
Theyprovideawaytomanageandmanipulatedataeffectively,enablingfasteraccess,
insertion,anddeletionoperations.

6. Introduction
Prof. Dr. K. Adisesha
6
Data Type:
Datatypeisawaytoclassifyvarioustypesofdatawhichdeterminesthevaluesthatcan
beusedwiththecorrespondingtypeofdata,thetypeofoperationsthatcanbe
performedonthecorrespondingtypeofdata.
Therearetwodatatypes:
Built-inDataType:Thosedatatypesforwhichalanguagehasbuilt-insupportare
knownasBuilt-inDatatype.
DerivedDataType:Thosedatatypeswhichareimplementationindependentasthey
canbeimplementedinoneortheotherwayareknownasderiveddatatypes.

7. Data Structures
Prof. Dr. K. Adisesha
7
Classification of Data Structure using C:
Datastructurearenormallydividedintotwobroadcategories:
PrimitiveDataStructure
Non-PrimitiveDataStructure
LinearDataStructure
Non-LinearDataStructure

8. Data Structures
Prof. K. Adisesha
8
Differences between Data Structure:
Themostcommonlyuseddifferencesbetweenondatastructurearebroadlycategorized
intofollowingtypes:
Aprimitivedatastructureisgenerallyabasicstructurethatisusuallybuiltintothe
language,suchasaninteger,afloat.
Anon-primitivedatastructureisbuiltoutofprimitivedatastructureslinkedtogether
inmeaningfulways,suchasaoralinked-list,binarysearchtree,AVLTree,graphetc.

9. Data Structures
Prof. Dr. K. Adisesha
9
Primitive Data Structure:
Datastructuresthataredirectlyoperateduponthemachine-levelinstructionsare
knownasprimitivedatastructures:
Therearebasicstructuresanddirectlyoperateduponbythemachineinstructions.
TheDatastructuresthatfallinthiscategoryare.
Integer
Floating-pointnumber
Characterconstants
stringconstants
pointersetc.,

10. Data Structures
Prof. Dr. K. Adisesha
10
Primitive Data Structure:
Datastructuresthataredirectlyoperateduponthemachine-levelinstructionsare
knownasprimitivedatastructures:
Themostcommonlyusedoperationondatastructurearebroadlycategorizedinto
followingtypes:
Create
Insertion
Selection
Updating
DestroyorDelete

11. Data Structures
Prof. Dr. K. Adisesha
11
Non-Primitive Data Structure:
TheDatastructuresthatarederivedfromtheprimitivedatastructuresarecalledNon-
primitivedatastructure:
Therearemoresophisticateddatastructures
Thenon-primitivedatastructuresemphasizeonstructuringofagroupofhomogeneous
(sametype)orheterogeneous(differenttype)dataitems:
LinearDatastructures
Non-LinearDatastructures

12. Data Structures
Prof. Dr. K. Adisesha
12
Non-Primitive Data Structure:
LinearDatastructures
LinearDatastructuresarekindofdatastructurethathashomogeneouselements.
Thedatastructureinwhichelementsareinasequenceandformalinerseries.
Lineardatastructuresareveryeasytoimplement,sincethememoryofthecomputeris
alsoorganizedinalinearfashion.
Somecommonlyusedlineardatastructuresare:
Stack
Queue
LinkedLists

13. Data Structures
Prof. Dr. K. Adisesha
13
Non-Primitive Data Structure:
Non-LinearDatastructures
ANon-LinearDatastructuresisadatastructureinwhichdataitemisconnectedto
severalotherdataitems.
Non-Lineardatastructuremayexhibiteitherahierarchicalrelationshiporparentchild
relationship.
Thedataelementsarenotarrangedinasequentialstructure.
Somecommonlyusednon-lineardatastructuresare:
Trees
Graphs

14. Data Structures
Prof. Dr. K. Adisesha
14
Non-Primitive Data Structure:
Themostcommonlyusedoperationondatastructurearebroadlycategorizedinto
followingtypes:
Traversal
Insertion
Selection
Searching
Sorting
Merging
DestroyorDelete

15. Memory Allocation
Prof. Dr. K. Adisesha
15
Memory Allocation in C:
Memoryallocationisaprocessbywhichcomputerprogramsandservicesareassigned
withphysicalorvirtualmemoryspace.
TheMemoryisdividedintothreesections.
HeapMemory:Itisapartofthemainmemory.Itisunorganizedand
treatedasaresourcewhenyourequiretheuseofitifnotrelease.
StackMemory:Itstorestemporaryvariablescreatedbyafunction.In
stack,variablesaredeclared,stored,andinitializedduringruntime.
CodeSection:Whenevertheprogramisexecuteditwillbebrought
intothemainmemory.Thisprogramwillgetstoredunderthecode
section.

16. Memory Allocation
Prof. Dr. K. Adisesha
16
Memory Allocation in C:
Memoryallocationisaprocessbywhichcomputerprogramsandservicesareassigned
withphysicalorvirtualmemoryspace.
Thememoryallocationisdoneeitherbeforeoratthetimeofprogramexecution.
Therearetwotypesofmemoryallocations:
Compile-timeorStaticMemoryAllocation:Memoryisallocatedfordeclared
variablesbythecompiler.
Run-timeorDynamicMemoryAllocation:Memoryallocationdoneatthetimeof
execution(runtime)isknownasdynamicmemoryallocation.

17. Memory Allocation
Prof. Dr. K. Adisesha
17
Static Memory Allocation in C:
Instaticmemoryallocationtheprogramexecutesfixesthesizethattheprogramis
goingtotake,anditcan’tbechangedfurther.So,theexactmemoryrequirementsmust
beknownbefore.
Allocationanddeallocationofmemorywillbedonebythecompilerautomatically.
KeyFeatures:
Allocationanddeallocationaredonebythecompiler.
Itusesadatastructuresstackforstaticmemoryallocation.
Variablesgetallocatedpermanently.
Executionisfasterthandynamicmemoryallocation.
Memoryisallocatedbeforeruntime.

18. Memory Allocation
Prof. Dr. K. Adisesha
18
Dynamic Memory Allocation in C:
InDynamicmemoryallocationsizeinitializationandallocationaredonebythe
programmer.Itismanagedandservedwithpointersthatpointtothenewlyallocated
memoryspaceinanareawhichwecalltheheap.
Heapmemoryisunorganizedanditistreatedasaresourcewhenyourequiretheuseof
itifnotreleaseit.
KeyFeatures:
Dynamicallocatedatruntime
Wecanalsoreallocatememorysizeifneeded.
DynamicAllocationisdoneatruntime.
Nomemorywastage

19. Memory Allocation
Prof. Dr. K. Adisesha
19
Dynamic Memory Allocation in C:
Therearesomefunctionsavailableinthestdlib.hheaderwhichwillhelptoallocate
memorydynamically.
malloc():functionallocatesmemoryatruntimeiscalledmalloc()functionreturnsa
pointerwiththevalueNULL.Syntax:int*p=(int*)malloc(Noofvalues*size(int));
calloc():functioninitializesthememorythatisallocatedsothatallbytesarezero.
Syntax:int*p=(int*)calloc(Numberofdataitems,sizeof(int));
realloc():Therealloc()functionenablesyoutoreuseorextendthememorythatyou
previouslyallocatedusingmalloc()orcalloc().
Syntax:int*np=(typecast)realloc(pointertype,numberofelements*sizeof(int));
free():Whenmemoryisallocateddynamicallyitshouldalwaysbereleasedwhenitis
nolongerrequired.Syntax:free(pointer);

20. Data Structures
Prof. Dr. K. Adisesha
20
Algorithms and Applications of Data Structures:
Algorithmisastep-by-stepprocedure,whichdefinesasetofinstructionstobeexecuted
inacertainordertogetthedesiredoutput.Algorithmsaregenerallycreated
independentofunderlyinglanguages.
Fromthedatastructurepointofview,followingaresomeimportantcategoriesof
algorithms.
Insert−Algorithmtoinsertiteminadatastructure.
Traverse−Algorithmtovisiteveryiteminadatastructure.
Update−Algorithmtoupdateanexistingiteminadatastructure.
Search−Algorithmtosearchaniteminadatastructure.
Sort−Algorithmtosortitemsinacertainorder.
Delete−Algorithmtodeleteanexistingitemfromadatastructure.

21. Algorithm
Prof. Dr. K. Adisesha
21
Characteristics of an Algorithm:
Analgorithmshouldhavethefollowingcharacteristics−.
Unambiguous−Algorithmshouldbeclearandunambiguous.Eachofitssteps(or
phases),andtheirinputs/outputsshouldbeclearandmustleadtoonlyonemeaning.
Input−Analgorithmshouldhave0ormorewell-definedinputs.
Output−Analgorithmshouldhave1ormorewell-definedoutputs,andshouldmatch
thedesiredoutput.
Finiteness−Algorithmsmustterminateafterafinitenumberofsteps.
Feasibility−Shouldbefeasiblewiththeavailableresources.
Independent−Analgorithmshouldhavestep-by-stepdirections,whichshouldbe
independentofanyprogrammingcode.

22. Algorithm
Prof. Dr. K. Adisesha
22
Characteristics of a Data Structure:
DataStructureisasystematicwaytoorganizedatainordertouseitefficiently.
FollowingtermsaretheCharacteristicsofadatastructure.
Correctness−Datastructureimplementationshouldimplementitsinterfacecorrectly.
TimeComplexity−Runningtimeortheexecutiontimeofoperationsofdatastructure
mustbeassmallaspossible.
SpaceComplexity−Memoryusageofadatastructureoperationshouldbeaslittleas
possible.

23. Algorithm
Prof. Dr. K. Adisesha
23
Algorithm Analysis:
Efficiencyofanalgorithmcanbeanalyzedattwodifferentstages,beforeimplementation
andafterimplementation.Theyarethefollowing.
APrioriAnalysis−Thisisatheoreticalanalysisofanalgorithm.Efficiencyofan
algorithmismeasuredbyassumingfactors,likeprocessorspeed,areconstantandhave
noeffectontheimplementation.
APosteriorAnalysis−Thisisanempiricalanalysisofanalgorithm.Theselected
algorithmisimplementedusingprogramminglanguage.Inthisanalysis,actualstatistics
likerunningtimeandspacerequired,arecollected.

24. Algorithm
Prof. Dr. K. Adisesha
24
Algorithm Complexity:
Thecomplexityofanalgorithmrepresentstheamountofmemoryspaceandtime
requiredbythealgorithminitslifecycle.
Spacecomplexity−Spacecomplexityofanalgorithmrepresentstheamountofmemory
spacerequiredbythealgorithminitslifecycle..
Timecomplexity−Timecomplexityofanalgorithmrepresentstheamountoftime
requiredbythealgorithmtoruntocompletion.

25. Algorithm
Calculate
Lines 1 and 4 count for one unit each
Line 3: executed N times, each time four units
Line 2: (1 for initialization, N+1 for all the tests, N for all the increments) total 2N + 2
total cost: 6N + 4 O(N)

N
i
i
1
3
1
2
3
4
1
2N+2
4N
1

26. Algorithm
Prof. Dr. K. Adisesha
26
Asymptotic Analysis of an algorithm:
AsymptoticanalysisofanalgorithmreferstoAsymptoticanalysisreferstocomputingthe
runningtimeofanyoperationinmathematicalunitsofcomputationofitsrun-time
performance.
TheAsymptoticanalysisofanalgorithmfallsunderthreetypes:
BestCase−Minimumtimerequiredforprogramexecution.
AverageCase−Averagetimerequiredforprogramexecution.
WorstCase−Maximumtimerequiredforprogramexecution.

27. Algorithm
Prof. Dr. K. Adisesha
27
Asymptotic Notations of an algorithm:
Followingarethecommonlyusedasymptoticnotationstocalculatetherunningtime
complexityofanalgorithm..
TheAsymptoticNotationsofanalgorithmfallsunderthreetypes:
BigOhNotation,Ο−Itmeasurestheworstcasetimecomplexity.
OmegaNotation,Ω−Itmeasuresthebestcasetimecomplexity.
ThetaNotation,θ−ItmeasurestheAveragecasetimecomplexity.

28. Algorithm
Prof. Dr. K. Adisesha
28
Big Oh Notation, ( Ο)of an algorithm:
ThenotationΟ(n)istheformalwaytoexpresstheupperboundofanalgorithm's
runningtime.
Itmeasurestheworstcasetimecomplexityorthelongestamountoftimeanalgorithm
canpossiblytaketocomplete.
Forexample,forafunctionf(n)
Itisrepresentedasfollows
Ο(f(n))={g(n):thereexistsc>0andn0suchthatf(n)≤c.g(n)foralln>n0.}

29. Algorithm
Prof. Dr. K. Adisesha
29
Omega Notation, Ωof an algorithm:
ThenotationΩ(n)istheformalwaytoexpressthelowerboundofanalgorithm's
runningtime.Itmeasuresthebestcasetimecomplexityorthebestamountoftimean
algorithmcanpossiblytaketocomplete
•Forexample,forafunctionf(n)
•Itisrepresentedasfollows
•Ω(f(n))≥{g(n):thereexistsc>0andn0suchthatg(n)≤c.f(n)foralln>n0.}

30. Algorithm
Prof. Dr. K. Adisesha
30
Theta Notation, θof an algorithm:
Thenotationθ(n)istheformalwaytoexpressboththelowerboundandtheupper
boundofanalgorithm'srunningtime.
Forexample,forafunctionf(n)
Itisrepresentedasfollows
θ(f(n))={g(n)ifandonlyifg(n)=Ο(f(n))andg(n)=Ω(f(n))foralln>n0.}

31. Algorithm
Prof. Dr. K. Adisesha
31
Common Asymptotic Notations:
Followingisalistofsomecommonasymptoticnotations.
constant−Ο(1)
logarithmic−Ο(logn)
linear−Ο(n)
nlogn−Ο(nlogn)
quadratic−Ο(n2)
cubic−Ο(n3)
polynomial−nΟ(1)
exponential−2Ο(n)

32. Recursion
Prof. Dr. K. Adisesha
32
Recursion:
Recursionistheprocessofrepeatingitemsinaself-similarway.Inprogramming
languages,ifaprogramallowsyoutocallafunctioninsidethesamefunction,thenit
iscalledarecursivecallofthefunction.
whileusingrecursion,programmersneedtobecarefultodefineanexitconditionfrom
thefunction,otherwiseitwillgointoaninfiniteloop.
Recursivefunctionsareveryusefultosolvemany
mathematicalproblems,suchascalculatingthe
factorialofanumber,generatingFibonacciseries,
etc.

33. Recursion
Prof. Dr. K. Adisesha
33
Recursion:
Recursionistheprocessinwhichafunctioncallsitselfupton-numberoftimes.Ifa
programallowstheusertocallafunctioninsidethesamefunctionrecursively,the
procedureiscalledarecursivecallofthefunction.
TypesofRecursioninC:
DirectRecursion
IndirectRecursion
TailRecursion
NoTail/HeadRecursion
Linearrecursion
TreeRecursion

34. Recursion
Prof. Dr. K. Adisesha
34
Types of the recursion:
FollowingarethetypesoftherecursioninCprogramminglanguage,asfollows:
DirectRecursion:Whenafunctioncallsitselfwithinthesamefunctionrepeatedly,it
iscalledthedirectrecursion.
IndirectRecursion:Whenafunctionismutuallycalledbyanotherfunctionina
circularmanner,thefunctioniscalledanindirectrecursionfunction.
Direct Recursion:
fun()
{
// write some code
fun();
// some code
}
Indirect Recursion:
fun1()
{
// write some code
fun2();
}
fun2()
{
// write some code
fun1();
// write some code
}

35. Recursion
Prof. Dr. K. Adisesha
35
Types of the recursion:
FollowingarethetypesoftherecursioninCprogramminglanguage,asfollows:
TailRecursion:Arecursivefunctioniscalledthetail-recursiveifthefunctionmakes
recursivecallingitself,andthatrecursivecallisthelaststatementexecutesbythe
function.Afterthat,thereisnofunctionorstatementislefttocalltherecursivefunction.
HeadRecursion:Afunctioniscalledthenon-tailorheadrecursiveifafunctionmakesa
recursivecallitself,therecursivecallwillbethefirststatementinthefunction.
Linearrecursion:Afunctioniscalledthelinearrecursiveifthefunctionmakesasingle
calltoitselfateachtimethefunctionrunsandgrowslinearlyinproportiontothesizeof
theproblem.
TreeRecursion:Afunctioniscalledthetreerecursion,inwhichthefunctionmakesmore
thanonecalltoitselfwithintherecursivefunction.

36. Recursion
Prof. Dr. K. Adisesha
36
Recursion:
TheCprogramminglanguagesupportsrecursion,i.e.,afunctiontocallitself.
Thefollowingexamplecalculatesthefactorialofagivennumberusingarecursive
function−
#include<stdio.h>
intfactorial(inti){
if(i<=1){
return1;
}
returni*factorial(i-1);
}
intmain(){
inti=12;
printf("Factorialof%dis%d\n",i,
factorial(i));
return0;
}

37. Recursion
Prof. Dr. K. Adisesha
37
Drawbacks of Recursion in Data Structure:
Therearesomepotentialdrawbackstousingrecursionindatastructures,including:
Memoryusage:Recursivealgorithmscanusealotofmemory,particularlyiftherecursion
goestoodeeporifthedatastructureislarge.Eachrecursivecallcreatesanewstackframeon
thecallstack,whichcanquicklyadduptoasignificantamountofmemoryusage.
Stackoverflow:Iftherecursiongoestoodeep,itcancauseastackoverflowerror,whichcan
crashtheprogram.
Performance:Recursivealgorithmscanbelessefficientthaniterativealgorithmsinsome
cases,particularlyifthedatastructureislargeoriftherecursiongoestoodeep.
Debugging:Recursivealgorithmscanbemoredifficulttodebugthaniterativealgorithms,
particularlyiftherecursiongoestoodeeporiftheprogramisusingmultiplerecursivecalls.
Codecomplexity:Recursivealgorithmscanbemorecomplexthaniterativealgorithm.

38. Recursion
Prof. Dr. K. Adisesha
38
Difference between Recursion and Iteration:
Basis Recursion Iteration
Basis of
repetition
Recursion is based on the idea of a function
calling itself. The base case is the simplest
version of the problem that can be solved
without recursion.
Iteration, on the other hand, uses looping
constructs such as "for" and "while" to repeat
a process a certain number of times or until a
specific condition is met.
Control flow
Recursion relies on the call stack to keep track
of function calls and their parameters. Each
recursive call pushes a new function call onto
the call stack, and each return pops the function
call off the stack.
Iteration, on the other hand, does not rely on
the call stack and uses variables and control
structures to control the flow of execution.
Performance
Recursion can be more elegant and easier to
understand for certain types of problems
Iteration is often more efficient than recursion,
especially for large datasets or complex
algorithms.

39. Unit -2 Arrays
Prof. Dr. K. Adisesha
39
Arrays:
Anarrayisdefinedasasetoffinitenumberofhomogeneouselementsorsamedata
items:
FollowingaretheimportanttermstounderstandtheconceptofArray.
Element−Eachitemstoredinanarrayiscalledanelement.
Index−Eachlocationofanelementinanarrayhasanumericalindex,whichis
usedtoidentifytheelement.
Declarationofarrayisasfollows:
Syntax:DatatypeArray_Name[Size];
Example:intarr[10];
Whereintspecifiesthedatatypeortypeofelementsarraysstores.
“arr”isthenameofarray&thenumberspecifiedinsidethesquarebracketsisthenumberof
elementsanarraycanstore,thisisalsocalledsizedorlengthofarray.

40. Arrays
Prof. Dr. K. Adisesha
40
Arrays:
RepresentaLinearArrayinmemory:
Theelementsoflineararrayarestoredinconsecutivememorylocations.
Itisshownbelow:
intA[5]={23,4,6,15,5,7}

41. Arrays
Prof. Dr. K. Adisesha
41
Calculating the length of the array:
Theelementsofarraywillalwaysbestoredintheconsecutive(continues)memory
location.
Thenumberofelementsthatcanbestoredinanarray,thatisthesizeofarrayoritslengthis
givenbythefollowingequation:
oA[n]isthearraysizeorlengthofnelements.
oThelengthofthearraycanbecalculatedby:
L=UB–LB+1
oToCalculatetheaddressofanyelementinarray:
Loc(A[P])=Base(A)+W(P-LB)
oHere,UBisthelargestIndexandLBisthesmallestindex
Example:IfanarrayAhasvalues10,20,30,40,50,storedinlocation0,1,2,3,4theUB=4
andLB=0 SizeofthearrayL=4–0+1=5

42. Arrays
Prof. Dr. K. Adisesha
42
Types of Arrays:
Theelementsofarraywillalwaysbestoredintheconsecutive(continues)memory
location.ThevarioustypesofArraysare:
SingleDimensionArray:
Arraywithonesubscript
Ex:intA[i];
TwoDimensionArray
Arraywithtwosubscripts(RowsandColumn)
Ex:intA[i][j];
MultiDimensionArray:
ArraywithMultiplesubscripts
Ex:intA[i][j]..[n];

43. Arrays
Prof. Dr. K. Adisesha
43
Abstract Data Type:
ADTsorabstractdatatypesarethewaysofclassifyingdatastructuresbyprovidinga
minimalexpectedinterfaceandsomesetofmethods.
AbstractDatatype(ADT)isatype(orclass)forobjectswhosebehaviorisdefinedbya
setofvaluesandasetofoperations.
Abstractdatatypes(ADTs)areawayofencapsulatingdataandoperationsonthatdata
intoasingleunit.
ArrayasADT(AbstractDataType)meandatastructurearrayandthesetofoperations:
RepresentationofData.
SetofOperationsontheData.

44. Arrays
Prof. Dr. K. Adisesha
44
Basic operations of Arrays:
Somecommonoperationperformedonarrayare:
Traversing
Insertion
Deletion
Searching
Sorting
Merging

45. Arrays
Prof. Dr. K. Adisesha
45
Traversing Arrays:
Traversing:Itisusedtoaccesseachdataitemexactlyoncesothatitcanbeprocessed:
WehavelineararrayAasbelow:
12345
1020304050
Here we will start from beginning and will go till last element and during this process
we will access value of each element exactly once as below:
A [0] = 10
A [1] = 20
A [2] = 30
A [3] = 40
A [4] = 50

46. Arrays
Prof. Dr. K. Adisesha
46
TraverseOperation:
Followingprogramtraversesandprintstheelementsofanarray:

47. Arrays
Prof. Dr. K. Adisesha
47
Insertion into Array:
Insertion:Itisusedtoaddanewdataiteminthegivencollectionofdataitems:
WehavelineararrayAasbelow:
12345
1020503015
New element to be inserted is 100 and location for insertion is 3.
So shift the elements from 5th location to 3rd location downwards by 1 place.
And then insert 100 at 3rd location

48. Arrays
Prof. Dr. K. Adisesha
48
Insertion into Array:
InsertionintoArray:
Insertion100intoArray
atPos=3
A [0] = 10
A [1] = 20
A [2] = 50
A [3] = 30
A [4] = 15

49. Arrays
Prof. Dr. K. Adisesha
49
Insertion into Array: Add a new data item in the given array of data:
InsertionintoArray:
A [0] = 1
A [1] = 3
A [2] = 5
A [3] = 7
A [4] = 8

50. Arrays
Prof. Dr. K. Adisesha
50
Deletion from Array:
Deletion:Itisusedtodeleteanexistingdataitemfromthegivencollectionofdata
items:
Deletion30fromArray
atPos3
A [0] = 10
A [1] = 20
A [2] = 30
A [3] = 40
A [4] = 50

51. Arrays
Prof. Dr. K. Adisesha
51
Deletion from Array:
A [0] = 1
A [1] = 3
A [2] = 5
A [3] = 7
A [4] = 8

52. Arrays Searching
Prof. Dr. K. Adisesha
52
Searching in Arrays:
Searching:Itisusedtofindoutthelocationofthedataitemifitexistsinthegiven
collectionofdataitems:
E.g.WehavelineararrayAasbelow:
12345
1020503035
Suppose item to be searched is 35. We will start from beginning and will compare 35
with each element.
This process will continue until element is found or array is finished.
Types of searching Algorithms:
Linear searching
Binary Searching

53. Arrays Searching
Prof. Dr. K. Adisesha
53
Linear search:
Linear Searching:Also called Sequential Searching.
It is used to find out the location of the data item if it exists in the given collection of
data items.
Example Searching element 33 from the array of elements:

54. Arrays Searching
Prof. Dr. K. Adisesha
54
Linear search:
Linear Searching:Also called Sequential Searching.

55. Arrays Searching
Prof. Dr. K. Adisesha
55
Binary Searching:
The binary search algorithm can be used with
only sorted list of elements.
Binary Search first divides a large array into
two smaller sub-arrays and then recursively
operate the sub-arrays.
Binary Search basically reduces the search
space to half at each step

56. Arrays Searching
Prof. Dr. K. Adisesha
56
Binary Searching:
The binary search algorithm can be used with only sorted list of elements.
Example: Searching the element 57 from the array of elements

57. Arrays Searching
Prof. Dr. K. Adisesha
57
Binary Searching:
Example:

58. Arrays Searching
Prof. Dr. K. Adisesha
58
Binary Searching:

59. Arrays Searching
Prof. Dr. K. Adisesha
59
Difference in Searching:

60. Arrays Searching
Prof. Dr. K. Adisesha
60
Difference in Searching:

61. Arrays Sorting
Prof. Dr. K. Adisesha
61
Sorting in Arrays:
ASortingAlgorithmisusedtorearrangeagivenarrayorlistelementsaccordingtoa
comparisonoperatorontheelements:
Thecomparisonoperatorisusedtodecidetheneworderofelementintherespective
datastructure.
TypesofSortingAlgorithmsare:
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Heap Sort
Radix Sort
Bucket Sort
Shell Sort

62. Arrays Sorting
Prof. Dr. K. Adisesha
62
Bubble Sort in Arrays:
BubbleSortisthesimplestsortingalgorithmthatworksbyrepeatedlyswappingthe
adjacentelementsiftheyareinwrongorder.

63. Arrays Sorting
Prof. Dr. K. Adisesha
63
Bubble Sort in Arrays:
BubbleSortisthesimplestsortingalgorithmthatworksbyrepeatedlyswappingthe
adjacentelementsiftheyareinwrongorder.
Algorithm
begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

64. Arrays Sorting
Prof. Dr. K. Adisesha
64
Insertion Sorting:
Insertionsortisasimplesortingalgorithmthatbuildsthefinalsortedarray(orlist)
oneitematatime.
Thisisanin-placecomparison-basedsortingalgorithm.Here,asub-listismaintained
whichisalwayssorted.

65. Arrays Sorting
Prof. Dr. K. Adisesha
65
Insertion Sorting:
Thisisanin-placecomparison-basedsortingalgorithm.Here,asub-listismaintained
whichisalwayssorted.
Thisisanin-placecomparison-basedsortingalgorithm.Here,asub-listismaintained
whichisalwayssorted.

66. Arrays Sorting
Prof. Dr. K. Adisesha
66
Insertion Sorting:ALGORITHM: Insertion Sort (A, N) A is an array with N unsorted elements.
Step 1: for I=1 to N-1
Step 2: J = I
While(J >= 1)
if ( A[J] < A[J-1] ) then
Temp = A[J];
A[J] = A[J-1];
A[J-1] = Temp;
[End if]
J = J-1
[End of While loop]
[End of For loop]
Step 3: Exit

67. Arrays Sorting
Prof. Dr. K. Adisesha
67
Selection Sort:
Selectionsortisasimpleandefficientsortingalgorithmthatworksbyrepeatedly
selectingthesmallest(orlargest)elementfromtheunsortedportionofthelistand
movingittothesortedportionofthelist.
To implement the Selection Sort algorithm, we need:
An array with values to sort.
An inner loop that goes through the array, finds the lowest value, and moves it to the front
of the array. This loop must loop through one less value each time it runs.
An outer loop that controls how many times the inner loop must run. For an array with n
values, this outer loop must run n−1 times.

68. Arrays Sorting
Prof. Dr. K. Adisesha
68
Selection Sort:

69. Arrays Sorting
Prof. Dr. K. Adisesha
69
Selection Sort:

70. Arrays Sorting
Prof. Dr. K. Adisesha
70
Merge Sort Algorithm:
Mergesortisasortingtechniquebasedondivideandconquertechnique.Mergesort
firstdividesthearrayintoequalhalvesandthencombinestheminasortedmanner.
Here’s a step-by-step explanation of how merge sort works:
Divide:Divide the list or array recursively into two halves
until it can no more be divided.
Conquer:Each subarray is sorted individually using the merge
sort algorithm.
Merge: The sorted subarrays are merged back together in
sorted order. The process continues until all elements from both
subarrays have been merged.

71. Arrays Sorting
Prof. Dr. K. Adisesha
71
Merging from Array:
Merging:It is used to combine the data items of two sorted files into single file in the
sorted form.
We have sorted linear array A as below:
123456
1040508095100
And sorted linear array B as below:
1234
20354590
After merging merged array C is as below:
12 3 4 5 6 7 8 9 10
1020 3540 4550 8090 95 100

72. Arrays Sorting
Prof. Dr. K. Adisesha
72
Quicksort:
Quicksortisoneofthefastestsortingalgorithms.Thisalgorithmtakesanarrayof
values,choosesoneofthevaluesasthe'pivot'element,andmovestheothervaluesso
thatlowervaluesareontheleftandhighervaluesareontherightofpivotelement.
Thealgorithmcanbedescribedlikethis:
Chooseavalueinthearraytobethepivotelement.
Ordertherestofthearraysothatlowervaluesthanthepivotelementareontheleft,and
highervaluesareontheright.
Swapthepivotelementwiththefirstelementofthehighervaluessothatthepivotelement
landsinbetweenthelowerandhighervalues.
Dothesameoperations(recursively)forthesub-arraysontheleftandrightsideofthepivot
element.

73. Arrays Sorting
73
Quicksort Algorithms :
Prof. Dr. K. Adisesha

74. Arrays Sorting
74
Quicksort Algorithms :
Prof. Dr. K. Adisesha

75. Arrays Sorting
75
Complexity of Sorting Algorithms :
Prof. Dr. K. Adisesha

76. Arrays
Prof. Dr. K. Adisesha
76
Two dimensional array:
A two dimensional array is a collection of elements and each element is identified by a
pair of subscripts. ( A[3] [3] ).
The elements are stored in continuous memory locations.
The elements of two-dimensional array as rows and columns.
The number of rows and columns in a matrix is called as the order of the matrix and
denoted as MxN.
The number of elements can be obtained by multiplying number of rows and number of
columns. A[0]A[1]A[2]
A[0] 10 20 30
A[1] 40 50 60
A[2] 70 80 90

77. Arrays
Prof. Dr. K. Adisesha
77
Representation of Two Dimensional Array:
A two dimensional array is a collection of elements and each element is identified by a
pair of subscripts. ( A[m] [n] )
A is the array of order m x n. To store m*n number of elements, we need m*n memory
locations.
The elements should be in contiguous memory locations.
There are two methods:
Row-major method
Column-major method
A[0]A[1]A[2]
A[0] 10 20 30
A[1] 40 50 60
A[2] 70 80 90

78. Arrays
Prof. Dr. K. Adisesha
78
Representation of Two Dimensional Array:
Row-Major Method:
All the first-row elements are stored in sequential
memory locations and then all the second-row
elements are stored and so on. Ex: A[Row][Col]
Column-Major Method:
All the first column elements are stored in sequential
memory locations and then all the second-column
elements are stored and so on. Ex: A [Col][Row]
1000 10 A[0][0]
1002 20 A[0][1]
1004 30 A[0][2]
1006 40 A[1][0]
1008 50 A[1][1]
1010 60 A[1][2]
1012 70 A[2][0]
1014 80 A[2][1]
1016 90 A[2][2]
1000 10 A[0][0]
1002 40 A[1][0]
1004 70 A[2][0]
1006 20 A[0][1]
1008 50 A[1][1]
1010 80 A[2][1]
1012 30 A[0][2]
1014 60 A[1][2]
1016 90 A[2][2]
Row-Major Method
Col-Major Method

79. Arrays
Prof. Dr. K. Adisesha
79
Calculating the length of the 2D-Array
:A two dimensional array is a collection of elements and each element is identified by a
pair of subscripts. ( A[m] [n] )
The size of array or its length is given by the following equation:
A[i][j] is the array size or length of m*n elements.
To Calculate the address of i*j thelement in array:
Row-Major Method: Loc(A[i][j])=Base(A)+W[n(i-LB)+(j-LB)]
Col-Major Method: Loc(A[i][j])=Base(A)+W[(i-LB)+m(j-LB)]
Here, Wis the number of words per memory location and LBis the smallest index

80. Arrays
Prof. Dr. K. Adisesha
80
Sparse matrix:
Sparsematricesarethosematricesthathavethemajorityoftheirelementsequaltozero.
Inotherwords,thesparsematrixcanbedefinedasthematrixthathasagreaternumber
ofzeroelementsthanthenon-zeroelements.
Representingasparsematrixbya2Darrayleadstothewastageoflotsofmemory.In
2Darrayrepresentationofsparsematrix,therearethreefieldsusedthatarenamedas-

81. Arrays
Prof. Dr. K. Adisesha
81
Advantages of Array
:A two dimensional array is a collection of elements and each element is identified by a
pair of subscripts. ( A[m] [n] )
It is used to represent multiple data items of same type by using single name.
It can be used to implement other data structures like linked lists, stacks, queues, tree,
graphs etc.
Two-dimensional arrays are used to represent matrices.
Many databases include one-dimensional arrays whose elements are records.

82. Arrays
Prof. Dr. K. Adisesha
82
Disadvantages of Array:
A two dimensional array is a collection of elements and each element is identified by a
pair of subscripts. ( A[m] [n] )
We must know in advance the how many elements are to be stored in array.
Array is static structure. It means that array is of fixed size. The memory which is
allocated to array cannot be increased or decreased.
Array is fixed size; if we allocate more memory than requirement then the memory
space will be wasted.
The elements of array are stored in consecutive memory locations. So insertion and
deletion are very difficult and time consuming.

83. Unit 3 Linked List
Prof. Dr. K. Adisesha
83
Lists (linked list):
A lists (Linear linked list) can be defined as a collection of variable number of
data items called nodes.
Lists are the most commonly used non-primitive data structures.
Each nodes is divided into two parts:
The first part contains the information of the element.
The second part contains the memory address of the next node in the list.
Also called Link part.

84. Linked List
Prof. Dr. K. Adisesha
84
Lists (linked list):
Types of linked lists:
Single linked list
Doubly linked list
Single circular linked list
Doubly circular linked list

85. Linked List
Prof. Dr. K. Adisesha
85
Single linked list:
The link field of the last node contains the memory address of the first node,
such a linked list is called circular linked list:
The information field contains the data of that node.
The link field contains the memory address of the next node.
The last link field contains the memory address as null (\).
There is only one link field in each node, the linked list is called singly linked
list.

86. Linked List
Prof. Dr. K. Adisesha
86
Single circular linked list:
A singly linked list contains two fields in each node -an information field and
the linked field:
The information field contains the data of that node.
The link field contains the memory address of the next node
The last link field contains the memory address of the first node.
In a circular linked list every node is accessible from a given node.

87. Linked List
Prof. Dr. K. Adisesha
87
Doubly linked list:
It is a linked list in which each node is points both to the next node and also
to the previous node:
In doubly linked list each node contains three parts:
FORW : It is a pointer field that contains the address of the next node
BACK: It is a pointer field that contains the address of the previous node.
INFO: It contains the actual data.
In the first node, if BACK contains NULL, it indicated that it is the first node in
the list.
The in which FORW contains, NULL indicates that the node is the last node.

88. Linked List
Prof. Dr. K. Adisesha
88
Doubly circular linked list:
It is a linked list in which each node is points both to the next node and also to
the previous node:
In doubly linked list each node contains three parts:
FORW : It is a pointer field that contains the address of the next node
BACK: It is a pointer field that contains the address of the previous node.
INFO: It contains the actual data.

89. Linked List
Prof. Dr. K. Adisesha
89
Operation on Linked List:
The operation that are performed on linked lists are:
Creating a linked list
Traversing a linked list
Inserting an item into a linked list.
Deleting an item from the linked list.
Searching an item in the linked list
Merging two or more linked lists.

90. Linked List
Prof. Dr. K. Adisesha
90
Creating a linked list:
The nodes of a linked list can be created by the following structure declaration:
struct Node
{
intinformation;
struct Node *link;
}*node1, *node2;
Here info is the information field and link is the link field.
The link field contains a pointer variable that refers the same node structure. Such a
reference is called as Self addressing pointer.

91. Linked List
Prof. Dr. K. Adisesha
91
Creating a linked list:
The nodes of a linked list can be created by the following structure declaration:

92. Linked List
Prof. Dr. K. Adisesha
92
Operator new and delete:
The nodes of a linked list can be created by the following structure declaration:
Operators new allocate memory space
Operators new [ ] allocates memory space for array.
Operators delete deallocate memory space.
Operators delete [ ] deallocate memory space for array.
struct Node
{
intinformation;
struct Node *link;
}*node1, *node2;

93. 93
Traversing is the process of accessing each node of the linked list exactly once to
perform some operation.
ALGORITHM: TRAVERS (START, P)
START contains the address of the first node. Another pointer p is temporarily used to visit all the nodes
from the beginning to the end of the linked list.
Step 1: P = START
Step 2: while P != NULL
Step 3: PROCESS data (P) [Fetch the data]
Step 4: P = link(P) [Advance P to next node]
Step 5: End of while
Step 6: Return
Traversing a linked list
Prof. Dr. K. Adisesha
Code:
struct node *temp = head;
printf("\n\nListelements are -\n");
while(temp != NULL) {
printf("%d --->",temp->data);
temp = temp->next;
}

94. 94
Inserting a node at the beginning of the linked list
Inserting a node at the given position.
Inserting a node at the end of the linked list.
Linked List
Inserting a node into the linked list:
Prof. Dr. K. Adisesha

95. 95
Linked List
Inserting node at Front:
Inserting a node at the beginning of the linked list
1. Create a node.
2. Fill data into the data field of the new node.
3. Mark its pointer field as NULL
4. Attach this newly created node to START
5. Make the new node as the START node.
Prof. Dr. K. Adisesha

96. 96
Linked List
Inserting node at Front:
Inserting a node at the beginning of the linked list
ALGORITHM: INS_BEG (START, P) START contains the address of the first node.
Step 1: P new Node;
Step 2: data(P) num;
Step 3: link(P) START
Step 4: START P
Step 5: Return
Prof. Dr. K. Adisesha

97. 97
Linked List
Inserting node at Front:
Inserting a node at the beginning of the linked list
Get the new node using getnode().
newnode= getnode();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
newnode-> next = start;
start = newnode;
Prof. Dr. K. Adisesha
void insert_at_beg()
{node *newnode;
newnode= getnode();
if(start == NULL)
{ start = newnode;}
else
{ newnode-> next = start;
start = newnode;}
}

98. 98
Linked List
Inserting node at End:
Inserting a node at the End of the linked list
1. Create a node.
2. Fill data into the data field of the new node.
3. Mark its pointer field as NULL
4. Attach this newly created node to Last
5. Make the new node as the Last node.
Prof. Dr. K. Adisesha

99. ALGORITHM: INS_END (START, P)
START contains the address of the first node.
Step 1: START
Step 2: P START [identify the last node]
while P!= null
P next (P)
End while
Step 3: Nnew Node;
Step 4: data(N) item;
Step 5: link(N) null
Step 6: link(P) N
Step 7: Return
99
Inserting node at End
Prof. Dr. K. Adisesha

100. Insert at the End
100
Inserting node at End
Prof. Dr. K. Adisesha
Allocate memory for new node
Store data
Traverse to last node
Change next of last node to recently created node
struct node *newNode;
newNode= malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;
struct node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = newNode;

101. 101
Inserting node at a given Position
Inserting a node at intermediate position:
Figure shows inserting a node into the single linked list at a specified intermediate
position other than beginning and end.
Prof. Dr. K. Adisesha

102. 102
Inserting node at a given Position
ALGORITHM: INS_POS (START, P1, P2)
START contains the address of the first node. P2 is new node
Step 1: START
Step 2: P1 START [Initialize node]
Count 0
Step 3:while P!= null
count count+1
P1 next (P1)
End while
Step 4: if (POS=1)
Call function INS_BEG( )
else if (POS=Count +1)
Call function INS_END( )
else if (POS<=Count)
P1 Start
For(i=1; i<=pos; i++)
P1 next(P1);
end for
[create] P2 new node
data(P2) item;
link(P2) link(P1)
link(P1) P2
else
PRINT “Invalid position”
Step 5: Return
Prof. Dr. K. Adisesha

103. 103
Inserting node at a given Position
Code: Insert at the Middle
Prof. Dr. K. Adisesha
Allocate memory and store data for new node
Traverse to node just before the required position of new node
Change next pointers to include new node in between
struct node *newNode;
newNode= malloc(sizeof(struct node));
newNode->data = 4;
struct node *temp = head;
for(int i=2; i< position; i++) {
if(temp->next != NULL) {
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;

104. 104
Deleting an item from the linked list:
Deletion of the first node
Deletion of the last node
Deletion of the node at the give position.
Deleting an node
Deleting an node:
Prof. Dr. K. Adisesha

105. 105
Deleting an node
Deletion of the first node:
This algorithm first copies data in the first node to a variable and delete the first node
of the linked list.
ALGORITHM: DEL_BEG(P, START) This used pointers P
Step 1: START
Step 2: P START;
Step 3: PRINT data(P)
Step 4:START Link(P)
Step 5:Free(P)
Step 6: STOP
Prof. Dr. K. Adisesha
Start = start->link;

106. 106
Deleting an node
Deletion of the first node:
The following steps are followed, to delete a node at the beginning of the list:
void delete_at_beg()
{node *temp;
if(start == NULL)
{ printf("\n No nodes are exist..");
return ;}
else
{temp = start;
start = temp -> next;
free(temp);
printf("\n Node deleted ");}
}
Prof. Dr. K. Adisesha
If the list is empty, Display the empty list message
If the list is not empty, follow the steps given below:
temp = start;
start = start -> next;
free(temp);

107. 107
Deleting an node
Deleting node from end:
Prof. Dr. K. Adisesha
The following steps are followed to delete a node at the end of the list:
If the list is not empty, follow the steps given below:
temp = prev= start;
while(temp -> next != NULL)
{
prev= temp;
temp = temp -> next;
}
prev-> next = NULL;
free(temp);

108. ALGORITHM: DEL_END (P1, P2, START) This used two pointers P1 and P2. Pointer P2 is used
to traverse the linked list and pointer P1 keeps the location of the previous node of P2.
Step 1: START
Step 2: P2 START;
Step 3: while ( link(P2) ! = NULL)
P1 P2
P2 link(P2)
While end
Step 4: PRINT data(p2)
Step 5: link(P1) NULL
Free(P2)
Step 6: STOP
108
Deleting an node
Deleting node from end:
Prof. Dr. K. Adisesha

109. Traverse to second last element
Change its next pointer to null
Code:
struct node * temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;
109
Deleting an node
Deleting node from end:
Prof. Dr. K. Adisesha

110. Step 1: START
Step 2: P1 START [Initialize node]
Count 0
Step 3:while P!= null
countcount+1
P1 next (P1)
End while
Step 4: if (POS=1)
Call function DEL_BEG( )
else if (POS=Count)
Call function DEL_END( )
else if (POS<=Count)
P2Start
For(i=1; i<=pos; i++)
P1 P2
P2 link(P2)
end for
PRINT data(P2)
link(P1) link( P2)
free(P2)
End if
Step 5: Return
110
Deleting node at a given Position
ALGORITHM: DEL_POS (START, P1, P2)
START contains the address of the first node. P2 is DEL-node
Prof. Dr. K. Adisesha

111. 111
Deleting node at a given Position
Delete from middle
Prof. Dr. K. Adisesha
Traverse to element before the element to be deleted
Change next pointers to exclude the node from the chain
Code:
struct node* temp = head;
for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;

112. Unit 4- Stack & Queues
Prof. Dr. K. Adisesha
112
Stack:
Stack is a linear data structure which follows a particular order in which the operations
are performed
Insertion of element into stack is called PUSH and deletion of element from stack is
called POP.
The order may be LIFO(Last In First Out) or FILO(First In Last Out).

113. Stack
Prof. Dr. K. Adisesha
113
Stack:
Memory Representation of Stack
The stack can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic

114. Stack
Prof. Dr. K. Adisesha
114
Operation on Stacks:
The various operation performed on Stacks are:
Stack( ):It creates a new stack that is empty. It needs no parameter and returns an
empty stack.
push(item): It adds a new item to the top of the stack.
pop( ): It removes the top item from the stack.
peek( ): It returns the top item from the stack but does not remove it.
isEmpty( ): It tests whether the stack is empty.
size( ): It returns the number of items on the stack.

115. Stack
Prof. Dr. K. Adisesha
115
Stack Conditions:
The various operation performed on Stacks depend on the following conditions:

116. Stack
Prof. Dr. K. Adisesha
116
PUSH Operation:
The process of adding one element or item to the stack is represented by an operation
called as the PUSH operation:
ALGORITHM:
PUSH (STACK, TOP, SIZE, ITEM)
STACK is the array with N elements. TOP is the pointer to the top of the element of the array. ITEM to be inserted.
Step 1: if TOP = N then [Check Overflow]
PRINT “ STACK is Full or Overflow”
Exit
[End if]
Step 2: TOP = TOP + 1 [Increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return

117. Stack
Prof. Dr. K. Adisesha
117
POP Operation:
The process of deleting one element or item from the stack is represented by an
operation called as the POP operation.
When elements are removed continuously from a stack, it shrinks at same end i.e., top:

118. ALGORITHM: POP (STACK, TOP, ITEM)
STACK is the array with N elements. TOP is the pointer to the top of the element of the array. ITEM
to be DELETED.
Step 1: if TOP = 0 then [Check Underflow]
PRINT “ STACK is Empty or Underflow”
Exit
[End if]
Step 2: ITEM = STACK[TOP] [copy the TOP Element]
Step 3: TOP = TOP -1 [Decrement the TOP]
Step 4: Return
Stack
Prof. Dr. K. Adisesha
118
POP Operation:
The process of deleting one element or item from the stack is represented by an
operation called as the POP operation.

119. Stack
Prof. Dr. K. Adisesha
119
PEEK Operation:
The process of returning the top item from the stack but does not remove it called as the
PEEK operation.
ALGORITHM: PEEK (STACK, TOP)
STACK is the array with N elements. TOP is the pointer to the top of the element of the
array.
Step 1: if TOP = NULL then [Check Underflow]
PRINT “ STACK is Empty or Underflow”
Exit
[End if]
Step 2: Return (STACK[TOP] [Return the top element of the stack]
Step 3:Exit

120. Stack
Prof. Dr. K. Adisesha
120
Program to demonstrate push and pop operation in stack in data structure in C
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
int top = -1, A[SIZE];
void push();
void pop();
void show();
int main()
{ int choice;
while (1)
{ printf("\nPerformoperations on the stack:");
printf("\n1.Push \n 2.Pop \n 3.Show\n4.End");
printf("\n\nEnterthe choice: ");
scanf("%d", &choice);
switch (choice)
{ case 1:
push();
break;
case 2:
pop();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("\nInvalidchoice!!");
} }
}

121. Stack
Prof. Dr. K. Adisesha
121
Program to demonstrate push and pop operation in stack in data structure in C
void push()
{ int x;
if (top == SIZE -1)
{ printf("\nOverflow!!"); }
else
{ printf("\nEnterthe element to the stack: ");
scanf("%d", &x);
top = top + 1;
A[top] = x; }
}
void pop()
{ if (top == -1)
{ printf("\nUnderflow!!"); }
else
{ printf("\nPoppedelement: %d", A[top]);
top = top -1; }
}
void show()
{ if (top == -1)
{ printf("\nUnderflow!!"); }
else
{ printf("\nElementspresent in the stack: \n");
for (int i= top; i>= 0; --i)
printf("%d\n", A[i]);
}
}

122. Stack
Prof. Dr. K. Adisesha
122
Application of Stacks:
It is used to reverse a word. You push a given word to stack –letter by letter and then pop
letter from the stack.
“Undo” mechanism in text editor.
Conversion of infix expression into prefix and postfix.
Evaluation of Arithmetic Expressions
Delimiter Checking
Processing Function Calls
To solve tower of Hanoi.
To sort elements using Quick sort
Runtime memory management.

123. An expression is a combination of operands and operators that after evaluation results
in a single value.
Operand consists of constants and variables.
Operators consists of {, +, -, *, /, ), ] etc.
Expression can be
Infix Expression: If an operator is in between two operands, it is called infix expression.
Example: a + b, where a and b are operands and + is an operator.
Postfix Expression: If an operator follows the two operands, it is called postfix expression.
Example: ab +
Prefix Expression: an operator precedes the two operands, it is called prefix expression.
Example: +ab
Stack
Prof. Dr. K. Adisesha
123
Arithmetic Expression:

124. Stack
Prof. Dr. K. Adisesha
124
Arithmetic Expression:
Converting an infix expression into a
postfix expression.
A+B/C+D*(E-F)^G

125. Stack
Prof. Dr. K. Adisesha
125
Arithmetic Expression:

126. Stack
Prof. Dr. K. Adisesha
126
Arithmetic Expression:
Evaluating Postfix expression:
let us consider the following infix expression:
2 * (4+3) -5.
Its equivalent postfix expression is:
2 4 3 + * 5.
The following step illustrates how this postfix
expression is evaluated.
Value=9

127. Stack
Prof. Dr. K. Adisesha
127
Delimiter Checking:
ThecommonapplicationofStackisdelimiterchecking,i.e.,parsingthatinvolves
analyzingasourceprogramsyntactically.
Toperformadelimiterchecking,thecompilermakesuseofastack.
Itisalsocalledparenthesischecking.
Valid Delimiter Invalid Delimiter
While ( i> 0) While ( i>
/* Data Structure *//* Data Structure
{ ( a + b) -c } { ( a + b) -c

128. Stack
Prof. Dr. K. Adisesha
128
Processing Function Calls:
Acallstackisadatastructureusedbycomputerprogramstokeeptrackoffunctioncalls.
WhenaRecursivefunctioniscalled,anewframeisaddedtothecallstack.
function factorial(n)
{ if (n == 0)
{
return 1;
}
else
{ return n * factorial(n -1);
}
}

129. Queue
Prof. Dr. K. Adisesha
129
Queue:
A queue is an ordered collection of items where an item is inserted at one end called the
“rear” and an existing item is removed at the other end, called the “front”.
Queue is also called as FIFO list i.e. First-In First-Out.
In the queue only two operations are allowed enqueue and dequeue.
Enqueue means to insert an item into back of the queue.
Dequeue means removing the front item.The people standing in a railway reservation
row are an example of queue.

130. Queue
Prof. Dr. K. Adisesha
130
Queue:
A queue is an ordered collection of items where an item is inserted at one end called the
“rear” and an existing item is removed at the other end, called the “front”.

131. Queue
Prof. Dr. K. Adisesha
131
Memory Representation of Queue:
The queue can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic

132. Queue
Prof. Dr. K. Adisesha
132
Memory Representation of Queue:
Memory Representation of a queue using array:
Queue is represented in memory using linear array.
Let QUEUE is a array, two pointer variables called FRONT and REAR are
maintained.
The pointer variable FRONT contains the location of the element to be removed or
deleted.
The pointer variable REAR contains location of the last element inserted.
The condition FRONT = NULL indicates that queue is empty.
The condition REAR = N-1 indicates that queue is full.

133. Queue
Prof. Dr. K. Adisesha
133
Types of Queues
:Queue can be of four types:
Simple Queue
Circular Queue
Priority Queue
De-queue ( Double Ended Queue)

134. Queue
Prof. Dr. K. Adisesha
134
Types of Queues
:SimpleQueue:SimpleQueueisalineardatastructurethatfollowstheFirst-In-First-
Out(FIFO)principle,whereelementsareaddedtotherear(back)andremovedfrom
thefront(head).
When a new element is added, all elements added before the new element must be
deleted in order to remove the new element.
Ordered collection of comparable data kinds.
Queue structure is FIFO (First in, First Out).

135. Queue
Prof. Dr. K. Adisesha
135
Types of Queues
:Circular Queue:
A circular queue is a special case of a simple queue in which the last member is linked
to the first, forming a circle-like structure.
The last node is connected to the first node.
Also known as a Ring Buffer, the nodes are connected
end to end.
Insertion takes place at the front of the queue, and
deletion at the end of the queue.

136. Queue
Prof. Dr. K. Adisesha
136
Types of Queues
:Priority Queue:
In a priority queue, the nodes will have some predefined priority in the priority queue.
The node with the higiestpriority will be the first to be removed from the queue. Insertion
takes place in the order of arrival of the nodes.
Some of the applications of priority queue:
Dijkstra’s shortest path algorithm
Prim’s algorithm
Data compression techniques like Huffman
code

137. Queue
Prof. Dr. K. Adisesha
137
Types of Queues
:Dequeue Queue:
Dequeue:It is a queue in which insertion and deletion takes place at the both ends.

138. Queue
Prof. Dr. K. Adisesha
138
Operation on Queues
:The various operation performed on Queue are :
Operation Description
enqueue()Process of adding or storing an element to the end of the queue
dequeue()Process of removing or accessing an element from the front of the queue
peek() Used to get the element at the front of the queue without removing it
initialize()Creates an empty queue
isfull()Checks if the queue is full
isempty()Check if the queue is empty

139. Queue
Prof. Dr. K. Adisesha
139
Queue Insertion Operation (ENQUEUE):
ALGORITHM: ENQUEUE (QUEUE, REAR, FRONT, ITEM )
QUEUE is the array with N elements. FRONT is the pointer that contains the location of the element to be deleted
and REAR contains the location of the inserted element. ITEM is the element to be inserted.
Step 1: if REAR = N-1 then [Check Overflow] Front Rear
PRINT “QUEUE is Full or Overflow”
Exit
[End if]
Step 2: if FRONT = NULL then [Check Whether Queue is empty]
FRONT = -1
REAR = -1
else
REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

140. Queue
Prof. Dr. K. Adisesha
140
Queue Deletion Operation (DEQUEUE):
ALGORITHM: DEQUEUE (QUEUE, REAR, FRONT, ITEM)
QUEUE is the array with N elements. FRONT is the pointer that contains the location of the element to be deleted and REAR
contains the location of the inserted element. ITEM is the element to be inserted.
Step 1: if FRONT = NULL then [Check Whether Queue is empty] Front Rear
 PRINT “QUEUE is Empty or Underflow”
 Exit
 [End if]
Step 2: ITEM = QUEUE[FRONT]
Step 3: if FRONT = REAR then [if QUEUE has only one element]
 FRONT = NULL
 REAR = NULL
 else
 FRONT = FRONT + 1 [Increment FRONT pointer]
Step 4: Return

141. Queue
Prof. Dr. K. Adisesha
141
Application of Queue:
Operating systems: Operating systems often use queues to manage processes and resources.
For example, a process scheduler might use a queue to manage the order in which processes
are executed.
Task Scheduling: Queues can be used to schedule tasks based on priority or the order in
which they were received.
Resource Allocation: Queues can be used to manage and allocate resources, such as
printers or CPU processing time.
Event Handling: Queues can be used to handle events in event-driven systems, such as GUI
applications or simulation systems.
Printer queues: Inprinting systems, queues are used to manage the order in which print jobs
are processed. Jobs are added to the queue as they are submitted, and the printer processes
them in the order they were received.

142. Unit-5
Prof. Dr. K. Adisesha
142
Non-Linear Data structures:
Non-lineardatastructuresinCthedataisstoredinmultiplelevels.The
implementationofnon-lineardatastructuresismorecomplexthanlineardata
structures
The different non-linear data structures are
Trees
Graphs.

143. Non-Linear Data structures
Prof. Dr. K. Adisesha
143
Non-Linear Data structures:
ANon-LinearDatastructuresisadatastructureinwhichdataitemis
connectedtoseveralotherdataitems:
The data items in non-linear data structure represent hierarchical relationship.
Each data item is called node.
The different non-linear data structures are
Trees
Graphs.

144. Non-Linear Data structures
Prof. Dr. K. Adisesha
144
Tree as data structure :
A tree is a data structure consisting of nodes organized as a hierarchy:
Tree is a hierarchical data structure which stores the information naturally in the form
of hierarchy style.
It is a non-linear data structure compared to arrays, linked lists, stack and queue.
It represents the nodes connected by edges.

145. Non-Linear Data structures
Prof. Dr. K. Adisesha
145
Terminology of a Tree:

146. Non-Linear Data structures
Prof. Dr. K. Adisesha
146
Tree as Data structure :
Different Types of Trees in Data Structure:
Binary Tree
Ternary Tree
N-aryTree
AVL Tree
Red-Black Tree
Binary Search-Tree
B-Tree

147. Non-Linear Data structures
Prof. Dr. K. Adisesha
147
Different Types of Trees in Data Structure:
BinaryTree:ABinaryTreeiscomposedofnodes,whereeachnodehasatmosttwochildren,
referredtoastheleftandrightsubtrees.
TernaryTree:ATernaryTreeisatreedatastructureinwhicheachnodehasatmostthree
childnodes,usuallydistinguishedas“left”,“mid”and“right”.
N-aryTree:AnN-aryTreeisageneralisationofbinarytreeswhereeachnodecanhaveupto
Nchildren,providingamoreflexibleandscalablehierarchicalstructure.
AVLTree:AVLtreeisaself-balancingBinarySearchTree(BST)wherethedifference
betweenheightsofleftandrightsubtreesforanynodecannotbemorethanone.
Red-BlackTree:ARed-BlackTreeisaself-balancingbinarysearchtreewiththekey
innovationofassigningcolours(redorblack)toitsnodes.

148. Non-Linear Data structures
Prof. Dr. K. Adisesha
148
Binary Tree:
A binary tree is an ordered tree in which each internal node can have maximum
of two child nodes connected to it:
A binary tree consists of:
A node ( called the root node)
Left and right sub trees.
A Complete binary tree is a binary tree in which each leaf is at the same distance from
the root i.e. all the nodes have maximum two subtrees.
Binary tree using array represents a node which is
numbered sequentially level by level from left to
right. Even empty nodes are numbered.

149. Non-Linear Data structures
Prof. Dr. K. Adisesha
149
Binary Search tree:
In a Binary search tree, the value of left node must be smaller than the parent
node, and the value of right node must be greater than the parent node.
Abinarysearchtreefollowssomeordertoarrangetheelements.
wecanobservethattherootnodeis40,andallthenodesoftheleftsubtreearesmaller
thantherootnode,andallthenodesoftherightsubtreearegreaterthantherootnode.
Supposethedataelementsare-45,15,79,90,10,55,12,20,50
Steps-Insert45asRoot.

150. Non-Linear Data structures
Prof. Dr. K. Adisesha
150
Full Binary Tree vs. Complete Binary Tree:
A full binary tree can be defined as a binary tree in which all the nodes have 0 or
two children.
Inotherwords,thefullbinarytreecanbedefinedasabinarytreeinwhichallthe
nodeshavetwochildrenexcepttheleafnodes.
Abinarytreeissaidtobeacompletebinarytreewhenallthelevelsarecompletely
filledexceptthelastlevel,whichisfilledfromtheleft.
Full Binary Tree
Complete Binary Tree

151. Non-Linear Data structures
Prof. Dr. K. Adisesha
151
Tree traversal:
The term 'tree traversal' means traversing or visiting each node of a tree.
A Tree Data Structure can be traversed in following ways:
Depth First Search or DFS
Inorder Traversal
Preorder Traversal
Postorder Traversal
Breadth First Search or BFS
Boundary Traversal
Diagonal Traversal

152. Non-Linear Data structures
Prof. Dr. K. Adisesha
152
Depth First Search or DFS
DFS,DepthFirstSearch,isanedge-basedtechnique.
ItusestheStackdatastructureandperformstwostages,firstvisitedverticesare
pushedintothestack,andsecondiftherearenoverticesthenvisitedverticesare
popped.
DepthFirstSearchorDFS
InorderTraversal
PreorderTraversal
PostorderTraversal

153. Non-Linear Data structures
Prof. Dr. K. Adisesha
153
Depth First Search or DFS
Inorder Traversal: This technique follows the 'left root right' policy.
It means that first left subtree is visited after that root node is traversed, and finally, the
right subtree is traversed.
Algorithm: Until all nodes of the tree are not visited
Step 1 -Traverse the left subtree recursively.
Step 2 -Visit the root node.
Step 3 -Traverse the right subtree recursively.

154. Non-Linear Data structures
Prof. Dr. K. Adisesha
154
Depth First Search or DFS
Preorder Traversal: This technique follows the 'root left right' policy.
It means that, first root node is visited after that the left subtree is traversed recursively,
and finally, right subtree is recursively traversed.
Algorithm: Until all nodes of the tree are not visited
Step 1 -Visit the root node
Step 2 -Traverse the left subtree recursively.
Step 3 -Traverse the right subtree recursively.

155. Non-Linear Data structures
Prof. Dr. K. Adisesha
155
Depth First Search or DFS
:Postorder Traversal: This technique follows the 'left-right root' policy.
It means that the first left subtree of the root node is traversed, after that recursively
traverses the right subtree, and finally, the root node is traversed.
Algorithm: Until all nodes of the tree are not visited
Step 1 -Traverse the left subtree recursively.
Step 2 -Traverse the right subtree recursively.
Step 3 -Visit the root node.

156. Non-Linear Data structures
Prof. Dr. K. Adisesha
156
Depth First Search or DFS
:Construct Tree from given Inorder and Preorder traversals.
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
InaPreordersequence,theleftmostelementistherootofthe
tree.Soweknow‘A’istherootforgivensequences.
Bysearching‘A’intheInordersequence,wecanfindoutall
elementsontheleftsideof‘A’isintheleftsubtreeand
elementsonrightintherightsubtree.
Soweknowthebelowstructurenow.

157. Non-Linear Data structures
Prof. Dr. K. Adisesha
157
Depth First Search or DFS:
Construct Tree from given Inorder and Preorder traversals.
Algorithm: buildTree()
Pick an element from Preorder. Increment a Preorder Index Variable to pick the next element
in the next recursive call.
Create a new tree node tNodewith the data as the picked element.
Find the picked element’s index in Inorder. Let the index be inIndex.
Call buildTree for elements before inIndexand make the built tree as a left subtree of tNode.
Call buildTree for elements after inIndexand make the built tree as a right subtree of tNode.
return tNode.

158. Non-Linear Data structures
Prof. Dr. K. Adisesha
158
Breadth First Search or BFS
:
BFS, Breadth-First Search, is a vertex-based technique for finding the shortest
path in the graph.
It uses a Queue data structure that follows first in first out.
Breadth First Search or BFS
Boundary Traversal
Diagonal Traversal

159. Non-Linear Data structures
Prof. Dr. K. Adisesha
159
Applications of tree data structure
Trees find applications in various fields, including.
Storing hierarchical data in File System
In chess game to store defense moves of player.
In server like DNS (Domain Name Server)
Web Search Engines
Computer Graphics.
To evaluate an expression
GPS Navigation systems
Artificial Intelligence

160. Non-Linear Data structures
Prof. Dr. K. Adisesha
160
Graph:
Graph is a mathematical non-linear data structure capable of representing many
kind of physical structures:
A graph is a set of vertices and edges which connect them.
A graph is a collection of nodes called vertices and the connection between them
called edges.
Definition: A graph G(V,E) is a set of vertices V and a set of edges E.

161. Non-Linear Data structures
Prof. Dr. K. Adisesha
161
Graph:
Graph is a mathematical non-linear data structure capable of representing many
kind of physical structures:
An edge connects a pair of vertices and many have weight such as length, cost and
another measuring instrument for according the graph.
Vertices on the graph are shown as point or circles and edges are drawn as arcs or line
segment

162. Non-Linear Data structures
Prof. Dr. K. Adisesha
162
Graph:
Types of Graphs:
Directed graph
Undirected graph
Simple graph
Weighted graph
Connected graph
Non-connected graph

163. Non-Linear Data structures
Prof. Dr. K. Adisesha
163
Graph Representation:
There are two techniques to represent a graph:
Adjacency Matrix: In the adjacency matrix, each row and column define a vertex. It is
a 2D array of V x V vertices.
Adjacency List: The index of the array defines a vertex, and every component in its
linked list describes the other vertices that form an edge with the vertex.
Adjacency Matrix Adjacency List

164. Non-Linear Data structures
Prof. Dr. K. Adisesha
164
Applications of Graph Data Structure:
In Computer science graphs are used to represent the flow of computation.
Graphs are used to represent networks of communication.
Graph theory is also used in network security.
In Google Maps, is used to find shortest path in road or a network.
The World Wide Web is an example of a directed graph.
Facebook uses undirected graphs to identify a user and the user’s friends.
In Electrical Engineering, graph theory is used in designing of circuit connections.
graph data structures define and compute the transport system.

165. Data structures
Prof. Dr. K. Adisesha
165
Thank you: