ساختمان های داده در c (آرایه)

آرايه ساده ترين ساختمان داده اي است كه در زبان c وجود دارد. ساده ترين شكل آن، آرايه يك بعدي است كه بردارنيز ناميده مي شود. آرايه يك بعدي، مجموعه مرتب و محدودي از عناصر همگن است. منظور از "محدود" اين است كه تعداد عناصر آرايه مشخص است.

آرايه به عنوان يك adt

adt آرايه

مجموعه عناصر:

دنباله اي با طول ثابت(مجموعه مرتب) از عناصر كه همگي از يك نوع اند.

عمليات اصلي:

دستيابي مستقيم به هر عنصر آرايه، به طوري كه مقادير را مي توان از اين عنصر بازيابي يا در آن ذخيره كرد.

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

آرايه يك بعدي كه نام ديگر آن بردار است، براي ذخيره مجموعه اي از عناصر همنوع به كار مي رود. عناصر آرايه يك بعدي در محل هاي متوالي حافظه ذخيره مي شوند. طول آرايه يك بعدي در هنگام اعلان بايد تعيين شود و در طول اجراي برنامه قابل تغيير نيست.

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

آرايه هاي يك بعدي را به آساني مي توان پياده سازي كرد. دستور زير را در نظر بگيريد:

int a[10];

اين دستور 10محل متوالي حافظه را تخصيص مي دهد كه درهر محل مي توان يك مقدار صحيح را ذخيره كرد. آدرس اولين محل، آدرس پايهنام دارد و با base(a) مشخص مي شود. اگر فرض كنيد هر مقدار صحيح چهار بايت از فضاي حافظه را اشغال مي كند، آنگاه اولين عنصر آرايه با شروع از آدرس base(a) در چهار بايت از حافظه ذخيره مي شود.

عنصر a[1] با شروع از آدرس 4+ base(a) در چهار بايت ذخيره مي شود به طور كلي، اگر طول هر عنصر آرايه a را size درنظر بگيريم، محل عنصر iﭐم به صورت زير محاسبه مي شود:

base(a) + i * size

مثال 1_1

فرض كنيد آرايه x به صورت int x[10] تعريف شود و base(x) برابر با 1000 باشد. اگر مقادير صحيح چهار بايت از فضاي حافظه را اشغال كنند، آدرس x[3] چيست؟

اهداف آموزشي

1. آشنايي با ذخيره عناصر آرايه

2. يافتن محل ذخيره عنصر آرايه (آدرس عنصر آرايه).

= base(x) + 3 *Sizeof(int) آدرس x[3]

= 1000 + 3*4
=1012

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

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

كاربرد آرايه در مرتب سازي

يكي از اعمالي كه به وفور در كامپيوتر انجام مي گيرد، عمل مرتب سازي است. الگوريتم هاي متعددي براي مرتب سازي وجود دارند كه در اين جا، الگوريتم مرتب سازي انتخابي را در نظر مي گيريم.

مثال 2_1

الگوريتم و برنامه اي كه عناصر آرايه اي به طول n را با الگوريتم انتخابي به طور صعودي مرتب مي كند.

الگوريتم مرتب سازي انتخابي

دريافتي:مقدار صحيح 1 =< n و آرايهx

برگشتي: آرايه x كه به طور صعودي مرتب شده است.

1. براي i = 0 تا n - 2 مراحل زير را انجام بده:

/* در گذر iﭐم، ابتدا كوچك ترين عنصر x[i] تا x[n-1] را پيدا كن*/

2.min = i

3. براي j = i + 1 تا n – 1 اعمال زير را انجام بده:

4. اگر x[j] < x[min] آنگاه

5.min = j

/* اكنون كوچك ترين عنصر را با iﭐمين عنصر ليست جابه جا كن.

6.item = x[i];

7.x[i] = x[min];

8.x[min] = item;

جست و جو در آرايه

جست و جو مي تواند به صورت ترتيبي يا دودويي انجام شود. جست و جوي دودويي در آرايه مرتب صورت مي گيرد.

مثال 4_1

الگوريتم و برنامه اي كه مقداري را در آرايه اي به طول n به طور خطي(ترتيبي) جست و جو مي كند. سپس زمان اجراي الگوريتم و پيچيدگي الگوريتم تعيين مي شود.

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

دريافتي: مقدار صحيح n، آرايه x به طول n ، و item كه بايد جست و جو شود.

برگشتي: اگر item وجود داشته باشد،مقدار 1 وگرنه مقدار صفر برگردانده مي شود.

1.o را در found قرار بده

2.o را در loc قرار بده

3.تا زماني كه n > locو found = 0 مراحل زير را انجام بده:

4.اگر item == x[loc] آن گاه

5. 1 را در found قرار بده

6.وگرنه loc را يك واحد اضافه كن.

7. Found را برگردان.

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

در اين تابع، تعداد مقايسه ها به مقدار item و عدد ورودي n بستگي دارد.

در بدترين حالت داريم:

T(n) = n

مثال 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

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

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

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

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

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

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

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

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

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

int a[3][5];

اكنون فرض كنيد آرايه 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

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

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

و به صورتa3*4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

مشكلات آرايه

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

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

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

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

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

نشانه گذاري O بزرگ

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

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

ازطرف ديگر، اگر با دو برابر شدن اندازه ورودي، زمان اجراي الگوريتم چهار برابر شود، آن گاه الگوريتم با نرخ توان دوم رشد مي كند. در اين مورد مي گوييم نرخ رشد آن، مرتبه است

ساده ترين روش محاسبه ي O مربوط به الگوريتم يا برنامه، در نظرگرفتن حلقه هاي تكرار و تودرتو بودن آن ها است.اگر فرض كنيم بدنه حلقه فقط حاوي دستورات ساده است، يك حلقه از O(n)، حلقه تودرتو از o(n) به توان سه است

و غيره. علاوه براين، بايد تعداد دفعات تكرار اجراي حلقه را تعيين كنيد.

حلقه زير را در نظربگيريد:

for(int i = 1; i < x_length; i*= 2)
{
process x[i];
}

بدنه حلقه k-1 بار اجرا مي شود كه i داراي مقادير 1، 2، 4، 8، 16، 32، ... و

است، به طوري كه 2 به توان k

كوچك تر از x_length مي باشد. لذا مي گوييم اين حلقه از Oلگاریتم n است

تعريف رسمي نشانه گذاري O بزرگ

برنامه اي را در نظر بگيريد كه به صورت زير پياده سازي شده است:

for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
Simple statement
}
}
for(k = 0; k < n; k++) {
Simple statement1
…
Simple statement5
}
Simple statement6
…
Simple statement30

فرض مي كنيم هر"Simple statement" يك واحد زماني را مصرف مي كند. حلقه داخلي، دستور Simple statement را n به توان 2

بار اجرا مي كند، سپس 5 دستور Simple statement

درحلقه اي با انديس kبه تعداد nبار اجرا مي شوند.سرانجام، 25دستور Simple statement اجرا مي گردند. بنابراين، داريم:

T(n)+n2+5n+25

اين عبارت، ارتباط بين زمان پردازش و n را نشان مي دهد. همان طور كه مشاهده مي كنيد، T(n) زمان پردازش را برحسب n بيان مي كند. اكنون رابطه زير را ببينيد:

T(n) = O(f(n))

اين رابطه به معناي اين است كه دو ثابت

n0و

c بزرگ تر از صفر، و تابع f(n) وجود دارند،

به طوري كه براي تمام n>n0

خواهيم داشت cf(n)<=T(n)

.به عبارت ديگر، وقتي n به

اندازه كافي بزرگ مي شود (بزرگ تر از n0

)، ثابتي مثل c وجود دارد كه براي آن، زمان

پردازش همواره كمتر يا مساوي cf(n) است.

بنابراين cf(n) حد بالاي كارايي است. كارايي هرگز بدتر از cf(n) نخواهد شد و ممكن است بهتر باشد.

v مقايسه كارايي ها

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

نمايش

O(1)

O(logn)

O(n)

O(nlogn)

䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü
䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü
䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü

O(n!)

نام

ثابت

لگاريتمي

خطي

لگاريتمي

- خطي

مرتبه 2

مرتبه 3

تواني

فاكتوريل

جدول زير نشان مي دهد كه وقتي n دوبرابر مي شود (مثلاً از 50 به 100 تبديل مي گردد)، نرخ رشد چگونه تغيير مي يابد. ستون سوم نسبت زمان هاي پردازش را براي دو مقدار مختلف نشان مي دهد. به عنوان مثال، اين ستون نشان مي دهد كه براي الگوريتم O(nlogn)، زمان پردازش 100 عدد، 35/2 برابر زمان لازم براي پردازش 50 عدد است.

F(100)/f(50)

F(100)

F(50)

O(f(n))

1

1.18

2

2.35

4

8

1

6.64

100

664

10,000

100,000

1

5.64

50

283

2500

12,500

O(1)

O(logn)

O(n)

O(nlogn)

O(n!)