تبلیغات

کتاب ساختمان داده

دسته بندي : فنی و مهندسی » کامپیوتر و IT

آرایه‌ها)  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                                      فضای اشغال‌شده توسط آرایه )فضای موردنیاز)

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

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

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

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

 3×2

1. روش سطری                      ROW Major

  0    1     2     3   4    5

4

3

6

1

5

2

          سطری     

 

 

2. روش ستونی                      column major

   0    1     2    3    4   5

4

6

5

3

1

2

          ستونی                

 

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

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

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

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

 

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

    L1 … U1 L2 … U2

     A[3][2]                 ====  در زبان C  داریم       è        A: [1 … 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روش ستونی                                  

تمرین: در یک آرایه به شکل A [1 ... 100 , 1 ... 26] of integer اگر این آرایه از محل 1000 حافظه شروع‌شده باشد محل داده A [60 ,6]  درروش سطری و محل داده A [20 ,4]  درروش ستونی کدام آدرس حافظه است.

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اندازه هر بعد ماتریس است.

    بالا مثلثی     == 6  حداکثر عناصر غیر صفر

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

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

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


 

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

1

2

5

3

1

1

        ===========>          

                                                             

بالا مثلثی

 
+ j     ستونی  =====>        بالا مثلثی

=============>        

جمع ماتریس‌ها

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

Am×n + Bm×n = Cm×n

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

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

Cij = aij+ bij

دسته بندی: فنی و مهندسی » کامپیوتر و IT

تعداد مشاهده: 908 مشاهده

فرمت فایل دانلودی:.docx

فرمت فایل اصلی: word

تعداد صفحات: 80

حجم فایل:1,834 کیلوبایت

 قیمت: 5,000 تومان
پس از پرداخت، لینک دانلود فایل برای شما نشان داده می شود.   پرداخت و دریافت فایل
  • محتوای فایل دانلودی: