מבוא לתכנות ולמדעי המחשב בשפת C/חיפוש בינארי, מערכים דו ממדיים, אתחול מערכים ומחרוזות

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

תבנית:ניווט מבוא


חיפוש בינארי[עריכה]

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

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

הקוד הבא ממש את האלגוריתם הזה:

#include <stdio.h>
#include <stdlib.h> 

int main() {
	int N=7; 
	int a[N],i,j; 

	for(i=0; i<N; ++i) {
		a[i] = rand()%100+1; 
	}
 
	// sorting.. 
	for(i=0; i<N-1; ++i) // a[i] will be the smallest of i..N-1 
		for(j=i+1; j<N; ++j)
			if(a[i] > a[j]) {
				int t = a[i]; 
				a[i] = a[j]; 
				a[j] = t; 
			}
			
	printf("The sorted array: "); 
	for(i=0; i<N; ++i) 
		printf("%d, ",a[i]); 
	printf("\n"); 
			
 	// binary search.. 
	while (1) {
		int k; 
		printf("Please enter a number to check if it's already stored: "); 
		scanf("%d",&k);  
 
		int found = 0; // false 
		int begin=0; 
		int end=N-1; 
		while (end >= begin) {
			int middle = (begin+end)/2; 
			if(k == a[middle]) {
				printf("Yes, %d, it is already in\n",k);
				found = 1;  
				break; 
			}
			else 
				if(k > a[middle]) 
					begin = middle+1; 
				else   // case: k < a[middle])     
					end = middle-1;  
		}
		if(!found)
			printf("No, %d is *not* in the array\n",k); 			
	}
	return 0; 
}

(שימו לב שהקוד מכיל לולאה אין סופית של פניה למשתמש בכדי לצאת יש ללחוץ על מקש Ctrl ובו זמנית על המקש C)

סיבוכיות: מכיוון שבכל איטרציה בחיפוש אנו נותרים עם קבוצה בגודל חצי (טוב, אולי חצי פחות אחד או אפילו פחות שתיים) מהקבוצה הקודמת, מספר הפעולות המקסימאלי הוא מספר הפעמים שאפשר לחלק את גודל המערך (N) בשתיים עד שמקבלים מספר השווה לאחד. במילים אחרות זה מספר הפעמים שאפשר להכפיל ב 2 את אחד עד שמגיעים לN. מספר ההכפלות ב 2 היא החזקה שבה יש להעלות את 2 בכדי להגיע ל N כלומר log בבסיס 2 של n: <m>\log_2{N} </m> ולכן נאמר שהסיבוכיות של חיפוש בינארי היא <m>O(\log_2{N}) </m> לעומת סיבוכיות לינארית <m>O(N) </m> של חיפוש סידרתי.

לשם המחשה, אם מדובר בחיפוש של מילארד מספרים, חיפוש סדרתי דורש כמילארד פעולות בעוד חיפוש בינארי דורש כ 30 בלבד!

מערכים דו מימדיים[עריכה]

ב C ניתן להגדיר מערך בעל שני מימדים. לדוגמה:

#include <stdio.h>

int main() {
    int array[7][5]; 

    array[0][3] = 17; 
    array[2][4] = 2; 
    array[6][0] = array[0][3] * array[2][4]; 

    array[7][2] = 9;  // bug: 7 is out of bound 
    array[6][5] = 12; // bug: 5 is out of bound 

    printf("%d\n",array[6][0]); 
    return 0;
}

פלט: לא מוגדר אבל כנראה:

34

המערך הדו ממדי שהוגדר מכיל משתנים מסוג int. לכל משתנה מתייחסים ע"י זו אינדקסים. האינדקס הראשון בתחום 0..6 והשני בתחום 0..4. שימו לב שהקוד מכיל שני באגים מהסוג הבעייתי - חריגה מגבולות מערך. זאת הסיבה שהתנהגות התוכנית לא מוגדרת. קרוב לוודאי שבמערכת שבה אתם משתמשים הבאגים האלה לא יתגלו כלל - מצב בעייתי במיוחד.

הנה דוגמה נוספת המחשבת לוח כפל חלקי ושומרת את כולו בזיכרון המחשב.

#include <stdio.h>

int main() {
    int  I = 5, J = 7; 

    int arr[I][J]; 
    int i,j; 
    for(i=0; i<I; ++i)
	for(j=0; j<J; ++j) 
	    arr[i][j] = (i+1)*(j+1); 

    for(i=0; i<I; ++i) {
	for(j=0; j<J; ++j) 
	    printf("%d\t",arr[i][j]);
	printf("\n");
    }

    return 0;
}

פלט:

1	2	3	4	5	6	7	
2	4	6	8	10	12	14	
3	6	9	12	15	18	21	
4	8	12	16	20	24	28	
5	10	15	20	25	30	35

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

למעשה, המערכים ב C לא מוגבלים לשני ממדים. ניתן להצהיר גם על מערכים רב ממדיים, לדוגמה:

#include <stdio.h>

int main() {
    double array[7][5][10][2]; 

    array[2][4][9][0] = 1.234567; 
    printf("%lf\n",array[2][4][9][0]); 
    return 0;
}

פלט:

1.234567

כדאי לשים לב שמערכים רב ממדיים לא נותנים יכולות חדשות שלא היו קיימות במערך חד ממדי. תמיד אפשר לייצג מספר ממדים במערך חד ממדי ע"י שימוש באריטמטיקה של אינדקסים.

לדוגמה, את הקוד ששמר במערך דו ממדי את לוח הכפל, אפשר היה לממש עם מערך חד ממדי באופן הבא:

#include <stdio.h>

int main() {
    const int I=5, J=7; 
    int ar[I*J]; 

    int i,j; 
    for(i=0; i<I; ++i)
	for(j=0; j<J; ++j)
	    ar[i*J+j] = (i+1)*(j+1); // like ar[i][j] = ..  

    for(i=0; i<I; ++i) {
	for(j=0; j<J; ++j)
	    printf("%d\t",ar[i*J+j]);
	printf("\n"); 
    }

    return 0;
}

אפשר לחשוב על מה שעשינו כאן כפריסה של המערך הדו ממדי לשורות שבכל אחת J תאים וסידורן בזו אחר זו במערך חד ממדי. לכן, בשביל להגיע לתא שהיה ב i,j צריך לעבור i (כי מתחיל מ 0) מקטעים באורך J ואז להוסיף את j, המקום במקטע שמייצג את השורה הרלוונטית: i*J+j.

באופן דומה, אפשר לשטח גם מערכים ממדים גבוהים יותר:

#include <stdio.h>

int main() {

    const int I=5, J=7, K=3; 
    int ar[I*J*K]; 

    int i=2, j=3, k=1; 

    ar[i*J*K+j*K+k] = 17; // like ar[i][j][k] = 17; 
    
    return 0;
}

אתחול מערכים[עריכה]

C מספקת דרך מקוצרת לאתחול מערכים:

#include <stdio.h>
 
int main() {
	int ar[5] = {3,2,1,5,4};
	int i; 
	for(i=0; i<5; ++i) 
		printf("%d, ", ar[i]);
	printf("\n"); 

	return 0; 
}

פלט:

3, 2, 1, 5, 4,

מכיוון שהקופיילר יכל לראות בעצמו כמה מקום דרוש למערך, אפשר לכתוב פשוט:

	int ar[] = {3,2,1,5,4};

וגם כך יוקצו למערך חמישה תאים.

את התוכנית הקצרה האחרונה, אפשר לכתוב גם באופן הבא:

#include <stdio.h>
 
int main() {
	int ar[] = {3,2,1,5,4};
	int i, n = sizeof(ar)/sizeof(int); 
	for(i=0; i<n; ++i) 
		printf("%d, ", ar[i]);
	printf("\n"); 

	return 0; 
}

גודל המערך מחושב בזמן ריצה מתוך מספר הbyte-ים הדרושים לאכסון המערך כולו מחולק במספר הbyte-ים הדרושים לתא int בודד. היתרון של כתיבה כזו היא שכעת ניתן לשנות את מספר האברים באתחול ולא צריך להתאים את שאר התוכנית לשינוי.

אתחול מערך דו ממדי מבוצע באופן דומה אך את המימד הפנימי יש צורך לספק באופן מפורש:

#include <stdio.h>

int main() {

    int ar[][3] = {{1,2,3},{4,5,6}}; 
    printf("ar[1][0] = %d \n",ar[1][0]);  
 
    return 0;
}

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

מחרוזות (strings)[עריכה]

מחרוזות ב C הם פשוט מערכים של char בעלי תו סיום מיוחד:

#include <stdio.h>

int main() {

    char a[] = {'h','e','l','l','o',' ','w','o','r','l','d','\0'}; 
    printf("%s\n",a); 
    a[6] = 'l'; 
    printf("%s\n",a); 
    return 0;
}

פלט:

hello world
hello lorld

הסבר: התו האחרון בכל מחרוזת חייב להיות '0\' שהוא הערך המספרי 0 של טיפוס מסוג char. כל תו מייוצג בזיכרון המחשב ע"י מספר שהוא קידוד ה ASCII שלו. המספר 0 לא מייצג תו ממשי אלא רק משמש כסימון.

s% הוא סימון ל printf להדפסת מחרוזת. הקוד יצר מערך של אותיות עם תו הסיום ושינה אות אחת מ w ל l.

הדפסת מחרוזת מסתיימת תמיד כאשר נמצא הערך '0\', אם נשכח לשים אותו, ההדפסה תמשיך להדפיס מה שיש במקרה בהמשך הזכרון עד שתגיע '0\' כלשהו. אם נמקם את תו הסיום האמצע המערך, רק התוים עד אליו יודפסו:

#include <stdio.h>

int main() {

    char a[] = {'h','e','l','l','o',' ','w','o','r','l','d'}; 
    printf("%s\n",a); 
    a[6] = '\0'; 
    printf("%s\n",a); 
    return 0;
}

פלט:

hello world
hello

הערה: אם אתם מעוניינים לדעת קידוד ASCII של תו מסויים, אפשר להשתמש בקוד כזה:

#include <stdio.h>

int main() {

    printf("%d %d %d \n",(int)'\0', (int)'A', (int)'B'); 
    return 0;
}

פלט:

0 65 66

האלמנט - (int) נקראה casting והוא ממיר את הערך לטיפוס int. בקוד זה המרנו שלושה ערכים מטיפוס char לערכים מטיפוס int וכך ראינו איך הם מקודדים במחשב.

קלט של מחרוזת[עריכה]

הקוד הבא מדגים קליטה של מחרוזת מהמשתמש:

#include <stdio.h>

int main() {

    char str[100]; 
    printf("What is your name? ");
    scanf("%s",str);
    printf("Hello %s, what's up?\nNow let me spell your name:\n",str);
    int i=0; 
    while(str[i]) {  // same as: while(str[i] != '\0')
	printf("%c-",str[i]);
	++i; 
    }
    printf("\n"); 
    return 0;
}

פלט:

What is your name? Yerahmiel
Hello Yerahmiel, what's up?
Now let me spell your name:
Y-e-r-a-h-m-i-e-l-

הסבר: לפני שקולטים מחרוזת מהמשתמש יש להכין מערך בגודל מספיק גדול להכיל אותה. כאן, ההנחה ששם משתמש אינו מכיל יותר ממאה תוים. פקודת הקלט היא כרגיל scanf הפעם עם הסימון של מחרוזת s%. שימו לב שבקלט של מחרוזת אין סימן & לפני המשתנה שמייצג את המחרוזת. הסיבה לכך תתבהר כשנלמד על מצביעים.

scanf דואגת להוסיף את תו הסיום '0\' בעצמה. הלולאה יכולה לשאול בפרוש מתי התא הנוכחי שונה מ 0 או פשוט להשתמש בתנאי המכיל רק את התא הנוכחי. כזכור, ב C כל ערך שונה מ 0 נחשב אמיתי ו 0 נחשב שיקרי.


תבנית:ניווט מבוא