ساختمان داده ها صفحه

ساختمان داده ها صفحه

ساختمان داده ها صفحه 1

Array آرایه ها

آرایه نوعی ساختمان داده است که عناصر آن هم نوع بوده و هر یک از عناصر با یک اندیس به صورت

مستقیم قابل دستیابی است . آرایه می تواند یک بعدی , دو بعدی و یا چند بعدی باش د. آرایه ها ی

دو بعدی را با نام ماتریس می شناسیم.

[L1 … U1 , L2 … U2 , Ln … Un]

Array [L … U] of items

تعداد عناصر آرایه = U – L + 1

بعدی n تعداد عناصر آرایه = [U1 – L1 + 1][U2 – L2 + 1][Un – Ln + 1]

فضای اشغال شده توسط آرایه (فضای مورد نیاز) = (U – L +1) × n

در A اگر آدرس شروع آرایه در حافظه 1000 باشد 25 Float [ مثال : در یک آرایه به نام [ 200

کدام آدرس قرار دارد.

A[i] = (i – L) × n + α

ام در حافظه i 25 ) = محل عنصر – 0) × 4 + 1000 = 1100

آرایه های دوبعدی یا ماتریس ها به دو روش در حافظه ذخیره می شوند.

3 2

4

6

5

3

1

2

×

  





  





Row Major 1. روش سطری

0 1 2 3 4 5

2 5 1 6 3 سطری 4

Column Major 2. روش ستونی

0 1 2 3 4 5

2 1 3 5 6 ستونی 4

A : Array [L1 … U1 , L2 … U2] of items

تعداد عناصری = [U1 – L1 + 1][U1 – L2 + 1]

در روش سطری A[i , j] آدرس = [(i – L1) × (U2 – L2 + 1) + (j – L2)] × n + α

در روش ستونی A[i , j] آدرس = [(j – L2) × (U1 – L1 + 1) + (i – L1)] × n + α

صفحه 2 ساختمان داده ها

مثال : طبق آرایه زیر , آدرس های خواسته شده را محاسبه نمائید.

L1 … U1 L2 … U2

A : [1 … 3 , 1 … == [ 2 􀃎 داریم C در زبان ==􀃎 A[3][2]

  





  





4

6

5

3

1

2

A [3 , 2] = (3 – 1) × (2 – 1 + 1) + (2 – 1) = 2 × 2 + 1 = روش سطری 5

A [3 , 2] = (2 – 1) × (3 – 1 + 1) + (3 – 1) = 1 × 3 + 2 = روش ستونی 5

A [1 , 2] = (1 – 1) × (2 – 1 + 1) + (2 – 1) = روش سطری 1

A [1 , 2] = (2 – 1) × (3 – 1 + 1) + (1 – 1) = روش ستونی 3

اگر این آرایه از محل 1000 A [1 ... 100 , 1 ... 26] of integer تمرین : در یک آرایه به شکل

در روش A [20 , در روش سطری و محل داده [ 4 A [60 , حافظه شروع شده باشد محل داده [ 6

ستونی کدام آدرس حافظه است.

A [60 , 6] = (60 – 1) × (26 – 1 + 1) + (6 – 1) × 2 + 1000 = 4078

A [20 , 4] = (4 – 1) × (100 – 1 + 1) + (20 – 1) × 2 + 1000 = 1638

در آرایه های دو بعدی مربعی یا ماتریس های مربعی که کلیه عناصر بالای قطر اصلی آن ص فر باشند

یک ماتریس پایین مثلثی تشکیل می گردد و برعکس اگر کلیه عناصر پایین قطر اصلی آن صفر باشند

یک ماتریس بالا مثلثی تشکیل خواهد شد . در یک ماتریس پایین مثلثی یا بالا مثلثی حداکثر

اندازه هر بعد ماتریس است. n عنصر غیر صفر داریم که

2

n(n +1)

  





  





0 0 4

0 2 5

1 6 7

6 = بالا مثلثی

2

3(3 + صفر = ( 1 حداکثر عناصر غیر

A [i , j] = 0 i > j =====> ماتریس بالا مثلثی

A [i , j] = 0 i < j =====> ماتریس پایین مثلثی

ساختمان داده ها صفحه 3

اگر اندازه ابعاد ماتریس های مثلثی افزایش یابند این ماتریس ها حاوی تعداد زیادی صفر خواهند بود

که ذخیره کردن سطری یا ستونی ماتریس به طور کامل در حافظه باعث هدر رفتن بخشی از فضای

حافظه می گرد د. به همین دلیل ماتریس های مثلثی را بصورت سطری یا ستونی بدون در نظر گرفتن

صفرها در حافظه ذخیره می کنند.

سطری <===== پایین مثلثی j

2

i 1 i +

( − ) ×

  





  





3 1 1

2 5 0

1 0 0

=====>

ستونی <===== بالا مثلثی i

2

j 1 j +

( − ) ×

  





  





0 0 4

0 2 5

1 6 7

=====>

1 2 3 4 5 6

1 2 5 3 1 پایین مثلثی 1

1 2 3 4 5 6

1 6 2 7 5 بالا مثلثی 4

صفحه 4 ساختمان داده ها

جمع ماتریس ها

در جمع دو ماتریس , حتماً باید یک ماتریس با یک ماتریس جمع شده و نتیجه نیز

خواهد ش د. در این عملیات عناصر دو آرایه نظیر به نظیر با یکدیگر جمع خواهند m× یک ماتریس

شد.

m× n m× n

n

Am×n + Bm×n = Cm×n

for (i = 0 , i < m , + + i)

for (j = 0 , j < n , + + j)

ij ij ij C = a + b

ضرب ماتریس ها

در عمل ضرب , یک ماتریس و یک ماتریس با یکدیگر ضرب شده و ماتریس بدست

آمده نیز دارای سطر و ستونهایی می باشد که سطر ماتریس بدست آمده با تعداد سطرهای ماتریس اول

و ستون ماتریس بدست آمده با تعداد ستونهای ماتریس دوم برابر است.

mL A Ln B

i

n

k

L

k

L

i

Cmn = Am ×B

   



  





−

−

−

−

−

−

=

    





    





  





  





5

1

1

2

3

1

0

1

1

1

2

2

3

1

0

5

4

1

2

3

3 × 4 × 4 × 2 = 3 × 2

for (i = 0 , i < m , + + i)

for (j = 0 , j < n , + + j)

{

C 0 ij =

for (k = 0 , k < L , + + k)

ij ik kj ij C = a × b + C

}

ساختمان داده ها صفحه 5

را در حاصلضرب دو ماتریس مثال قبل بدست آورید. C [1 , تمرین : مقدار [ 0

کنیم . پس بنابراین Trace بالا را for جواب : برای بدست آوردن مقدار خواسته شده باید حلقه های

داریم :

= ij C 0

ij ik kj ij C = a × b + C

= ij C 2 × 1 + 0 = 2

= ij C 5 × 0 + 2 = 2

= ij C 3 × 1 + 2 = 5

= ij C 1 × 3 + 5 = 8

i j k L ij C

1 0 0

1

2

3

4 0

2

2

5

8

ترانهاده

برای اینکه ترانهاده یک ماتریس را بدست آوریم جای سطرها و ستونهای ماتریس عوض می شوند.

   



  





→ 







7

0

1

5

3

2

7 A

5

0

3

1

2

A T

  





  





→

  





  





4 5 8

0 2 3

2 1 1

1 3 8

1 2 5

2 0 4

Am×n

for (i = 0 , i < m , + + i)

for (j = 0 , j < n , + + j)

A [j] [i] = A [i] [j]

صفحه 6 ساختمان داده ها

جستجوی خطی در آرایه

Array A[n] , x

Int search (A[n] , x) ;

{

int i = 1 ;

while (i <= n && A[i] != x)

i + + ;

if (i > n ) return – داده پیدا نشده // 1

else return i // داده در محل اندیس آرایه است

}

1 2 3 4 5

1 5 2 8 6

n x i A[i]

5 8 1

2

3

4

1

5

2

8

x = A[4]

جستجوی دودویی برای آرایه های مرتب

Int bsearch (A[n] , int x , int L , int U)

{

int i ;

while

{

i = 





+

2

L U

 

;

if ( x < A[i] ) U = i – 1

else if ( x > A[i] ) L = i + 1

else return i // است i داده در اندیس

}

return – داده پیدا نشده است // 1

}

ساختمان داده ها صفحه 7

x i L U A[i]

8 5

2

4

3

1

3

4

10

4

12

2

5

8

جمع دو چندجمله ای بوسیله آرایه

P(x) = anxn + an–1xn–1 + …. + a2x2 + a1x + a0

an an–1 an–2 …. a1 a

P(x) = 3x2 + 5x + 2

P(x) = 3x3 + 3

P(x) x100 + 2

یا پشته Stack

لیستی است که اعمال ورودی و خروجی یا اض افه و حذف در آن از یک طرف لیست انجام Stack

می گویند. بدین معنی که آخرین Last In First Owt (LIFO) می شود. به این جهت به آن لیست

پشته می گوین د. با افزودن داده top ورودی به پشته , اولین خروجی خواهد بو د. عنصر بالایی پشته را

از پشته قرار می گیر د. برای خارج کردن top یکی زیاد شده و داده در محل top روی پشته , متغیر

top خارج می گردد و متغیر Stack قرار گرفته از top یک عنصر از پشته نیز داده ای که در محل

می تواند تا top , عضوی n صفر است و با افزودن داده به یک پشته top یکی __________کم می شو د. مقدار اولیه

تغییر کند. n مقدار

Top = === 0 􀃎 پشته خالی است

Top = n ===􀃎 پشته پر است

را در x داده Push (x) . کردن می شناسیم pop کردن و push دو عمل اصلی برای پشته ها را با

ذخیره می کند. x عنصر بالای پشته را در متغیر pop بالای پشته قرار می دهد و عمل

x = pop ≡ pop (x)

0 3 5 2 +

3 0 0 3

=

3 3 5 5

1 ضریب 2

100 توان 0

صفحه 8 ساختمان داده ها

Stack : Array [1 .. n] of items

int pop ( ) void push (int x)

{ {

int x ; if (top = = n)

if (top = 0) {

{ C out << “ ; “ پشته پر است

C out << “ پشته خالی است “ ; return – 1 ;

return – 1 ; }

} else

else {

{ top + + ;

x = Stack [top] ; Stack [top] ;

top = top – 1 ; }

} }

return x ;

}

چقدر است؟ C و B و A مثال : مقدار نهایی

n = 5 A = 10 B = 2 C = 5

push (B)

push (A + B)

pop (C)

push (A – B)

push (C)

push (B)

pop (A)

pop (B)

push (A × B)

push (C)

push (A)

pop (B)

pop (C)

pop (A)

2

2 12

12 24

12 8

2

A B C

10 2 5

2 12 12

24 2 12

ساختمان داده ها صفحه 9

پشته های چندگانه

برای نشان دادن بالاترین top پشته دوگانه : برای پیداسازی دو پشته در یک آرایه نیاز به دو متغیر 1

در جهت عکس یکدیگر top و 2 top برای بالاترین عنصر پشته دوم داریم . 1 top عنصر پشته اول و 2

است. top2 = n + و مقدار اولیه 1 top1 = حرکت می کنند. مقدار اولیه 0

top1 = === 0 􀃎 پشته 1 خالی است

top2 = n + === 1 􀃎 پشته 2 خالی است

top2 = top1 + === 1 􀃎 آرایه پر است

دنباله های قابل قبول در پشته ها

هرگاه اعدادی را به صورت مرتب شده صعودی داشته باشیم و بخواهیم اعداد دیگری را از آن استخراج

کنیم باید این قانون را راعایت کنیم که اعداد بزرگتر در صورتیکه اعداد کوچکتر در پشته قرار

1 را در نظر می گیری م. عدد 2 در , 2 , 3 , نگرفته اند حق قرار گرفتن در پشته را ندارند . مثلاً اعداد 4

شود push شده باشد و عدد 3 زمانی می تواند push شود که حتماً عدد 1 push صورتی می تواند

شده باشند. push که اعدا 1 و 2 قبلاً

1 را داریم. کدامیک از اعداد زیر را می توانیم تولید کنیم ؟ , 2 , 3 , مثال : چهار عدد 4

2 1 3 4 3 1 4 2 3 2 4 1 4 2 3 1 4 3 1 2

push 1

push 2

push 3

pop 3

push 1

push 2

push 3

push 4

pop 4

push 1

push 2

push 3

push 4

pop 4

pop 3

push 1

push 2

pop 2

pop 1

push 3

pop 3

push 4

pop 4

قابل تولید نیست

push 1

push 2

push 3

pop 3

pop 2

push 4

pop 4

pop 1

قابل تولید نیست قابل تولید نیست

داشته باشیم بطوریکه c و b و a 1) و سه عدد 2 3 اگر اعداد به صورت صعودی داده شوند ( 4

قابل تولید نیست. abc در اینصورت دنباله b < c < a

1 n

↑

top1 ↑

top2 = n + 1

صفحه 10 ساختمان داده ها

ارزشیابی عبارت

اولویت عملگر

را داشته باشیم اولویت عملگرها را به صورت زیر می نویسیم : a × b + c / d بطور کلی اگر عبارت

1. ( )

2. Not , – ( توان , (قرینه

3. and , × , / , mod

4. OR , + , –

5. < , > , < = , > = , < > (! =)

نکته : بین عملگرهایی که اولویت مساوی دارند عملگری زودتر محاسبه می گردد که سمت چپ باشد.

روش نمایش عبارات محاسباتی

میانوندی infix a + b

پسوندی postfix ab +

پیشوندی prefix + ab

تبدیل عبارات میانوندی به پسوندی و پیشوندی بدون استفاده از پشته

-1 پرانتز گذاری

-2 برای تبدیل به پیشوندی , درون هر پرانتز عملگر را به سمت چپ منتقل می کنیم.

-3 برای تبدیل به پسوندی , درون هر پرانتز عمگلر را به سمت راست منتقل می کنیم.

-4 پرانتزها را حذف می کنیم.

مثال :

((a + (b × (c ↑ a )))− (b / c ))

postfix = (a(b( ca) )↑ × + (bc)/)= abca ↑ × + bc /−

prefix = − +a × b ↑ ca / bc

1

2

3

4

5

ساختمان داده ها صفحه 11

postfix به infix استفاده از پشته در تبدیل عبارات

را از چپ به راست پیمایش می کنیم. infix -1 عبارت

می کنیم. push -2 پرانتز باز را در پشته

-3 عملوندها را در خروجی می نویسیم.

پشته دارای عملگری با اولویت بیشتر یا مساوی top -4 در صورتیکه به یک عملگر رسیدیم اگر

ک رده و در خروجی pop پشته را top می کنیم در غیر اینصورت عملگر push نبود آنرا

می نویسیم.

می کنیم تا به اولین پرانتز باز برسیم. pop -5 هرگاه به پرانتز بسته رسیدیم آنقدر

مثال :

((a + (b × (c ↑ a )))− (b / c ))

abca ↑ × + bc /− ↑

×

بنویسید. postfix مثال : با استفاده از پشته , عبارت زیر را به صورت

a + b× c ↑ a − b / c

↑ abca ↑ × + bc /−

(

( /

+ (

( –

(

× /

+ –

صفحه 12 ساختمان داده ها

بنویسید. postfix مثال : با استفاده از پشته , عبارت زیر را به صورت

a +(b×c) ↑ a − b / c

× abc× a ↑ +bc /−

از دو پشته استفاده می کنیم . یکی پشته عملوندها و prefix به عبارات infix برای تبدیل عبارات

postfix به infix کردن در پشته عملگرها مانند تبدیل pop کردن و push . دیگری پشته عملگره ا

شدن هر عملگر pop می کنی م. در صورت push است. با رسیدن به هر عملوند آنرا در پشته عملوندها

در prefix شده و با عملگر مربوطه به شکل pop از پشته عملگرها , دو عملوند بالای پشته عملوندها

است. postfix به infix می شود. بقیه قوانین مانند قوانین push پشته عملوندها

بنویسید. prefix به infix مثال : عبارت زیر را بوسیله پشتبه از

a + (b× c) ↑ d / a − c× b

× c d a d

( ↑ / × b ×bc ↑ ×bcd /↑ ×bcda

+ - a + a / ↑ ×bcda

− +a / ↑ ×bcda × cd

تبدیل کنید. prefix زیر را بوسیله دو پشته به infix مثال : عبارت

a + b× c ↑ (2 − b)× c /(d + a)

- b

( + 2 -2b a

↑ ( c ↑ c-2b c d +da

× × / b ×b↑ c-2b ××b↑ c-2b /××b↑ c-2bc+da

+ a +a/× ×b↑ c-2bc+da

infix به postfix تبدیل عبارت

تبدیل کر د. برای این منظور infix ورودی را به postfix می توان رشته Stack با استفاده از یک

( ↑ /

+ –

ساختمان داده ها صفحه 13

می شو د. با رسیدن به هر push را از چپ پردازش می کنیم . هر عملوند درون پشته postfix رشته

تولید شده infix نوشته می شو د. سپس عبارت infix شده و بصورت pop عملگر , دو عنصر پشته

می شو د. در پایان پردازش رشته ورودی , پشته حاوی یک عنصر است که شکل push درون پشته

پشته سمت top باید لزوماً پرانتزگذاری شده باش د. عملوند infix مورد نظر می باش د. خروجی infix

راست عملگر نوشته می شود.

مثال :

abca↑ ×+bc/–

a

c c↑ a c

b b×(c↑ a) b b/c

a a+(b×(c↑ a)) (a+b×(c↑ a))–(b/c))

infix به prefix تبدیل عبارات

باید رشته ورودی را از سمت راست پردازش کنیم . مانند روش infix به prefix بر ای تبدیل عبارت

شده و pop می شوند و با رسیدن به هر عملگر , دو عملوند بالای پشته push قبل عملوندها در پشته

پشته top می شو د. عملوند push نوشته می شود و نتیجه در پشته infix با عملگر ورودی بصورت

سمت چپ عملگر قرار می گیرد.

–+a×b↑ ca/bc

c b a

b a (c↑ a) (b×(c↑ a)) (a+(b×(c↑ a))

c (b/c) (a+b×(c↑ a) –(b/c)

و بالعکس prefix به postfix تبدیل عبارات

infix به همدیگر می توان آنها را ابتدا تبدیل به حالت میانی prefix و postfix برای تبدیل عبارات

را با روشهای گفته شده به حالت مطلوب تبدیل نمو د. همچنین می توان infix کرده و سپس عبارت

را با استفاده از الگوریتم قبلی به یکدیگر تبدیل کرد . با prefix و postfix بصورت مسقتیم عبارت

این تفاوت که هنگامیکه در حین پردازش رشته ورودی به یک عملگر رسیدیم , دو عملوند بالای پشته

شوند به هر کدام از حالتهای push با عملگر ورودی در پشته infix شده و به جای اینکه به pop

می شوند. push در پشته prefix یا postfix مورد نظر

صفحه 14 ساختمان داده ها

(queue) صف

صف لیستی است که عمل افزودن داده ها درون آن از یک طرف لیست یا انتهای لیست و عمل حذف

(First In First Out) FIFO داده ها از سمت دیگر یا ابتدای لیست انجام می شو د. صف را لیست

می نامن د. زیرا اولین عنصر ورودی , اولین عنصر خروجی از صف نیز هست . در ساختمان داده صف دو

به ترتیب برای نشان دادن جلو و انتهای صف بکار می روند . صف را می توان با rear و front متغیر

استفاده از آرایه ها یا لیست های پیوندی پیاده سازی کرد.

تغییر کند که n می تواند از صفر تا rear و front عضوی از عناصر بدانیم مقادیر n اگر صف را آرایه ای

front = rear = تعریف می کنیم . 0 rear و front برای صف در ابتدا مقادیر اولیه صفر را برای

باشد صف n برابر با rear برابر باشد صف خالی است و در صورتیکه rear با front در صورتیکه متغیر

پر است.

rear = n ===􀃎 صف پر است

front = rear ===􀃎 صف خالی است

دو عمل اصلی برای صف , حذف کردن داده ها از صف و افزودن داده ها به صف است که به ترتیب با

x به این معنی است که عنصر Addqueue(x) نمایش می دهی م. تابع Addqueue و delqueue

قرار x نیز مقدار جلوی صف را برداشته و در متغیر delqueue به انتهای صف اضافه شده است و

x = delqueue . می دهد

از صف delqueue و Addqueue پیاده سازی تابع

queue : Array [1 .. n] of item

برای حذف کردن برای اضافه کردن

void Addqueue (int x) int delqueue ( )

{ {

if (rear = = n) if (front = = rear)

C out << “ } ; “ صف پر است

else C out << “ ; “ صف خالی است

{ return 0 ;

rear + + ; }

queue[rear] = x ; else

} {

} front + + ;

x = queue[front] ;

return x ;

}

}

ساختمان داده ها صفحه 15

را بدست آورید. C و B و A مثال : با استفاده از توابع صفحه قبل مقادیر نهایی

A = 5 B = 10 C = 2 n = 4

Addqueue (A + B)

Addqueue (C)

Addqueue (B × C)

A = delqueue ( )

B = delqueue ( )

Addqueue (B – A)

A = 15 B = 2 C = پس بنابراین داریم : 2

ب ه صورتیکه نوشته شد یک صف خطی را پیاده سازی می کنند . delqueue و Addqueue توابع

مشکل صف خطی این است که تنها یک بار قابل پر شدن است و در صورتیکه عناصر آن حذف شوند

مواجه می شوید به همین دلیل صف را بصورت حلقوی تعریف می کنیم . « صف پر است » نیز با پیغام

بع د از رسیدن به آخرین مقدار خود در صورت وجود شرایط front و rear ( در صف حلقوی (دوار

n – عضوی را بصورت آرایه صفر تا 1 n لازم مجدداً مقادیر اولیه را می توانند بگیرن د. صف حلقوی

تعریف می کنیم.

queue : Array [0 .. n – 1] of item

قرار می گیرد. queue[ عنصر بعدی در [ 0 rear = n – در این حالت وقتی 1

به معنای خالی بودن صف است ولی شرط پر بودن صف بدین ترتیب front = rear در صف حلقوی

تغییر می یابد.

front = (rear + 1) mod n ===􀃎 شرط پر بودن

front = rear ===􀃎 صف خالی است

باید صفر rear = n – یکی اضافه می شود و در صورتیکه 1 rear , برای اضافه کردن به صف حلقوی

را با رابطه زیر در هر شرایطی مقداردهی می کنند. rear بشود. بدین منظور

rear = (rear + 1) mod n

نیز برقرار است. front این مسئله برای

front = (front + 1) mod n

15 2 20 –13

1 2 3 4

Rear Front A B C

0

1

2

3

4

0

1

2

5

15

10

2

2

صفحه 16 ساختمان داده ها

برای حذف کردن برای اضافه کردن

void Addqueue (int x) int delqueue ( )

{ {

rear = (rear + 1) mod n if (front = = rear)

if (front = = rear) {

C out << “ صف پر است “ ; C out << “ ; “ صف خالی است

else return 0 ;

queue[rear] = x ; }

} else

{

front = (front + 1) mod n

x = queue[front] ;

}

}

مثال :

Addqueue [50] r = 1 0 1 2 3 f = 0 50

Addqueue [20] r = 2 0 1 2 3 f = 0 50 20

Addqueue [30] r = 3 0 1 2 3 f = 0 50 20 30

delqueue ( ) r = 3 0 1 2 3 f = 1 50 20 30

Addqueue [10] r = 0 0 1 2 3 f = 1 10 50 20 30

ساختمان داده ها صفحه 17

بنویسید. postfix و prefix مثال : عبارت زیر را بصورت

a2 bc (a 2 b c) (1 2)

− ⇒ ↑ − × ↑ /

postfix = a2 ↑ bc× −12/ ↑

prefix = ↑ − ↑ a2× bc /12

مرتب سازی

در مرتب سازی تعدادی عنصر که از ورودی داده شده اند را بر اساس کلیدشان بصورت صعودی یا نزولی

مرتب می کنیم.

(Selection Sort) مرتب سازی انتخابی

بار پیمایش می شود. در هر پیمایش n – 1 , (A[1..n]) عنصری n در مرتب سازی انتخابی یک آرایه

بزرگترین عنصر در محل درست خود یعنی انتهای آرایه قرار می گیرد . با این روش آرایه از انتها مرتب

می شود . در مرتب سازی انتخابی می توان با انتخاب کوچکترین عنصر در هر پیمایش و قرار دادن آن در

محل درست خود یعنی ابتدای آرایه در هر پیمایش , مرتب سازی را از ابتدای لیست انجام داد.

مثال :

10 5 8 20

25 12

10 5 8

20 12 پویش اول 25

10 5 8

12 20 پویش دوم 25

10 5 8 12 20 پویش سوم 25

8 5 10 12 20 پویش چهارم 25

5 8 10 12 20 پویش پنجم 25

صفحه 18 ساختمان داده ها

برنامه کلی مرتب سازی انتخابی به شرح ذیل می باشد :

for (i = n ; i > 1 ; – – 1)

{

max = A[1] ;

index = 1 ;

for (i = 2 ; j < = i ; + + j)

if (A[j] > max)

{

max = A[j] ;

index = j ;

}

A[index] = A[i] ;

A[i] = max ;

}

مثال :

3 2 5 1

1 2 3 4

i j n max index

4 2 4 3 1

3 4 5 3

4 3 1

2

3

n نکته : در مرتب سازی انتخابی , حداکثر و حداقل 2

مقایسه داری م. حداقل جابجایی صفر و حداکثر

بار خواهد بود. n جابجایی نیز

ساختمان داده ها صفحه 19

(Bubble Sort) مرتب سازی حبابی

بار پیمایش می شود و در هر پیمایش n – 1 , (A[1..n]) عنصری n در مرتب سازی حبابی یک آرایه

دو عنصر متوالی با یکدیگر مقایسه شده که در صورت لزوم جابجا خواهند شد . در هر پیمایش , طول

آرایه پیمایش شده نسبت به مرحله قبل یکی کم می شود.

10 30 50 40 90 20

10 30 50 40 90 20

40 50 20 مرحله اول 90

10 30 40 50 20 90

20 مرحله دوم 50

10 30 40 20 50 90

20 مرحله سوم 40

10 30 20 40 50 90

20 مرحله چهارم 30

10 20 30 40 50 مرحله پنجم 90

مرتب سازی از انتهای لیست

for (i = 1 ; i < n ; + + i)

for (j = 1 ; j < = n ; + + j)

if (A[j]) > A[j + 1])

swap (A[j] , A[j + 1]) ;

مرتب سازی از ابتدای لیست

for (i = 1 ; i < n ; + + i)

for (j = n ; j > = i ; – – j)

if (A[j]) < A[j – 1])

swap (A[j] , A[j – 1]) ;

مثال :

5 3 7 2 i j n

1 2 3 4 1 4 4

2 5 3 2 پویش اول 7 3

3 2

2 3 5 1 پویش دوم 7

4

« الگوریتم متعادل است »

صفحه 20 ساختمان داده ها

n در هر پویش امکان 2 دارد جابجایی وجود . حداقل تعداد جابجایی نیز صفر است.

مرتب سازی حبابی یهینه شده

for (i = 1 ; i < = x ; + + i)

{

sw = 0 ;

for (j = 1 ; j < n – 1 ; + + j)

if (A[j] > A[j + 1])

{

sw = 1 ;

swap (A[j] , A[j + 1]) ;

}

if (sw = = 0) break ;

}

(Insertion Sort) مرتب سازی دَرجی

ام در i عنصر اول لیست مرتب هستند. پس عنصر i – در مرتب سازی درجی فرض شده است که 1

جای صحیح خود قرار دارد.

For (i = 2 ; i < = n ; + + i)

{

y = A[i] ;

j = i – 1 ;

while (j > 0 & & (y < A[j]))

{

A[j + 1] = A[j] ;

j = j – 1 ;

}

A[j + 1] = y ;

}

ساختمان داده ها صفحه 21

50 60 40 20 10 30 i n y j

1 2 3 4 5 6 2 6 60 1

3 40 2

50 60 40 4 20 1

5 10 0

50 40 60 3

2

40 50 60 1

0

10 40 50 60 4

3

2

1

0

تا پویش داریم و در بهترین حالت نیز جابجایی نداریم. n در این جابجایی حداقل

مثال : آرایه زیر را به روش درجی مرتب کنید.

1 2 3 4 5

n i j y A 4 8 5 2 6

5 2 1 8 4 8

3 2 5 4 5 8

4 1 2 2 4 5 8

3 6 2 4 5 6 8

2

1

0

4

3

صفحه 22 ساختمان داده ها

(merge sort) مرتب سازی ادغامی

عنصری تبدیل به n مرتب سازی ادغامی مبتنی بر تقسیم و حل است و در روش ادغامی لیست

لیست های یک عنصری شده (با تقسیمات متوالی بر 2) و سپس لیست های یک عنصری که مرتب

هستند ادغام شده و لیست های دو تایی مرتب تشکیل می دهند و سپس لیست های دو تایی مرتب

شده با هم ادغام می شوند و این فرآیند تا تولید لیست اولیه به صورت مرتب ادامه پیدا می کند که این

حالت نیز بصورت بازگشتی است.

11 2 20 18 1 8 7 12 17 5

11 2 20 18 1 8 7 12 17 5

11 2 20 18 1 8 7 12 17 5

11 2 20 18 1 8 7 12 17 5

11 2 1 18 8 7 5 17

2 11 7 8

2 11 20 7 8 12

1 2 11 18 20 5 7 8 12 17

1 2 5 7 8 11 12 17 18 20

Void mergsort (int L , int U)

{

int i ;

if ( L < U )

{

i = ( L + U ) / 2 ;

mergsort ( L , i ) ;

mergsort ( i + 1 , U ) ;

merg ( L , i , U ) ;

}

}

ساختمان داده ها صفحه 23

مثال :

5 1 7 2

5 1 7 2

5 1 7 2

1 5 2 7

1 2 5 7

مرتب کنید. merge sort مثال : آرایه زیر را بوسیله

1 2 3 4 L = 4 U = 4

A 5 3 1 4 L = 3 U = 4

Merge sort ( 1 , 4 ) L = 3 U = 4 i = 3

1 2 3 4 L = 2 U = 2

3 5 1 4 L = 1 U = 1

L = 1 U = 2 i = 1

1 3 4 5 L = 1 U = 4 i = 2

تمرین : برنامه ای بنویسید که دو آرایه مرتب را بگیرد و در هم ادغام کند.

L = 3 U = 3 L = 4 U = 4

L = 3 U = 3 i = 3

L = 1 U = 1 L = 2 U = 2

L = 1 U = 2 i = 1

L = 1 U = 4 i = 2

صفحه 24 ساختمان داده ها

(quick sort) مرتب سازی سریع

در روش مرتب سازی سریع , یک عنصر بعنوان عنصر محوری در نظر گرفته می شود که عنصر محوری

را معمولاً اولین عنصر آرایه در نظر می گیرند . بعد از اولین پیمایش , عنصر محوری در محل مناسب

خود در لیست قرار می گ یرد و لیست به دو بخش مجزا تقسیم می گردد . عناصر سمت چپ عنصر

محوری که کوچکتر از عنصر محوری هستند و عناصر سمت راست عنصر محوری که همگی بزرگتر از

عنصر محوری می باشند . این عمل مجدداً بر روی هر یک از دو بخش انجام می شود تا به لیست های

0 و بدترین زمان اجرای آن (n Log n) یک عنصری مرتب برسیم . متوسط زمان اجرای این الگوریتم

0 می باشد که زمانی اتفاق می افتد که آرایه از پیش مرتب باشد. (n2)

1 2 3 4 5 6 7 8 9

12 10 2 8 15 7 3 1 14

محوری

(Pivot)

j I

3 10 2 8 1 7 12 15 14

i j i j

2 1 3 8 10 7 12 14 15

Void quicksort (int L , int U )

{

int i , j , pivot ;

if ( L < U )

{

i = L + 1 ; j = U ; pivot = A[L] ;

while ( i < j )

{

while ( A [i] < pivot ) i + + ;

while ( A[j] > pivot ) j - - ;

if ( i < j ) swap ( A[i] , A[j]) ;

}

swap ( A[L] , A[j] ) ;

quicksort ( L , j – 1 ) ;

quicksort ( j + 1 , U ) ;

}

}

ساختمان داده ها صفحه 25

(Link List) لیست پیوندی

لیست ها ساختمان داده ای هستند که اندازه آنها بصورت پویا تغییر می کند . پیمایش در لیست های

پیوندی بصورت ترتیبی (خطی ) است . بنابراین برای حذف , اضافه یا جستجو باید لیست را از ابتدا

در لیست پیوندی ساخ تاری با دو فیلد اصلی دار د . یکی (node) بصورت خطی پیمایش کر د. هر گره

فیلد داده که می تواند از هر نوع داده ای باشد و دیگری فیلد آدرس که به محل عنصر بعدی در لیست

پیوندی اشاره می کند . در ساختمان داده لیست پیوندی اعمال اصلی حذف داده از لیست , اضافه

یا (Head) کردن داده به لیست و جستجو در لیست انجام می شود . عنصر اول لیست پیوندی را هد

لیست می گویند و معمولاً این عنصر را برای سادگی پیمایش خالی نگه می دارند . (Header) هدر

برای افزودن داده جدید به لیست پیوندی 4 عمل اصلی انجام می گیرد.

جدید بر اساس اطلاعات جدید افزوده شدنی (node) -1 تشکیل گره

(p -2 بدست آوردن آدرس گره ای که باید قبل از گره جدید قرار گیرد (مثلاً گره

اشاره می کند. p -3 آدرس گره جدید که به محل اشاره گر

تغییر می دهیم. new node را به محل p -4 آدرس گره

Void insert ( int x , node * start )

{

node * p , * q , * new node ;

q = start → next ;

p = start ; new node = new ( node ) ; new node → data = x ;

while ( q → data < newnode data)

x

1442→443

{

p = q ;

q = q → next ;

}

new node → next = p → next ;

p → next = new node ;

}

صفحه 26 ساختمان داده ها

مثال : می خواهیم گره 15 را به لیست اضافه کنیم :

→ 6 → 12 → 14 → 20 → 30

↑

Start (p)

↑

q

(15) x

p q

Start 6

6 12

12 14

14 20

مراحل حذف یک گره از لیست پیوندی

(q) -1 یافتن گره قبل از گره مشخص شده برای حذف

حذف می شود) p) p→next به q→next -2 تغییر دادن

در نظر گرفته ایم. p -3 آزاد کردن حافظه ای که برای

void dellinklist ( int x , node * store )

{

node * p , * q ;

p = start ;

q = p ;

while ( p → data ! = x )

{

q = p ;

p = p → next ;

}

q → next = p → next ;

delete (p) ;

}

ساختمان داده ها صفحه 27

مثال : گره شماره 3 را حذف کنید.

5 → 8 → 3 → 2 \

5 → 8 → 2 \

تمرین : برنامه های زیر چه کاری انجام می دهند؟

node * f ( int x , node * start )

{

node * p ;

p = start ;

while ( p ) ;

if ( p → data ! = x && p ) p = p → next ;

else return p ;

}

void g ( node * start )

{

if (start ! = Null )

{

C out << start → data ;

g ( start → next ) ;

}

}

عناصر لیست g عمل جستجو را انجام می دهد و در قسمت دوم یعنی f جواب : در قسمت اول یعنی

را به ترتیب چاپ می کند.

p q

5 5

8 8

3 2

صفحه 28 ساختمان داده ها

لیست پیوندی چرخشی

لیست ما تبدیل به (start) به هد لیست اشاره گر کند Null اگر اشاره گر عنصر انتهای لیست به جای

لیست تک پیوندی چرخشی می شود.

تمرین : عمل حذف و اضافه را در یک لیست پیوندی چرخشی بنویسید.

ساختمان داده ها صفحه 29

لیست دو پیوندی

در لیست دو پیوندی سه بخش وجود دارد.

data -1 بخش

-2 بخش سمت راست که به گره بعدی اشاره می کند.

-3 بخش سمت چپ که به گره قبلی اشاره می کند.

struct Linklist

{

struct Linklist * left ;

data ;

struct Linklist * right ;

}

typedeg struct Linklist node

node * p , * q ;

مراحل اضافه کردن داده به لیست دو پیوندی

(new node) -1 تشکیل گره جدید با استفاده از اطلاعات اضافه شدنی

-2 پیدا کردن محل درج گره جدید

new node و p -3 انتساب مقادیر مورد نظر به بخشهای آدرس چپ و آدرس راست گره های

void insert (int x , node * start )

{

node * newnode , * p ;

newnode = new (node) ;

مرحله 1 newnode → data = x ;

newnode → right = Null ;

newnode → left = Null ;

p = start → right ;

مرحله 2 while ( p → data < x ) p = p → right ;

p = p → left ;

( p → right ) → left = newnode ;

مرحله 3 newnode → left = p ;

newnode → right = p → right ;

p → right = newnode ;

}

صفحه 30 ساختمان داده ها

start . مثال : گره عدد 6 را به لیست زیر اضافه کنید

→

← 1 →←

5 →

← 7 →

← 9 \

↑ ↑ ↑

p P p p

6

↑

حذف از لیست دو پیوندی

void delete ( int x , node * start )

{

node *p ;

p = start → right ;

while ( p && p → data < x ) p = p → right ;

if ( p = = Null | | p → data > x ) return “ ; “ داده در لیست نبوده است

( p → Left ) → right = p → right ;

( p → right ) → Left = p → Left ;

delete ( p ) ;

}

نمایش چندجمله ایها با استفاده از لیست های پیوندی

همانطور که چندجمله ایها بوسیله آرایه ها قابل نمایش بودند با استفاده از لیست های پیوندی نیز

می توان چندجمله ایها را نمایش داد . برای این منظور باید ساختار متناسب با چندجمله ای تولید کرد .

این ساختار شامل ی ک توان , یک ضریب و یک اشاره گر به جمله بعدی چند جمله ای است . به این

ترتیب در نمایش چندجمله ایها بوسیله لیست های پیوندی از حافظه بصورت بهتری استفاده شده است

ولی چون پیمایش در لیست های پیوندی , ترتیبی یا خطی است زمان محاسبات روی چندجمله ایها

در صورت استفاده از لیست پیوندی افزایش می یابد.

2 1 → 3 5 → 2 0

2x + 3x5 + 2

ساختمان داده ها صفحه 31

(Graph) گراف

به (Edge = که بوسیله یالهایی (لبه , یال (Vertex = مجموعه ای است از گره ها (گره G گراف

یکدیگر متصل شده ان د. گراف ها می توان ند جهت دار یا غیر جهت دار باشند . اگر هر یال در گراف دارای

جهت مشخصی باشد بدین معنی که مبدأ و مقصد آن مشخص بوده و غیرقابل جابجایی , این گراف ,

گراف جهت دار خواهد بود . هر دو گره که مستقیماً با یک یال به هم متصل باشند را دو گره مجاور یا

گرافی که بین تمام گره ها مسیر مستقیم وجود داشته باشد را .(Adjacement) همسایه گویند

نمایش می دهند. kn گره را با n گراف کامل می گویند. گراف کامل با

تعداد کل یالها در گراف کامل غیرجهت دار و در گراف کامل جهت دار خواهد

B . بود

)

2

n(n −1) n(n − 1

A C F

D

E

یک B و A در گراف برسیم گوئیم بین B با عبور از تعدادی یال و گره میانی به گره A اگر از گره

تعداد یالهایی است که در مسیر پیموده می شوند . اگر در مسیری گره ای n . وجود دار د n مسیر از طول

بیش از یکبار دیده شده باشد آن مسیر , مسیر غیر ساده است در غیر اینصورت مسیر ساده خواهد

بود . اگر در یک مسیر , گره مبدأ و گره مقصد بر هم منطبق بودند یا گره مبدأ همان گره مقصد بود ,

گراف دارای سیکل یا دور است.

c - b - e = مسیر ساده

c - a - e - b = مسیر غیر ساده

a - b - e - a = سیکل

فاصله دو گره در گراف برابر است با کوتاهترین مسیر بین آن دو گره

قطر گراف برابر است با بزرگترین فاصله بین دو گره در گراف

a

b

e

c d

صفحه 32 ساختمان داده ها

گراف متصل : گرافی که بین هر دو گره مسیری وجود داشته باشد را گراف متصل گویند.

گراف غیر متصل : گرافی است که حداقل بین دو گره آن هیچ مسیر وجود نداشته باشد.

یال وجود داشته باشد. n - گره متصل باشد این است که حداقل 1 n شرط لازم برای اینکه گرافی با

گراف تهی : گرافی است که مجموعه ای از گره ها باشد و هیچ یالی بین گره ها وجود نداشته باشد.

درجه هر گره : تعداد یالهایی که از یک گره عبور می کند را درجه آن گره گویند.

تذکر : درجه خروجی برای گراف های جهت دار تعداد یالهای خارج شده از یک گره را نشان می دهد و

درجه ورودی برای گراف های جهت دار تعداد یالهایی که به یک گره وارد شده اند می باشد.

مجمع درجات گره ها در گراف های بدون جهت دو برابر تعداد یالهاست و مجموع درجات ورودی یا

مجموع درجات خروجی در گراف های جهت دار تعداد یالها را نشان می دهد.

روشهای نمایش گراف ها

-1 ماتریس مجاورتی

n × n ماتریس مجاورتی روشی عمومی برای پیاده سازی گراف ها است . در این روش از یک ماتریس

تعداد گره های گراف است. n برای نمایش گراف استفاده می کنیم که

گرا ف وزن دار : گراف وزن دار گرافی است که به هر یال آن یک وزن (ارزش) منتصب شده باشد.

7 × 7

A [ i , j ] = یا 1 w if i , j متصل باشند

A [ i , j ] = 0 if متصل نباشند j و i

نکته : ماتریس گراف های غیر جهت دار , ماتریس متقارن است.

a b c d e f g

a 0 1 1 0 0 0 0

b 1 0 1 1 1 0 0

c 1 1 0 0 1 0 0

d 0 1 0 0 1 0 0

e 0 1 1 1 0 1 0

f 0 0 0 0 1 0 1

g 0 0 0 0 0 1 0

a

b

d

g

f

e

c

ساختمان داده ها صفحه 33

a b c d e f g

a 0 0 0 0 0 0 0

b 3 0 0 0 0 0 0

c 1 9 0 0 10 0 0

d 0 7 0 0 7 0 0

e 0 8 0 0 0 5 0

f 0 0 0 0 0 0 0

g 0 0 0 0 0 2 0

a b c d e

a 0 1 1 0 0

b 0 1 0 0

c 1 1 0 1 1

d 0 0 1 0 1

A =

e 0 0 1 1 0

1

a b c d e

a 0 0 1 0 0

b 1 0 0 0 0

c 0 1 0 1 0

d 0 0 0 0 1

e 0 0 1 0 0

مجموع سطر ی یا ستونی هر گره در ماتریس برای گراف های بدون جهت برابر با درجه هر گره است و

مجموع سطری هر گره در ماتریس برای گراف های جهت دار برابر است با درجه خروجی هر گره و

مجموع ستونی هر گره در ماتریس برای گراف های جهت دار برابر است با درجه ورودی هر گره.

a

b

c

d

e f

g

1

3

7

9 8 7

10 5

2

a b

c

d

e

a b

c

d

e

صفحه 34 ساختمان داده ها

A صفحه قبل را در نظر گرفته و ماتریس های A تمرین : ماتریس 2

A و 3 کنید آنرا حساب .

a b c d e a b c d e a b c d e

a 0 1 1 0 0 a 0 1 1 0 0 a 2 1 1 1 1

b 1 0 1 0 0 b 1 0 1 0 0 b 1 2 1 1 1

c 1 1 0 1 1

×

c 1 1 0 1 1

A2 =

c 1 1 4 1 1

d 0 0 1 0 1 d 0 0 1 0 1

⇒

d 1 1 1 2 1

e 0 0 1 1 0 e 0 0 1 1 0 e 1 1 1 1 2

a b c d e a b c d e a b c d e

a 2 1 1 1 1 a 0 1 1 0 0 a 2 3 5 2 2

b 1 2 1 1 1 b 1 0 1 0 0 b 3 2 5 2 2

c 1 1 4 1 1

×

c 1 1 0 1 1

A3 =

c 5 5 4 5 5

d 1 1 1 2 1 d 0 0 1 0 1

⇒

d 2 2 5 2 3

e 1 1 1 1 2 e 0 0 1 1 0 e 2 2 5 3 2

حال برای اینکه ماتریس بدست آمده را امتحان کنیم تا درست بودن آن ثابت گردد یک عدد را در

بدست می آید) و حالات موجود را بررسی می کنیم : c - d نظر گرفته (مثلاً عدد 5 که از خانه های

c - d - c - d

c - b - c - d

c - e - c - d

c - a - c - d

c - d - e - d

A نکته : قطر اصلی ماتریس 2 دهد درجه هر گره را نشان می .

A در ماتریس [ i , j ] عنصر k

وجود دارد. j و i بین k نشان می دهد که چه تعداد مسیر به طول

n فضای لازم برای نمایش دادن یک گراف با استفاده از ماتریس مجاورتی از مرتبه 2

تعداد n است که

گره های گراف می باشد.

-2 لیست همجواری

برای نمایش گراف ها می توانیم از لیست های همجواری استفاده کنیم . بدینصورت که آرایه ای به تعداد

گره های گراف ایجاد می کنیم . هر عنصر این آرایه اشاره گری است به ابتدای یک لیست پیوندی . این

لیست پیوندی شامل گره هایی است که به گره متناظر با عنصر آرایه متصل اند.

ساختمان داده ها صفحه 35

در گراف های غیر جهت دار تعداد کل گره ها در لیست های پیوندی دو برابر تعداد یالهای گراف است

ولی در گراف های جهت دار مجموع تعداد گره های لیست های پیوندی برابر تعداد یالهای گراف است .

و در n + e فضای مصرفی در نمایش بوسیله لیست همجواری در گراف های جهت دار از مرتبه

تعداد گره های گراف است. n تعداد یالهای گراف و e . است n + 2e گراف های غیر جهت دار

n = | V |

e = | E |

1 → 2 → 3 → 5 \

2 → 1 \

3 → 2 \

4 → 3 → 5 → 6 \

5 → 3 → 6 → 1 \

6 → 2 → 1 \

روشهای پیمایش گراف

دو روش کلی برای پیمایش گراف وجود دارد.

breadth first search (bfs) 1. اول سطح

depth first search (dfs) 2. اول عمق

a - b - c - f - e - g – d

(bfs)

2 3

4

6 5

1

f

g

e

c d

b

a

f

g

e

c d

b

a

صفحه 36 ساختمان داده ها

تعریف درخت : درخت گراف متصل بدون سیکل است.

روش اول سطح

در پیمایش اول سطح با شروع از یک گره و ملاقات آن , کلیه گره های مجاور آن نیز ملاقات می شوند.

سپس این رویه به ترتیب برای هر یک از گره های مجاور تکرار می شود . برای پیاده سازی پیمایش اول

از ساختمان داده صف استفاده می کنیم . بدین ترتیب که رئوس مجاور هنگام ملاقات وارد (bfs) سطح

صف می شوند , سپس از سر صف یک عنصر را حذف کرده و گره های مجاور آنرا ضمن ملاقات به صف

اضافه می کنی م. هر گره در صورتی ملاقات می شود (وارد صف می گرد د) که قبلاً ملاقات نشده باشد .

گراف) می باشد. bfs نتیجه پیمایش اول سطح , درخت پوشای اول سطح (درخت

لزوماً منحصر به فرد نیست. bfs پیمایش اول سطح از یک گراف و در نتیجه درخت پوشای

مثال : گراف زیر را بوسیله روش اول سطح پیمایش کرده و درخت پوشای آنرا بکشید.

a - b - f - c - e - d - g

روش اول عمق

در پیمایش اول عمق با شروع از یک گره و ملاقات آن , یکی از گره های مجاوری که ملاقات نشده را

ملاقات می نمائیم و این عمل را متناوباً تکرار می کنیم . اگر در یک گره بودیم و همه گره های مجاور آن

ملاقات شده بود , یک مرحله به عقب برمی گردیم . برای پیاده سازی درپیمایش اول عمق از پشته

است که لزوماً منحصر به فرد نیست. dfs استفاده می کنیم. نتیجه پیمایش اول عمق , درخت پوشای

a - b - c - d - f - e - g

g

f

e

d

b c

a

g

f

e

d

b c

a

g

f

e

d

b c

a

g

f

e

d

b c

a

ساختمان داده ها صفحه 37

شروع کرده و اول سطح و اول عمق گراف زیر را بنویسید. e تمرین : از گره

اول سطح = e - b - c - d - f - g - a

اول عمق = e - c - b - a - d - f - g

کدنویسی روش اول سطح و اول عمق

→

1

sw = 0

→

→

2

sw = 0

→

3

sw = 0

→

4

sw = 0

→

5

sw = 0

→

Struct Linklist

{

int data ;

struct Linklist *Next ;

}

typedef struct Linklist node ;

struct LinkArray

{

int sw ;

node *Link ;

}

typedef struct LinkArray pointer ;

pointer *graphnodes ;

graphnodes = New pointer [n] ;

g

d f

e

c

a b

صفحه 38 ساختمان داده ها

الگوریتم پیمایش اول سطح

شروع می کنیم. پس بنابراین داریم : k در این پیمایش از رأس

Void bfs ( pointer graphnodes [ ] , int k )

{

node *p ;

graphnodes [ k ] sw = 1 ;

C out << k ;

Addqueue ( k ) ; . را به انتهای صف اضافه می کند k مقدار

while ( ! ( queue . empty ( ))) چک می کند که آیا صف خالی است یا خیر

{

k = delqueue ( ) ; . قرار می دهد k از صف یک مقدار حذف کرده و در

p = graphnodes [ k ] . Link ;

do

{

if ( graphnodes [ p → data ] . sw = = 0 )

{

addqueue ( p → data ) ; C out << p → data ;

graphnodes [ p → data ] . sw = 1 ;

}

p = p → Next ;

}

while ( p ) ;

}

}

Graphnodes [ 5 ]

↓

1 → 3 → 5 \

sw = 0 1 P P

2 → 3 → 5 \

sw = 0 1 P P

3 → 1 → 2 → 4 \

sw = 0 1 P P P

4 → 5 → 3 \

sw = 0 1 P P

5 → 2 → 1 → 4 \

sw = 0 1 P P P

ساختمان داده ها صفحه 39

k

1 3 5 2 4 1

3

1 3 5 2 4 5

2

4

الگوریتم اول عمق

شروع می کنیم. پس بنابراین داریم : k در این پیمایش از رأس

Void dfs ( pointer graphnodes [ ] , int k ) //

{

node *p ;

graphnodes [ k ] . sw = 1 ; C out << k ;

for ( p = graphnodes [ k ] . Link ; p ! = Null ; p = → Next )

if ( graphnodes [ p → data ] . sw = = 0 )

dfs ( graphnodes , p → data ) ;

}

همان گراف بالا را در نظر می گیریم :

1 → 3 → 5 \

sw = 0 1 P (1) P (12)

2 → 3 → 5 \

sw = 0 1 P (4) P (5)

3 → 1 → 2 → 4 \

sw = 0 1 P (2) P (3) P (11)

4 → 5 → 3 \

sw = 0 1 P (9) P (10)

5 → 2 → 1 → 4 \

sw = 0 1 P (6) P (7) P (8)

1 3 2 5 4

5

4

2

3

1

صفحه 40 ساختمان داده ها

مثال :

1 → 2 → 3 \

sw = 0 1 P (1,1) P (2,1) P (3,1) = Null

2 → 1 \

sw = 0 1 P (1,2) P (2,2) = Null

3 → 1 → 4 \

sw = 0 1 P (1,3) P (2,3) P (3,3) = Null

4 → 3

sw = 0 1 P (1,4) P (2,4) = Null

از یک شروع می کنیم.

1 2 3 4 k

1

2

3

4

درخت پوشای بهینه (حداقل هزینه)

درخت پوشای بهین ه در گراف های ارزش دار (وزن دار ) ساخته می شود و آن درختی است که اگر ارزش

تمام گراف های آن را جمع کنیم کوچکترین عدد ممکن حاصل گردد.

در الگوریتم کراسکال , یالهای گراف را به : (kraskal) • روش اول الگوریتم کراسکال

ترتیب صعودی مرتب می کنیم . از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف

اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد . این روال را آنقدر ادامه می دهیم تا

درخت پوشای بهینه تشکیل گردد.

􀀹 fe = 2

􀀹 bf = 3

􀀹 bd = 5 , 􀀹 ae = 5

􀀸 be = 6

􀀹 cd = 7

􀀸 de = 8 , af = 8

􀀸 df = 9

􀀸 ab = 10 2 + 3 + 5 + 5 + 7 = 22

􀀸 bc = 20

1 2

4 3

c

b

a

d

f

8

20

3

10 8

e

2

5

5

6

7

9

c

b

a

d

3 f

e

2

5

5

7

ساختمان داده ها صفحه 41

در این روش از یک رأس شروع می کنیم و کمترین : (prim) • روش دوم الگوریتم پریم

یال (یال با کمترین وز ن) که از آن می گذرد را انتخاب می کنی م. در مرحله بعد یالی انتخاب

می شود که کمترین وزن را در بین یالهایی که از دو گره موجود می گذرد داشته باشیم . به

همین ترتیب در م رحله بعد یالی انتخاب می گردد که کمترین وزن را در بین یالهایی که از

سه گره موجود می گذرد داشته باشد . این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه

حاصل شو د. باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می شود که در

گراف دور ایجاد نکند . تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در

مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در

الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.

• • روش سوم الگوریتم سولین : در الگوریتم سولین برای هر گره یال با کمترین هزینه که از

آن ع بور می کند را رسم می کنی م. در مرحله بعد ، گراف به مؤلفه هایی تقسیم می شود و یالی

انتخاب می گردد که با کمترین هزینه دو مؤلفه گراف را به همدیگر متصل نماید با شرط عدم

وجود دور در گراف. آنقدر این مراحل را ادامه می دهیم تا درخت پوشای بهینه حاصل شود.

صفحه 42 ساختمان داده ها

تمرین : درخت پوشای بهینه گراف زیر را به سه حالت رسم نمائید :

􀀹 ac = 2 , 􀀹 de = 2 , 􀀹 gh = 2

􀀹 be = 3

􀀹 eh = 4

􀀹 ab = 5 , 􀀹 gi = 5

􀀸 hi = 6

􀀹 ef = 7

􀀸 bc = 8

􀀸 fh = 9 , 􀀸 ce = 9

􀀸 dg = 10

􀀸 bd = 11

􀀸 cf = 12

􀀸 eg = کراسکال 13

2 + 2 + 2 + 3 + 4 + 5 + 5 + 7 = 30

(e روش پریم (شروع از (e روش سولین (شروع از

g

d e

b c

a

f

h

i

5

2

4

2 7

3

5 2

g

d e

b c

a

f

h

i

5 6

9

2

10 13 4

2 7

11 3 9 12

8

5 2

g

d e

b c

a

f

h

i

5

4

3

1 8

2

6 7

g

d e

b c

a

f

h

i

1

1

2

1 1

1

2 1

ساختمان داده ها صفحه 43

حداقل هزینه بین گره های گراف (الگوریتم دایکسترا)

برای محاسبه حداقل هزینه ها از یک گره به گره های دیگر در گراف وزن دار ، از الگوریتم دایکسترا

استفاده می کنی م. بدین منظور باید ابتا ماتر یس هزینه های گراف را تشکیل دهیم و سپس با شروع از

گره مفروض ، هزینه آن گره تا سایر گره ها را بدست آوریم . برای بدست آوردن هزینه حداقل بین دو

گره دو انتخاب کلی وجود دارد :

Wij -1 مسیر مستقیم بین دو گره

Wik + Wkj -2 استفاده از یک گره میانی

آنقدر این روال را ادامه می دهیم تا تمام گره های گراف ملاقات شوند.

مثال : گراف زیر را در نظر بگیری د. از گره شماره 1 شروع کرده و حداقل هزینه بین گره ها را نسبت به

گره 1 بدست آورید.

􀀹 􀀹 􀀹 􀀹 􀀹 􀀹 􀀹

1 2 3 4 5 6 7 1 2 3 4 5 6 7

1 0 13 7 ∞ ∞ ∞ ∞ 1 0 13 7 ∞ ∞ ∞ ∞

2 ∞ 0 ∞ 8 4 ∞ ∞ 3 0 13 7 ∞ ∞ ∞ 9

3 ∞ 10 0 ∞ ∞ ∞ 2 7 0 13 7 ∞ ∞ 12 9

4 ∞ ∞ 5 0 ∞ ∞ 11 6 0 13 7 ∞ ∞ 12 9

5 1 ∞ ∞ 9 0 ∞ ∞ 2 0 13 7 21 17 12 9

6 6 ∞ 5 ∞ ∞ 0 ∞ 5 0 13 7 21 17 12 9

7 ∞ ∞ ∞ ∞ ∞ 3 0 4

جواب ماتریس

6

7

5

3

2

10

5

11

9

4

13

1

8 5

3 4

1 2

7

6

صفحه 44 ساختمان داده ها

مثال : حداقل هزینه بین گره های گراف زیر را در خصوص گره شماره 2 محاسبه نمائید.

􀀹 􀀹 􀀹 􀀹 􀀹 􀀹

1 2 3 4 5 6 1 2 3 4 5 6

1 0 7 12 ∞ ∞ ∞ 2 9 0 11 16 ∞ ∞

2 9 0 11 16 ∞ ∞ 1 9 0 11 16 ∞ ∞

3 ∞ 10 0 ∞ 8 6 3 9 0 11 16 19 17

4 3 ∞ ∞ 0 30 ∞ 4 9 0 11 16 19 17

5 ∞ 18 3 ∞ 0 ∞ 5 9 0 11 16 18 17

6 ∞ ∞ 2 4 1 0

12

8

11

7 10

9

3

16

18 3

30 1

4

6 2

1 2 3

4 5 6

ساختمان داده ها صفحه 45

چه عملی انجام می دهد؟ f سؤال : تابع

node * f( node *p )

{

node *q ;

q = Null ;

if ( p )

{

q = New ( node ) ;

q → data = p → data ;

q = Next = f( p → Next ) ;

}

return q ;

}

جواب :

تابع بالا از لیست پیوندی کی کپی تهیه می کند.

2 → 5 \

P = Null q = Null

P = 5 q = 5 ?

P = 2 q = 2 ?

2 → 5 \

صفحه 46 ساختمان داده ها

بنویسید. postfix زیر را بصورت prefix سؤال : عبارت

+ + a / b – c d / – a b – + c × d 5 / a – b c

جواب :

a b c d – / + a b – c d 5 × + a b c – / – / +

زیر را بنویسید. postfix سؤال : حاصل عبارت

6 , 2 , 3 , + , – , 3 , 8 , 2 , / , + , × , 2 , ↑ , 3 , +

جواب :

(6 – (2 + 3)) × (3 + (8 / 2)) ↑ 2 + 3 = 52

بنویسید. prefix و postfix سؤال : عبارت زیر را بصورت

(a / (b – c + d)) × (e – a) × c

جواب :

Postfix = a b c – d + / e a – × c ×

Prefix = × × / a + – b c d – e a c

را بنویسید. f سؤال : خروجی تابع

void f( node *x )

{

node *p ;

int i ;

i = 0 ;

if ( x ! = Null )

{

p = x ;

do

{

i + + ;

p = p → Next ;

}

while ( p ! = x )

}

C out << i ;

}

جواب : تعداد ندهای لیست پیوندی چرخشی را محاسبه و چاپ می کند.

ساختمان داده ها صفحه 47

را بنویسید. g سؤال : خروجی تابع

node *g (node *p )

{

node *m , *L ;

m = Null ;

while ( p )

{

L = m ; m = p ;

p = p → Next ;

m → Link = L ;

}

return m ;

}

جواب : لیست پیوندی را معکوس می کند.

گراف زیر را بنویسید. dfs شروع کرده و پیمایش های a سؤال : الف) از گره

a b d e c f

a b e c f d

a c f e b d

a c e b d f

در این گراف نوشت که با هم یکی باشند؟ bfs و یک dfs ب) آیا می توان یک

جواب : خیر

نوشت که با هم برابر باشند یا خیر؟ bfs و dfs ج) در حالت کلی گراف ها آیا می توان یک

آن با هم یکی خواهد شد. bfs و dfs شروع کنیم e جواب : بله مثلاً اگر در گراف زیر از گره

dfs = e a b c d

bfs = e a b c d

a

f

d e

b c

e

a b

d c

صفحه 48 ساختمان داده ها

سؤالات میان ترم

-1 آرایه ای 11 عنصری بشکل زیر موجود اس ت . می خواهیم آن را به روش درجی مرتب کنیم.

آرایه در مرحله پنجم پویش آن چگونه خواهد بود. ( 10 نمره)

14 7 3 20 18 4 17 9 11 30 25

1 2 3 4 5 6 7 8 9 10 11

جواب :

3 4 7 14 18 20 17 9 11 30 25

1 2 3 4 5 6 7 8 9 10 11

-2 زیربرنامه ای بنویسید که آدرس شروع دو لیست پیوندی مرتب را گرفته و آدرس شروع لیست

پیوندی مرتب حاصل از ترکیب دو لیست پیوندی داده شده را برگرداند. ( 20 نمره)

node ordermerg ( node * start 1 , node * start 2 )

{

node * p , * q , * start , * s ;

s = new ( node ) ; s → next = Null ;

start = s ;

p = start 1 → next ;

q = start 2 → next ;

while ( p && q )

if ( p → data < q → data )

{

s → next = p ;

s = p ;

p = p → next ;

}

else

{

s → next = q ;

s = q ;

q = q → next ;

}

if ( p ) s → next = p ;

else s → next = q ;

return start ;

}

ساختمان داده ها صفحه 49

داریم. زیربرنامه ای بنویسید که Start و 2 Start -3 دو لیست پیوندی با آدرس های شروع 1

آدرس شروع لیست پیوندی ترکیب این دو لیست را برگرداند. ( 10 نمره)

node * concatlist ( node * start 1 , node * start 2 )

{

node * p ;

p = start 1 → next ;

while ( p → next ) p = p → next ;

p → next = start 2 → next ;

return start 2 ;

}

-4 هزینه درخت پوشای مینیمم گراف زیر را از روش پریم بدست آوری د. درخت حاصل چند یال

دارد؟ ترتیب رسم یالهای درخت پوشای بهینه را با استفاده از الگوریتم پریم ذکر کنید .

15 نمره) )

4 – 5 : 60 1 – 3 : 15

4 – 6 : 20 1 – 6 : 55

4 – 1 : 30 5 – 5 : 40

1 – 5 : 45 2 – 6 : 25

1 – 2 : 10 2 – 3 : 50

3 – 5 : 35

جواب :

1) 1 – 2 : 10

2) 2 – 3 : 15

3) 2 – 6 : 25 = 105

4) 6 – 4 : 20

5) 3 – 5 : 35

30

35

45

55

60

10

15

40

50

20

25 1

2

3

4

5

6

35

10

15

20

25 1

2

3

4

5

6

صفحه _____________50 ساختمان داده ها

مرتب کند. (selection sort) -5 زیربرنامه ای بنویسید که آرایه ای از اعداد را به صورت انتخابی

یک آرایه مرتب شده را توسط کدام یک از روشهای مرتب سازی گفته شده مجدداً مرتب کنیم

تا کندتر مرتب سازی انجام شود. ( 20 نمره)

for (i = n ; i > 1 ; – – 1)

{

max = A[1] ;

index = 1 ;

for (i = 2 ; j < = i ; + + j)

if (A[j] > max)

{

max = A[j] ;

index = j ;

}

A[index] = A[i] ;

A[i] = max ;

}

10 را بصورت ستونی در حافظه از محل 1000 حافظه ذخیره × -6 یک آرایه دو بعدی 20

6 ] آرایه , کرده ای م. در صورتیکه هر عنصر آرایه 2 بایت فضا مصروف کند آدرس عنصر [ 7

در حافظه چیست؟ ( 5 نمره)

[6,7]= [(6×10)+ 5]× 2 +1000 = روش ستونی 1130

[6,7]= [(5× 20)+ 6]× 2 +1000 = روش سطری 1212

مرتب (Quick sort) -7 آرایه اعداد در سؤال 1 را با استفاده از الگوریتم مرتب سازی سریع

می کنی م. در مرحله اول مرتب سازی (پویش اول آرای ه) ، آرایه به چه شکل خواهد بود؟

10 نمره) )

14 7 3 20 18 4 17 9 11 30 25

محور i1

i2

J3

i3

j2

j1

4 7 3 11 9 14 17 18 20 30 25

جواب قسمت دوم : اگر یک آرایه مرتب

شده داشته باشیم و با مرتب سازی

درجی یا حبابی آن را مجدداً مرتب

کنیم بهترین حالت مرتب سازی را

انتخاب کرده ایم ولی اگر مرتب سازی

سریع را انتخاب کنیم کندترین حالت

را انتخاب کرده ای م. حال اگر یک آرای ه

نامرتب داشته باشیم بهترین حالت

برای مرتب سازی حالت مرتب سازی

سریع و یا ادغامی است.

ساختمان داده ها صفحه 51

هر یک را dfs و bfs -8 پیمایش اول عمق و اول سطح گراف زیر را بنویسید و درخت پوشای

تشکیل دهی د. پیمایش اول سطح را از گره 5 و پیمایش اول عمق را از گره 9 شروع کنی د.

20 نمره) )

نکته : از بین سؤالات 1 و 7 تنها به یکی پاسخ دهید. همه مرتب سازی ها بصورت صعودی است.

bfs = 5 1 6 2 4 7 9 3 10 8 dfs = 9 6 5 1 2 3 4 7 10 8

1

3 6

2 5

4

10

7

8 9

1

3 6

2 5

4

10

7

8 9

1

3 6

2 5

4

10

7

8 9

صفحه 52 ساختمان داده ها

(Tree) درخت

درخت مجموعه ای است متناهی از یک یا چند گره که یک گره خاص را بنام ریشه مشخص کرده ایم و

سایر گره ها به مجموعه های مجزایی تقسیم می شوند که هر مجموعه خود یک درخت است و

زیر درخت ریش ه نامیده می شو د. تعداد زیر درخت های هر گره درجه آن گره اس ت. فاصله هر گره تا

ریشه درخت را سطح آن گره می نامند . بزرگترین درجه گره در درخت ، درجه درخت نامیده می شو د.

تایی می گوین د. به گره هایی که درجه آنها صفر است برگ m باشد درخت را m اگر درجه درخت

گف ته می شو د. برگها زیر درخت ندارن د. برگها را گره های خارجی درخت و سایر گره ها غیر از (Leaf)

برگها را گره های داخلی درخت می نامند . دو گره که دارای پدر مشترک هستند را گره های همزاد

گویند . حداکثر سطح یک گره در درخت را ارتفاع (عمق) درخت گوین د. پیش فرض سطح ریشه 1

است.

درخت دودویی طبق تعریف درختی است که درجه آن 2 باشد یعنی هر گره حداکثر 2 فرزند داشته

باشد. یکی فرزند سمت راست و یکی فرزند سمت چپ که با هم متفاوت (متمایز) هستند.

فرزند سمت راست است فرزند سمت چپ است

مثال : با سه گره چند درخت دودویی می توان ساخت.

درخت اریب درخت اریب

کاملاً پر ) : درختی است که همه گره ها بجز گره های سطح آخر (برگها) ) Perfect • درخت

دارای حداکثر فرزندان بوده (حداکثر درجه درخت) و برگها هم سطح نیز باشند.

کامل ) : درختی است که اگر گره های آنرا شماره گذاری کنیم ، ) Complete • درخت

1

2

1

2

ساختمان داده ها صفحه 53

متناظرش منطبق باشن د. یعنی می توان گفت درختی است که Perfect شماره ه ا بر درخت

تا حد d بوده و برگها در سطح Perfect درخت ، d - باشد تا ارتفاع 1 d اگر ارتفاع آن

ممکن در سمت چپ باشند.

پر) : درختی که در آن گره ها یا برگ هستند و یا به تعداد درجه درخت فرزند ) Full • درخت

گویند. full دارند را درخت

نیست Perfect است Complete است Full

است Full نیست Full نیست Complete

است Complete نیست Perfect نیست Perfect

هم هست. Full و Complete باشد حتماً Perfect - درختی که

نیست. Perfect است لزوماً Complete - درختی که

نیست. Full است لزوماً Complete - درختی که

نیست. Complete است لزوماً Full - درختی که

براب با 2 1 خواهد بود. d - حداکثر تعداد گره ها در یک درخت دودویی به ارتفاع d −

2d−1

2d−1 −1

n 1

Log2−

برابر با خواهد بود. d - حداثر تعداد برگها در یک درخت دودویی به ارتفاع

برابر با خواهد بود. d - حداکثر تعداد گره های غیر برگ یک درخت با ارتفاع

گره دارای ارتفاع خواهد بود. n - درختی دودویی با

صفحه 54 ساختمان داده ها

سؤال : درخت دودویی زیر را در نظر بگیرید به سؤالهای آن پاسخ دهید.

-1 حداکثر چند برگ وجود دارد؟

2 بدست می آید. اگر بعنوان مثال ارتفاع 4 را در نظر بگیریم داریم : d− حداکثر تعداد برگها از رابطه 1

d−1 −1

2d −1

2d−1 = 24−1 = 23 = حداکثر تعداد برگهای موجود در این درخت 8

-2 حداکثر چند گره غیر از برگ داریم؟ (گره های داخلی)

حداکثر گره های داخلی از رابطه 2 بدست می آید. باز هم در ارتفاع 4 داریم :

2d−1 −1= 24−1 −1= 23 −1= 8 −1= 7

-3 حداکثر چند گره وجود دارد؟

حداکثر تعداد گره ها از رابطه بدست آمده و بعنوان مثال باز هم در ارتفاع 4 داریم :

2d −1= 24 −1=16 −1=15

داریم؟ d -4 چند درخت کامل متمایز به ارتفاع

حداکثر تعداد درخت کامل متمایز نیز از همان رابطه تعداد برگها بدست می آید . پس در ارتفاع 4

داریم :

2d−1 = 24−1 = 23 = 8

تا گره داشته باشیم : n سؤال : اگر

الف) حداکثر عمق چقدر است؟

خواهد بو د. در این حالت درخت ب صورت کاملاً اریب خواهد بو د. یعنی تمام n حداکثر عمق برابر با

فرزندان از یک سمت (چپ یا راست) رشد می کنند.

ب) حداقل عمق چقدر است؟

گره از رابطه زیر بدست می آید : n حداقل ارتفاع یک درخت دودویی با

[Log ] 1 [Log8 ] 1 3 1 4

2

n2

+ ⇒ + = + =

1

5 6

8 9 10 11 12 13 14 15

3

7

2

4

1

2

3

4

ساختمان داده ها صفحه 55

تایی نیز قابل تعمیم است. m نکته : همه روابط گفته شده برای درخت های

تعداد گره های دو فرزندی باشند رابطه n تعداد برگهای در یک درخت دودویی و 2 n اگر 0

برقرار است. n0 = n2 +1

روشهای پیمایش درخت

-1 آرایه

برای نمایش درخت های دودویی می توان از آرایه ها استفاده کرد . بدین منظور به تعداد گره های درخت

کامل متناظر با درخت مفروض برای یک آرایه حافظه نیاز داریم . در آنصورت داریم :

ریشه در خانه اول آرایه قرار می گیرد. 􀂙

2 قرار می گیرد که خواهد i در آرایه درون خانه i فرزند سمت چپ گره ای با اندیس 􀂙

فرزند سمت چپ ندارد. i بود. اگر بود یعنی گره

2i ≤ n

2i > n

i +1 > n i +1≤ n

2 = فرزند سمت چپ i

2 آرایه قرار می گیرد که i + در آرایه درون خانه 1 i فرزند سمت راست گره ای با اندیس 􀂙

فرزند سمت راست ندارد. i 2 خواهد بود. اگر 2 باشد یعنی گره

2 = فرزند سمت راست i + 1

در نمایش درخت های دودویی بوسیله آرایه ها اگر درخت کامل نباشد اتلاف حافظه خواهیم داشت ولی

اگر درخت کامل باشد روش خوبی خواهد بود.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

a b c d e g f h I

2 = فرزند سمت چپ i

⇒ i = پدر هر گره

2

i

2 = فرزند سمت راست i + 1

a

d e

f h i

b c

g

صفحه 56 ساختمان داده ها

-2 لیست های پیوندی

برای نمایش درخت ها به روش لیست پیوندی باید گره هایی با ساختار زیر تعریف کنیم.

هر گره یک فرزند سمت چپ و یک فرزند سمت راست و یک داده دارد . در ساختار تعریف شده

مشخص کردن پدر هر گره به سادگی امکان پذیر نیست . برای رف ع این مشکل می توان در ساختار هر

که به پدر آن گره اشاره می کند تعریف نمود. Parent گره یک فیلد جدید به نام

Struct Treetype

{

int data ;

struct Treetype * Lchild ;

struct Treetype * Rchild ;

struct Treetype * Parent ;

}

typedef struct Treetype Tree ;

a

b

g

c

d e

f h i

ساختمان داده ها صفحه 57

روشهای پیمایش درخت

-1 پیمایش اول عمق (عمقی)

سه روش پیمایش عمقی به شرح ذیل می باشد :

سوم دوم اول

فرزند سمت راست فرزند سمت چپ ریشه . 1 Preorder ( (پیش ترتیب

ریشه فرزند سمت راست فرزند سمت چپ . 2 Postorder ( (پس ترتیب

فرزند سمت راست ریشه فرزند سمت چپ . 3 Inorder ( (میان ترتیب

Preorder = a b d g c e h f i j

Postorder = g d b h e i j f c a

Inorder = d g b a e h c i f j

Inorder الگوریتم پیمایش عمقی به روش

Void Inorder ( Tree * T )

{

if ( T ! = Null )

{

Inorder ( T → Lchild ) ;

C out << T → data ;

Inorder ( T → Rchild );

}

}

a

d e

g h i

b c

f

j

صفحه 58 ساختمان داده ها

Preorder الگوریتم پیمایش عمقی به روش

Void Preorder ( Tree * T )

{

if ( T ! = Null )

{

C out << T → data ;

Preorder ( T → Lchild ) ;

Preorder ( T → Rchild );

}

}

Postorder الگوریتم پیمایش عمقی به روش

Void Postorder ( Tree * T )

{

if ( T ! = Null )

{

Postorder ( T → Lchild ) ;

Postorder ( T → Rchild );

C out << T → data ;

}

}

infix درخت متناظر با عبارت

زیر را در نظر می گیریم. infix عبارت

(a + b /(c ↑ 2)×(b − c)/(f ↑ (h − 3)+ 5))

یک درخت دودویی دارد. infix هر عبارت

↑ ↑

a

f

b

/

c 2

×

+ /

c

-

b

+

3

-

5

h

ساختمان داده ها صفحه 59

Inorder = a + b / c ↑ 2× b − c / f ↑ h − 3 + 5

بدون در نظر گرفتن پرانتزها است. infix این همان عبارت

Preorder = × +a / b ↑ c2 /− bc+ ↑ f − h35

بدون در نظر گرفتن پرانتزها است. prefix این همان عبارت

Postorder = abc2 ↑ /+ bc − fh3− ↑ 5 + /×

بدون در نظر گرفتن پرانتزها است. postfix این همان عبارت

-2 پیمایش اول سطح (سطحی)

Void Levelorder ( Tree * T )

{

while ( T )

{

C out << T → data ;

if ( T → Lchild ) addqueue ( T → Lchild ) ;

if ( T → Rchild ) addqueue ( T → Rchild ) ;

T = delqueue ( ) ;

}

}

(Binary Search Tree) BST درخت جستجوی دودویی

ساختمان داده هایی که تا کنون بررسی شده اند هر یک دارای نقاط ضعفی هستند . مثلاً درج در آرایه

مرتب مستلزم شیفت دادن داده ها و در نتیجه کندتر شدن الگوریتم است . پیمایش های مختلف روی

لیست های پیوندی نیز بصورت خطی انجام می شود که هزینه انجام اعمال را بالا می برد . درخت های

جستجوی دودویی راهکاری پیشنهاد می کنند که هزینه انجام اعمال اصلی مانند حذف ، اضافه و

n تا Log جستجو با زمان متوسط بهتری انجام می شو د. این زمان برابر است با ارتفاع درخت که از

از آنها کاملاً مؤثر اس ت. کلیدهای BST متغیر است . ترتیب ورود عناصر یا کلیدها برای تشکیل درخت

متفاوتی ایجاد می کنند. BST یکسان با ترتیب متفاوت ، درخت های

n2

صفحه 60 ساختمان داده ها

17 20 25 40 4 8 7 13 16 40 20 4 8 13 7 17 25 16

پیمایش کنیم در خروجی لیست مرتب صعودی خواهیم inorder ر ا بصورت BST اگر درخت

داشت.

است. n ( تایی ورودی (نامرتب n از یک آرایه BST هزینه ساخت یک درخت دودویی n2

×Log

BST الگوریتم جستجو در یک درخت دودویی

int BSTSearch ( node * T , int * x )

{

int founded = 0 ;

if ( T )

{

if ( T → data < x )

founded = BSTSearch ( T → Right , x ) ;

else if ( T → data > x )

founded = BSTSearch ( T → Left , x ) ;

else founded = 1 ;

}

return founded ;

}

17

20

25

40

4

8

13

16

7

40

20

25

17

4

8

13

16

7

ساختمان داده ها صفحه 61

مثال : می خواهیم ببینیم عدد 13 در درخت زیر وجود دارد یا خیر؟

←T

x = 13

F = 0

= 1

← T x = 13 F = 0 = BSTSearch (13 , 13)

← T x = 13 F = 0 = BSTSearch (8 , 13)

← T x = 13 F = 0 = BSTSearch (4 , 13)

← T x = 13 F = 0 = BSTSearch (20 , 13)

خروجی = founded = 1

وقتی خروجی برابر با 1 باشد یعنی داده پیدا شده و در صورتیکه 0 باشد یعنی داده پیدا نشده است.

BST الگوریتم اضافه کردن داده به درخت دودویی

Void insertBST ( node * T , int x )

{

node * p , * q , * S ;

p = new (node) ; p → data = x ;

p → Right = Null ; p → Left = Null ;

S = T ;

While ( S && S → data != x )

{

if ( S → data > x ) { q = S ; S = S → Left ; }

else if ( S → data < x ) { q = S ; S = S → Right ; }

}

if ( !S ) if ( q → data > x ) q → Left = p ;

else q → Right = p ;

}

40

20

25

17

4

8

13

16

7

40

20

4

8

13

صفحه 62 ساختمان داده ها

حذف

پیدا کنی م. حال BST برای حذف یک گره از درخت جستجو دودویی ابتدا باید آن گره را در درخت

یکی از وضعیتهای زیر رخ می دهد :

-1 اگر گره مورد نظر برگ باشد حذف می شود یعنی حافظه گرفته شده برای گره آزاد شده و

می شود. Null اشاره گر پدرش

-2 اگر گره حذف شدنی فقط یک فرزند داشته باشد فرزند آن گره جایگزین گره حذف شدنی

می گردد و یا می توان مورد بعدی را انجام داد.

Null -3 اگر گره دارای دو فرزند باشد یک قدم به راست و سپس آنقدر به چپ می رویم تا به

برسیم . با Null برسیم و یا برعکس یک قدم به چپ و سپس آنقدر به راست می رویم تا به

دنبال کردن هر یک از حالات فوق گره آخر را جایگزین گره حذف شدنی کرده و حافظه آنرا

آزاد می کنیم.

اگر بخواهیم گره شماره 40 را حذف کنیم هم می توانیم گره شماره 38 و هم می توانیم گره 􀂙

شماره 42 را جایگزین آن کنیم.

اگر بخواهیم گره شماره 20 را حذف کنیم هم می توانیم گ ره شماره 15 و هم می توانیم گره 􀂙

شماره 22 را جایگزین آن کنیم.

اگر بخواهیم گره شماره 15 را حذف کنیم هم می توانیم گره شماره 10 و هم می توانیم گره 􀂙

شماره 12 را جایگزین آن کنیم.

کپه) ) heap درخت

که تعداد موجود در هر گره از مقدار م وجود در گره های (Complete) درختی است دودویی کامل

است . در صورتیکه در درخت (maxheap) فرزندانش کوچکتر نباش د. این کپه ، کپه بیشترین

خواهیم (minheap) دودویی کامل مقدار هر گره از مقدار گره فرزندانش بیشتر نباشد کپه کمترین

داشت.

35

20 40

50

15

10

25 45

5

22 28

12

38

42

ساختمان داده ها صفحه 63

maxheap minheap

بدست آورد (یعنی بدون محاسبه O( بزرگترین عنصر را می توان ب ا مرتبه زمانی ( 1 maxheap در

کمترین عنصر را می توان با مرتبه minheap زیرا ریشه درخت بزرگترین عنصر است ) و متقابلاً در

بدست آورد (در این حالت نیز کمترین عنصر همان ریشه درخت است). O( زمانی ( 1

heap افزودن داده به درخت

داده جدید را در انتهای لیست آرایه قرار می دهیم (توجه heap برای افزودن داده جدید به درخت

را درون آرایه نگهداری می کنیم ). روال زیر تا رسیدن به ابتدای آرایه و یا بر قرار heap اینکه درخت

انجام می شود : heap بودن شرط درخت

برای اولین بار آخرین عنصر آرای ه) با پدر خ ویش در خانه مقایسه ) i داده موجود در خانه 􀀹

می شو د. در صورت جابجایی مجدداً این مقایسه برای خانه جدید ( ) انجام می گردد. این

می نامند. heap روش را افزودن به طریقه درج در

2

i

2

i

n2

انجام می شود. Log برای هر عنصر با مرتبه زمانی heap درج در درخت 􀀹

درخت زیر را در نظر بگیرید :

18

9 12

4

1

2 5

3

10

12

9

18

18

9 12

4

1

2 5

3

10

صفحه 64 ساختمان داده ها

آرایه این درخت به شکل زیر خواهد شد.

1 2 3 4 5 6 7 8 9

18 9 12 4 2 10 5 1 3

نیز برقرار باشد. heap حال می خواهیم داده شماره 8 را به این آرایه اضافه کنیم و درخت

1 2 3 4 5 6 7 8 9 10

18 9 12 4 2 10 5 1 3 8

18 9 12 4 8 10 5 1 3 2

حال می خواهیم ابتدا داده شماره 7 و سپس داده شماره 25 را به آرایه اضافه کنیم.

1 2 3 4 5 6 7 8 9 10 11 12

18 9 12 4 8 10 5 1 3 2 7 25

18 9 12 4 8 25 5 1 3 2 7 10

18 9 25 4 8 12 5 1 3 2 7 10

25 9 18 4 8 12 5 1 3 2 7 10

چون داده شماره 7 بر سر جای خود درست قرار گرفته است پس آنرا دست نمی زنیم و فقط داده

برقرار باشد. heap شماره 25 را آنقدر جابجا کرده تا درخت

به روش جوان ترین پدر heap روش ساخت درخت دودویی

عنصر ورودی را در یک آرایه قرار ده ید. سپس از n در ایجاد کپه به روش جوان ترین پدر ابتدا همه

پائین درخت شروع کرده ، هر پدر و فرزندانش را بصورت کپه تنظیم می کنیم و به سمت بالا (ریشه)

حرکت می کنی م. همینطور که به سمت ریشه می رویم زیردرخت ها بصورت کپه درآمده ان د. در این

هستند باید از جوان ترین پدر شرو ع کنیم که اگر heap روش چون برگها خودبخود به تنهایی یک

تا باشند از عنصر 2 i عناصر آرایه

کنیم i شروع می .

ساختمان داده ها صفحه 65

درآورید. heap مثال : درخت زیر را به روش جوان ترین درخت به صورت درخت دودویی

1 2 3 4 5 6 7 8 9

5 8 2 3 4 7 9 20 14

20 3

9 2

20 8

14 8

20 5

14 5

8 5

20 14 9 8 4 7 2 3 5

بنویسید. heap مثال : آرایه زیر را به روش درج بصورت درخت

1 2 3 4 5 6 7 8 9

5 8 2 3 4 7 9 20 14

5 8

8 5 2 3 4 7

8 5 7 3 4 2 9

8 5 9 3 4 2 7 20

8 5 9 20 4 2 7 3 14

9 5 8 20 4 2 7 3 14

9 20 8 5 4 2 7 3 14

9 20 8 14 4 2 7 3 5

20 9 8 14 4 2 7 3 5

20 14 8 9 4 2 7 3 5

20

14 9

8

3

4 2

5

7

20

14 8

9

3

4 7

5

2

صفحه 66 ساختمان داده ها

حذف یک عنصر

ریشه درخت خارج شده و داده آخر به جای آن قرار می گیر د . ، heap برای حذف یک عنصر از درخت

2 عنصر ماکزیمم را در صورت لزوم با i + 2 و 1 i شروع می کنیم و بین (i = ) سپس از ابتدای آرایه

عوض می کنی م. به همین ترتیب جابجایی انجام گرفته تا زمانیکه به انتهای آرایه برسیم (یک i عنصر

گره فرزندی نداشته باشد).

1 2 3 4 5 6 7 8 9

20 14 9 8 4 7 2 3 5

5 14 9 8 4 7 2 3

14 5 9 8 4 7 2 3

14 8 9 5 4 7 2 3

14 8 9 5 4 7 2 3

heap در این مثال عنصر 20 را حذف کرده و عنصر 5 را جایگزین کرده و بقیه مراحل ساخت درخت

را انجام داده ایم.

چه کاری انجام می دهد؟ f سؤال : تابع

int f (node * T )

{

int L , r ;

if ( T )

{

L = f ( T → Left ) ;

R = f ( T → Right ) ;

if L > r return L + 1 ;

else return r + 1 ;

}

return 0 ;

}

جواب : ارتفاع درخت را نشان می دهد.

20

14 8

9

3

4 7

5

2

ساختمان داده ها صفحه 67

چه کاری انجام می دهد؟ f سؤال : تابع

node * f ( node * T )

{

node * r , * s , * q ;

q = Null ;

if ( T )

{

r = f ( T → Left ) ;

s = f ( T → Right ) ;

q = New ( node ) ;

q → Left = r ;

q → Right = s ;

q → data = T → data ;

}

return q ;

}

جواب : از یک کپی تهیه می کند.

چه کاری انجام می دهد؟ g سؤال : تابع

int g ( node * T )

{

if ( T )

{

if ( ! T → Left ) && ( ! T → Right )

return 1 ;

else

return ( g ( T → Left ) + g ( T → Righe ) + 1 ) ;

}

return 0 ;

}

جواب : تعداد گره ها را چاپ می کند.

صفحه 68 ساختمان داده ها

چه کاری انجام می دهد؟ h سؤال : تابع

int h ( node * T )

{

if ( T )

{

if ( T → Left = = Null ) && ( T → Right = = Null )

return 1 ;

else

return ( h ( T → Left ) + h ( T → Righe ) ) ;

}

return 0 ;

}

جواب : تعداد برگها را چاپ می کند.

زیر را داری م. درخت دودویی آنرا تشکیل داده و پیمایش Preorder و Inorder سؤال : پیمایش

آنرا بنویسید. Postorder

Inorder : E A C K F H D B G

Preorder : F A E K C D H G B

Postorder : E C K A H B G D F

زیر را داری م. درخت دودویی آنرا تشکیل داده و پیمایش Postorder و Inorder سؤال : پیمایش

آنرا بنویسید. Preorder

Inorder : C B A E F H I D G

Postorder : C A B F I D G H E

Preorder : E B C A H F G D I

F

A D

E

B

K G

C

H

E

C B A F H I D G

C

I D

A I D G

I

F

ساختمان داده ها صفحه 69

آرایه زیر را از دو روش درج و جوان ترین پدر بدست آورید . maxheap سؤال : درخت

1 2 3 4 5 6 7 8

10 15 22 4 11 23 19 14

14 4

23 22 19

23 15 10

22 10 19

23 15 22 14 11 10 19 4

به روش جوان ترین پدر

1 2 3 4 5 6 7 8

10 15 22 4 11 23 19 14

10 15

15 10 22

22 10 15 4 11

22 11 15 4 10 23

22 11 23 4 10 15 19 14

22 11 23 14 10 15 19 4

23 11 22 14 10 15 19 4

23 14 22 11 10 15 19 4

23 14 22 11 10 15 19 4

به روش درج

The END !__