Data structure and algorithms unit 1 pdf SRM

this slide show cover basics of data structure and algorithms

1. 18CSC201J
DATA STRUCTURES AND
ALGORITHMS
UNIT 1
Prepared by
Dr. Pretty Diana Cyril
Dr. S. Thanga Revathi
Dr. Mary Subaja Christo
Dr. K. Kalai selvi
R Lavanya

2. Topics to be covered
S1 : Introduction –Basic Terminology -Data Structures
S2 : Data Structure Operations -ADT
S3 : Algorithms –Searching Techniques –Complexity –Time, Space Matrix
S4 : Algorithms –Sorting -Complexity –Time, Space Matrix
S5 : Mathematical notations –Asymptotic notations –Big O, Omega
S6 : Asymptotic notations –Theta –Mathematical functions
S7 : Data Structures and its Types -Linear and Non Linear Data Structures
S8 : 1D, 2D Array Initialization using Pointers -1D, 2D Array Accessing
using Pointers
S9 : Declaring Structure and accessing –Declaring Arrays of Structures and
accessing

3. INTRODUCTION
BASIC TERMINOLOGY

4. Introduction
•DataStructurecanbedefinedasthegroupofdataelementswhich
providesanefficientwayofstoringandorganizingdatainthecomputer
sothatitcanbeusedefficiently.
•SomeexamplesofDataStructuresarearrays,LinkedList,Stack,Queue,
etc.
•DataStructuresarewidelyusedinalmosteveryaspectofComputer
Sciencei.e.OperatingSystem,CompilerDesign,Artificialintelligence,
Graphicsandmanymore.

5. Basic Terminology
•Dataarevaluesorsetsofvalues
•Adataitemreferstoasingleunitofvalues.Dataitemsaredividedinto
subitemsarecalledgroupitems.
oForexample,anemployee’snamemaybedividedintothreesubitems
firstname,middlenameandlastnamebutthesocialsecuritynumber
wouldtreatedasasinglename.
•Collectionsofdataareorganizedintoahierarchyoffields,recordsand
files.

6. Basic Terminology (Cont..)
•Recordcanbedefinedasthecollectionofvariousdataitems.
oForexample,ifwetalkaboutthestudententity,thenitsname,address,
courseandmarkscanbegroupedtogethertoformtherecordforthe
student.
•Recordisclassifiedaccordingtolength.Afilecanhavefixedlength
recordsorvariablelengthrecords.
•Infixedlengthrecords,alltherecordscontainthesamedataitemswith
thesameamountofspaceassignedtoeachdataitems.
•Invariablelengthrecords,filerecordsmaycontaindifferentlengths.
Variablelengthrecordshaveaminimumandamaximumlength.
oForexample,studentrecordshavevariablelength,sincedifferent
studentstakedifferentnumbersofcourses

7. Basic Terminology (Cont..)
•AFileisacollectionofvariousrecordsofonetypeofentity.
oForexample,ifthereare60employeesintheclass,thentherewillbe20
recordsintherelatedfilewhereeachrecordcontainsthedataabout
eachemployee.
•Anentityrepresentstheclassofcertainobjects.Itcontainsvarious
attributes.Eachattributerepresentstheparticularpropertyofthatentity.
oForexample,consideranemployeeofanorganization:
Attributes: Name AgeSexSocialSecurityNumber
Values: JOHN 34 M 134-24-5533
•Fieldisasingleelementaryunitofinformationrepresentingtheattribute
ofanentity.

8. Basic Terminology –Example
•Aprofessorkeepsaclasslistcontainingthefollowingdataforeachstudent:
Name,Major,StudentNumber,TestScores,FinalGrades
a)Statetheentities,attributesandentitysetofthelist.
b)Describethefieldvalues,recordsandfile.
c)Whichattributecanserveasprimarykeysforthelist?
a) Each student is an entity, and the collection of students is the entity set. The properties, name,
major, and so on. of the students are the attributes.
b) The field values are the values assigned to the attributes, i. e., the actual names, test scores,
and so on. The field values for each student constitute a record, and the collection of all the
student records is the file.
c) Either Name or Student Number can serve as a primary key, since each uniquely determines
the student’s record. Normally the professor uses Name as the primary key, but the registrar
may use students Number.

9. DATA STUCTURES

10. Data Structures
•DataStructurecanbedefinedasthegroupofdataelementswhich
providesanefficientwayofstoringandorganizingdatainthecomputer
sothatitcanbeusedefficiently.
•DataStructuresarethemainpartofmanycomputersciencealgorithmsas
theyenabletheprogrammerstohandlethedatainanefficientway.
•Itplaysavitalroleinenhancingtheperformanceofasoftwareora
programasthemainfunctionofthesoftwareistostoreandretrievethe
user'sdataasfastaspossible.

11. Classification of Data Structures

12. Primitive & Non-Primitive of Data Structures
•Primitivedatastructuresarethefundamentaldatatypeswhichare
supportedbyaprogramminglanguage.
•Somebasicdatatypesareinteger,real(float),character,andBoolean.
•Non-primitivedatastructuresaredatastructureswhicharecreatedusing
primitivedatastructures.
•Examplesofsuchdatastructuresincludelinkedlists,stacks,trees,and
graphs.
•Non-primitivedatastructurescanfurtherbeclassifiedintotwocategories:
linearandnon-lineardatastructures.

13. Linear Data Structures
•Iftheelementsofadatastructurearestoredinalinearorsequential
order,thenitisalineardatastructure.
•Examplesincludearrays,linkedlists,stacks,andqueues.
•Lineardatastructurescanberepresentedinmemoryintwodifferent
ways.
•Onewayistohavealinearrelationshipbetweenelementsbymeansof
sequentialmemorylocations.
•Theotherwayistohavealinearrelationshipbetweenelementsbymeans
oflinks.

14. Non Linear Data Structures
•If the elements of a data structure are not stored in a sequential order,
then it is a non-linear data structure.
•The relationship of adjacency is not maintained between elements of a
non-linear data structure.
•Examples include trees and graphs.

15. Review Questions
•Ahospitalmaintainsapatientfileinwhicheachrecordcontainsthefollowingdata:
Name,Admissiondate,Socialsecuritynumber,Room,Bednumber,Doctor
a)Whichitemscanserveasprimarykeys?
b)Whichpairofitemscanserveasaprimarykey?
c)Whichitemscanbegroupitems?
•Whichofthefollowingdataitemsmayleadtovariablelengthrecordswhenincludedas
itemsintherecord:
(a)age,(b)sex,(c)nameofspouse,(d)namesofchildren,(e)education,
(f)previousemployers

16. DATA STUCTURE
OPERATIONS

17. Data Structure Operations
•Thedatainthedatastructuresareprocessedbycertainoperations.
oTraversing
oSearching
oInserting
oUpdating
oDeleting
oSorting
oMerging

18. Data Structure Operations (Cont..)
•Traversing-Visitingeachrecordsothatitemsintherecordscanbe
accessed.
•Searching-Findingthelocationoftherecordwithagivenkeyorvalueor
findingallrecordswhichsatisfygivenconditions.
•Inserting-Addinganewrecordtothedatastructure.
•Updating–Changethecontentofsomeelementsoftherecord.
•Deleting-Removingrecordsfromthedatastructure.
•Sorting-Arrangingrecordsinsomelogicalornumericalorder.
o(Eg:Alphabeticorder)
•Merging-Combingrecordsfromtwodifferentsortedfilesintoasingle
file.

19. Example
•Anorganizationcontainsamembershipfileinwhicheachrecordcontains
thefollowingdataforagivenmember:
Name,Address,TelephoneNumber,Age,Sex
a.Supposetheorganizationwantstoannounceameetingthrougha
mailing.ThenonewouldtraversethefiletoobtainNameand
Addressofeachmember.
b.Supposeonewantstofindthenamesofallmemberslivingina
particulararea.Againtraverseandsearchthefiletoobtainthedata.
c.SupposeonewantstoobtainAddressofaspecificPerson.Thenone
wouldsearchthefilefortherecordcontainingName.
d.Supposeamemberdies.Thenonewoulddeletehisorherrecord
fromthefile.

20. Example
e.Supposeanewpersonjoinstheorganization.Thenonewouldinsert
arecordintothefile
f.Supposeamemberhasshiftedtoanewresidencehis/heraddress
andtelephonenumberneedtobechanged.Giventhenameofthe
member,onewouldfirstneedtosearchfortherecordinthefile.
Thenperformtheupdateoperation,i.e.changesomeitemsinthe
recordwiththenewdata.
g.Supposeonewantstofindthenumberofmemberswhoseageis65
orabove.Againonewouldtraversethefile,countingsuchmembers.

21. ABSTRACT DATA TYPE

22. Abstract Data Types
•AnAbstractDatatype(ADT)isatypeforobjectswhosebehavioris
definedbyasetofvalueandasetofoperations.
•ADTreferstoasetofdatavaluesandassociatedoperationsthatare
specifiedaccurately,independentofanyparticularimplementation.
•TheADTconsistsofasetofdefinitionsthatallowustousethefunctions
whilehidingtheimplementation.
•Abstract in the context of data structures means everything except the
detailed specifications or implementation.
•Data type of a variable is the set of values that the variable can take.
•Examples: Stacks, Queues, Linked List
ADT = Type + Function Names + Behaviour of each function

23. ADT Operations
•Whilemodelingtheproblemsthenecessarydetailsareseparatedoutfrom
theunnecessarydetails.Thisprocessofmodelingtheproblemiscalled
abstraction.
•Themodeldefinesanabstractviewtotheproblem.Itfocusesonlyon
problemrelatedstuffandthatyoutrytodefinepropertiesoftheproblem.
•Thesepropertiesinclude
oThedatawhichareaffected.
oTheoperationswhichareidentified.

24. ADT Operations ( Cont..)
•Abstractdatatypeoperationsare
oCreate-Createthedatastructure.
oDisplay-Displayingalltheelementsstoredinthedatastructure.
oInsert-Elementscanbeinsertedatanydesiredposition.
oDelete-Desiredelementcanbedeletedfromthedatastructure.
oModify-Anydesiredelementcanbedeleted/modifiedfromthedata
structure.

25. Abstract Data Types Model
•TheADTmodelhastwodifferentparts
functions(publicandprivate)anddata
structures.
•BotharecontainedwithintheADTmodel
itself,anddonotcomewithinthescopeof
theapplicationprogram.
•Datastructuresareavailabletoallofthe
ADT’sfunctionsasrequired,andafunction
maycallanyotherfunctiontoaccomplish
itstask.
•Datastructuresandfunctionsarewithinthe
scopeofeachother.

26. Abstract Data Types Model (Cont..)
•Dataareentered,accessed,modifiedand
deletedthroughtheexternalapplication
programminginterface.
•ForeachADToperation,thereisan
algorithmthatperformsitsspecifictask.
•Theoperationnameandparametersare
availabletotheapplication,andthey
provideonlyaninterfacetothe
application.
•Whenalistiscontrolledentirelybythe
program,itisimplementedusingsimple
structure.

27. Review Questions
•______areusedtomanipulatethedatacontainedinvariousdata
structures.
•In______,theelementsofadatastructurearestoredsequentially.
•______ofavariablespecifiesthesetofvaluesthatthevariablecantake.
•Abstractmeans______.
•Iftheelementsofadatastructurearestoredsequentially,thenitisa
______.

28. ALGORITHMS
SEARCHING TECHIQUES

29. Algorithms
•Analgorithmisawelldefinedlistofstepsforsolvingaparticular
problem.
•Thetimeandspacearetwomajormeasuresoftheefficiencyofan
algorithm.
•Thecomplexityofanalgorithmisthefunctionwhichgivestherunning
timeand/orspaceintermsofinputsize.

30. Searching Algorithms
•SearchingAlgorithmsaredesignedtocheckforanelementorretrievean
elementfromanydatastructurewhereitisstored.
•Basedonthetypeofsearchoperation,thesealgorithmsaregenerally
classifiedintotwocategories:
•LinearSearch
•BinarySearch

31. Linear Search
•Linearsearchisaverybasicandsimplesearchalgorithm.
•InLinearsearch,wesearchanelementorvalueinagivenarrayby
traversingthearrayfromthestarting,tillthedesiredelementorvalueis
foundorwecanestablishthattheelementisnotpresent.
•Itcomparestheelementtobesearchedwithalltheelementspresentinthe
arrayandwhentheelementismatchedsuccessfully,itreturnstheindexof
theelementinthearray,elseitreturn-1.
•Linearsearchisappliedonunsortedorunorderedlists,whenthereare
fewerelementsinalist.

32. Linear Search -Example
•Searcheachrecordofthefile,oneatatime,untilfindingthegivenvalue.

33. Algorithm for Linear Search
•InSteps1and2ofthealgorithm,weinitialize
thevalueofPOSandI.
•InStep3,awhileloopisexecutedthatwould
beexecutedtillIislessthanN.
•InStep4,acheckismadetoseeifamatchis
foundbetweenthecurrentarrayelementand
VAL.
•Ifamatchisfound,thenthepositionofthe
arrayelementisprinted,elsethevalueofIis
incrementedtomatchthenextelementwith
VAL.
•Ifallthearrayelementshavebeencompared
withVALandnomatchisfound,thenit
meansthatVALisnotpresentinthearray.

34. Program for Linear Search

35. Linear Search -Advantages
•Whenakeyelementmatchesthefirstelementinthearray,thenlinear
searchalgorithmisbestcasebecauseexecutingtimeoflinearsearch
algorithmisO(n),wherenisthenumberofelementsinanarray.
•Thelistdoesn’thavetosort.Contrarytoabinarysearch,linearsearching
doesnotdemandastructuredlist.
•Notinfluencedbytheorderofinsertionsanddeletions.Sincethelinear
searchdoesn’tcallforthelisttobesorted,addedelementscanbeinserted
anddeleted.

36. Linear Search -Disadvantages
•Thedrawbackofalinearsearchisthefactthatitistimeconsumingifthe
sizeofdataishuge.
•Everytimeavitalelementmatchesthelastelementfromthearrayoran
essentialelementdoesnotmatchanyelementLinearsearchalgorithmis
theworstcase.

37. Binary Search
•BinarySearchisusedwithsortedarrayorlist.Inbinarysearch,wefollow
thefollowingsteps:
1)Westartbycomparingtheelementtobesearchedwiththeelement
inthemiddleofthelist/array.
2)Ifwegetamatch,wereturntheindexofthemiddleelementand
terminatetheprocess
3)Iftheelement/numbertobesearchedisgreaterthanthemiddle
element,wepicktheelementsontheleft/rightsideofthemiddle
element,andmovetostep1.
4)Iftheelement/numbertobesearchedislesserinvaluethanthe
middlenumber,thenwepicktheelementsontheright/leftsideof
themiddleelement,andmovetostep1.

38. Binary Search -Example
•BinarySearchisusefulwhentherearelargenumberofelementsinan
arrayandtheyaresorted.

39. Algorithm for Binary Search
•InStep1,weinitializethevalueofvariables,BEG,
END,andPOS.
•InStep2,awhileloopisexecuteduntilBEGisless
thanorequaltoEND.
•InStep3,thevalueofMIDiscalculated.
•InStep4,wecheckifthearrayvalueatMIDis
equaltoVAL.Ifamatchisfound,thenthevalue
ofPOSisprintedandthealgorithmexits.Ifa
matchisnotfound,andifthevalueofA[MID]is
greaterthanVAL,thevalueofENDismodified,
otherwiseifA[MID]isgreaterthanVAL,thenthe
valueofBEGisaltered.
•InStep5,ifthevalueofPOS=–1,thenVALisnot
presentinthearrayandanappropriatemessageis
printedonthescreenbeforethealgorithmexits.

40. Program for Binary Search

41. Binary Search (Cont..)
Advantages
•Iteliminateshalfofthelistfrom
furthersearchingbyusingthe
resultofeachcomparison.
•Itindicateswhethertheelement
beingsearchedisbeforeorafter
thecurrentpositioninthelist.
•Thisinformationisusedtonarrow
thesearch.
•Forlargelistsofdata,itworks
significantlybetterthanlinear
search.
Disadvantages
•Itemploysrecursiveapproach
whichrequiresmorestackspace.
•Programming binarysearch
algorithmiserrorproneand
difficult.
•Theinteractionofbinarysearch
withmemory hierarchyi.e.
cachingispoor.

42. Difference between Linear & Binary Search
Linear Search
•LinearSearchnecessitatesthe
inputinformationtobenotsorted
•LinearSearchneedsequality
comparisons.
•Linearsearchhascomplexity
C(n)=n/2.
•LinearSearchneedssequential
access.
Binary Search
•BinarySearchnecessitatesthe
inputinformationtobesorted.
•BinarySearchnecessitatesan
orderingcontrast.
•BinarySearchhascomplexity
C(n)=log
2n.
•BinarySearchrequiresrandom
accesstothisinformation.

43. COMPLEXITY
TIME, SPACE MATRIX

44. Linear Search –Time & Space Matrix
•Time Complexity
oWeneedtogofromthefirstelementtothelastso,intheworstcasewe
havetoiteratethrough‘n’elements,nbeingthesizeofagivenarray.
•Space Complexity
oWe don't need any extra space to store anything.
oWe just compare the given value with the elements in an array one by
one.
Space Complexity is O(1)
Time Complexity is O(n)

45. Binary Search –Time & Space Matrix
•Time Complexity
oWestartfromthemiddleofthearrayandkeepdividingthesearch
areabyhalf.
oInotherwords,searchintervaldecreasesinthepowerof2(2048,1024,
512,..).
•Space Complexity
oWe just need to store three values: `lower_bound`, `upper_bound`, and
`middle_position`.
Space Complexity is O(1)
Time Complexity is O(Log n)

46. Review Questions
•Theworstcasecomplexityis______whencomparedwiththeaverage
casecomplexityofabinarysearchalgorithm.
(a)Equal(b)Greater(c)Less(d)Noneofthese
•Thecomplexityofbinarysearchalgorithmis
(a)O(n)(b)O(n2)(c)O(nlogn)(d)O(logn)
•Whichofthefollowingcasesoccurswhensearchinganarrayusinglinear
searchthevaluetobesearchedisequaltothefirstelementofthearray?
(a)Worstcase(b)Averagecase(c)Bestcase(d)Amortizedcase
•Performanceofthelinearsearchalgorithmcanbeimprovedbyusinga
______.
•Thecomplexityoflinearsearchalgorithmis______.

47. ALGORITHM
SORTING

48. SORTING
•Sortingisatechniquetorearrangetheelementsofalistinascendingor
descendingorder,whichcanbenumerical,lexicographical,oranyuser-
definedorder.
•Sortingisaprocessthroughwhichthedataisarrangedinascendingor
descendingorder.
Sortingcanbeclassifiedintwotypes;
1.InternalSorts
2.ExternalSorts

49. SORTING -INTERNAL SORTS
•InternalSorts:-Thismethodusesonlytheprimarymemoryduringsorting
process.Alldataitemsareheldinmainmemoryandnosecondarymemory
isrequiredforthissortingprocess.
•Ifallthedatathatistobesortedcanbeaccommodatedatatimeinmemory
iscalledinternalsorting.Thereisalimitationforinternalsorts;theycanonly
processrelativelysmalllistsduetomemoryconstraints.Thereare3typesof
internalsortsbasedonthetypeofprocessusedwhilesorting.
(i)SELECTION:-Ex:-Selectionsortalgorithm,HeapSortalgorithm
(ii)INSERTION:-Ex:-Insertionsortalgorithm,ShellSortalgorithm
(iii)EXCHANGE :-Ex:-BubbleSortAlgorithm,Quicksortalgorithm

50. SORTING –EXTERNAL SORTS
•ExternalSorts:-Sortinglargeamountofdatarequiresexternalorsecondary
memory.ThisprocessusesexternalmemorysuchasHDD,tostorethedata
whichisnotfitintothemainmemory.So,primarymemoryholdsthe
currentlybeingsorteddataonly.
•Allexternalsortsarebasedonprocessofmerging.Differentpartsofdataare
sortedseparatelyandmergedtogether. Ex:-MergeSort

51. INSERTION SORT
•InsertionSortAlgorithmsortsarraybyshiftingelementsonebyoneandinserting
therightelementattherightposition
•Itworkssimilartothewayyousortplayingcardsinyourhands

52. INSERTION SORT
•Insertionsortsworksbytaking
elementsfromthelistonebyone
andinsertingthemintheircurrent
positionintoanewsortedlist.
•InsertionsortconsistsofN-1
passes,whereNisthenumberof
elementstobesorted.
•Theithpassofinsertionsortwill
inserttheithelementA[i]intoits
rightfulplaceamongA[1],A[2]to
A[i-1].Afterdoingthisinsertion
therecordsoccupyingA[1]....A[i]
areinsortedorder.
Pseudo code
INSERTION-SORT(A)
for i = 1 to n
key ← A [i]
j ← i –1
while j > = 0 and A[j] > key
A[j+1] ← A[j]
j ← j –1
End while
A[j+1] ← key
End for

53. Working of insertion sort –Ascending order
•Westartbyconsideringthesecondelementofthegivenarray,i.e.elementat
index1,asthekey.
•Wecomparethekeyelementwiththeelement(s)beforeit,i.e.,elementatindex0:
–Ifthekeyelementi.eindex1islessthanthefirstelement,weinsert
thekeyelementbeforethefirstelement.(swap)
–Ifthekeyelementisgreaterthanthefirstelement,thenweinsertitremainsat
itsposition
–Then,wemakethethirdelementofthearrayaskeyandwillcompareitwith
elementstoit'sleftandinsertitattherightposition.
•Andwegoonrepeatingthis,untilthearrayissorted
.

54. Example
Letusnowunderstandworking
withthefollowingexample:
Considerthefollowingarray:25,17,
31,13,2whereN=5
FirstIteration:Compare17with25.
Thecomparisonshows17<25.
Henceswap17and25.
Thearraynowlookslike:
17,25,31,13,2

55. EXAMPLE (Cont..)
Second Iteration:.
•Now hold on to the third element
(31) and compare with the ones
preceding it.
•Since 31> 25, no swapping takes
place.
•Also, 31> 17, no swapping takes
place and 31 remains at its position.
•The array after the Second iteration
looks like:
17, 25, 31, 13, 2

56. EXAMPLE (Cont..)
ThirdIteration:StartthefollowingIteration
withthefourthelement(13),andcompareit
withitsprecedingelements.
•Since13<31,weswapthetwo.
•Arraynowbecomes:17,25,13,31,2.
•Buttherestillexistelementsthatwehaven’t
yetcomparedwith13.Nowthecomparison
takesplacebetween25and13.Since,13<25,
weswapthetwo.
•Thearraybecomes17,13,25,31,2.
•Thelastcomparisonfortheiterationisnow
between17and13.Since13<17,weswapthe
two.
•Thearraynowbecomes13,17,25,31,2.

57. EXAMPLE (Cont..)
FourthIteration:Thelast
iterationcallsforthe
comparisonofthelast
element(2),withallthe
precedingelementsand
maketheappropriate
swapping between
elements.
•Since,2<31.Swap2and
31.
Arraynowbecomes:13,
17,25,2,31.
•Compare2with25,17,
13.
•Since,2<25.Swap25
and2.
Insertion sort consists of N -1 passes
Where N=5 So 5-1=4
Number of pass=4(4
th
iteration all the
elements are sorted)
13, 17, 2, 25, 31.
•Compare 2 with 17 and 13.
•Since, 2<17. Swap 2 and 17.
•Array now becomes:
13, 2, 17, 25, 31.
•The last comparison for the
Iteration is to compare 2
with 13.
•Since 2< 13. Swap 2 and 13.
•The array now becomes:
2, 13, 17, 25, 31.
•This is the final array after
all the corresponding
iterations and swapping of
elements.

58. Advantages & Disadvantages
Advantages
•Themainadvantageoftheinsertionsortisitssimplicity
•Italsoexhibitsagoodperformancewhendealingwithasmalllist.
•Theinsertionsortisanin-placesortingalgorithmsothespace
requirementisminimal
Disadvantages
•Thedisadvantageoftheinsertionsortisthatitdoesnotperformwhen
comparedtofewother,sortingalgorithms
•Withn-squaredstepsrequiredforeverynelementtobesorted,the
insertionsortdoesnotdealwellwithahugelist.
•Theinsertionsortisparticularlyusefulonlywhensortingalistoffew
items

59. •Themovementofairbubblesinthewaterthatriseuptothesurface,eachelementofthearraymoveto
theendineachiteration.Therefore,itiscalledabubblesort.
•Bubblesortisasimplesortingalgorithm.Thissortingalgorithmiscomparison-basedalgorithmin
whicheachpairofadjacentelementsiscomparedandtheelementsareswappediftheyarenotin
order
Steps to implement bubble sort:
Assume that there are n elements in the list
1.In first cycle,
1.Start by comparing 1st and 2nd element
and swap if they are not in order.
2.After that do the same for 2nd and 3rd
element. Repeat till n-1
th
and n
th
elements are compared.
3.At the end of cycle one element
(max/min) will be placed as the last
element in of list.
2.The process specified in step 1 is repeated for
another n-2 times, where in each time the
number of comparisons reduce by 1 as the
list of sorted elements grow.
BUBBLE SORT

60. Working of Bubble Sort –Ascending order
Suppose we are trying to sort the elements
inascending order.
Let us now understand working with the following
example:
Consider the following array: -2,45,0,11,-9 where
N=5
First Iteration (Compare and Swap)
•Starting from the first index, compare the first and
the second elements.
•If the first element is greater than the second
element, they are swapped.
•Now, compare the second and the third elements.
Swap them if they are not in order.
•The above process goes on until the last element

61. Second Iteration
•The same process goes on for the
remaining iterations.
•After each iteration, the largest
element among the unsorted
elements is placed at the end.
Put the largest element at the end
Working of Bubble Sort (Cont..)

62. Third Iteration
In each iteration, the comparison takes place
up to the last unsorted element.
Compare the adjacent elements
Fourth Iteration
The array is sorted when all the unsorted elements
are placed at their correct positions.
The array is sorted if all elements are kept in the right order.
Now all the elements are sorted
Working of Bubble Sort (Cont..)

63. ADVANTAGES AND DISADVANTAGES
Advantage:
•Itisthesimplestsortingapproach.
•Theprimaryadvantageofthebubblesortisthatitispopularandeasytoimplement.
•Inthebubblesort,elementsareswappedinplacewithoutusingadditionaltemporarystorage.
Stablesort:doesnotchangetherelativeorderofelementswithequalkeys.
•Thespacerequirementisataminimum
Disadvantage:
•Bubblesortiscomparativelysloweralgorithm.
•Themaindisadvantageofthebubblesortisthefactthatitdoesnotdealwellwithalist
containingahugenumberofitems.
•Thebubblesortrequiresn-squaredprocessingstepsforeverynnumberofelementstobe
sorted.

64. COMPLEXITY –TIME ,
SPACE TRADE OFF

65. SPACE COMPLEXITY
•Spacecomplexityisthetotalamountofmemoryspaceusedbyan
algorithm/programincludingthespaceofinputvaluesforexecution.So
tofindspace-complexity,itisenoughtocalculatethespaceoccupiedby
thevariablesusedinanalgorithm/program.
•SpacecomplexityS(P)ofanyalgorithmPis,
•S(P)=C+SP(I)
•WhereCisthefixedpartandS(I)isthevariablepartofthealgorithm
whichdependsoninstancecharacteristicI.
Example:
Algorithm: SUM(A, B)
Step 1 -START
Step 2 -C ← A + B + 10
Step 3 –Stop
Here we have three variables A, B & C and one
constant. Hence S(P) = 1+3.
Space requirement depends on data types of given
variables & constants. The number will be multiplied
accordingly.

66. How to calculate Space Complexity of an
Algorithm?
•In the Example program, 3 integer variables are used.
•The size of the integer data type is 2 or 4 bytes which depends on the architecture of the
system (compiler). Let us assume the size as 4 bytes.
•The total space required to store the data used in the example program is 4 * 3 = 12, Since
no additional variables are used, no extra space is required. Hence,space complexity for
the example program is O(1), or constant.

67. EXAMPLE 2
•Inthecodegivenabove,thearraystoresamaximumofnintegerelements.Hence,the
spaceoccupiedbythearrayis4*n.Alsowehaveintegervariablessuchasn,iandsum.
•Assuming4bytesforeachvariable,thetotalspaceoccupiedbytheprogramis4n+12
bytes.
•Sincethehighestorderofnintheequation4n+12isn,sothespacecomplexityisO(n)
orlinear.

68. EXAMPLE 3
#include<stdio.h>
int main()
{
int a = 5, b = 5, c;
c = a + b;
printf("%d", c);
}
Space Complexity: size(a)+size(b)+size(c)
=>let sizeof(int)=2 bytes=>2+2+2=6 bytes
=>O(1) or constant

69. Example 4
#include <stdio.h>
int main()
{
int n, i, sum = 0;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]); sum = sum + arr[i];
}
printf("%d", sum);
}
SpaceComplexity:
•Thearrayconsistsofninteger
elements.
•So,thespaceoccupiedbythearray
is4*n.Alsowehaveinteger
variablessuchasn,iandsum.
Assuming4bytesforeachvariable,
thetotalspaceoccupiedbythe
programis4n+12bytes.
•Sincethehighestorderofninthe
equation4n+12isn,sothespace
complexityisO(n)orlinear.

70. •TimeComplexityofanalgorithmrepresentstheamountoftime
requiredbythealgorithmtoruntocompletion.
•TimerequirementscanbedefinedasanumericalfunctionT(n),where
T(n)canbemeasuredasthenumberofsteps,providedeachstep
consumesconstanttime.
•Eg.Additionoftwon-bitintegerstakesnsteps.
•TotalcomputationaltimeisT(n)=c*n,
•where c is the time taken for addition of two bits.
•Here,weobservethatT(n)growslinearlyasinputsizeincreases.
Time Complexity

71. Time Complexity (Cont..)
Two methods to find the time complexity for an algorithm
1.Count variable method
2.Table method
9/11/21 71

72. Count Variable Method
72

73. Table Method
•The table contains s/e and frequency.
•The s/e of a statement is the amount by which the count changes as
a result of the execution of that statement.
•Frequency is defined as the total number of times each statement is
executed.
•Combiningthesetwo,thestepcountfortheentirealgorithmis
obtained.
739/11/21

74. Example 1
749/11/21

75. intsum(intA[],intn)
{
intsum=0,i;
for(i=0;i<n;i++)
sum=sum+A[i];
returnsum;
}
•In above calculation
Costis the amount of computer time required for a single operation in each line.
•Repetitionis the amount of computer time required by each operation for all its repetitions.
•Totalis the amount of computer time required by each operation to execute.
So above code requires'4n+4' Unitsof computer time to complete the task. Here the exact time is
not fixed. And it changes based on thenvalue. If we increase thenvalue then the time required also
increases linearly.
Totally it takes '4n+4' units of time to complete its execution
Example 2

76. Example 3
Consider the following piece of code...
int sum(int a, int b)
{
return a+b;
}
In the above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time to return the
value. That means, totally it takes 2 units of time to complete its execution. And it does not change
based on the input values of a and b. That means for all input values, it requires the same amount of
time i.e. 2 units.
If any program requires a fixed amount of time for all input values then its time complexity is
said to be Constant Time Complexity

77. Cost Times
i =1; c1 1
sum=0; c2 1
while(i<=n){ c3 n+1
i =i+1; c4 n
sum=sum+i; c5 n
}
3n+3
Total Cost =c1 + c2 + (n+1)*c3 + n*c4 + n*c5
The time required for this algorithm is proportional to n
Example 4

78. Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*(n+1)*c5+n*n*c6+n*n*c7+n*c8
The time required for this algorithm is proportional
to n
2
Example 5

79. INSERTION SORT -TIME COMPLEXITY

81. Time Complexity of Bubble Sort

82. Review Questions
Sort the following numbers using bubble sort and Insertion sort
•35,12,14,9,15,45,32,95,40,5
•3, 1, 4, 1, 5, 9, 2, 6, 5
•17 14 34 26 38 7 28 32
•35,12,14,9,15,45,32,95,40,5

83. Review questions
83
1. Calculate the time complexity for the below algorithms using table
method

84. 84
2.
3.
9/11/21

85. MATHEMATICAL
NOTATIONS

86. 1.FloorandCeilingFunctions

87. 2. Remainder Function (Modular Arithmetic)

88. 3. Integer and Absolute Value Functions

89. 4.SummationSymbol(Sums)

90. 5.FactorialFunction

91. 6.Permutations

92. 7.ExponentsandLogarithms

93. ASYMPTOTIC
NOTATIONS
BIG O, OMEGA

94. Asymptotic Analysis
•Thetimerequiredbyanalgorithmfallsunderthreetypes−
•BestCase−Minimumtimerequiredforprogramexecution.
•AverageCase−Averagetimerequiredforprogramexecution.
•WorstCase−Maximumtimerequiredforprogramexecution.
94

95. Asymptotic Analysis (Cont..)
•Asymptoticanalysisofanalgorithmreferstodefiningthemathematical
boundation/framingofitsrun-timeperformance.
•Derivethebestcase,averagecase,andworstcasescenarioofanalgorithm.
•Asymptoticanalysisisinputbound.
•Specifythebehaviourofthealgorithmwhentheinputsizeincreases
•Theoryofapproximation.
•Asymptoteofacurveisalinethatcloselyapproximatesacurvebutdoes
nottouchthecurveatanypointoftime.
95

96. Asymptotic notations
•Asymptoticnotationsaremathematicaltoolstorepresentthetime
complexityofalgorithmsforasymptoticanalysis.
•Asymptoticorderisconcernedwithhowtherunningtimeofanalgorithm
increaseswiththesizeoftheinput,ifinputincreasesfromsmallvalueto
largevalues
1.Big-Ohnotation(O)
2.Big-Omeganotation(Ω)
3.Thetanotation(θ)
4.Little-ohnotation(o)
5.Little-omeganotation(ω)
969/11/21

97. Big-Oh Notation (O)
•Big-ohnotationisusedtodefinetheworst-caserunningtimeofanalgorithm
andconcernedwithlargevaluesofn.
•Definition:Afunctiont(n)issaidtobeinO(g(n)),denotedast(n)ϵO(g(n)),if
t(n)isboundedabovebysomeconstantmultipleofg(n)foralllargen.i.e.,if
thereexistsomepositiveconstantcandsomenon-negativeintegern0such
that
t(n)≤cg(n)foralln≥n0
•O(g(n)):Classoffunctionst(n)thatgrownofasterthang(n).
•Big-ohputsasymptoticupperboundonafunction.
9/11/21 97

98. Big-Oh Notation (O)
9/11/21 98

99. Big-Oh Notation (O)
1<logn<√n<n<nlogn<n
2
<n
3
<…………… <2
n
<3
n
<….<n
n
•Lett(n)=2n+3 upperbound
2n+3≤_____??
2n+3≤5nn≥1
herec=5andg(n)=n
t(n)=O(n)
2n+3≤5n
2
n≥1
herec=5andg(n)=n
2
t(n)=O(n
2
)
99

100. Big-Omega notation (Ω)
•Thisnotationisusedtodescribethebestcaserunningtimeofalgorithmsand
concernedwithlargevaluesofn.
•Definition:Afunctiont(n)issaidtobeinΩ(g(n)),denotedast(n)ϵΩ(g(n)),if
t(n)isboundedbelowbysomepositiveconstantmultipleofg(n)foralllarge
n.i.e.,thereexistsomepositiveconstantcandsomenon-negativeintegern0.
Suchthat
t(n)≥cg(n)foralln≥n0
•Itrepresentsthelowerboundoftheresourcesrequiredtosolveaproblem.
9/11/21 100

101. Big-Omega notation (Ω)
9/11/21 101

102. Big-Omega notation (Ω)
1<logn<√n<n<nlogn<n
2
<n
3
<…………… <2
n
<3
n
<….<n
n
•Lett(n)=2n+3 lowerbound
2n+3≥_____??
2n+3≥1nn≥1
herec=1andg(n)=n
t(n)=Ω(n)
2n+3≥1lognn≥1
herec=1andg(n)=logn
t(n)=Ω(logn)
9/11/21 102

103. Asymptotic Analysis of Insertion sort
•Time Complexity:
•Best Case: the best case occurs if the array is already sorted, tj=1 for
j=2,3…n.
•Linear running time: O(n)
9/11/21 103

104. Asymptotic Analysis of Insertion sort
•Worst case : If the array is in reverse sorted order
•Quadratic Running time. O(n2)
9/11/21 104

105. Properties of O, Ω and θ
Generalproperty:
Ift(n)isO(g(n))thena*t(n)isO(g(n)).SimilarforΩandθ
TransitiveProperty:
Iff(n)ϵO(g(n))andg(n)ϵO(h(n)),thenf(n)ϵO(h(n));thatisOis
transitive.AlsoΩ,θ,oandωaretransitive.
ReflexiveProperty
Iff(n)isgiventhenf(n)isO(f(n))
SymmetricProperty
Iff(n)isθ(g(n))theng(n)isθ(f(n))
TransposeProperty
Iff(n)=O(g(n))theng(n)isΩ(f(n))
9/11/21 105

106. Review Questions
•Indicate constant time complexity in terms of Big-O notation.
A.O(n)
B.O(1)
C.O(logn)
D.O(n^2)
•Big oh notation is used to describe__________
•Big O Notation is a_________functionused in computer science to
describe an____________
•Big Omega notation (Ω) provides _________bound.
•Given T1(n) =O(f(n)) and T2(n)=O(g(n).Find T1(n).T2(n)
106

107. ASYMPTOTIC NOTATION -THETA
MATHEMATICAL FUNCTIONS

108. Asymptotic Notation –THETA Θ

109. Example -THETA
•Show that n2 /2 –2n = Θ(n2 ).

110. Example -THETA

111. Mathematical Functions

112. Mathematical Functions (Cont..)

113. Review Questions
1.Give examples of functions that are in Θ notation as well as functions
that are not in Θ notation.
2.Which function gives the positive value of the given input?
3.K (mod) M gives the reminder of ____ divided by ____
4.For a given set of number n, the number of possible permutation will be
equal to the ____________ value of n.
5.________Notation is used to specify both the lower bound and upper
bound of the function.

114. DATA STRUCTURES AND
ITS TYPES

115. Data Structure
•A data structure is basically a group of data elements that are put together
under one name
•Defines a particular way of storing and organizing data in a computer so
that it can be used efficiently
•Data Structures are used in
∙Compilerdesign
∙Operatingsystem
∙Statisticalanalysispackage
∙DBMS
•The selection of an appropriate data structure provides the most efficient
solution

116. Terms in Data Structure
•Data:Datacanbedefinedasanelementaryvalueorthecollectionofvalues,forexample,student's
nameanditsidarethedataaboutthestudent.
•GroupItems:DataitemswhichhavesubordinatedataitemsarecalledGroupitem,forexample,
nameofastudentcanhavefirstnameandthelastname.
•Record:Recordcanbedefinedasthecollectionofvariousdataitems,forexample,ifwetalkabout
thestudententity,thenitsname,address,courseandmarkscanbegroupedtogethertoformthe
recordforthestudent.
•File:AFileisacollectionofvariousrecordsofonetypeofentity,forexample,ifthereare60
employeesintheclass,thentherewillbe20recordsintherelatedfilewhereeachrecordcontains
thedataabouteachemployee.
•AttributeandEntity:Anentityrepresentstheclassofcertainobjects.itcontainsvariousattributes.
Eachattributerepresentstheparticularpropertyofthatentity.
•Field:Fieldisasingleelementaryunitofinformationrepresentingtheattributeofanentity.

117. Types in Data Structure

118. Types of Data Structure
Primitive Data Structures:
Primitive data structures are the fundamental data types which are supported by a programming language. Some
basic data types are
∙Integer
∙Real
∙Character
∙Boolean
Non-Primitive Data Structures:
Non-primitive data structures are those data structures which are created using primitive data structures.
Examples of such data structures include
∙linked lists
∙stacks
∙trees
∙graphs

119. LINEAR AND NON -
LINEAR DATA
STRUCTURES

120. Types of Data Structure –Non Primitive
Linear
Arrays
•Anarrayisacollectionofsimilar
typeofdataitemsandeachdata
itemiscalledanelementofthe
array.
LinkedList
•Dynamicdatastructureinwhich
elements(callednodes)forma
sequentiallist

121. Types of Data Structure –Non Primitive Linear
Stack
•Lineardatastructureinwhich
insertionanddeletionofelements
aredoneatonlyoneend,whichis
knownasthetopofthestack
Queue
•Lineardatastructureinwhichthe
elementthatisinsertedfirstisthe
firstonetobetakenout

122. Types of Data Structure –Non Primitive -Non Linear
•Thedatastructurewheredataitemsarenotorganizedsequentiallyis
callednonlineardatastructure
•Types
•Trees
•Graphs

123. Types of Data Structure –Non Primitive -Non Linear
TREES
•Atreeisanon-lineardatastructurewhichconsistsofacollectionofnodes
arrangedinahierarchicalorder.
•Oneofthenodesisdesignatedastherootnode,andtheremainingnodes
canbepartitionedintodisjointsetssuchthateachsetisasub-treeofthe
root.

124. Types of Data Structure –Non Primitive -Non Linear
GRAPHS
•A graph is a non-linear data structure which is a collection of vertices (also
called nodes) and edges that connect these vertices.
•A graph is often viewed as a generalization of the tree structure.
•every node in the graph can be connected with another node in the graph.
•When two nodes are connected via an edge, the two nodes are known as
neighbours.

125. Review Questions
1.Compare a linked list with an array.
2.Is Array static structure or dynamic structure (TRUE / FALSE)
3.The data structure used in hierarchical data model is _________
4.In a stack, insertion is done at __________
5.Which Data Structure follows the LIFO fashion of working?
6.The position in a queue from which an element is deleted is called as
__________

126. POINTER

127. Definition and Features of Pointer
⮚Definition:
•Pointerisavariablethatstorestheaddressofanothervariable.
⮚Features
•Pointer saves the memory space.
•Execution time of pointer is faster because of direct access to the memory
location.
•With the help of pointers, the memory is accessed efficiently, i.e., memory
is allocated and deallocated dynamically.
•Pointers are used with data structures.

128. Pointer declaration, initialization and accessing
•Considerthefollowingstatement
intq=159;
Inmemory,thevariablecanberepresentedasfollows−
159
q
1000
Variable
Value
Address

129. Pointer declaration, initialization and accessing(Cont..)
•Declaringapointer
It means ‘p’ is a pointer variable which holds the address of another
integer variable, as mentioned in the statement below −
int *p;
•Initialization of a pointer
Address operator (&) is used to initialise a pointer variable.
For example −
int q = 159;
int *p;
p= &q;
Variable Value Address
q
p
159 1000
1000 2000

130. •Accessing a variable through its pointer
To access the value of a variable, indirection operator (*) is used.
For example −
int q=159, *p,n;
p=&q;
n=*p
Here, ‘*’ can be treated as value at address.
p = &q;
n = *p; n =q
Pointer declaration, initialization and accessing(Cont..)

131. 1D INITIALIZATION &
ACCESSING USING
POINTERS

132. ⮚The compiler allocates Continuous memory locations for all the elements
of the array.
⮚The base address = first element address (index 0) of the array.
⮚Syntax: data_type (var_name)[size_of_array]
•For Example − int a [5] = {10, 20,30,40,50};
⮚Elements
•The five elements are stored as follows −
Pointers and one-dimensional arrays
Elementsa[0] a[1] a[2] a[3] a[4]
Values 10 20 30 40 50
Address1000 1004 1008 1012 1016
Base Address
a=&a[0]=1000
//Declaration
int *p;
int my_arr[] = {11, 22, 33, 44, 55};
p = my_arr;

133. •If‘p’isdeclaredasintegerpointer,then,anarray‘a’canbepointedbythe
followingassignment−
p=a;(or)p=&a[0];
•Everyvalueof'a'isaccessedbyusingp++tomovefromoneelementtoanother
element.Whenapointerisincremented,itsvalueisincreasedbythesizeofthe
datatypethatitpointsto.Thislengthiscalledthe"scalefactor".
•Therelationshipbetween‘p’and'a'isexplainedbelow
P=&a[0]=1000
P+1=&a[1]=1004
P+2=&a[2]=1008
P+3=&a[3]=1012
P+4=&a[4]=1016
Pointers and one-dimensional arrays (Cont)

134. •Address of an element is calculated using its index and the scale factor of
the data type. An example to explain this is given herewith.
•Address of a[3] = base address + (3* scale factor of int)
= 1000 + (3*4)
= 1000 +12
= 1012
•Pointers can be used to access array elements instead of using array
indexing.
•*(p+3) gives the value of a[3].
•a[i] = *(p+i)
Pointers and one-dimensional arrays (Cont..)

135. •Following is the C program for pointers and one-dimensional arrays −
#include<stdio.h> main ( )
{
int a[5];
int *p,i;
printf ("Enter 5 lements");
for (i=0; i<5; i++)
scanf ("%d", &a[i]);
p = &a[0];
printf ("Elements of the array are");
for (i=0; i<5; i++)
printf("%d", *(p+i));
}
Output
When the above program is executed, it produces the following result −
Enter 5 elements : 10 20 30 40 50
Elements of the array are : 10 20 30 40 50
Example Program

136. POINTER ARRAYS
Syntax: data_type (*var_name)[size_of_array]
•Example:
int (*arr_ptr)[5], *a_ptr, arr[5][5] ={{10,20,30,23,12}, {15,25,35,33,88},
{45,25,77,57,54}, {65,34,67,33,99}, {44,45,55,44,65}};
arr_ptr=& arr;
a_ptr=& arr;
arr_ptr++;
a_ptr++;
Example Program
1020
10
1024
20
1028
30
1032
23
1036
12
1040
15
1044
25
1048
35
1052
33
1056
88
1060
45
1064
25
1068
77
1072
57
1076
54
1080
65
1084
34
1088
67
1092
33
1096
99
1100
44
1104
45
1108
55
1112
44
1116
65
arr_ptr
a_ptr

137. Example Program : 1D array using Pointer
#include<stdio.h>
int main()
{
int array[5];
int i,sum=0;
int *ptr;
printf("\nEnter array elements (5 integer values):");
for(i=0;i<5;i++)
scanf("%d",&array[i]);
/* array is equal to base address * array = &array[0] */
ptr = array; for(i=0;i<5;i++)
{
//*ptr refers to the value at addresssum = sum + *ptr;
ptr++;
}
printf("\nThe sum is: %d",sum);
}
Output
Enter array elements (5 integer values): 1 2 3 4 5
The sum is: 15

138. 2D INITIALIZATION &
ACCESSING USING
POINTERS

139. Pointers and two-dimensional arrays
•Memoryallocationforatwo-dimensionalarrayisasfollows−
inta[3][3]={1,2,3,4,5,6,7,8,9};
1 2 3
4 5 6
7 8 9
0 1 2
0
1
2
Row 1-> 1 2 3
a[0][0] a[0][1] a[0][2]
1000 1004 1008
Row 2-> 4 5 6
a[1][0] a[1][1] a[1][2]
1012 1016 1020
Row 1-> 7 8 9
a[2][0] a[2][1] a[2][2]
1024 1028 1032
Base Address=1000=&a[0][0]

140. Pointers and two-dimensional arrays
•AssigningBaseAddresstopointer
int*p
p=&a[0][0](or)
p=a
Pointerisusedtoaccesstheelementsof2-dimensionalarrayasfollows
a[i][j]=*(p+j*columnsize+j)
a[1][2]=*(1000+1*3+2)
=*(1000+3+2)
=*(1000+5*4)//4isScalefactor
=*(1000+20)
=*(1020)
a[1][2]=6

141. Example Program
#include<stdio.h>main()
{inta[3][3],i,j;
int*p;
clrscr();
printf("Enterelementsof2Darray");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%d",&a[i][j]);
}
}
p=&a[0][0];
printf("elementsof2darrayare");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d\t",*(p+i*3+j));
}
printf("\n");
}
getch();
}
Output
When the above program is
executed, it produces the
following result −
enter elements of 2D array 1 2 3 4
5 6 7 8 9
Elements of 2D array are
1 2 3
4 5 6
7 8 9

142. Review Questions
1.Let’sconsider60studentstookthiscourse.Eachstudentissupposedto
givearating1,2,34or5;onebeingbadand5beinggood.Findthe
ratingsarespreadcountthenumberoftimeseachratingwasgiven.
2.WriteaPrograminCforthefollowingArrayoperations
a. Creating an Array of N Integer Elements
b. Display of Array Elements with Suitable Headings
c. Inserting an Element (ELEM) at a given valid Position (POS)
d. Deleting an Element at a given valid Position(POS)
e. Exit.
Support the program with functions for each of the above operations.

143. DECLARING STRUCTURE
AND ACCESSING

144. Definition of Structures
•Structuresareuserdefineddatatypes
•Itisacollectionofheterogeneousdata
•Itcanhaveinteger,float,doubleorcharacterdatainit
•Wecanalsohavearrayofstructures
struct<<structname>>
{
members;
}element;
Wecanaccesselement.members;

145. Declaration of Structures
Syntax:
struct struct_Name
•{
•<data-type>
member_name;
•<data-type>
member_name;
•…
•} list of variables;
Example: Structure to hold student
details struct Student
{
int regNo; char name[25];
int english, science, maths;
} stud;

146. Declaration of Structures
Syntax:
struct struct_Name
{
<data-type>
member_name;
<data-type>
member_name;
…
};
struct struct_Name struct_var;
struct Student
{
int regNo; char name[25];
int english, science, maths;
};
struct Student stud;

147. Declaration of Structures
//Static Initialization of stud
stud.regNo=1425;strcpy(stud.name,“Banu”);
stud.English=78;stud.science=89;stud.maths=56;
//Dynamic Initialization of stud
scanf(“%d %s %d %d %d”,&stud.regNo, stud.name, &stud.English,&stud.science,
&stud.maths);

148. Accessing and Updating Structures
struct Student
{
int regNo; char name[25];
int english, science, maths;
};
struct Student stud;
scanf(“%d %s %d %d %d”,&stud.regNo, stud.name,
&stud.english,&stud.science, &stud.maths);
printf("Register number =%
d\n",stud.Regno); printf("Name
%s",stud.name);
stud.english= stud.english +10;
stud.science++;
//Accessing member
Regno
//Accessing member
name
//Updating member
english
//Updating member

149. Nested Structures
struct Student
{
int regNo; char name[25];
struct marks
{ int english, science, maths;}
}
Amar;
Amar.regNo;
Amar.marks.english
;
Amar.marks.science
;
Amar.marks.maths;
struct Student
{
int regNo; char
name[25];
struct m marks;
} Amar;
struct m
{
int english; int
science;
int maths;
};
struct Student
{
int regNo; char name[25];
struct {int english, science, maths } marks;
} Amar;

150. Example Program
#include <stdio.h>
#include <string.h>
struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};
/* book 1 specification */ strcpy( Book1.title, "C
Programming"); strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407
int main( )
{
struct Books Book1; /* Declare Book1 of type Book */
struct Books Book2; /* Declare Book2 of type Book */

151. Example Program
/* book 2 specification */ strcpy( Book2.title,
"Telecom Billing"); strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;
/* print Book1 info */
printf( "Book 1 title : %s\n", Book1.title);
printf( "Book 1 author : %s\n", Book1.author);
printf( "Book 1 subject : %s\n", Book1.subject);
printf( "Book 1 book_id : %d\n", Book1.book_id);
/* print Book2 info */
printf( "Book 2 title : %s\n", Book2.title);
printf( "Book 2 author : %s\n", Book2.author);
printf( "Book 2 subject : %s\n", Book2.subject);
printf( "Book 2 book_id : %d\n", Book2.book_id);
return 0;
}
OUTPUT
Book 1 title : C Programming
Book 1 author : Nuha Ali
Book 1 subject : C Programming Tutorial
Book 1 book_id : 6495407
Book 2 title : Telecom Billing
Book 2 author : Zara Ali
Book 2 subject : Telecom Billing Tutorial
Book 2 book_id : 6495700

152. Example Program
#include<stdio.h>
structstudent
{
charname[20];
intid;
floatmarks;
};
voidmain()
{
structstudents1,s2,s3;
intdummy;
printf("Enterthename,id,andmarksofstudent1");
scanf("%s%d%f",s1.name,&s1.id,&s1.marks);
scanf("%c",&dummy);
printf("Enterthename,id,andmarksofstudent2");
scanf("%s%d%f",s2.name,&s2.id,&s2.marks);
scanf("%c",&dummy);
printf("Enterthename,id,andmarksofstudent3");
scanf("%s%d%f",s3.name,&s3.id,&s3.marks);
scanf("%c",&dummy);
printf("Printingthedetails....\n");
printf("%s%d%f\n",s1.name,s1.id,s1.marks);
printf("%s%d%f\n",s2.name,s2.id,s2.marks);
printf("%s%d%f\n",s3.name,s3.id,s3.marks);
}

153. Example Program
Output
Enter the name, id, and marks of student 1
James
90
90
Enter the name, id, and marks of student 2
Adoms
90
90
Enter the name, id, and marks of student 3
Nick
90
90
Printing the details....
James 90 90.000000
Adoms 90 90.000000
Nick 90 90.000000

154. DECLARING ARRAY OF
STRUCTURES AND
ACCESSING

155. Array of Structures
struct Student
{
int regNo; char name[25];
int english, science, maths;
};
struct Student stud[10];
scanf(“%d%s%d%d%d”,&stud[1].regNo,stud[1].name,&stud[1].english,&stu
d[1].science,
&stud[1].maths);
printf("Register number =
%d\n",stud[1].Regno); printf("Name
%s",stud[1].name); stud.[1]english=
stud[0].english +10;
stud[1].science++;
//Accessing member
Regno
//Accessing member
name
//Updating member
english
//Updating member

156. Example Program
#include<stdio.h>
#include<string.h>
structstudent{
introllno;
charname[10];
};
intmain()
{
inti;
structstudentst[5];
printf("EnterRecordsof5students");
for(i=0;i<5;i++){
printf("\nEnterRollno:");
scanf("%d",&st[i].rollno);
printf("\nEnterName:");
scanf("%s",&st[i].name);
}
printf("\nStudentInformationList:");
for(i=0;i<5;i++){
printf("\nRollno:%d,Name:%s",st[i].rollno,st[i].name);
}
return0;
}

157. Example Program
OUTPUT
Enter Records of 5 students Enter
Rollno:1 Enter Name:Sonoo Enter
Rollno:2 Enter Name:Ratan Enter
Rollno:3 Enter Name:Vimal Enter
Rollno:4 Enter Name:James Enter
Rollno:5 Enter Name:Sarfraz Student
Information List: Rollno:1, Name:Sonoo
Rollno:2, Name:Ratan Rollno:3,
Name:Vimal Rollno:4, Name:James
Rollno:5, Name:Sarfraz

158. Review Questions
1.Write a C program for student mark sheet using structure
2.Write a C program using structure to find students grades in a class
3.Write a C program for book details using structure
4.Calculating the area of a rectangle using structures in C language.