C הקדמה לתכנות ב
C++ הקדמה להיררכית מחלקות ב	הצגה מזורזת :C++ הבנת	דף הבית

שיעור 4: מערכים ומיון בועות (Bubble Sort)

בחלק זה, תיצור תוכנית קטנה שיוצרת 10 מספרים אקראיים וממיינת אותם. התחל עורך והדפס את הקוד הבא:

#include <stdio.h> 
 
#define MAX 10 
 
int a[MAX]; 
int rand_seed=10; 
 
int rand() /* from K&R - returns random number between 0 and 32767.*/  
{ 
    rand_seed = rand_seed * 1103515245 +12345;    
    return (unsigned int)(rand_seed / 65536) % 32768;  
} 
 
void main()  
{    
    int i,t,x,y; 
  
    /* fill array */    
    for (i=0; i < MAX; i++)    
    {      
        a[i]=rand();      
        printf("%d\n",a[i]);    
    } 
  
    /* more stuff will go here in a minute */ 
}

קוד זה מכיל מספר מושגים חדשים, למרות שהשורות include# ו define# צריכות להיות מוכרות לך. השורה int a[MAX]; מדגימה איך להצהיר על מערך של משתנים ב C. לדוגמה, ההצהרה int a[10]; מוצהרת כך בפסקל:

a:array [0..9] of integer;

כל המערכים ב C מתחילים באינדקס 0 וממשיכים עד n-1. לכן, int a[10]; מכיל 10 אלמנטים, והאינדקס התקף הגדול ביותר הוא 9. בניגוד לפסקל, C לא מציעה אף דרך לשנות את התחום של ערכי האינדקס. שים לב גם שבגלל המיקום של המערך a, הוא גלובלי לכל התוכנית.

השורה int rand_seed=10 מצהירה גם היא על משתנה גלובלי, הפעם בשם rand_seed. הוא מאותחל ל 10 בכל פעם שהתוכנית מתחילה. הערך הזה הוא הגרעין ההתחלתי לקוד המספר הרנדומלי שאחריו. במחולל מספרים רנדומלים אמיתי, הגרעין צריך להיות מאותחל כערך רנדומלי, כגון זמן המערכת. כאן, פונקצית ה rand תייצר את אותם ערכים בכל פעם שיריצו את התוכנית.

השורה ()int rand היא הצהרה על פונקציה. ההצהרה המקבילה על פונקציות בפסקל נראית כך:

function rand:integer;

פונקצית ה rand לא מקבלת אף פרמטר ומחזירה מספר שלם. ארבע השורות הבאות מיישמות את פונקצית ה rand. אנחנו נתעלם מהן לעת עתה.

פונקצית ה main היא רגילה. ארבעה משתני int מקומיים מוצהרים, והמערכים ממולאים ב 10 ערכים רנדומלים תוך שימוש בלולאת for. יש לציין שמערכים ממופתחים בדיוק כמו בפסקל.

כעת הוסף את הקוד הבא במקום של הערת ה more stuff….

/* bubble sort the array */    
for (x=0; x < MAX-1; x++)      
    for (y=0; y < MAX-x-1; y++)        
        if (a[y] > a[y+1])        
        {  
            t=a[y];  
            a[y]=a[y+1];  
            a[y+1]=t;        
        } 
/* print sorted array */    
printf("--------------------\n");    
for (i=0; i < MAX; i++)      
printf("%d\n",a[i]);

קוד זה ממיין ערכים רנדומלים ומדפיס אותם בסדר ממוין.

תרגילים

1. בקטע הקוד הראשון, נסה לשנות את לולאת ה for שממלאת את המערך לשורת קוד אחת. וודא שהתוצאה זהה לזו שהתקבלה מהקוד המקורי.

2. הוצא את קוד מיון הבועות ושים אותו בפונקציה משל עצמו. (ראה שיעור 6, אם יש צורך.) כותרת הפונקציה תהיה void bubble_sort. לאחר מכן העבר גם את המשתנים לפונקציה והפוך אותם למקומיים שם. כיוון שהמערך גלובלי, אין צורך להעביר את הפרמטרים שלו.

3. אתחל את גרעין המספר הרנדומלי לערכים אחרים.

שגיאות ב C מהן יש להימנע:

1. ל C אין כל בדיקת תחומים, לכן אם האינדקס שלך עבר את קצה המערך, היא לא תספר לך על זה. היא בסופו של דבר תיפול או תיתן לך נתוני זבל.

2. קריאה לפונקציה צריכה לכלול () אפילו אם לא מועברים כל פרמטרים. לדוגמא, C תקבל את השורה ;x=rand אבל הקריאה לא תעבוד. הכתובת בזיכרון של פונקצית ה rand תוכנס ל x. חייבים לכתוב ;()x=rand.

לדף הראשון

<< לדף הקודם

לדף הבא >>