آرایه ها

آرایه ها

اسلاید 1: مبانی کامپیوتر و برنامه سازیفصل دهم : آرايه هاتهیه اسلایدها: دکتر سعید ابریشمیمدرس : سید کاظم شکفته

اسلاید 2: 10 آرایه هادر مبحث الگوريتمها با يك ساختمان داده مهم، يعني آرايه ها آشنا شديم.البته در C ساختمان داده هاي ديگر ي همچون ساختارها نيز وجود دارند، اما آرايه ها همچنين مهمترين ساختمان داده موجود در اين زبان هستند.آرايه در C عبارتست از مجموعه اي از داده هاي همنوع كه تحت يك نام مشترك و در خانه هاي متوالي حافظه ذخيره مي گردند.براي دسترسي به عناصر آرايه، بايد از نام آرايه بعلاوه انديس استفاده كرد.در قسمتهاي بعدي، نحوه تعريف و استفاده از آرايه ها را تشريح خواهيم كرد.

اسلاید 3: 1-10 آرايه هاي يك بعديپيش از آنكه بتوان از يك آرايه يك بعدي استفاده كرد، بايد آن را اعلان كرد.اعلان آرايه ها بصورت زير انجام مي گردد:<type> <var-name>[<size>] ;بعنوان مثال:int A[10];خط بالا يك آرايه 10 تايي از اعداد صحيح بنام A ايجاد مي نمايد.هر كدام از عناصر اين آرايه مي توانند بعنوان يك متغير مستقل مورد استفاده قرار گيرد.براي دسترسي به عناصر اين آرايه بايد از انديس استفاده نمود. در زبان C انديسها در داخل كروشه [] قرار مي گيرند.نكته بسيار مهمي كه بايد بدان توجه كرد آنستكه در C انديس يك عدد صحيح است كه از 0 آغاز مي گردد.

اسلاید 4: 1-10 آرايه هاي يك بعديA[0]A[1]A[2]A[3]A[9]int A[10] ;A[2] = 8 ;8

اسلاید 5: 1-10 آرايه هاي يك بعديمثال 1) برنامه اي بنويسيد كه شماره دانشجويي و معدل تعدادي دانشجو را دريافت، و سپس چنانچه معدل دانشجو از ميانگين كلاس :بيش از يك نمره بيشتر باشد، چاپ كند : عاليحداكثر يك نمره بيشتر يا كمتر باشد، چاپ كند : خوببيش از يك نمره كمتر باشد، چاپ كند : ضعيف#include <stdio.h>void main() { float average[100] ;//آرایه نگهداری معدل دانشجویان long int id[100] ;//آرایه نگهداری شماره دانشجویان float totalAverage;//میانگین كل دانشجویان int i, n ; printf(enter number of students : ); scanf(%d, &n);//دریافت تعداد دانشجویان //حلقه دریافت مشخصات دانشجویان و محاسبه میانگین معدلها for (i = 0; i < n ; i ++) { printf(enter id and average : ); scanf(%ld %f, &id[i], &average[i]); totalAverage += average[i]; } totalAverage /= n; //حلقه دریافت مقایسه معدل هر دانشجو با میانگین كلاس و چاپ پیام مناسب for (i = 0; i < n ; i ++) { if (average[i] >= totalAverage + 1) printf(%ld : excellent !n, id[i]); else if (average[i] >= totalAverage – 1) printf(%ld : good !n, id[i]); else printf(%ld : weak !n, id[i]); }}

اسلاید 6: 1-10 آرايه هاي يك بعديچند نكته مهم راجع به آرايه در C وجود دارد كه حتما بايد به آنها دقت كنيد:اندازه آرايه ها در C ثابت بوده و حتما بايد توسط يك مقدار ثابت صحيح تعيين گردد. بعنوان مثال اعلان زير خطاي نحوي محسوب مي گردد:int n ;n=100 ; int A[n];اما مي توان با استفاده از متغير هاي ثابت (ثابتهاي داراي نام)، اندازه آرايه را تعيين كرد، كه در قسمتهاي بعدي به آن اشاره خواهد شد.انديس آرايه ها در C عدد صحيح بوده و هميشه از 0 شروع مي شود. لذا به تفاوت عنصر چهار آرايه يعني A[4] و چهارمين عنصر آرايه يعني A[3] دقت كنيد. اين مسئله معمولا باعث بروز خطاهاي منطقي مي گردد.در C مرز آرايه ها بررسي نمي گردد. بدين معنا كه چنانچه انديسي خارج از محدوده مجاز يك آرايه استفاده شود، باعث ايجاد خطا توسط كامپايلر نمي گردد، اما مسلما برنامه را دچار يك خطاي منطقي خواهد كرد. بعنوان مثال:int A[10] ;A[12] = 20 ; //this is not a syntax error but a logical errorلذا بررسي مرزهاي آرايه بعهده خود برنامه نويس است و بايد از درستي برنامه خود و خارج نشدن از محدوده مجاز مطمئن گردد.

اسلاید 7: 1-10 آرايه هاي يك بعديمقداردهي اوليه به آرايه هاي يك بعدي بصورت زير انجام مي پذيرد:int A[3] = {5, 2, 8};كه در اينجا A[0] برابر 5 ، A[1] برابر 2 و A[2] برابر 8 خواهد شد.علاوه براين مي توان فقط به تعدادي از عناصر آرايه مقدار داد، دراينصورت مقدار عناصر باقيمانده آرايه اتوماتيك 0 خواهد شد.int B[10] = {5, 8} ;در اينجا عناصر B[2] به بعد مقدار 0 خواهند گرفت. بنابراين مي توان براي 0 كردن كليه عناصر يك آرايه به شكل زير عمل كرد :int C[10] = {0};چنانچه به آرايه مقدار دهي اوليه كرده باشيم، مي توان تعداد عناصر آرايه را نيز ذكر نكرد، دراينصورت اندازه آرايه بطور اتوماتيك برابر تعداد مقادير مشخص شده خواهد شد.int C[] = {10, 15, 20};در مثال فوق آرايه C با 3 عضو درنظر گرفته مي شود.

اسلاید 8: 2-10 متغیرهای ثابتهمانطور كه در قسمت قبل گفته شد، گرچه اندازه يك آرايه بايد ثابت صحيح باشد؛ اما مي توان از متغيرهاي ثابت نيز استفاده كرد.يك متغير ثابت، متغيري است كه فقط مي تواند در هنگام اعلان مقدار اوليه بگيرد و اين مقدار ديگر قابل تغيير نيست. براي اعلان متغيرهاي ثابت، از كلمه كليدي const قبل از نوع متغير استفاده مي گردد. بعنوان مثال:const int k = 10;اكنون هرگونه تلاش براي تغيير مقدار k، باعث ايجاد يك خطاي نحوي توسط كامپايلر خواهد شد. به اين نوع متغيرها، ثابتهاي نام دار نيز گفته مي شود.اين متغيرها در تعريف مقادیر ثابتی که مقدار آنها در طول برنامه تغییر نمی کند، بکار می روند. بعنوان مثال :const float pi = 3.14;این کار نه تنها خوانایی برنامه را بالا می برد (بدلیل استفاده از کلمه pi که برای همه شناخته شده است)، بلکه باعث می شود تغییر پذیری برنامه نیز بالا برود. بدین معنا که در صورتیکه برنامه نویس تصمیم گرفت مقدار ثابت را عوض کند، نیازی به تغییر کل برنامه نیست و فقط کافی است مقدار اولیه متغیر را عوض نماید.

اسلاید 9: 2-10 متغیرهای ثابتاز این مسئله می توان در تعریف آرایه ها نیز استفاده کرد.بدین صورت که بجای آنکه اندازه آرایه را با یک ثابت صحیح مشخص نماییم، آن را با یک متغیر ثابت تعریف می کنیم.با اینکار، درصورتیکه نیازی به تغییر اندازه آرایه (یا آرایه ها) گردد، فقط کافی است مقدار اولیه متغیر ثابت خود را تغییر دهیم. مثال 2) برنامه اي بنويسيد كه سال ورود تعدادي دانشجو را دريافت و سپس تعداد ورودي هاي سالهاي 75 تا 84 را محاسبه و چاپ نمايد.

اسلاید 10: 2-10 متغیرهای ثابت#include <stdio.h>void main() { const int startYear = 75; const int yearNo = 10; int count[yearNo] = {0}; int i, n, year; printf(enter student no :); scanf(%d,&n); for (i=0; i<n ; i++) { printf(enter entrance year :); scanf(%d,&year); count [year – startYear] ++; } for (i=0 ; i<yearNo ; i++) printf(year = %d count = %d n,startYear + i , count[i]);}

اسلاید 11: 3-10 آرایه های چندبعدیهمانطور كه در بخش الگوريتمها گفته شد، آرايه ها مي توانند داراي ابعاد بيشتري نيز باشند.در زبان C نيز مي توان يك آرايه چند بعدي را بصورت زير اعلان كرد:<type> <var-name>[<size 1>][<size 2>] … [<size n>] ;بعنوان مثال، اعلان زير يك آرايه دوبعدي را معرفي مي نمايد:int A[5][8] ;براي دسترسي به هر عنصر از اين آرايه بايد از دو علامت [] استفاده كرد. توجه كنيد كه انديس سطرها و ستونها هر دو از 0 آغاز مي گردند.

اسلاید 12: 3-10 آرایه های چندبعدیسطرستون0123401234567A[2][3]A[1][6]int A[5][8] ;A[3][1] = 24 ;24

اسلاید 13: 3-10 آرایه های چندبعدیالبته در مورد آرايه هاي با ابعاد بالاتر نيز به شكل مشابهي عمل مي گردد.بعنوان مثال به نحوه استفاده از يك آرايه سه بعدي در مثال زير دقت كنيد:int B[5][8][6] ;B[2][4][0] = 12;مثال 3) یكی از اساتید قصد دارد آماری از نمرات دانشجویان خود در كوییز های بین ترم تهیه نماید. وی 5 كوییز در طول ترم برگذار نموده است و اكنون نیاز به اطلاعات زیر دارد:میانگین نمرات هر دانشجو برای كل كوییزهامیانگین نمرات كل دانشجویان برای هر كوییزبرنامه اي بنويسيد كه نمرات دانشجویان را براي 5 كوییز دريافت و اطلاعات خواسته شده را چاپ نماید.

اسلاید 14: 3-10 آرایه های چندبعدیدانشجوی اولدانشجوی دومدانشجوی سوم...کوییز اولکوییزدومکوییز سومکوییز چهارمکوییز پنجم

اسلاید 15: 3-10 آرایه های چندبعدی#include <stdio.h>const int maxStudent = 100;//حداكثر تعداد دانشجویان const int quizNo = 5;//تعداد كوئیزهاvoid main() { float grades[maxStudent][quizNo] ;//آرایه نگهداری نمرات دانشجویان float quizAverage, //میانگین نمرات هر كوئیز studentAverage;//میانگین نمرات هر دانشجو int i, j, n; printf(enter number of students: ); scanf(%d,&n);//دریافت تعداد دانشجویان //حلقه دریافت اطلاعات دانشجویان for (i=0 ; i<n ; i++) { printf(student no %d:n,i+1); for (j=0 ; j<quizNo ; j++) { printf(enter grade of quiz %d: , j+1); scanf(%f, &grades[i][j]); } }

اسلاید 16: 3-10 آرایه های چندبعدی //حلقه های متداخل برای محاسبه میانگین نمرات هر دانشجو printf(Students averages:n); for (i=0 ; i<n ; i++) { studentAverage = 0.0; for (j=0; j<quizNo; j++) studentAverage += grades[i][j]; studentAverage /= quizNo ; printf(student no %d: average=%f n,i+1, studentAverage); } //حلقه های متداخل برای محاسبه میانگین نمرات هر كوئیز printf(Average of each quiz:n); for (j=0 ; j<quizNo ; j++) { quizAverage = 0.0; for (i=0; i<n; i++) quizAverage += grades[i][j]; quizAverage /= n ; printf(quiz no %d: average=%f n,j+1, quizAverage); }}

اسلاید 17: 3-10 آرایه های چندبعدیو نكته آخر اينكه مقداردهي اوليه به آرايه هاي چندبعدي امكان پذير است و بصورت زير انجام مي پذيرد:int A[3][4] = { {12, 5, 3, 8} , {-3, 7, -9, 2}, {4, 22, 18, 6} };يعني يك علامت {} براي كل مقداردهي قرار مي گيرد، سپس هر رديف از آرايه در داخل يك {} مجزا قرار مي گيرد.براي ابعاد بالاتر نيز به روش مشابهي عمل مي گردد. بعنوان مثال براي آرايه هاي سه بعدي داريم:int A[2][3][4] = { { {12, 5, 3, 8} , {-3, 7, -9, 2}, {4, 22, 18, 6} } , { {8, 1, -3, 4} , {-2, 8, 11, 21} , {7, 3, -15, -8} } };

اسلاید 18: 4-10 ارسال آرایه های یک بعدی به توابعآرایه ها را نیز همچون سایر نوع داده ها می توان به یک تابع ارسال کرد. برای اینکار ابتدا باید تابع را بگونه ای تعریف کنیم که یک پارامتر از نوع آرایه را دریافت کند.فرض کنید تابعی بنام sumArray داریم که یک آرایه یک بعدی از اعداد صحیح را بعنوان ورودی دریافت می نماید و مجموع عناصر آن را باز می گرداند.تعریف این تابع بصورت زیر است:int sumArray(int A[], int size) { int i , sum = 0; for (i=0; i<size; i++) sum += A[i]; return(sum) ;}

اسلاید 19: 4-10 ارسال آرایه های یک بعدی به توابعهمانطور که می بینید، اندازه آرایه مشخص نشده است و این یک نکته مثبت است؛ چرا که تابع sumArray می تواند هر آرایه صحیحی را با هر اندازه ای دریافت نماید.درواقع حتی اگر اندازه آرایه را نیز مشخص نمایید، کامپایلر از آن صرفنظر خواهد کرد.دومین پارامتر، اندازه واقعی آرایه A را مشخص می نماید. معمولا توابع بگونه ای نوشته می شوند که هنگام ارسال یک آرایه به یک تابع، اندازه آن نیز بعنوان یک پارامتر ارسال گردد. در هنگام فراخوانی تابع sumArray، برای ارسال آرایه موردنظر کافی است که تنها نام آرایه را بدون کروشه استفاده نماییم.void main() { int data1[3] = {5, 10, 15}; int data2[5] = {1, 6, 4, 12, 5} ; int sum1, sum2; sum1 = sumArray(data1, 3); sum2 = sumArray(data2, 5); printf(sum1 = %dn,sum1); printf(sum2 = %dn,sum2);}

اسلاید 20: 4-10 ارسال آرایه های یک بعدی به توابعنکته بسیار مهم، نحوه ارسال آرایه ها به توابع است.زبانC آرایه ها را توسط ارجاع به تابع ارسال می نماید، بدین معنا که در هنگام ارسال یک آرایه به تابع، بجای یک کپی از آرایه، خود آرایه ارسال می شود.در حقیقت در فصلهای بعدی خواهید دید که برای ارسال یک آرایه، آدرس اولین عنصر آن ارسال می گردد. لذا تابع می تواند از طریق این آدرس، به کلیه داده های آرایه اصلی دسترسی پیدا کند.اما چرا C در مورد آرایه ها به روش متفاوتی عمل می نماید؟ دلیل این مسئله آن است که معمولا یک آرایه حافظه بسیار زیادی را اشغال می کند، لذا تهیه یک کپی کردن از آن، نه تنها باعث اشغال حافظه می شود بلکه زمان زیادی را نیز صرف خواهد کرد. اما آیا می توان یک آرایه را توسط مقدار به یک تابع ارسال کرد؟ متاسفانه خیر.اما اگر نگران تغییر سهوی آرایه ارسالی به یک تابع هستید می توانید آن را بگونه ای به تابع ارسال نمایید که تغییر آن در تابع ممکن نباشد.زبان C یک نحوه دیگر ارسال داده ها به توابع بنام ارسال توسط ارجاع ثابت می باشد.چنانچه در هنگام تعریف یک پارامتر از یک تابع، از کلمه کلیدی const استفاده شود، کامپایلر اجازه تغییر مقادیر آن پارامتر را در حین اجرای تابع نخواهد داد. با این ارسال آرایه ها بصورت ارجاع ثابت، می توانیم مانع از انجام تغییرات ناخواسته در آرایه شویم.

اسلاید 21: 4-10 ارسال آرایه های یک بعدی به توابعمثال 4) برنامه ای بنویسید که با استفاده از یک تابع، اشتراک دو مجموعه را محاسبه و چاپ نماید.void intersection(const int A[], int na, const int B[], int nb, int C[], int &nc) { int i,k,j,sw; k = 0; for (i=0; i<na; i++) { sw = 1; for (j=0; j<nb && sw; j++) if (A[i] == B[j]) { C[k] = A[i] ; k ++; sw = 0; } } nc = k;}void printSet(int set[], int size) { int i; printf({ ) ; for (i=0; i<size; i++) printf(%d ,set[i]) ; printf(}n);}

اسلاید 22: 4-10 ارسال آرایه های یک بعدی به توابعvoid main() { int set1[5] = {5, 8, 3, 12, 20}; int set2[3] = {12, 16, 8} ; int result[3] , resultSize ; intersection(set1, 5, set2, 3, result, resultSize); printf(set 1 = ); printSet(set1,5) ; printf(set 2 = ); printSet(set2,3) ; printf(intersection = ); printSet(result,resultSize) ;}

اسلاید 23: 5-10 ارسال آرایه های چندبعدی به توابعدر این قسمت، ابتدا به نحوه ارسال آرایه های دو بعدی به توابع می پردازیم و سپس آرایه های با ابعاد بالاتر را بررسي خواهيم كرد. شاید تصور کنید که برای تعریف یک آرایه دوبعدی بعنوان پارامتری از یک تابع، تنها قرار دادن دو علامت [] کافی است و نیازی به ذکر ابعاد آن نیست.اما متاسفانه اینگونه نیست، بلکه برنامه نویس باید تعداد ستونهای آرایه دوبعدی را صریحا مشخص نماید، اما نیازی به تعیین تعداد ردیفهای آن نیست.بعنوان مثال فرض کنید تابعی مانند test داریم که بعنوان ورودی یک آرایه دو بعدی و تعدادی پارامتر دیگر دریافت می کند. تعریف تابع بصورت زیر اشتباه است:void test(int A[][], …) {تعریف درست، تعریفی مانند زیر است:void test(int A[][10] , …) {در هنگام فراخوانی تابع test، می توان هر آرایه دوبعدی 10 ستونی را به آن ارسال کرد. آرایه ارسالی به تابع می تواند 5×10 و یا 20×10 باشد، اما نمی تواند مثلا 5×20 باشد.

اسلاید 24: 5-10 ارسال آرایه های چندبعدی به توابعمثال 5) تابعي بنويسيد كه ميزان فروش تعدادي شركت در 12 ماه سال را بعنوان ورودي دريافت، و ميانگين فروش شركتي را كه بيشترين ميانگين فروش را داشته است، بازگرداند.float maxSales(const long int sales[][12], int companyNo) { int i,j; float average , max; max = 0.0; for (i=0 ;i<companyNo; i++) { average = 0; for (j=0; j<12; j++) average += sales[i][j] ; if (average > max) max = average ; } return(max);}

اسلاید 25: 5-10 ارسال آرایه های چندبعدی به توابعمثال 6) برنامه ای بنویسید که حاصلضرب دو ماتریس را با استفاده از یک تابع محاسبه نماید.#include <stdio.h>const int maxCol = 10;void multiply(const int A[][maxCol], const int B[][maxCol], int m,int p, int n, int C[][maxCol] ) { int i,j,k,sum; for (i=0; i<m; i++) for (j=0; j<n; j++) { sum = 0; for (k=0; k<p; k++) sum += A[i][k] * B[k][j] ; C[i][j] = sum; }}void printMatrix(int matrix[][maxCol], int row,int col) { int i,j; for (i=0; i<row; i++) { for (j=0; j<col ;j++) printf(%d ,matrix[i][j]); printf(n); }}

اسلاید 26: 5-10 ارسال آرایه های چندبعدی به توابعvoid main() { int matrix1[2][maxCol] = { {7 ,3 , 2} , {-2, 6, 1} }; int matrix2[3][maxCol] = { {2 , 7 , -4, -1} , { 3 ,-3, 5, -8} , {6, -7, 2, 3} }; int result[2][maxCol] ; multiply(matrix1, matrix2, 2, 3, 4, result); printf(matrix1 is :n); printMatrix(matrix1,2,3) ; printf(nmatrix2 is :n); printMatrix(matrix2,3,4) ; printf(nmultiply of matrix1 and matrix2 is :n); printMatrix(result,2,4) ;}

اسلاید 27: 5-10 ارسال آرایه های چندبعدی به توابعاما ارسال آرايه هاي با ابعاد بالاتر به توابع نيز مشابه آرايه هاي دوبعدي است.به اين صورت كه در هنگام تعريف يك پارامتر از تابع بعنوان يك آرايه چندبعدي، مشخص كردن بعد اول لزومي ندارد، اما اندازه كليه ابعاد بعدي بايد حتما مشخص گردد.بعنوان مثال به تابع زير دقت کنید :void test(int A[][5][10], … ) {این تابع بعنوان ورودي يك آرايه سه بعدي دريافت مي نمايد كه حتما بايد بعد دوم آن 5 و بعد سوم آن 10 باشند، اما اندازه بعد اول هر مقداري مي تواند باشد.

اسلاید 28: 6-10 برخي عمليات مهم برروي آرايه هاهمانطور كه قبلا گفته شد، آرايه ها از ساختمان داده هاي بسيار مهم برنامه نويسي بوده و تقريبا مي توان گفت هيچ برنامه اي وجود ندارد كه به نحوي از آرايه ها استفاده نكند.به همين دليل براي انجام بعضي از عمليات مهم بر روي آرايه ها، الگوريتمهاي كارا و موثري توسط محققين ابداع شده است، كه چند نمونه از مهمترين آنها را بررسي مي نماييم.

اسلاید 29: 1-6-10 الگوريتمهاي مرتب سازيشايد مهمترين عملي كه برروي يك آرايه يك بعدي انجام مي شود، مرتب كردن آن بصورت صعودي يا نزولي است. بدليل اهميت اين كار، الگوريتمهاي متعددي براي آن ابداع شده است كه برخي از آنها بسيار پيچيده هستند.در اينجا 3 الگوريتم ساده مورد بررسي قرار گرفته اند كه براي آرايه هاي كوچك بسيار كارا هستند. اما براي مرتب سازي آرايه هاي بزرگ، بايد از روشهاي پيچيده تري استفاده شود كه در كتابهاي پيشرفته تر مورد بررسي قرار گرفته اند.در الگوريتمهاي زير فرض شده است كه قصد داريم آرايه را بصورت صعودي مرتب نماييم، گرچه با يك تغيير كوچك مي توان آن را به نزولي تبديل نمود.

اسلاید 30: 1-1-6-10 الگوريتم مرتب سازي انتخابی162212352784119مرحله اول822163527124119مرحله دوم812223527164119مرحله سوم...

اسلاید 31: 1-1-6-10 الگوريتم مرتب سازي انتخابیvoid selectionSort(int A[], int n) { int i,j; for (i=0; i<n; i++) for (j=i+1; j<n; j++) if (A[i] > A[j]) swap(A[i],A[j]) ;}

اسلاید 32: 2-1-6-10 الگوريتم مرتب سازي حبابی162212352784119مرحله اول161222278351941مرحله دوم121627228193541مرحله سوم...

اسلاید 33: 2-1-6-10 الگوريتم مرتب سازي حبابیvoid bubbleSort(int A[], int n) { int i, contSw; do { contSw = 0; n --; for (i=0; i<n; i++) if (A[i] > A[i+1]) { swap(A[i], A[i+1]) ; contSw = 1; } } while (contSw) ;}

اسلاید 34: 3-1-6-10 الگوريتم مرتب سازي درجیدر اين روش مرتب سازي از عمل درج استفاده مي شود. اين روش را مي توان بصورت زير مرحله بندي كرد:مرحله 1- فرض مي كنيم آرايه فقط داراي عنصر اول است و ساير عناصر را درنظر نمي گيريم. در اينصورت يك آرايه يك عنصري مرتب داريممرحله 2 – عنصر دوم را در آرايه مرتب مرحله قبل درج مي نماييم. اكنون يك آرايه دو عنصري مرتب داريم.مرحله 3- عنصر سوم را در آرايه مرتب مرحله قبل درج مي نماييم. اكنون يك آرايه سه عنصري مرتب داريم....مرحله k – عنصر kام را در آرايه مرتب k-1 عنصري مرحله قبل درج مي نماييم تا يك آرايه k عنصري مرتب بدست آوريم....مرحله n – عنصر n را در آرايه مرتب مرحله قبل درج كرده تا آرايه مرتب نهايي حاصل شود.

اسلاید 35: 3-1-6-10 الگوريتم مرتب سازي درجی162212352784119مرحله اول161222352784119مرحله دوم1222162784119مرحله سوم351222163584119مرحله چهارم27354119مرحله پنجم827221612835122716221941مرحله ششم41128مرحله هفتم1935272216

اسلاید 36: 3-1-6-10 الگوريتم مرتب سازي درجیvoid insertionSort(int A[], int n) { int i, j, cur; for (i=1; i<n; i++) { cur = A[i] ; for (j=i-1; j>=0 && cur<A[j]; j--) A[j+1] = A[j] ; A[j+1] = cur ; }}

اسلاید 37: 3-1-6-10 الگوريتم مرتب سازي درجیدر مورد سه الگوریتم مرتب سازی ذکرشده چند نکته قابل ذکر است:هر 3 الگوریتم برای مرتب سازی یک آرایه از اعداد صحیح (int) نوشته شده اند، اما روش بهتر آن است که آنها را بصورت یک الگو بنویسیم که قادر به مرتب سازی هر نوع آرایه ای باشند. الگوها و نحوه پیاده سازی آنها در فصل گذشته مورد بحث قرار گرفتند.هر 3 الگوریتم برای مرتب سازی بصورت صعودی نوشته شده اند، اما می توان آنها را با یک تغییر کوچک به مرتب سازی نزولی تبدیل کرد.حتی می توان تابع را بگونه ای نوشت که یک پارامتر دیگر برای تعیین نوع مرتب سازی نیز بعنوان ورودی دریافت و براساس مقدار آن، مرتب سازی را بصورت صعودی یا نزولی انجام دهد.

اسلاید 38: 2-6-10 الگوریتمهای جستجویکی دیگر از الگوریتمهای بسیار مهم برای آرایه ها، الگوریتمهای جستجو هستند.موارد زیادی پیش می آیند که قصد داریم به دنبال یک داده در یک آرایه جستجو کرده و مکان آن را پیدا کنیم.در این قسمت دو روش متداول جستجو را مورد بررسی قرار می دهیم. البته معمولا برای عمل جستجو از ساختمان داده های پیچیده تری همچون درختهای جستجوی دودویی استفاده می گردد، که از بحث ما خارج است.

اسلاید 39: 1-2-6-10 الگوریتم جستجوی خطیجستجوی خطی، ساده ترین نوع جستجو است که در آرایه های نامرتب استفاده می شود. در این روش داده مورد نظر به ترتیب با تک تک عناصر آرایه مقایسه می شود تا مکان آن پیدا شود. int linearSearch(int A[], int n, int x) { int i; for (i=0; i<n; i++) if (x == A[i]) return(i); return(-1) ;}اگر آرایه دارای n عنصر باشد، در بدترین حالت نیاز به n مقایسه برای پیدا کردن داده مورد نظر داریم و این در صورتی است که داده در آخرین مکان آرایه قرار داشته باشد.اما از آنجا که احتمال قرار گرفتن داده در هریک از مکانهای آرایه یکسان است، بطور متوسط نیاز به n/2 مقایسه خواهیم داشت.

اسلاید 40: 2-2-6-10 الگوریتم جستجوی دودوییچنانچه آرایه مورد جستجو مرتب شده باشد، روش بسیار کاراتری برای جستجو وجود دارد. این روش که به جستجوی دودویی موسوم است، با هربار مقایسه، نیمی از عناصر آرایه را از بازه جستجو حذف می نماید. در نتیجه جستجو در یک آرایه بزرگ با سرعت بسیار زیادی صورت می پذیرد.برای تشریح الگوریتم، فرض کنید آرایه موردنظر بصورت صعودی مرتب شده است. ابتدا عنصر وسط آرایه را پیدا کرده و داده مورد جستجو را با آن مقایسه می کنیم. سه حالت ممکن است رخ دهد:اگر داده مورد جستجو با عنصر وسط آرایه مساوی باشد، داده پیدا شده و مکان آن را باز می گردانیم.اگر داده مورد جستجو از عنصر وسط آرایه کوچکتر باشد، بنابراین باید در نیمه اول آرایه به دنبال آن جستجو نماییم. اگر داده مورد جستجو از عنصر وسط آرایه بزرگتر باشد، بنابراین باید در نیمه دوم آرایه به دنبال آن جستجو نماییم.چنانچه حالت اول رخ دهد، جستجو پایان یافته و مکان داده بازگردانده می شود. اما اگر حالت دوم یا سوم رخ دهد، عملیات جستجو به روش فوق مجددا برای نیمه اول یا نیمه دوم آرایه تکرار می شود. بدین ترتیب بازه مورد جستجو به نیمی از آرایه کاهش می یابد.عملیات تا زمانی ادامه می یابد که یا داده مورد نظر پیدا شود و یا بازه مورد جستجو آنقدر کوچک شود که داده ای باقی نماند (یعنی طول بازه مورد جستجو به صفر برسد)، که در اینصورت داده در آرایه وجود ندارد.

اسلاید 41: 2-2-6-10 الگوریتم جستجوی دودویی09949x=<>04850992474xx0232548<>=داده پیدا شدداده پیدا شد……50737599<>=داده پیدا شد……

اسلاید 42: 2-2-6-10 الگوریتم جستجوی دودوییint binarySearch(int A[], int n, int x) { int low, high, mid; low = 0; high = n-1; while (low <= high) { mid = (low + high) / 2; if (x == A[mid]) return(mid); else if (x < A[mid]) high = mid-1; else low = mid + 1; } return(-1);}

اسلاید 43: 2-2-6-10 الگوریتم جستجوی دودویی8112335425358627178012345678923حد بالاحد پایین

اسلاید 44: 2-2-6-10 الگوریتم جستجوی دودوییint recBinarySearch(int A[], int low, int high, int x) { int mid; if (low > high) return(-1); mid = (low + high) / 2; if (x == A[mid]) return(mid); else if (x < A[mid]) return(recBinarySearch(A, low, mid-1, x)); else return(recBinarySearch(A, mid+1, high, x)) ;}نحوه فراخواني اوليه اين تابع برای جستجوی داده 52 در آرايه 100 عنصري data بصورت است:recBinarySearch(data, 0, 99, 52)

اسلاید 45: 2-2-6-10 الگوریتم جستجوی دودوییبراي محاسبه زمان مورد نياز يك جستجو، بايد به اين نكته توجه كرد كه با هر مقايسه، بازه جستجو نصف مي شود.بدترين حالت زماني است كه داده اصلا پيدا نشود و يا در آخرين مقايسه (زماني كه تنها يك عنصر باقي مانده است) پيدا شود.سوال اينجاست كه چند بار مي توان اندازه آرايه را نصف كرد تا سرانجام به يك عنصر رسيد؟ بعنوان مثال در يك آرايه با 1.000.000 عنصر، تنها به 20 مقايسه نياز است. به همين دليل جستجوي دودويي يكي از بهترين روشهاي جستجو محسوب مي گردد.

اسلاید 46: 3-6-10 الگوریتم ادغاميكي ديگر از الگوريتمهاي مفيد، ادغام دو آرايه مرتب است. ادغام دو آرايه مرتب به معناي ايجاد يك آرايه مرتب ديگر است كه حاوي تمام عناصر دو آرايه اوليه باشد.يك روش ضعيف براي اين كار آن است كه ابتدا عناصر هر دو آرايه را در آرايه جواب كپي كنيم و سپس آرايه جواب را مرتب نماييم. اما مرتب سازي آرايه جواب زمان زيادي را صرف خواهد كرد.خوشبختانه الگوريتم بهتري وجود دارد كه در آن نيازي به مرتب سازي نهايي آرايه جواب نيست.طرح كلي اين الگوريتم به شرح زير است:يك شمارنده براي هريك از دو آرايه در نظر بگيريد و آنها را برابر صفر قرار دهيد.در هر مرحله، دو عنصري را كه شمارنده ها برروي آنها قرار دارند، با يكديگر مقايسه نماييد؛ عنصر كوچكتر را به آرايه جواب منتقل كرده و شمارنده مربوط به آن را يك واحد افزايش دهيد. اين مرحله را تا پايان يافتن يكي از دو آرايه تكرار كنيد.در پايان، تمام عناصر باقيمانده از آرايه ناتمام را به ترتيب به آرايه جواب منتقل نماييد.

اسلاید 47: 3-6-10 الگوریتم ادغام81443521732495664734349525664738141732

اسلاید 48: 3-6-10 الگوریتم ادغامvoid merge(int A[], int na, int B[], int nb, int C[], int &nc) { int i=0, j=0, k=0;while (i<na && j<nb) { if (A[i] < B[j]) { C[k] = A[i] ; i++ ; } else if (A[i] > B[j]) { C[k] = B[j] ; j++ ; } else { C[k] = A[i] ; i++ ; j ++ ; } k++ ; } for (; i<na; i++, k++) C[k] = A[i]; for (; j<nb; j++, k++) C[k] = B[j]; nc = k;