0 ratings0% found this document useful (0 votes) 77 views30 pagesDsa chp-1 - English
data stuacture handwritten notes ch-1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Unit-1 Basic Concepts of Data Shite leg@Z
4 Stmwchac_ Basic.
conce ph
: Data ; igo collecbon of ni paar >—alpha bet i
and Sumbal which combine and nepnesent the
incfitmaly
-_ row
7 Stnuctune
“tallow to ghoup nonhomogeneous clement
Eogetisch
Dota Structure.
ar ie 0% mathe matical sepne sentation of date
is caller data tauctwe
Data Stach i &__sepnese atation eon Logica
ne 7 : indrviclual
of dota
ance i ni; i
i ani i i
used ef Fe cient
=) Fon Data Sta%tne fll wing points as cansidered
4. Armount of rnemnony — s0guined tm chose
2) Arnouat of time witted +. process thy laf
3. Reprsenfation of dota in me mony
4. Openchin _perdoum on a data
&.
= Dota Stnuctue ho. fillosiag feotous
4.1 “They Con be dlecnyn pase Inte theis Componen
element 2. the cunnonge ment fF element: 6 the rain
—Acohses of "the ———___
_ dal Types — Dat :
Date _Stiw. Ss g__xspactemlation of ¢ >
logical xe loti xi indivt ™
lems of date
Data Stauchos i woninty —dividled inte ty
Linas Stauchao ond —_Nown= Livan Data
Dete sauae
|
Lineon Data | | Won = lineon
St Chae lout Structww
! ! LT
eanay] [stock | Loueue | Tinbtist! | set] Frabte | Teall
| ] 5 ane
1 | Singly link lear
[Simple | [Cincatas | id 09. Aniay, Stack, Queue, Bivkdst
7 al Non-linear Dota Structure.
Tn this Dolo Stele olata ane not ste ol
in & eguence _ynannen_
e4..“Tnee Garoph, Set “Table
2. Homogenous Data Stwelune
“The. __Dote Strveinny in hich alle tha Blements
hove Sarna. dototype. i colle al Hornogencs Dota
_Stauchao
cg. Aanoy
on
The DoteaStautture —? which data _h dif ers
Di Ffen nat clotatipe is oiled Aan = hone gencas
Data Stnucture
ey | Structure, Union, Clas:
i ie
ben the dota net memnony — dunamivall, mean
Tot ¢ nuntime “then that’ ype of “stauchne
i Called Dynami Dota _ Stnuchme
cg J inkl. t:
6. Stedte Data __ 5 taucture
In the Stotic Dots Stnuchre the Sige of he
dota. ¢ fixed ond it tant# be _efAonge
TT
i duxing the exeretimn —of ——_ aroqgseaun
4. Ani Ha Primitive — e __Non= Prinaltice a
Titanic ns | ____~
T
|
[Primitive Dobe Stuucts [Non=Prism’tive i Data Staaten
| |
| | | | |
Featege | [toate] [ Chosoeta!
/ [anray| | Lift | | Gle: IC
Theolean | . ar
Late Non \insar | |
1 |
| | |
Tstock | I @ueuel Wintevstl [reo | | Gasp] |
Paimitive Deto Sbauctiar.
Primitive Dota Stouchre ane Aindawatel dade ype,
}
tshich ons suppanfed cm paogéammn'ag leaQuages Tt
1 2!
int, Phat, chniect, bnale
Tat
“i
im ’
“it is G_datatype whith ove toro, true andl
i = - = ) Aveauge Case __onulysis gut O aaal behovi a Ef 1.4 Almay
An —anray is _n gnoup of element _sahich Lavitain
a amen —Gnd sama datdype
Syntax i= ‘
ee on = datatype __ovrnay name [sige Is
Amn is__one _tyac__of since —efoda slaarane
wwhich _ choays stomt vitta _iadex _O..
_ 3 Chota etenstics of —Armny 7
opt
> Annoy ha 2 which is called
clement
2 Fvey element hes _unigue number which is
callet _addcas
— Element numbers ane honed by name and
index of whene index start _fhom _zer0
= All the elemeSt of an hoe Common nam
= Caray clements _ ase alusiys stoned in
____SegWenrial manny
— Ino insertion and deletion ig slower
and time Consuming. but otanchoy and santing—
oss fast .
_—>_When stray is declared but vot initiahse
Contains Soubage value a ___4e = Types iF _ Almay —=——
Thee _on__-Hour type —of
1. One__Dimensional _Asinay —
2. Two Bimensional A =
3. Muli Bimen sional Annay—
be all [One Dimensional A: $<
An tein ig 9, group of element” wshins
—tentain Ame nome ond! same clatertype
Le wha sete
Tr dokulype —oamoy-nomaL sige]
(Eaaagl 2
# include < stdioh >
Fteivclude < Conio.h >
“void “vnain( >
int_n,i, ol so)s
| clascn 5
I printf (* ne ety ov wert fo cabs?
I ‘stant (y
| print t ( ? ari 5
I or C203; Ae
= ! print CO nf /. al=” j 33
atch 5, Pe a a printf Ct
PeGis 041 wn 3 it+)
- paintf (\n nlndl= 2d” i
4
3 getch (V5
I
| Output :-
How nay dita you went to enter = 4
JEvten Date i=
nlol= 1
InfiJ=2
|af2J=3
nl3Jah
Entened Dota one i=
nfoJ= 1
[rt=2
[2)=3
[nal = ra y!””~—“—sCs—s
2 Tao Din mensional — | Anna Wy =
_Someti Dimensions! OY Kaa — aha
igunmne. ded likes —in_|
mone.__thar on dimen
5 motrix then we we Tao — Dimen! ioael _Arvay. —_ |
Syntax as F
Example =
## include 2000 +10
= 2010
Adduoss fF aliitid ; Sais
2. Colmar 0%
pte ora sf onnay
Ainst cel of the aahay. 7
Co.
ys occupied by econd (Galuan of
T o
| ( ae
{ 9 etal I ule Tol Ua Cols
lq - et
se CH aN
Tt in oun example Oust base ne i br
then —neaeennny valleratinn = will bes this
Chesie ~. joe “nant. terecaterelt i considening a
dato typ of elements
2002 200L-
Colie)] fol
Coli —Colons
00S 2008 20 2012 2044,
Tololato Oia) ololsialny
Column } Column
Addue calculation fon _pexticulan _anteyy
oa AL 1 y= Bae Addisas + b/] mC +iyT
Hest =
I Bore Addorre = 417° clemat ameotty —_cllocaf
ponfirulan dathhy re
Me Mamben of ror
‘Lxample:— |
Find ths ramon —allvection of a £1 [1 le
Ailsa (ALAC = as Addy 2 Wa +
zon + 20201) 44) +
2ood + 2 (2+) t-
Zon + 2 (3)
2000 +6
2006
| Dadsaas of _ aLaist. TS 2006
q
v
T
vl we » _ 1.8 Oven ew cf diflexeat —dtay —openatinns
p Various _opennbions of arse rote ab
Hescoube be lora
FG) Tanseation
pT Adding a new data element inte the nero
(i) Deletion
Removing a_date element from ths _somnay.
(ii) Travensal es stsev seat __
Accessing 7 dato clement +a _teeieaf bs onee in
such _& esti thot all the data Clemaat
Gus __paacessed
St a
_ Finding fotaton fon _specific fata in
¢,
the. ray
CY Sonting
Awa Zain data element in _loarcaf (in
oscendiuf on descending D onder 7 Ezal Allpanition fon __0910y opeubus
() Trsestion %- 7
Thi openation insets an lemevt
-dinsessive / cna
into___one
pee Tnseat (AP, x)
| Hoxe
As it's on oniay
P=y Positem ot which you wont to ingen _
NEw) lement.
NZ Number f element in =the _ahnay.
X=) Value of the neo “elenwf to be
inserted ji the _onoy
|| Temp
| A peapead <— alten l
I TEmp <— TEmp-t
Step axl oInsent element
Ale) <— 7
Step 4i- | Increment size
eof the coma
eS A <—_ y+" :
Step J: [Finished J
Eyit
Ci) Deletion =
This gpexahon i used +o delete, element
Frown one dimensiona Caray
Algorithm Derete Ca, Pw >
Heso,
A= Tt’s on cana
ra
oO
=) The “postion! of «which “you want to
delete an element g
=) Wurbens of elesaents in tht onnay—
Step t= | Tnitelsation |
TEMP <— P
Giep 2:-[ Shift the element oa positien up
Repeat while Téme grates < /-1
Afteml <— Alteme+1 |
TEMP <— Temp +i
Sten 3] Decnement size of the arnay |
N<— py-t° ——— Step tl “Step be] pg
(Cit) Taowensal =
Thi ae ti —
dimensional! _onoy, fox in. entry om —dlisplayiag ©
cLimensiona/ —_Gseuay-—_———__=
(a, 1a,ue)
Fetwent sf one.
Algeni-tuea = TRAVERSE
Hex
A= It’s fon —onhay -
LB=y Lowen limit of __on onnay
UB =) Uppen Limit of an onnay,
Step 1 [ Taitiols T
CouvrT <— 18
Step 2t- C Proce Annoy |
ee step 4
while (Couwt < UB)
Step ae | Traverse. Antay |
wide ALCouwil” on Read AL cout
Shep kim Ininement Counten |
COUWT <— Count + 4
Shep Site [Finished 1 : we
i Exit — Go Seanchi = : Oo Sasa
This “Wenation is used to__seanch —_panticular
Ly clameat in _one__ dimensional Any.
—— Algarten = Searcu CA, Vx)
Hone,
A =Y Tt -an__Asnay
=) Element which you want ty search
=) Namben of clernent in the
T annoy.
Step 1-1 Ini
Sp Fi dieige L_
Step 2 i L Penfomm Seanch |
Repeat while AL Count J
CovwT_< Count + 1.
Shep 2 to [Succesfil Search 2 I
if Comvt = W then
te U Z
clee Z ;
waite“ Successhel seanch ’ - nf ¥) Son tng
—— —atnay —_in ascending —
a
a
This " openation 32 used _4o sont the. —elenaeals gp
_ ordi _on—desteathing onda
Alponithre = SortCA, aL)
Hert,
+
A=) Tt, fn Arntuy
=) Number of element in the _anngy
Step t = C tnitialize T
LAST <
Step 23 Leenham Poss l
Re peat. thi te, 5S fon FASS = 1.
A= 1.
Step Din Pitetialige — SWAP fin each ..'PASS
Teme <— 0
Sip bp [ Penanmn pain wise Com pasar al
Repeat fon T=1,2,.., LAST -1
te alt] > alr+1J
then
Ali <->» »lT+4)
Temp <— Temp +4.
Step 5 [ Finished | —
1 Seanchiag tn element indo amnay
Soniting. ¢ Seanthing ane Funda meatal opera hans
+ Se
op jon fF finding letation of party cules
deta item fnew alleen f Gisen__ittens,
— A table on o file isn collector of xocond
and each _serond ha ing__One._on mone freld.
— There ane two tne of conching method
Ok use = =
1) Lineat Seanch Segueatial Seanch
z Biaaay Seanch
1) / inean Seach :-
Thi. i the Simplest techigu do tind out
‘ t luce F5 s. table
list
La __+this _technigue seanch th glue. of
cuticuhn elemeat in ‘table on a _list ina
6. gueatia wnonnen until the dlesive second
” fou nd.
i + LiwepR seagcw Cr, x)
Howe,
= Total element
Value to be seanch in the. [rad Step 3:- | Find value
ca te (LiK1= x)
then FLAG <— 0
Gap b | Check frat vase L
. If Fhag= t :
I then waite (° Unsuccesshl _Seaach D,
| else.
I wonite C* Sucresshi/ sith”)
=D Finished |
Ce ° Exit
Ib
Seach = |
\ B
inasy
1 Oo.
_seaach ng an lement value fom 800
toble 70. list:
i Binany search —_aloanithm take — less time. Hus —
linea) conth, “Thi. technique i oy [—
fhicienf. 47s
Allgonithe:= _BIvary searcy (List, p/, x)
Henne,
ieee se annoy of +h elernent
N= Total element
= Valk peel conch
—? LOW, HIGH , MIDDLE
west, middle ‘nit ?. ane hi
element
Step te | Tita fon Searching |
O, HtGe <—" w-1, FLaGeJ
Step wf Repect Code fon caching I
Repeat thay hep ~h
vhile J ow < Aten
Step 3:1 Ftad out mine |
MALDPLE <— LowW+HiGy
2
Step bb s- [ Find out canthing element T
Tr x LIST LMIDpL
then HIGH <—— Mzpp.e -4
elseif > List[mrppes
LOW MIDDLE + 4
else if = 1157 [mip pred
wa then FLAG EO
EXIT Step 5 [Seanch i sutcesst.| of _unsut eth]
| 7 fa bo <— DO _
= ce “ uccesfe) 2) >
se =
eT sacl Seach 2)
iz Step $= Joe ehed ||
Exit
