ساختمان های داده در C (آرایه) صفحه 2

Game Over · 12th January 2010

مثال 5_1

الگوريتم و برنامه اي كه جست و جوي دودويي را در آرايه اي انجام مي دهد.

حل: ابتدا الگوريتم و سپس برنامه جست و جوي دودويي و در ادامه، زمان اجراي الگوريتم را خواهيد ديد.

الگوريتم جست وجوي دودويي

دريافتي: عدد صحيح n، آرايه n عنصري مرتب صعودي aو item كه بايد جست وجو شود.

برگشتي: اگر item پيدا شود، found = 1 و موقعيت آن در locقرار مي گيرد، و گرنه صفر در found قرار مي گيرد.

1.0found

2.0first

3.n - 1 را در Last قرار بده

4.تا زماني كه first < Last و found = 0 اعمال زير را انجام بده:

5.loc

6.اگر item < a[loc] آنگاه

7.loc - 1Last /* جست وجو در بخش اول */

8.وگرنه، اگر item > a[loc] آنگاه

9.loc + 1first /* جست وجو در بخش دوم */

10. وگرنه 1 found

11.

Game Over · 12th January 2010

محاسبه زمان جست و جوي دودويي

در جست و جوي دودويي، تعداد مقايسه ها برخسب item و تعداد عناصر آرايه (n) متفاوت است. اگر مقدار item برابر با a[mid] باشد، آنگاه فقط يك مقايسه انجام مي شود. اگر itemبرابر با

عنصر اول+(عنصر وسط-1)/2

باشد، 2بار مقايسه صورت مي گيرد. به همين ترتيب، در بدترين حالت، يعني زماني كه itemدر آرايه نباشد، تعداد مقايسه ها

مرحله، تعداد عناصر مورد جست وجو نصف مي شود.

Game Over · 12th January 2010

آرايه هاي دو بعدي

نوع=;[ name[dim1][dim2

Game Over · 12th January 2010

v پياده سازي آرايه هاي دو بعدي

آرايه هاي دوبعدي مي توانند به صورت سطري ياستوني ذخيره شوند. در روش سطري، ابتداعناصر سطر اول، سپس عناصر سطردوم و غيره ذخيره مي شوند.در روش ستوني، ابتدا عناصر ستون اول، سپس عناصر ستون دوم و غيره ذخيره مي شوند. در C آرايه ها به صورت سطري ذخيره مي شوند.آريه زير را درنظر بگيريد:

int a[3][5];

Game Over · 13th January 2010

اكنون فرض كنيد آرايه a با m سطر و n ستون تعريف شده است كه m و n از قبل مشخص هستند:

int a[m][n];

براي رسيدن به اولين عنصر سطر iﭐم (يعني عنصر a[i][0] ) بايد از i سطر كامل بگذريم كه هر سطر آن داراي n عنصر است. لذا آدرس عنصر سطر i برابر است با:

= base(a) + i * n * size آدرس اولين عنصر سطر i

فاصله اولين عنصر سطر i تا ستون j برابر با j * size است. بنابراين آدرس عنصر a[i][j] به صورت زير است:

= base(a) + i * n * size + j * size آدرس عنصر a[i][j]

= base(a) + (j * n + j) * size

Game Over · 13th January 2010

كاربرد آرايه هاي دو بعدي

نام ديگر آرايه هاي دو بعدي، ماتريس است كه كاربردهاي فراواني در حل مسئله دارد. نمونه هايي از ماتريس ها در زير مشاهده مي شوند كه ماتريس a را

و به صورتa3*4

مي نويسيم و ماتريس b را5*2

مي گوييم و به صورت b2*5

مینویسیم

Game Over · 13th January 2010

v ماتريس هاي اسپارس

ماتريسي كه تعداد زيادي از عناصر آن صفر باشند، ماتريس اسپارسناميده ميشود.

Game Over · 13th January 2010

الگوريتم تعيين ترانهاده ماتريس اسپارس

دريافتي:نمايش ماتريس اسپارس

برگشتي: ترانهاده ماتريس اسپارس

1.تعداد ستون هاي ماتريس اسپارس را برابر با تعداد سطرهاي ماتريس ترانهاده قرار مي دهيم.

2.تعداد سطرهاي ماتريس اسپارس را برابر با تعداد ستون هاي ماتريس ترانهاده قرار مي دهيم.

3.تعداد عناصر مخالف صفر ماتريس اسپارس را برابر با تعداد عناصر مخالف صفر ماتريس ترانهاده قرار مي دهيم.

4.براي قرار دادن مقادير مخالف صفردر ماتريس ترانهاده، درستون دوم نمايش ماتريس اسپارس به دنبال كوچك ترين انديس (يعني صفر) مي گرديم و پس از پيدا كردن اين انديس، جاي سطر و ستون آن را عوض كرده، به همراه مقدار آن سطر و ستون، در ابتداي ماتريس ترانهاده قرار مي دهيم. به همين ترتيب، در ستون دوم نمايش ماتريس اسپارس به دنبال انديس هاي 1، 2،... و n - 1 مي گرديم. پس از جابه جايي سطر و ستون، به ترتيب در ترانهاده ماتريس اسپارس قرار مي دهيم.

اگرستون دوم نمايش ماتريس اسپارس به طور صعودي مرتب باشند،مرحله 4به اين صورت انجام مي شودكه،جاي سطر و ستون ماتريس اسپارس عوض مي شود و به همراه مقدار آن سطر و ستون به ترتيب در ماتريس ترانهاده قرار مي گيرد.

Game Over · 13th January 2010

جمع دو ماتريس اسپارس

در جمع دو ماتريس اسپارس، فقط عناصر متناظر، در صورت وجود با هم جمع مي شوند و چنانچه نتيجه جمع صفر نباشد، در ماتريس حاصل قرار مي گيرد. الگوريتم آن به شرح زير است:

الگوريتم جمع دو ماتريس اسپارس

دريافتي: سه ماتريس اسپارس a ،b و c

برگشتي: حاصل جمع دو ماتريس اسپارس (c)

1.شماره سطر اولين عنصر مخالف صفر ماتريس aرا با شماره سطر اولين عنصر مخالف صفر از ماتريس b مقايسه كن. سه حالت ممكن است رخ دهد:

الف. اگرشماره سطرماتريس aكمتر از شماره سطر ماتريس bباشد، با توجه به اين كه شماره سطرها صعودي مي باشند، آنگاه شماره سطر aاز تمام شماره سطرهاي b كمتر است. نتيجه مي گيريم كه عنصر متناظر با اين موقعيت در ماتريس b وجود ندارد(صفر است). اين عنصر را در ماتريس cقرار دهيد.

ب. اگر شماره سطر ماتريس b كمتر از شماره سطر ماتريس aباشد، مشخصات عنصر ماتريس b در ماتريس c قرار مي گيرد.

ج. اگر شماره سطرها برابر باشند، شماره ستون ها را باهم مقايسه كنيد. در اين جا نيز سه حالت ممكن است رخ دهد. درحالت كوچك تر يا بزرگ تر بودن، مثل سطرها عمل كنيد. در حالت تساوي(چون سطرها برابر بودند)،مقادير دوعنصر را جمع كنيد و اگرحاصل جمع مخالف صفر بود، به همراه مشخصات آن عنصر در آرايهc قرار دهيد. اگر حاصل جمع دو عنصر صفر بود، مشخصات آن عنصر در cقرار نمي گيرد. زيرا نمايش ماتريس اسپارس فقط عناصر غير صفر را دربرمي گيرد.

Game Over · 13th January 2010

مشكلات آرايه

آرايه ها چند مشكل دارند كه در هنگام استفاده از آن ها بايد در نظر گرفته شوند:

• حد و مرز آرايه ها در C كنترل نمي شود.

• ظرفيت آرايه در طول اجراي برنامه تغيير نمي كند.

• درج كردن مقداري در بين مقادير ديگر در آرايه، مستلزم جابه جايي عناصر است.

• حذف مقداري از آرايه نيز مستلزم جابه جايي عناصر است.


صفحه اصلی \| تلویزیون اینترنتی \| فال حافظ شیرازی \| پنل ارسال SMS از اینترنت \| سنجش تمرکز شما \| شهر بازی \| تبليغات \| تماس با مدیران انجمن ها

جدیدترین موضوعات انجمنها دانلود تولبار جی تاک