הרצאה 7 - מחרוזות (strings)

אחרי שלמדנו להשתמש במערכים, נדגים הרבה ממה שלמדנו על סוג מיוחד של מערכים - מחרוזות. נזכיר כמה פרטים שראינו כבר בעבר:

1. הטיפוס char מייצג תו בודד, שגודלו בייט אחד (sizeof(char) = 1).
2. את הערך בזכרון שמכיל המשתנה אנחנו ממירים באמצעות טבלת ASCII לקבלת התו עצמו.
3. ניתן לייצר מערך של תווים *char בצורה דומה למערך של שלמים שפגשנו, *int.

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

int binary_search(int* array, int len, int target);

לעומת זאת, במערכי תווים ננקוט בגישה שונה. במקום להעביר ביחד עם מערך תווים את האורך שלו, נסמן בתו מיוחד את סוף המערך. התו 0\ הוא בעל ערך ASCII של 0 ונקרא null terminator. נשתמש בו לטובת הסימון הזה:

הגדרה: מחרוזת היא מערך תווים []char שהתו האחרון בו הוא 0\.

למשל, המחרוזת “HelloWorld” בזכרון נראת כך:

ניתן להגדיר מחרוזות בכמה צורות שקולות:

1. כמערך תווים:

char* str = {'H', 'e', 'l', 'l', 'o', '\0'};

2. עם string literal:

char* str = "Hello";

3. בכתיבה לכל איבר:

char str[6]; // string len is 5 + 1 fo
str[0] = 'H';
str[1] = 'e';
str[2] = 'l';
str[3] = 'l';
str[4] = 'o';
str[5] = '\0';

הערות:

1. נשים לב שיש הבדל דק אבל חשוב שכעת אפשר להבין בנוגע להצהרה על משתני char לעומת מחרוזות *char. הצהרה עם גרשיים יחידיים 'x' היא על משתנה char שמכיל תו, בעוד שעם גרשיים כפולים "x" היא על המחרוזת המתאימה:

char single_char = 'x'; // 1 byte
char* string = "x"; // pointer to {'x', '\0'}, 2 bytes

2. המשמעות של הוספת תו הסיום 0\ היא בשביל להכיל n תווי מחרוזת יש להשתמש ב-n + 1 בתים - n בשביל התווים עצמם ו-1 עבור 0\.
3. ניתן להדפיס מחרוזת עם printf עם המזהה s%:

#include <stdio.h>
char* str = "My favorite number is - ";
int fave;
scanf("%d", &fave);
printf("%s %d", str, fave);

מחרוזת היא מערך לכל דבר - ניתן לבצע עליו איטרציה:

char* str = "Learning computer science in C!";
for(int i = 0; str[i] != '\0'; i++) {
    printf("str[i] = %c\n", str[i]);
}

דוגמאות

1. כתבו פונקציה המקבלת מחרוזת ומחזירה את מספר האותיות הקטנות שבה.

int count_lowercase(char* str) {
    int lowercase = 0;
    for(int i = 0; str[i] != '\0'; i++) {
        if(str[i] >= 'a' && str[i] >= 'z') {
            lowercase++;
        }
    }
    return lowercase;
}

2. כתבו פונקציה שמחשבת אורך מחרוזת.

int strlen(char* str) {
    int len = 0;
    while(*str) {
        len++;
        str++; // Pointer arithmetic!
    }
    return len;
}

הערה: ניתן להשתמש בכתיבה while(*str) באופן שקול לכתיבה while(*str != '\0') מכיוון שערך ה-ASCII של 0\ הוא 0, ולכן ערכו בהמרה לבוליאני הוא false - כל תו אחר יקבל את הערך true.

<string.h>

בדומה לספריות אחרות שפגשנו כמו <stdlib.h> או <stdio.h>, קיימת ספריה בשם <string.h> שמכילה מספר גדול של פונקציות שימושיות בשימוש במחרוזות. כמה דוגמאות:

1. strcmp - פונקציה המשווה בין שתי מחרוזות ומחזירה 0 אם כל תו בהן זהה, אחרת ערך גדול מ-0.
2. strcat - משרשרת שתי מחרוזות זו לזו.
3. strcpy - מעתיקה את כל התווים ממחרוזת אחת לאחרת.

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

תרגיל

נתונה מחרוזת str המורכבת מתווים ומספר אי-שלילי של רווחים. למשל:

1. "Hello world"
2. "i am learning "
3. "5rasd33asd"
4. ""

כתבו את הפונקציה int last_word_len(char* str) שמחזירה את האורך של המילה האחרונה במחרוזת, כאשר כל מילה מופרדת מהאחרות על ידי מספר גדול מ-0. למשל, עבור הדוגמאות הבאות יוחזר:

1. 5
2. 8
3. 10
4. 0

פתרון

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

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

int strlen(char* str) {
    int len = 0;
    while(*str++) {
        len++;
    }
    return len;
}
int last_word_len(char* str) {
    int i = strlen(str) - 1; // step 1
    while(str[i] == ' ') { // step 2
        i--;
    }
    int word_len = 0;
    while(i >= 0 && s[i] != ' ') { // step 3
        i--;
        word_len++;
    }
    return word_len;
}

תרגיל

נתונה מחרוזת letters ומחרוזת word המורכבות מאותיות קטנות באנגלית בלבד. כתבו פונקציה bool can_create_word(char* letters, char* word) שקובעת האם ניתן להרכיב את המחרוזת word מהאותיות במחרוזת letters בלבד, כאשר ניתן להשתמש בכל אות כמספר הפעמים שמופיעה ב-letters. אין חובה להשתמש בכל האותיות מ-letters. לדוגמא, מהמחרוזת pudgy penguins ניתן להרכיב את המילים design ו-genius, אבל לא ניתן להרכיב את paparazzi.

פתרון

נפרק את השאלה שאנחנו שואלים. למעשה, אנחנו שואלים - האם עבור כל אות ב-word, מספר הפעמים שבה היא מופיעה ב-word היא לפחות מספר הפעמים שהיא מופיעה ב-letters? מכיוון שמספר האותיות הקטנות באנגלית הוא סופי, נקצה מערך סטאטי שיספור את התדירות של הופעת כל אות ב-letters, ולאחר מכן נעבור על כל האותיות ב-word ו-״נחלק״ אותן.

bool can_create_word(char* letters, char* word) {
    int letter_freq['z' - 'a' + 1] = {0};
    for(int i = 0; letters[i]; i++) {
        char letter = letters[i];
        letter_freq[letter - 'a']++;
    }
    for(int i = 0; word[i]; i++) {
        char letter = word[i];
        if(--letter_freq[letter - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

יש בפתרון כמה נקודות מורכבות:

1. מספר האותיות הקטנות הוא:
   'z' - 'a' + 1
   מכיוון ש-'a' ו-'z' הן אותיות קטנות בפני עצמן. אי-הוספת ה-1 היא טעות קלאסית הנקראת off-by-one וכדאי מאוד להזהר מהן ע“י בדיקה מדויקת של האלגוריתם.
2. הגדרנו מערך בו לכל אות קטנה יש מיקום בו נספרת התדירות שלו במחרוזת letters. בשביל לקבל את המיקום של אות כלשהי במערך, חיסרנו את 'a' ממנה - כך קיבלנו שהמקום של 'a' במערך הוא 0, של 'b' במערך הוא 1 וכך הלאה.
3. לאחר מכן, בכל שלב “חילקנו” את התדירויות ב-letters ל-word ע“י אופרטור ה--- (לפני המשתנה!), ואז בדקנו האם “חרגנו” ע:“י השוואה ל-0.

תרגיל

ממשו את שתי הפונקציות הבאות:

int str_to_int(char* str);
char* int_to_str(int n);

הפונקציה הראשונה תקבל מחרוזת המורכבת מתווי ASCII של ספרות בלבד ([0-9]) ותחזיר את המספר שהן מייצגות - לדוגמא, המחרוזת "953" תחזיר את המספר 953. הפונקציה השנייה תקבל מספר ותחזיר מחרוזת תקינה המייצגת את המספר.

פתרון

הפונקציה הראשונה יחסית פשוטה למימוש. מחרוזות קוראים משמאל לימין, ולכן נתקל בהתחלה בספרה הגבוהה ביותר של המספר, ואז אחת אחריה וכו’. עבור כל ספרה נכפיל ב-10 בשביל להסיט את הספרה מקום אחד שמאלה, נהפוך כל תו ASCII במחרוזת למקביל המספרי שלו ע“י חיסור של התו '0' ואז נוסיף את הספרה עצמה. נשים לב למקרה קצה חשוב - אם המספר שלילי, התו הראשון הוא - ויש לטפל בכך!

#include <stdbool.h>
int str_to_int(char* str) {
    int n = 0;
    int sign = str[0] == '-' ? -1 : 1;
    int i = 0;
    if(sign == -1) {
        i++;
    }
    while(str[i]) {
        n = n * 10 + (str[i++] - '0');
    }
    return n * sign;
}

הפונקציה השנייה מעט מורכבת יותר למימוש. נפעל לפי השלבים הבאים:

1. נתחיל במציאת מספר הספרות במספר. נעשה זאת ע“י חלוקת ב-10 עד שנגיע ל-0 - מכיוון שחלוקת int-ים ב-C מעגלת כפי מטה, נקבל בדיוק את מספר הספרות. נזהר להשתמש ב-do-while במקום ב-while על מנת שעבור המספר 0 עדיין נקבל אורך של 1 לפחות.
2. נקצה מחרוזת באורך שקיבלנו ועוד 1 עבור ה-null terminator. נכתוב לסוף המחרוזת את ה-null terminator.
3. כעת, מכיוון שמחרוזת קוראים משמאל לימין, נסרוק את המספר בצורה הפוכה. בכל שלב ניקח את המודולו לחלוקה ב-10 על מנת לחלץ את הספרה עצמה ונוסיף לכך '0' בשביל להמיר ממספר לתו ASCII. לאחר זאת נחלק את המספר ב-10 בשביל לקדם בספרה אחת את האיטרציה.

#include <stdlib.h>
#include <stdbool.h>
char* int_to_str(int n) {
    int tmp = n, len = 0;
    bool negative = n < 0;
    do {
        len++;
        tmp /= 10;
    } while(tmp);
    int total_len = len + (negative ? 1 : 0);
    char* s = malloc(total_len + 1);
    if(!s) {
        return NULL;
    }
    s[total_len] = '\0';
    int abs_n = negative ? -n : n;
    for (int i = total_len - 1; i >= negative; i--) {
        s[i] = (abs_n % 10) + '0';
        abs_n /= 10;
    }
    if (negative) {
        s[0] = '-';
    }
    return s;
}