فصل 7 آرايهها
فصل 7
آرايهها
هدف کلی
آشنایی با قابلیتهای متعدد آرایه‌ها
هدفهای رفتاری
از دانشجو انتظار می‌رود، پس از خواندن این فصل،
1. با مفهوم آرایه آشنا شود.
2. بردار و ماتریس را بشناسد.
3. نحوة تعریف آرایه‌های یک‌بعدی را بیان کند.
4. کلاس حافظه در آرایه‌ها و نحوة مقداردهی اولیة آنها را بشناسد.
5. چگونگی تعریف آرایه‌های چندبعدی را بداند.
6. با نحوة انتقال آرایه به تابع آشنا شود.
7. با رشتهها، ثابت رشته‌ای، و متغیر رشته‌ای آشنایی پیدا کند.
8. هدف از به کاربردن آرایه‌ها در مرتب‌سازی و روشهای آن را بداند.
9. انواع رشته‌های جستجو را نام ببرد.
10. با توابع کتابخانه‌ای strcpy، strcat، strlen، strcmp، و strcmoi آشنا شود.
مقدمه
آرايه مجموعه عناصري است كه ويژگيها و صفات يكسانی دارند. به عبارت ديگر آرايه فضاي پيوسته‌ای از حافظة اصلي كامپيوتر است كه مي‌تواند چندين مقدار را در خود جاي دهد. همة عناصر يك آرايه از يك نوع‌اند و با انديس مشخص مي‌شوند.
از نظر رياضي معمولاً آرايههاي يك‌بعدي را بردار و آرايههاي دوبعدي را ماتريس نامند. همچنين به طريق مشابه مي‌توان آرايههاي چندبعدي را تعريف كرد.
تعريف آرايهها
در زبان C، آرايهها به شکل متغيرهاي معمولي تعريف مي‌شوند با اين تفاوت که نام آرايه بايد با مشخصة اندازه همراه باشد.
آرایة یک‌بعدی
آراية يك بعدي به صورت زير تعريف مي‌شود.
type array-name [array-size] ;
كه در آن array-name نام آرايه است كه از قانون نامگذاري متغيرها پيروي مي‌كند، array-size بزرگي و يا تعداد عناصر آرايه است و type نيز نوع عناصر آن را مشخص مي‌كند. براي مثال اگر آراية a داراي 7 عنصر از نوع int باشد، به‌اين صورت معرفي مي‌شود.
int a[7] ;
و خانه‌هاي اختصاص داده شده به آن به صورت متوالي و به شكل زير خواهد بود.
|
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
|
|
|
|
|
|
|
|
a[6] |
a[5] |
A[4] |
a[3] |
a[2] |
a[1] |
a[0] |
همان طور که می‌بینید شمارة خانه‌ها از صفر تا شش است. به عبارت ديگر حد پايين آن برابر صفر و حد بالاي آن يك واحد از طول يا بزرگي آرايه كمتر خواهد بود كه در مثال مزبور، حد بالاي آن برابر 6 است.
روش برنامه‌نویسی خوب آن است كه اندازة آرايه به صورت ثابت سمبوليك تعريف شود. از آنجا که با تغيير مقدار ثابت سمبوليک اندازة آرايه به راحتي تغيير می‌کند، اين عمل تغيير برنامه‌اي را که از آرايه سود مي‌‌برد سادهتر مي‌سازد.
v مثال 7ـ1 به دستورهای زير توجه کنيد.
#define size 50
int A[size] ;
در اينجا طول آرايه به صورت غيرمستقيم و با استفاده از دستور define مشخص شده است. کلاس حافظه ممکن است خودکار، ایستا، يا خارجی باشد، اما نمي‌تواند ثبات تعريف شود. بنابراين در حالت كلي مي‌توان آرايه‌ای يك‌بعدي را به صورت زير تعريف كرد.
storage-class data-type array-name [expression] ;
كه در آن expression ممکن است عدد صحيح يا متغير از نوع int و يا عبارت سادة محاسباتي باشد كه از تركيب مقادير عددي صحيح و متغيرهايي از نوع int با استفاده از عملگرهاي محاسباتي مانند + و - تشكيل شده است. نتيجة اين عبارت يك عدد صحيح خواهد بود که معرف بزرگي آرايه است. متعارف آن است كه بزرگي آرايه به صورت عدد صحيح و يا متغيري از نوع عدد صحيح تعيين گردد. واضح است كه اگر بزرگي آرايه به صورت متغير از نوع int بيان گردد، بايد مقدار آن هنگام تعريف عناصر آن تشخيص داده شود. براي آرايههايي که درون يک تابع يا بلوک تعريف مي‌گردند سطح ذخيره‌‌سازي خودکار و براي آرايههايي که بيرون از تابع تعريف مي‌گردند سطح ذخيره‌‌سازي خارجي پيش فرض خواهد بود.
v
v مثال 7ـ2 به نمونه‌هايي از تعريف چند آراية يك بعدي توجه کنيد.
int A[5] ;
float B[25] ;
static float C[15] ;
double x1[10] ;
char str[80] ;
در اين اعلان آراية A از نوع int با 5 عنصر و آراية B از نوع float با 25 عنصر و آرايه C از نوع float با 15 عنصر و از لحاظ کلاس حافظه نیز ایستا تعريف شده است. همچنين آراية x1 از نوع double و آراية str از نوع char با 80 عنصر تعريف شده است. (آرايههاي کاراکتري معمولاً براي نمايش رشتهها به کار مي روند.)
v
مراجعه به عناصر آرايه
وقتي كه آرايه‌اي را تعريف مي‌كنيم، كامپايلر مجموعه‌ای حافظه به صورت پيوسته يا متوالي براي آن در نظر ميگيرد. وقتي كه آرايه‌اي ايجاد شد، براي مراجعه به هر عنصر آن كافي است پس از نام آرايه، شمارة عنصر مورد نظر را در درون يك زوج كروشه قرار دهيم. همچنين در زبان C، انديس آرايه از صفر آغاز ميگردد.
v مثال 7ـ3 اگر A نام آرايه‌اي باشد كه از پيش تعريف شده و مقاديري نيز به آن اختصاص داده شده باشد در اين صورت دستور k = A[2] ; يك كپي از محتواي خانة شمارة 2 آرايه (يعني سومين عنصر آرايه) را به متغير k نسبت مي‌دهد.
يادآور مي‌شويم كه نامگذاري آرايهها از قانون نامگذاري متغيرها تبعيت مي‌كند و نوع عناصر آن نيز مانند متغيرهاي معمولي ممکن است int، float، char و جز آن باشد.
v
کلاسهای حافظه درآرايه (و نحوة مقداردهي اولية آنها)
گفتیم که آرايهها از نظر کلاس حافظه ممکن است خودکار، ایستا يا خارجي تعريف شوند، ولي نمي‌توانند ثبات تعريف شوند. آرايههاي از نوع خودکار، برخلاف متغيرهاي خودکار ممکن است هنگام تعريف، مقدار اوليه بپذيرند.
حال باتوجه به این توضيح‌ها مي‌توان شکل كلي مقداردهي اوليه به آرايهها را به صورت زير بيان كرد.
storage-class data-type array-name [size] = {value1 , value2 , … valuem} ;
كه در آن value1، valuem...value2 به ترتيب مقدار اولية اولين، دومين،... و m اُمين عنصر آرايه را مشخص مي‌كنند.
فرض كنيد كه آرايههاي a، b و c به صورت زير تعريف شده‌اند.
int a[7] = {1 , 2 , 3 , 4 , 5 , 6 , 7} ;
static float b[5] = {2.5 , -3.5 , 1.25 , 12.5 , 3.14} ;
char c[3] = {’a’ , ’b’ ,’c’} ;
ملاحظه مي‌كنيد كه آراية b ازنظر کلاس حافظة ایستا معرفي شده است، ولي کلاس حافظة دو آراية a و c به طور صريح بيان نشده است. بنابراين بايد فرض كرد كه هر دوي آنها خارجي‌اند. پس مقادير عناصر سه آراية مزبور به صورت زير خواهد بود.
a[0] = 1 b [0] = 2.5 c (0) = a
a[1] = 2 b [1] = 3.5 c (1) = b
a[2] = 3 b [2] = 1.25 c (2) = c
a[3] = 4 b [3] = 12.5
a[4] = 5 b [4] = 3.14
a[5] = 6
a[6] = 7
اگر آرايه‌اي به صورت مقداردهي اوليه تعريف گردد، نياز نيست بزرگي يا اندازة آن را مشخص كنيم.
v مثال 7ـ4 به اعلان آراية زير توجه کنيد.
int digit[ ] = {1 , 2 , 3 , 4 , 5} ;
كه عناصر آن به اين صورت خواهد بود.
digit[0] = 1
digit[1] = 2
digit[2] = 3
digit[3] = 4
digit[4] = 5
در مثالهاي ذکر شده، آرايههايي كه مقادير اوليه گرفته‌اند و كلاس حافظة آنها به طور صريح مشخص نشده از نوع خارجي فرض شده‌اند (يعني از نوع خودکار نيستند).
v
v مثال 7ـ5 برنامة زير نمرة امتحاني 25 نفر دانشجويان كلاسي را در درس رياضي ميخواند و تعداد دانشجويان مردود و همچنين تعداد دانشجوياني را كه نمرة امتحاني آنان كمتر از معدل كلاس است تعيين و در خروجي چاپ ميکند.
# include
main ()
{
int i , f = 0 , p = 0 ;
float a[25] , average , sum = 0 ;
for (i = 0 ; i<25 ; ++ i)
{
scanf ("%f " , &a[i]) ;
sum = sum + a[i] ;
if (a[i]<10)
f = f + 1 ;
}
average = sum / 25 ;
for (i = 0 ; i<25 ; ++i)
if (a[i] < average)
p = p + 1 ;
printf ("%f %d %d" , average , f , p) ;
}
در اين برنامه f و p به‌ترتيب معرف تعداد دانشجويان مردود و دانشجوياني است كه نمرة آنان كمتر از معدل كلاسي است و در آغاز مقدار اولية صفر داده شده است. در ضمن يادآور مي‌شويم كه اين برنامه را به طور متعارف نمي‌توانيم بدون استفاده از آرايه بنويسيم، زيرا قبل از اينكه نمرة امتحاني همة دانشجويان خوانده شود و معدل كلاس محاسبه گردد، نمي‌توان تعيين كرد كه آيا نمرة دانشجوي مورد نظر از معدل كلاس كمتر است يا نه. بنابراين چنانچه نمره‌های دانشجويان را با متغيری ساده معرفي كنيم، هر بار كه نمرة دانشجوي جديدي خوانده مي‌شود، در همان حافظه مي‌نشيند. لذا نمرة دانشجوي قبلي پاك ميگردد. پس اگر معدل كلاس را بدون استفاده از آرايه حساب كنيم، در پايان خواندن نمرة دانشجويان به حافظة كامپيوتر، فقط نمرة نفر آخر را در حافظه خواهيم داشت و درنتيجه در مورد دانشجويان اول تا بيست و چهارم نمي‌توانيم تعيين كنيم كه نمرة كدام يك از آنها كمتر از معدل كلاس است. پس در اين مثال استفاده از آرايه الزامي است. درنتيجة آن 25 نمره به 25 آدرس مختلف خوانده مي‌شود. همچنين بايد توجه كنيم كه چون انديس از صفر شروع مي‌شود، شمارة انديسها از صفر تا بيست و چهار خواهد بود.
v
آرايههاي چند بعدي
آرايههاي چندبعدي نيز مشابه آرايههاي يك‌بعدي تعريف مي‌گردند، با اين تفاوت كه طول يا بزرگي هر بعد آرايه در داخل يك زوج كروشه مشخص ميگردد. از اين رو آراية دوبعدي دو جفت کروشه و آراية سه بعدي سه جفت کروشه دارد.
بنابراين شکل كلي تعريف آراية n بعدي به صورت زير خواهد بود.
storage-class data-type array-name[size1][size2]… [sizen] ;
كه در آن sizen ,..., size2 , size 1 به‌ترتيب بزرگي بعد يكم تا n اُم آرايه است.
براي مثال يك آراية دوبعدي 3 Î 4 از نوع int را مي‌توان به صورت زير معرفي كرد.
int a[3][4] ;
در شکل 7ـ1 آراية دوبعدي m Î n (شامل m سطر و n ستون) را مي‌بینید.
به طريق مشابه مي‌توان آرايههاي 3 بعدي يا بيشتر را تعريف كرد، مانند مثالهاي زير.
int a[3][4][5] ;
float b[2][3][8][5] ;
char page[2][5][10] ;
|
ستون n |
|
ستون 3 |
ستون 2 |
ستون 1 |
| |||
|
a[0][n -1] |
... |
a[0][2] |
a[0][1] |
a[0][0] |
سطر 1 | |||
|
|
|
|
|
|
|
|
| |
|
a[1][n -1] |
... |
a[1][2] |
a[1][1] |
a[1][0] |
سطر 2 | |||
|
. |
|
|
|
. |
. |
. |
. | |
|
. |
|
|
|
. |
. |
. |
. | |
|
. |
|
|
|
. |
. |
. |
. | |
|
|
|
|
|
|
|
|
| |
|
a[m -1][n -1] |
... |
a[m - 1][2] |
a[m -1][1] |
a[m -1][0] |
سطر m | |||
شکل 7ـ1 آرایة دوبعدی m Î n
همچنين مي‌توان هنگام تعريف آرايههاي دوبعدي يا بالاتر به آنها مقدار اوليه نسبت داد كه البته بايد آراية مورد نظر از کلاس حافظة ایستا يا خارجي باشد.
v مثال 7ـ6 دستور زير را در نظر بگيريد.
int array[3][4] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12} ;
در اينجا فرض بر اين است كه آرايه از کلاس حافظة خارجي است. آراية مزبور را مي‌توان جدولي تصور كرد كه داراي 3 سطر و 4 ستون (4 عنصر در هر سطر) است. مقادير اوليه نيز به ترتيب به عناصر سطرها اختصاص مي‌يابد (يعني انديس يا زيرنويس سمت راست سريع‌تر حركت مي‌كند). بنابراين مقادير عناصر آراية مزبور به صورت زير خواهد بود.
array[0][0] = 1 array[0][1] = 2 array[0][2] = 3 array[0][3] = 4
array[1][0] = 5 array[1][1] = 6 array[1][2] = 7 array[1][3] = 8
array[2][0] = 9 array[2][1] = 10 array[2][2] = 11 array[2][3] = 12
توجه داشته باشيد كه عملكرد يا محدودة تغييرات انديس اول (انديس سمت چپ) از صفر تا 2 و انديس دوم (انديس سمت راست) از صفر تا 3 است.
v
نحوة اختصاص مقادير اوليه به عناصر آرايه را مي‌توان با دسته‌بندي كردن آنها در داخل زوج آكولاد تغيير داد. برای مثال در آراية دوبعدي مقادير داخل هر زوج آكولاد دروني به ترتيب به عناصر يكي از سطرها نسبت داده خواهد شد. اگر تعداد مقادير موجود در درون هر زوج آكولاد دروني كمتر از تعداد عناصر سطر متناظر آن باشد، به بقية عناصر سطر مزبور مقدار صفر نسبت داده خواهد شد. براي مثال، نتيجة عملكرد دستور زیر
int array[3][4] = {
{1 , 2 , 3 , 4} ,
{5 , 6 , 7 , 8} ,
{9 , 10 , 11 , 12}
} ;
با مثال 7ـ6 يكسان خواهد بود.
حال دستور زير را درنظر بگيريد.
int array[3][4] = {
{1 , 2 , 3} ,
{4, 5 , 6} ,
{7, 8 , 9}
} ;
به عناصر ستون چهارم مقاديري نسبت داده نشده است. لذا مقادير آنها برابر صفر خواهد شد؛ يعني مقادير عناصر آراية مورد نظر به صورت زير خواهد بود.
array[0][0] = 1 array[0][1] = 2 array[0][2] = 3 array[0][3] = 0
array[1][0] = 4 array[1][1] = 5 array[1][2] = 6 array[1][3] = 0
array[2][0] = 7 array[2][1] = 8 array[2][2] = 9 array[2][3] = 0
درحالي كه اگر آراية مزبور را به صورت int array[3][4] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9) ; تعريف كنيم، مقادير نسبت داده شده به عناصر آراية مورد نظر به صورت خواهد بود.
array[0][0] = 1 array[0][1] = 2 array[0][2] = 3 array[0][3] = 4
array[1][0] = 5 array[1][1] = 6 array[1][2] = 7 array[1][3] = 8
array[2][0] = 9 array[2][1] = 0 array[2][2] = 0 array[2][3] = 0
انتقال آرايه به تابع
در زبان C، وقتي كه نام آرايه به عنوان آرگومان تابع ظاهر مي‌شود، آدرس اولين عنصر آرايه تعبير ميگردد. بنابراين هنگامي كه آرايه‌اي را به عنوان آرگومان به تابع گذر يا انتقال مي‌دهيم، تمامي آرايه به آن تابع انتقال مي‌يابد. اين روش انتقال آرگومان به تابع، با آنچه در مورد انتقال متغيرهاي معمولي به تابع در فصل مربوط به توابع بيان شد و فراخواني با مقدار نامیدیم متفاوت است. روش فراخواني جديد را فراخواني با آدرس يا فراخواني با ارجاع نامند. در اين روش به جاي كپي داده‌ها، آدرس آنها به تابع انتقال مي‌يابد. تشريح كامل اين روش را در فصل 8 بيان می‌کنیم.
براي گذر دادن آرايه‌ای به تابع بايد فقط نام آن بدون كروشه و بدون انديس، به عنوان آرگومان واقعي، در فراخواني تابع ظاهر گردد. در تعريف تابع نيز بايد آرگومان فرمال متناظر آن به همان طريق نوشته شود و به عنوان آرايه تعريف گردد. بدين طريق كه نام آرايه همراه با يك زوج كروشة بدون انديس نوشته شود و نوع داده آن نيز مشخص گردد.
v مثال 7ـ7 قطعه برنامة زير نحوة فرستادن يا گذردادن آرايه را به تابع نشان مي‌دهد.
main()
{
int n ; /* variable declaration */
float avg ; /* variable declaration */
float list [100] ; /* array definition */
float average () ; /* function declaration */
….
avg = average (n , list) ;
….
}
float average (a , x) /* function definition */
int a ; /* formal argument declaration */
float x[ ] ; /* formal argument (array) declaration */
{
….
}
ملاحظه مي‌كنيد كه تابع فرعي average در داخل تابع اصلي فراخوانده شده است. اين تابع داراي دو آرگومان است: يكي متغير n كه نوع آن int و معرف تعداد عناصر آرايه است. ديگري آراية يك‌بعدي list كه نوع عناصر آن float است. همچنين مي‌بينيد كه در فراخواني تابع، آراية list به صورت متغير ساده ظاهر شده است.
در تعريف تابع نيز در سطر اول دو آرگومان فرمال را كه a و x ناميده شده‌اند مشاهده مي‌كنيد. سپس در دو سطر بعدي دو آرگومان مزبور به ترتيب به‌صورت int و آراية يك‌بعدي از نوع float توصيف شده‌اند. ملاحظه مي‌كنيد كه بين آرگومان واقعي n و آرگومان فرمال a تناظر وجود دارد. به طريق مشابه تناظري بين آرگومان واقعي list و آرگومان فرمال x وجود دارد. در واقع لازم نيست كه آرگومانهاي واقعي با آرگومانهاي فرمال همنام باشند و به همين دليل آرگومانهاي فرمال را متغيرهاي مجازي يا ساختگي نيز مي‌نامند. همچنين ملاحظه مي‌كنيد كه بزرگي آرايه x، در توصيف آرگومان فرمال، مشخص نشده است. همين طور مشاهده مي‌كنيد كه در تعريف تابع به صورت پيش‌نمونه يا prototype در تابع اصلي، پس از نام تابع فقط يك زوج پرانتز تهي به كار رفته است.
حال اگر در تعريف تابع فرعي، توصيف آرگومانهاي آن نيز در همان خط اول تابع، پس از ذكر نام تابع در درون زوج پرانتز انجام گيرد، بايد در تعريف پيش‌نمونه در تابع اصلي نيز اين تناظر محفوظ بماند؛ يعني بايد پس از نام تابع آرگومانهاي آن نيز در درون زوج پرانتز توصيف گردند (برخلاف حالت قبل كه فقط يك زوج پرانتز تهي به كار می‌رفت). قطعه برنامة زير همان مثال قبلي را با اين شيوه نشان مي‌دهد.
main
{
int n ; /* variable declaration */
float avg ; /* variable declaration */
float list [100] ; /* array definiation */
float average (int , float[ ]) ; /* function declaration */
....
avg = average (n , list) ;
....
}
float average (int a , float x [ ]) /* function definition */
{
....
....
}
v
در انتقال نام آرايه به تابع، آدرس اولين عنصر آرايه به تابع منتقل مي‌شود؛ يعني نام آرايه، آدرس اولين عنصر آرايه تفسير مي‌شود. وقتي كه تابع فراخواني مي‌شود، اين آدرس به آرگومان فرمال متناظر آن اختصاص مي‌يابد. پس آرگومان مزبور به عنوان اشاره‌گر به اولين عنصر آرايه برمي‌گردد. بنابراين هر عملي كه در تابع فرعي روي آرايه انجام گيرد، نتيجة آن در تابع اصلي (يا تابع فراخواننده) نيز منعكس مي‌شود. به طوري كه بيان شد، اين شيوة فراخواني تابع را فراخواني با آدرس نامند.
وقتي كه در درون تابع فراخوانده شده به عنصر آرايه مراجعه مي‌شود، انديس عنصر مورد نظر به مقدار اشاره‌گر افزوده ميگردد تا به آدرس آن عنصر در درون آرايه دلالت نمايد. پس هر عنصري از آرايه به سادگي در درون تابع در دسترس قرار می‌گيرد و به طوري كه گفتیم هر عنصر آرايه كه در درون تابع تغيير يابد، اثر اين تغيير در تابع فراخواننده نيز منعكس خواهد شد.
v مثال 7ـ8 برنامة زير برنامة ساده‌ای را نشان مي‌دهد كه آرايه‌ای 3 عنصري را به تابع گذر مي‌دهد و مقادير عنصر آرايه در درون آن تابع تغيير مي‌يابد. مقادير عناصر آرايه در سه موقعيت از برنامه نوشته شده است تا اثر اين تغييرات را نشان دهد.
# include
main ()
{
int count , a [3] ; /* array definition */
void modify (int a[ ]) ; / * function declaration */
printf("\n from main , before calling the function: \n") ;
for (count = 0 ; count<=2 ; + + count)
{
a[count] = count + 1 ;
printf ("a[%d] = %d\n" , count , a[count]) ;
}
modify(a) ;
printf ("\n from main , after calling the function: \n") ;
for (count = 0 ; count<=2 ; ++ count)
printf ("a[%d] = %d\n" , count , a[count]) ;
}
void modify (int a[ ]) /* function definition */
{
int count ;
printf ("\n from the function , after modifying the values: \n") ;
for (count = 0 ; count< = 2 ; ++ count)
{
a[count] = -9 ;
printf ("a[%d] = %d" , count , a [count]) ;
}
return ;
}
در اولين حلقه‌اي كه در درون تابع اصلي ظاهرمي‌گردد، مقاديرa [0] = 1 , a [1] = 2 , a [2] = 3 به عناصر آرايه نسبت داده مي‌شود و همين مقادير با دستورprintf نمايش می‌یابد. سپس، آراية مزبور به تابع modify گذر داده مي‌شود كه در درون تابع مزبور به هريك از عناصر آرايه مقدار 9- نسبت داده مي‌شود. سپس همين مقادير جديد در آن تابع چاپ ميگردد. بالاخره پس از برگشت كنترل از تابع فرعي به تابع اصلي، دوباره مقادير عناصر آرايه نمايش می‌یابد.
اگر برنامة مزبور اجرا گردد، خروجي زير را خواهيم داشت.
from main , before calling the function:
a [0] = 1
a [1] = 2
a [2] = 3
from the function , after modifying the values:
a [0] = -9
a [1] = -9
a [2] = -9
from main , after calling the function:
a [0] = -9
a [1] = -9
a [2] = -9
اين نتايج نشان مي‌دهد كه تغييرات اعمال شده با تابع modify روي آرايه، در تابع اصلي نيز منعكس شده است.
v
آرايهها و رشتهها
در زبان C رشتهها، آرايه‌اي از كاراكترها تعريف مي‌شوند به طوري که هر کاراکتر رشته، درون يک عنصر از آرايه ذخيره ميگردد. هر رشته به كاراكتر null كه نشانة پايان است خاتمه مي‌يابد. ثابت رشته‌اي در داخل دوبل گيومه قرار می‌گیرد و وقتي كه ذخيره ميگردد، كاراكتر null به طور خودکار به انتهاي آن افزوده مي‌شود. در داخل يك برنامه، كاراكتر null در فرم escape sequence با '\0' نشان داده مي‌شود. ثابت رشته‌اي آرايه‌اي را معرفي مي‌كند كه محدوده يا انديس پايين آن صفر و محدوده يا انديس بالاي آن تعداد كاراكترهايي است كه در رشته وجود دارد.
v مثال 7ـ9 به رشتة زير توجه کنيد.
" payam noor university "
اين رشته آرايه‌ای 22 كاراكتري است (دو فضاي خالي بين کلمات و يک \0 نيز كاراكتر شمرده مي‌شوند). تعريف اين رشته ممکن است در آرايه‌ای کاراکتري به شکل زير باشد.
char str[ ] = " payam noor university "
متغيرهاي رشته‌اي متغيرهايي‌اند كه مقادير آنها ممکن است يك رشته باشد. در واقع متغيرهاي رشته‌اي، آرايههايي از نوع char اند.
v
v مثال 7ـ10 برنامة زير 15 رشته (مثلاً اسامي 15 نفر) را ميخواند و آنها را در سطرهاي متوالي چاپ مي‌كند. فرض بر اين است كه طول هر رشته با درنظر گرفتن null character پايان رشته حداكثر 12 كاراكتر است.
# include
main ()
{
char name[12] ;
int i ;
for (i = 1 , i < = 15 ; ++i)
{
scanf ("%s" , name) ;
printf ("\n %s" , name) ;
}
}
ملاحظه مي‌كنيد كه متغير رشته‌اي name به صورت آرايه معرفي شده است. در ضمن در خواندن اطلاعات به كمك تابع scanf، فقط نام متغير، بدون اپراتور آدرس (يعني بدون علامت `&') و بدون ذكر انديس آرايه، به كار می‌رود، زيرا به طوري كه گفتیم، نام آرايه آدرس اولين خانه يا اولين عنصر آن است. همچنين هم در موقع خواندن مقدار براي name و همين طور در چاپ مقدار آن از كد فرمت %s استفاده شده است.
مي‌توان مجموعه‌ای از رشتهها را به صورت آرايه‌اي از رشتهها تعريف كرد. در اينجا چون خود رشته به تنهايي يك آرايه است، هر مجموعه از رشتهها مي‌توانند آرايه‌ای دوبعدي را تشكيل دهند كه اگر آنها را به صورت جدول مستطيل شكل تصور كنيم، هر سطر اين جدول معرف يكي از رشتهها خواهد بود.
v
v مثال 7ـ11 قطعه برنامة زير اسامي 15 نفر را به آراية رشته‌اي name ميخواند و آنها را در سطرهاي متوالي چاپ مي‌كند.
# include
main ()
{
char name[15][12] ;
int i ;
for (i = 0 ; i<15 ; ++i)
scanf ("%s" , &name[i]) ;
for (i = 0 ; i<15 ; ++i)
printf ("\n%s" , name[i]);
}
ملاحظه كنيد كه در خواندن اطلاعات رشته‌اي به آرايه و در چاپ كردن آن فقط بعد اول آرايه به كار برده شده است؛ يعني در واقع اگر آراية دو بعدي در اين مجموعه از رشتهها را، همان طور كه گفتیم، جدولی مستطيل شكل فرض كنيم كه در هر سطر آن يك رشته قرار دارد، در خواندن اطلاعات هر بار سطری خوانده مي‌شود كه آدرس آن سطر و در نتيجه اپراتور آدرس نيز به كار رفته است. به اين طريق مشابه در چاپ كردن آن نيز هر بار اطلاعات يك سطر كه شامل يك رشته است چاپ ميگردد.
v
روشهاي مرتب سازي
يکي از کاربردهاي متداول آرايهها، استفاده از آنها در روشهاي مرتب سازي است. چنانچه مجموعه‌اي از داده‌ها يا اطلاعات، براساس ويژگي يا نظم خاصی سازمان‌دهي شوند، اين عمل را مرتبسازي گويند. در اين صورت پيدا كردن عنصری دلخواه در درون آن مجموعه، سادهتر و سريع‌تر انجام ميگيرد. بنابراين عمل مرتب كردن، به منظور سرعت بخشيدن به عمل جستجوست.
تعداد مقايسه‌‌ها و نيز تعداد جابه‌جايي عناصر، از عوامل اساسي در مورد سرعت مرتب‌‌سازيهایند. طبيعي است كه هر روش مرتبسازي كه سرعت بالا و منطق ساده‌تری داشته باشد و همچنين حافظة كمتري اشغال كند مطلوب‌تر است. بر اين اساس روشهاي متعددي مطرح شده که در ادامه چند نمونه را بررسي مي‌کنیم.
روش مرتبسازي حبابي
اين روش از نظر منطق، ساده‌ترين و از نظر كارآيي پايين‌‌ترين روش مرتبسازي اطلاعات به شمار مي‌رود. در اين روش ابتدا عنصر اول با عنصر دوم مقايسه مي‌شود. اگر عنصر اول بزرگ‌تر از دومي باشد، جاي آن دو تعويض مي‌شود. سپس اين عمل در مورد عنصر دوم با سوم و همين‌طور براي بقية عناصر به صورت متوالي انجام ميگيرد؛ يعني، در پايان با عنصر n-1 اُم مقايسه مي‌شود كه اگر بزرگ‌تر از آن بود جايشان تعويض مي‌شود. وقتي كه اين عمل يك بار كامل شد، بزرگترين عنصر آرايه به آخر آرايه منتقل مي‌شود. حال اگر خانة آخر را ناديده بگيريم و اين عمل را دوباره براي خانه‌ها يا عناصر 1 تا n-1 تكرار كنيم، اين بار بزرگترين عنصر خانه‌ها 1 تا n-1 (كه دومين عنصر بزرگ آرايه خواهد بود) به خانة n-1 آرايه منتقل مي‌شود. اگر اين عمل را به صورت تكراري براي n-1 بار انجام دهيم و براي سرعت عمل بيشتر، در هر بار تكرار نيز خانة آخر محدودة جاري آرايه را ناديده بگيريم، يعني هر بار از طول ناحية مورد مقايسه يك واحد كاسته شود، در پايان، عناصر آرايه به صورت صعودي مرتب ميگردد. اگر بخواهيم كه عناصر آراية مورد نظر به‌صورت نزولي مرتب شود، بايد در مقايسة دو عنصر متوالي ai با ai+1، چنانچه ai كوچك‌تر از ai+1 باشد، جاي آن دو با يكديگر تعويض شود.
از آنجايي كه در اين روش مرتب سازي در هر بار تكرار، بزرگترين عنصر آرايه به سمت بالا يا انتهاي آرايه حركت مي‌كند (مانند حبابهاي هوا كه در آب جوش موجود است)، آن را مرتب سازي حبابي نامند.
v مثال 7ـ12 تابع زير آراية n عنصري A را به روش حبابي مرتب ميکند.
void BubbleSort (int A[ ] , int n)
{
int i , j , temp ;
for (i =1 ; i
for (j =0 ; j
if (A[ j] > A[ j+1])
{
temp = A [ j] ;
A[ j] = A[ j+1] ;
A[ j+1] = temp ;
}
}
v
روش مرتب سازي انتخابي
در اين روش مرتب سازي، شيوة كار بدين صورت است كه محل بزرگترين عنصر را در درون آراية n عنصري مورد نظر می‌یابیم و جاي آن را با عنصر آخر يعني an عوض مي‌كنيم؛ سپس بين عناصر a1 تا an-1 محل بزرگترين عنصر را (كه در واقع دومين عنصر بزرگ آراية اصلي خواهد بود) به‌دست مي‌آوريم و جاي آن را با عنصر an-1 عوض مي‌كنيم. اين كار را n-1 بار تكرار مي‌كنيم. در اين صورت در تكرار آخر فقط دو عنصر a1 و a2 را خواهيم داشت كه بايد بزرگترين آن دو در خانة a2 قرار گيرد.
برتري اين روش نسبت به روش مرتبسازي حبابي آن است كه تعداد تعويض عناصر كمتر مي‌شود، زيرا در اين روش، در هر تكرار حداكثر يكبار جابه‌جايي انجام ميگيرد.
v مثال 7ـ13 تابع زير آراية n عنصري A را به روش انتخابي مرتب ميکند.
void SelectionSort (int a[ ] , int n)
{
int i , max , temp ;
for (i = 1 ; i
{
max = 0 ;
for (j =1 ; j<= n-i+1 ; + + j)
if (A[ j] > A[max])
max = j ;
if (max != n-i)
{
temp = A[max] ;
A[max] = A[n-i] ;
A[n-i] = temp ;
}
}
}
v
روشهاي جستجو
يکي ديگراز کاربردهاي متداول آرايهها، استفاده از آنها در روشهاي جستجوست. هر گاه در داخل مجموعه‌اي از عناصر، دنبال عنصر خاصي بگرديم، اين عمل را جستجو كردن نامند. جستجو، در اغلب زمينه‌ها، ب‌ويژه در مورد بانکهاي اطلاعاتي و سيستمهاي تجاري، كاربرد زيادي دارند.
شيوه‌هاي متعددي براي جستجو وجود دارد كه دو روش متداول آن را در ادامه بررسي مي‌کنیم.
جستجو به روش خطي
اين روش ساده‌ترين راه براي جستجو در آرايه يا جدول نامرتب است. براي اين کار عنصر مورد جستجو را به طور متوالي با عناصر اول تا n اُم آن جدول مقايسه مي‌كنيم. چنانچه در حين مقايسه، عنصر مزبور پيدا شد، شمارة آن يادداشت می‌شود و عمل جستجو خاتمه مي‌يابد. در غير اين صورت پيغام مناسب صادر مي‌شود. در اين روش رابطة بين تعداد عناصر جدول و تعداد مقايسه‌‌ها به صورت معادلة درجه اول خواهد بود.
v مثال 7ـ14 تابع زير عنصر x را در آراية n عنصري A به روش جستجوي خطي جستجو مي‌كند. اگر پيدا شد، انديس آن، و در غير اين صورت مقدار صفر را برمي‌گرداند.
int LinearSearch (int A[ ] , int n , int x)
{
int i ;
for (i = 0 ; i < n ; + + i)
if (x = = A[i])
return (i +1) ;
return (0) ;
}
v
جستجو به روش دودويي
روش ديگر براي جستجوي عنصري در داخل جدول يا آرايه روش دودويي است. اين روش در صورتي امكان‌پذير است كه عناصر جدول مورد نظر مرتب شده باشد. همچنين، در مقايسه با روش قبلي، از سرعت بيشتري برخوردار است.
در اين روش، عنصر اول و عنصر آخر جدول را با دو متغير مانند L و H نمايش مي‌دهيم و سپس عنصر مورد جستجو را با عنصر وسطي جدول يا m = (L + H) / 2 مقايسه مي‌كنيم. اگر مساوي بود، عنصر مورد جستجو پيدا شده است. در غير اين صورت، چنانچه عنصر مورد جستجو از عنصر وسطي بزرگ‌تر باشد، L را مساوي m+l وگرنه H را مساوي m-1 قرار مي‌دهيم. سپس اين عمليات را باز هم تكرار مي‌كنيم؛ يعني باز هم عنصر وسطي جدول حاصل را به‌دست مي‌آوريم و عنصر مورد جستجو را با مقدار آن مقايسه مي‌كنيم. اين عمل تا موقعي كه شرط L ≤ H برقرار نباشد، ادامه مي‌يابد و پيغامي مبني بر عدم وجود عنصر مورد جستجو در داخل جدول مورد نظر چاپ ميگردد.
v مثال 7ـ15 مراحل الگوريتم جستجو به روش دودويي براي ده عدد زير در جدول نمايش داده شده است.
65 , 141 , 192 , 205 , 218 , 389 , 424 , 500 , 538 , 567
|
جستجوي عدد 567 |
جستجوي عدد 205 | ||||||
|
m |
h |
l |
X |
m |
h |
l |
X |
|
5 |
10 |
1 |
218 |
5 |
10 |
1 |
218 |
|
8 |
10 |
6 |
500 |
2 |
4 |
1 |
141 |
|
9 |
10 |
9 |
538 |
3 |
4 |
3 |
192 |
|
10 |
10 |
10 |
567 |
4 |
4 |
4 |
205 |
v
v مثال 7ـ16 تابع زير در آراية مرتب شدة n عنصري، به روش دودويي عنصر x را جستجو مي‌كند. اگر پيدا شد، انديس آن و در غير اين صورت مقدار صفر را برمي‌گرداند.
int BinarySearch (int A[ ] , int n , int x)
{
int middle , L , H ;
L = 0 ;
H = n-1 ;
while (L <= H)
{
middle = (L+H)/2 ;
if (x = = A[middle])
return (middle +1) ;
if (x >A[middle])
L = middle +1 ;
else
H = middle -1 ;
}
return (0) ;
}
v
توابع كتابخانه‌اي (در مورد رشتهها)
اغلب نسخه‌‌های زبان C، مجموعة وسيعي از توابع كتابخانه‌اي در مورد عمليات روي رشتهها را پشتيباني مي‌كنند كه در مبحث توابع كتابخانه‌اي بحث کردیم. چند تابع بسيار متداول كه در نوشتن برنامه‌ها كاربرد زيادي دارند در جدول 7ـ1 آمده است.
جدول 7ـ1 چند تابع متداول در برنامه‌های کاربردی
|
عمل تابع |
نام تابع |
|
رشتة s2 را روي رشتة s1 كپي مي‌كند. |
strcpy (s1 , s2) |
|
رشتة s2 را به دنبال رشتة s1 ملحق (ضميمه) مي‌كند. |
strcat (s1 , s2) |
|
طول رشتة s را برمي‌گرداند. |
strlen (s) |
|
رشتة s1 را با رشتة s2 مقايسه مي‌كند. |
strcmp (s1, s2) |
اگر بخواهيم درمورد مقايسة دو رشته، تمايز بين حروف بزرگ و كوچك ناديده گرفته شود، تابع strcmp را به صورت strcmpi به كار مي‌بریم.
در ضمن يادآور مي‌شويم كه توابع كتابخانه‌اي مربوط به رشتهها در فايل string.h قرار دارند. پس اگر بخواهيم در برنامه‌اي از اين تابع استفاده كنيم، بايد دستور # include را نيز قبل از تابع main به كار بريم.
حال به چند مثال در مورد رشتهها توجه کنيد.
v مثال 7ـ17 برنامة زير نحوة استفاده و كاربرد چند تابع كتابخانه‌اي را نشان مي‌دهد.
# include
# include
main ()
{
char s1[80] , s2[80] , s3[80] ;
gets (s1) ;
gets (s2) ;
printf ("\n Lengths: %d %d\n" , strlen (s1) , strlen (s2)) ;
if (!strcmp (s1 , s2))
printf ("\n The strings are equal\n") ;
strcpy (s1 , s3) ;
strcat (s1 , s2) ;
printf ("\n %s" , s3) ;
printf ("\n %s" , s1) ;
}
اين برنامه دو رشته از ورودي می‌خواند و آن دو را به هم متصل ميکند.اگر اين برنامه را اجرا و براي دو رشتة s1 و s2 كلمة "computer science" را وارد کنیم، خروجي برنامة مزبور به صورت زير خواهد بود.
Lengths: 16 16
The strings are equal
computer science
computer sciencecomputer science
v
v مثال 7ـ18 برنامه‌اي بنويسيد كه اسامي n نفر دانشجو را بخواند، سپس آنها را به ترتيب الفبا مرتب و چاپ كند. n، حداكثر 15 است كه با اولين دستور ورودي خوانده مي‌شود.
# include
# include
main ()
{
int i , n , j ;
char name [15][12] , temp [12] ;
scanf ("%d" , &n) ;
for (i=0 ; a
scanf ("%s" , &name[i]) ;
for (i=1 ; i
for (j=0 ; j
if (strcmp (name[j] , name [j+1]) > 0)
{
strcpy (temp , name [j]) ;
strcpy (name[j] , name [j+1]) ;
strcpy (name[j+1] , temp) ;
}
for (i=0 ; i
printf ("\n %s" , name[i]) ;
}
در اين برنامه از آرايههاي دوبعدي، روش مرتب سازي حبابي و چند تابع کتابخانه‌اي رشته‌اي استفاده شده است.
v
خودآزمایی 7
1.با استفاده از آرايه برنامه‌اي بنويسيد که جمله‌های اول تا دهم سري فيبوناچي را محاسبه و چاپ كند.
2. برنامه‌ای بنويسيد که اعداد زوج 2 تا 20 را به عناصر آرايه‌ای 10 عنصري نسبت دهد و سپس شمارة هر عنصر و مقدار متناظر آن را در دو ستون نشان دهد و چاپ كند.
3. برنامة زير آرايه‌ای 10 عنصري را، هنگام تعريف آن، مقداردهي اوليه مي‌كند. سپس مجموع مقادير آن را محاسبه و چاپ مي‌كند. خروجي این برنامه چیست؟
# include
# define size 10
main()
{
int i , total = 0 ;
int A[size] = {10 , 9 , 8 , 7 , 6 , 5 , -5 , -6 , -7 , -8} ;
for (i = 0 ; i
total += A[i] ;
printf (" Sum = %d" , total) ;
}
4. برنامه‌اي بنويسيد كه عددي صحيح را دريافت کند و معادل آن را به شکل باينري (در مبناي 2) چاپ كند.
5. برنامه‌اي بنويسيد كه متني را از ورودي بخواند وحروف کوچک را به حروف بزرگ تبديل کند.
6. برنامه‌اي بنويسيد كه با استفاده از تابع كتابخانه‌اي rand كه اعداد تصادفي ايجاد مي‌كند، 6000 بار پرتاب تاس تخته نرد را شبيه‌سازي كند.
7. تفاوت بين فراخواني با مقدار و فراخواني با آدرس (يا فراخواني با ارجاع) در اين فصل به اختصار بيان شد. برنامه‌ای بنویسید که تفاوت انتقال (ارسال) تمامي آرايه به يك تابع (يعني درواقع ارسال آدرس آرايه به تابع) يا فراخواني با آدرس را با انتقال عنصري از آرايه به تابع، يعني فراخواني با مقدار، نشان مي‌دهد، به‌طوري كه در حلقة for اول مقادير آرايه چاپ گردد. سپس تابع modifyarray(a) فراخواني شود. در اين فراخواني، نام آرايه (يعني آدرس آغاز آرايه) به تابع انتقال يابد. تابع مزبور مقدار هريك از عناصر آرايه را دو برابر كند. پس از برگشت كنترل به تابع اصلي، مقادير آرايه چاپ گردد. نتيجة عملكرد تابع فرعي روي آرايه در تابع اصلي نيز منعكس شود. سپس با فراخواني تابع modifyelement يك عنصر آرايه، به آن تابع انتقال يابد (كه درواقع فراخواني با مقدار است). تابع مزبور مقدار عنصر دريافتي را دوبرابر كند و نتيجه چاپ گردد. پس از برگشت مجدد كنترل به تابع اصلي، مقدار عنصر مزبور دوباره چاپ شود و نتيجة عملكرد تابع modifyelement در تابع اصلي منعكس نشود.
8. در علم آمار، سه پارامتر ميانگين، ميانه و مد مجموعه‌ای از مقادير به شکل زير تعريف مي‌شوند.
الف) ميانگين (mean) n مقدار a1 , a2 ,... , anكه آن را ميانگين حسابي نيز نامند، برابر است با:
ب) اگر عناصر را به صورت صعودي مرتب كنيم، چنانچه تعداد عناصر فرد باشد، مقدار عنصر وسطي را ميانه (media) نامند و چنانچه تعداد عناصر زوج باشد، نصف مجموع دو مقدار وسطي را ميانه نامند.
ج) مد (mode) عبارت از عنصري است كه بيشتر از بقيه تكرار شده باشد.
نتيجه عبارت است از يك پرسش از 99 نفر كه مقادير عددي صحيح بين 1 تا 10 است. برنامه‌اي بنويسيد كه 3 پارامتر ميانگين، ميانه و مد را محاسبه و چاپ کند و همچنين نمودار ميله‌اي يا هيستوگرام پاسخها را به صورت ستاره رسم كند.
9. برنامه‌اي بنويسيد كه 100 عدد را به حافظه بخواند. سپس عددي را از طريق ورودي دريافت كند و با فراخوانده شدن تابعي، عدد دريافتي در درون مجموعه اعداد جستجو شود. اگر پيدا شد، تابع مزبور شمارة آن را برگرداند. در غير اين صورت مقدار 1- برگرداند. سپس در تابع اصلي پيغام مناسبي مبني بر اينكه عدد مورد نظر پيدا شده است يا نه چاپ شود.
10. برنامه‌اي بنويسيد كه عناصر دو ماتريس a و b را كه داراي m سطر و n ستون باشند، به حافظه بخواند و سپس مجموع آن دو را براساس قانون جمع ماتريسها به دست آورد و چاپ كند. m و n حداكثر 8 اند كه با اولين دستور ورودي خوانده مي‌شوند.
11. برنامه‌اي بنويسيد كه عناصر دو ماتريس a و b را به حافظه بخواند و سپس حاصل ضرب آن دو را براساس قانون ضرب ماتريسها به دست آورد و نتيجه را به فرم ماتريس (آراية دوبعدي) چاپ كند. ماتريس a داراي m سطر و n ستون و ماتريس b، داراي n سطر و h ستون است. m و n و h حداكثر 7 اند كه از اولين دستور ورودي خوانده مي‌شوند.
12. برنامه‌اي بنويسيد كه يك سطر متن را با استفاده از تابع getchar و هر بار يك كاراكتر به يك آراية كاراكتري بخواند. سپس آراية كاراكتري مزبور را به صورت رشته چاپ كند.
13. تابعي بنويسيد كه طول رشته‌ای را به دست آورد و برگرداند.
14. تابعي بنويسيد كه بدون استفاده از تابع كتابخانه‌اي strcat، دو رشته را به هم ملحق كند (يعني رشتة دوم را به آخر رشتة اول ضميمه کند).
15. تابعي بنويسيد كه در درون يك رشته، زير رشتة ديگري را جستجو كند. اگر وجود داشت، محل آن (يعني از چندمين كاراكتر رشته اول شروع شده است) را برگرداند، در غير اين صورت مقدار 1- برگرداند.
16. تابعي بنويسيد كه در درون رشتة S1، از كاراكتر i اُم آن به طول j كاراكتر در رشته S2 كپي كند.
17. برنامه‌اي بنويسيد كه مجموعه‌ای از رشتهها را به حافظه بخواند و سپس با فراخوانده شدن تابعي، رشته‌هاي مزبور به ترتيب الفبا مرتب کند. تعداد رشتهها حداكثر 10 رشته است كه پايان آن با كلمة "END" مشخص شده است.
مطالب مشابه :
فرترن
برای اضافه کردن فايل برنامه فرترن ساختار برنامه در فرترن اين دستور برای دريافت
جاوا
فايل دريافت شده در مرحله دوم را در برنامه ارائه شده ( موجود در فايل java.awt.Graphic.html
برنامه هاي تنظيمات فرآيند
كليه Setting هاي نرم افزاري در فايل با دريافت موقعيت برنامه ، فايل Xyminmax.txt در
واژه
و نحوه دريافت فايل در برنامه نویسی زبان سطح پایین زبانی است که به ماشین فرترن فرترن
فصل 7 آرايهها
رشتهها در فايل string.h قرار دارند. پس اگر بخواهيم در برنامه‌اي از اين را دريافت کند
آشنایی با پسوند ها
اين فايل در برنامه هاي زبان برنامه نويسي فرترن نيز و دريافت فايل ها بين
برچسب :
برنامه دريافت فايل در فرترن