תוכן הפרק

מצביעים כארגומנטים לפונקציות

אריתמטיקה של כתובות

מצביעים ומחרוזות תוים

מערכים של מחרוזות

המפעיל sizeof

עוד על המפעילים new delete

מערכים רב ממדיים מול מערכי מצביעים

מחסנית של תווים

מימוש מחסנית על ידי מערך

הקובץ CSTACK.h

הקובץ CSTACK.cpp

השימוש USE.CPP

המפעיל ->

צורה נוספת לשמור נתונים: רשימה מקושרת

מימוש שני למחסנית

הקובץ CSTACK.h

הקובץ CSTACK.cpp

שורת הפקודה - command line arguments main(int argc, char* argv[])

מצביע לפונקציה חופשית

מצביע לפונקציה חברה במחלקה

הגדרת טיפוס מסובך

הגדרת cast מסובך

מצביעים כארגומנטים לפונקציות

1. ב C++ מעבירים ארגומנטים לפונקציה על ידי call by value.

נניח כי אנו רוצים לקרא לפונקציה swap(a, b) שתחליף את הערכים של a ו b.

void swap(int x, int y)

{

int t = x;

x = y;

y = t;

}

swap(a, b) מחליף עותקים של a ו b בתוך הפונקציה swap() בלבד.

void swap(int *px, int *py)

{

int t = *px;

*px = *py;

*py = t;

}

swap(&a, &b) מחליף את a ו b בפונקציה הקוראת ל swap().

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

#include <iostream.h>

void ReadNums(int* n1, int* n2)

{

cin >> *n1 >> *n2;

}

// reads a number.

// if it is positive returns 1 and puts the number in the location

// that i points to.

// otherwise returns 0.

int ReadPosNum(int* i)

{

int t;

cin >> t;

if (t > 0) {

*i = t;

return 1;

}

return 0;

}

void main()

{

int low, high;

int a[200];

ReadNums(&low, &high);

// fills a with positive numbers starting with index low

// until index high.

while(low <= high)

{

if (ReadPosNum(&a[low]))

low++;

}

}

• מאחר ו s הוא מצביע מותר לי לקדמו (s++).

• שינוי s אינו משפיע מחוץ לפונקציה מכיוון ש s הוא העותק הפרטי של הפונקציה.

int strlen(char *s)

{

int n;

for (n = 0; *s != '\0'; s++)

n++;

return n;

}

בכל מקרה מעבירים מצביע ל char כארגומנט:

char array[100] = "abcdefg";

char ptr = "vvv";

strlen("hello"); // value - 5

strlen(array); // value - 7

strlen(ptr); // value - 3

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

f(int a[100]);

f(int a[]);

f(int *a);

4. מכיוון שמעבירים רק מצביע אפשר להעביר רק חלק מהמערך כארגומנט לפונקציה:

int arr[20];

f(&arr[2]); º f(arr + 2);

5. בתוך הפונקציה, אם אנו בטוחים כי קיימים איברים אחורה מותר לפנות אליהם:

f(int a[])

{

a[-2]++; // increments arr[0]

}

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

אריתמטיקה של כתובות

כבר ראינו:

· p++ מקדם לאיבר הבא.

· p+=i מקדם לאיבר ה iי הבא.

· אחד מהדברים החזקים ב C++ זהו האיחוד בין מערכים, מצביעים ואריתמטיקה של כתובות.

הפעולות המותרות בין מצביעים:

· השמות בין מצביעים לאותו טיפוס.

· חיבור או חיסור של int למצביע.

· השוואה וחיסור בין מצביעים לאיברים של אותו מערך.

· השמה של 0 למצביע והשוואה של מצביע ל 0 (0 מטיפוס int).

6. השמות בין מצביעים לאותו טיפוס.

f()

{

int x = 2, *pi1 = &x, *pi2;

pi2 = pi1;

}

7. חיבור או חיסור של int למצביע.

int a[100];

f()

{

int *pi, i = 5;

pi = a - 2*5/3 + i; // pi = &a[-3+i] OR pi = &a[2]

}

הבטוי a - 2*5/3 + i הוא מטיפוס מצביע ל int וערכו a + 2*sizeof(int) .

8. השוואה וחיסור בין מצביעים לאיברים של אותו מערך.

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

int strlen(char *s)

{

char *p = s;

while (*p)

p++;

return p - s;

}

צורת החישוב של חיסור בין מצביעים:

p - s = (address of p - address of s) / sizeof (*p)

גודל איבר המרחק בבתים

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

if (p > s)

//...

else if (p == s) השוואה בין כתובות בזכרון:

// ...

else // p < s

// ...

בC++ מובטח כי הכתובת 0 אינה קיימת, ז.א., אם מצביע מכיל 0 הוא אינו מצביע לדבר.

int *pi = 0; // initialize empty pointer

if (pi == 0) // is pointer empty?

בקובץ <stdio.h> מגדירים: NULL להיות הערך 0.

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

int strlen(char *s)

{

char *p = s;

if (s == NULL) return 0;

while(*p)

p++;

return p - s;

}

main()

{

int x;

char *s1 = "abcd", *s2 = NULL, *s3;

x = strlen(s1); // O.K. returns 4

x = strlen(s2); // NULL check returns 0

x = strlen(s3); // Error: garbaged pointer. *p - Run Time Error

}

פעולות לא חוקיות בין מצביעים:

1. לחבר שני מצביעים.
2. לכפול, לחלק או shift עם מצביע ו int.
3. להוסיף או להחסיר float, double, long double.
4. לבצע השמה בין שני מצביעים לטיפוסים שונים ללא בצוע הסבת טיפוס מפורשת.

מצביע ל void

· משמש להצבעה על שטח זכרון מבלי שידוע מהו הטיפוס של האיבר המוצבע.

· אסור לחבר/להחסיר int או לנסות לגשת דרכו לנתון ( * או [ ] ).

· מותר לבצע השמות ממנו ואליו (בלי cast) ולבצע השוואות, עם מצביעים לטיפוסים אחרים.

enum VarType {INT, DOUBLE };

void print_arr(void *a, int n, VarType type)

{

int i;

if (a == NULL)

return;

if (type == INT){

int *ai = a;

for(i = 0; i < n; i++)

cout << ai[i];

} else if (type == DOUBLE) {

for (i = 0; i < n; i++)

cout << ((double*)a)[i]);

}

return;

}

מצביעים ומחרוזות תוים

a b c d \0

איתחולים:

char s[] = "abcd"; s:

· אתחול של מערך תווים: אסור לשנות את s, כי הוא שם של מערך. מותר לשנות את ערכי רכיבי המערך.

a b c d \0

char *s = "abcd"; s:

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

העתקת מחרוזות 4 גירסאות:

void strcpy(char *dst, char *src)

{

int i = 0;

while ((dst[i] = src[i]) != '\0')

i++;

}

void strcpy(char *dst, char *src)

{

while ((*dst = *src) != '\0') {

src++;

dst++;

}

}

void strcpy(char *dst, char *src)

{

while ((*dst++ = *src++) != '\0')

;

}

void strcpy(char *dst, char *src)

{

while (*dst++ = *src++) // != '\0' is not needed

;

}

השוואת מחרוזות:

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

// <string.h> compares two strings:

// if s1 less than s2: returns < 0

// if s1 equal to s2: returns = 0

// if s1 greater than s2: returns > 0

int strcmp(char* s1, char* s2)

{

while (*s1 && *s2 && *s1 == *s2)

{

s1++;

s2++;

}

return *s1 - *s2;

}

מערכים של מחרוזות

מערכים יכולים להכיל כל טיפוס של איבר ובפרט מצביע. אפשר להגדיר מערך של מחרוזות, כלומר מערך של מצביעים ל char.

#include <iostream.h>

void writeLines(char* lineptr[], int nlines)

{

for (int i = 0; i < nlines; i++)

cout << lineptr[i];

}

לתשומת לב: האופרטור cout << מדפיס מצביע מטיפוס char* בצורה שונה מיתר במצביעים. אם נדפיס מצביע שאינו מצביע ל char* תודפס הכתובת המאוחסנת במצביע. אבל במקרה שמדפיסים מצביע מטיפוס char* מודפסת המחרוזת שתחילתה מוצבעת על ידי המצביע.

ההגדרה char *lineptr[] פרושה ש lineptr הוא מערך של מצביעים ל char.

נניח כי הגדרנו:

char *lines[5] = {

"lines is\n",

"an array of\n",

"pointers to\n",

"char\n",

"\n"

};

· lines הוא מערך בגודל 5 של מצביעים ל char.

· כל איבר במערך הוא מצביע ל char. כל איבר מצביע אל מחרוזת באורך שונה.

· lines[i] הוא מצביע ל char.

· *lines[i] הוא התו הראשון במחרוזת ה i.

· lines הוא מערך. לכן יש לו טיפוס של מצביע לאיבר שלו, כלומר, מצביע למצביע ל char.

· lines+1 זהו מצביע לאיבר השני במערך lines.

· *lines זהו האיבר הראשון במערך, כלומר, מצביע למחרוזת הראשונה.

המבנה בזיכרון הוא:

lines:

lines is\n\0

5. כאשר מעבירים לפונקציה מערך כארגומנט, מה שעובר הוא מצביע לאיבר הראשון של המערך. במקרה שלנו כאשר נקרא לפונקציה writelines. מה שנעביר יראה כך:

6. מכיוון שמעבירים מצביע לאיבר הראשון יכולנו להגדיר את lineptr בכל אחד מהאופנים הבאים:

char *lineptr[5] OR char *lineptr[] OR char **lineptr

7. הערה לגבי קבוע מחרוזת (string literal): "abc" הוא קבוע מטיפוס const char* וערכו היא כתובת בלוק הזיכרון המכיל את המחרוזת. לכן אם נכתוב *"abc" נקבל את התו a ואם נכתוב "abc"[2] נקבל את התו c.

המפעיל sizeof

sizeof expr sizeof(expr)

sizeof Type sizeof(Type)

8. מופעל על טיפוס או ביטוי, וערך המפעיל הוא הגודל בבתים של הטיפוס Type או של טיפוס הביטוי expr (גוש הזכרון שנחוץ לאחסון הטיפוס של הביטוי).
9. ערך המפעילsizeof הוא מטיפוס unsigned int (או ליתר דיוק size_t).
10. הערך של המפעיל sizeof מחושב עוד בזמן ההידור ולא בזמן ריצה. מכיוון שלכל ביטוי יש טיפוס הידוע עוד בזמן ההידור, יש אפשרות למהדר לקבוע מהו הגודל בבתים של כל טיפוס.
11. לא מחשבים את ערך הביטוי (דבר שאפשרי רק בזמן ריצה) אלא רק את גודל הטיפוס שלו.

sizeof (int) // 4 bytes (for 32 bit compiler)

sizeof (char) // 1

sizeof (char *) // 4 bytes for pointer (for 32 bit compiler)

sizeof (4/3) // 4 same as int

double *pd;

sizeof pd // 4 for pointer

sizeof *pd // 8 like sizeof double

sizeof pd[10000] // 8 like sizeof *pd. we don’t access pd[10000]

int aaa[2][2][4]

sizeof aaa[0][0][0] // 4 sizeof int

sizeof aaa[0][0] // 16: 4 ´ 4

sizeof aaa[0] // 32: 2 ´ 4 ´ 4

sizeof aaa // 64: 2 ´ 2 ´ 4 ´ 4

// number of elements in aaa.

int n = sizeof aaa / sizeof aaa[0]; // n gets 2

// number of elemements in aaa[0][0].

int m = sizeof aaa[0][0] / sizeof *aaa[0][0]; // m gets 4

אם נעביר את המערך כארגומנט לפונקציה f() עובר מצביע לאיבר הראשון:

f(int aaaptr[2][2][4]);

f(int aaaptr[ ][2][4]); // all are the same

f(int (*aaaptr)[2][4]);

sizeof aaaptr // 4, sizeof pointer

sizeof aaaptr[0] // 32, same as sizeof aaa[0]

עוד על המפעילים new delete

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

· המפעיל delete מוחק עצם או משתנה שנוצר על ידי המפעיל new.

· המפעיל delete[] מוחק מהזכרון מערך של עצמים או משתנים שנוצר על ידי מפעיל new.

· ערך המפעילים delete, delete[] הוא מטיפוס void.

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

· דוגמא להקצאת מערך:

// program reads n integers and prints them in reverse order.

void main()

{

int n, i;

cout << "Enter number of numbers:"

cin >> n;

int *a = new int[n];

if (a == NULL)

return; // allocation failed

cout << "enter numbers"

for (i = 0; i < n; i++)

cin >> a[i];

for (i = n-1; i >= 0; i--)

cout << a[i];

delete[] a; // delete[] - deleting an array.

}

· אם יצרנו מערך על ידי מפעיל new נמחק אותו על ידי מפעיל delete[].

#include <string.h> // in order to use: strlen, strcpy

// function concatenates (משרשרת) two strings s1 s2.

// returns a new string as the result

char *strcat(char* s1, char* s2)

{

int len = strlen(s1);

char *s = new char[len + strlen(s2) + 1];

if (!s)

return s; // allocation failed.

strcpy(s, s1);

strcpy(s + len, s2); // starting from '\0' of s1

return s;

}

void main()

{

char *str = strcat("hello, ", "world\n"); // a new string

if (str)

cout << str; // print: hello, world

delete[] str; // we should delete s.

}

חזרה להתחלה

מערכים רב ממדיים מול מערכי מצביעים

· אפשר לממש מערכים רב ממדיים באמצעות מצביעים. לרוב עושים כך, אבל צריך להכיר בהבדלים:

const int N = 3;

const int M = 2;

void main()

{

int a[N][M] = {{1, 2}, {3, 4}, {5, 6}};

int *b[M]; // array[3] of pointers to int

int **c; // pointer to pointer to int

int i, j, k;

// creation

c = new int *[N]; // array[3] of pointer to int

for (i = 0; i < N; i++) {

b[i] = new int[M]; // array[2] of int

c[i] = new int[M];

}

// initialize b and c to have the same values as a.

for (k = 1, i = 0; i < N; i++)

for (j = 0; j < M; j++)

b[i][j] = c[i][j] = k++;

// free arrays

for (i = 0; i < N; i++) {

delete[] b[i];

delete[] c[i];

}

delete[] c;

}

a:

	c:

ההבדלים בין השיטות:

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

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

3. מספר השורות ומספר האיברים בכל שורה במערך c נקבעים בזמן ריצה.

· ההבדל בין המערכים הוא ביצירה ובמחיקה. פרט להבדל זה אפשר להשתמש בכל המערכים באופן זהה.

דוגמאות לעבודה עם מצביעים עבור מטריצה:

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

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

· בנוסף עושים שימוש באריתמטיקה של כתובות.

· שימוש בעובדה שמערך הוא גוש רציף של נתונים בזכרון.

int matrix[][5] = {

{ 1, 2, 3, 4, 5},

{ 6, 7, 8, 9, 10},

{11, 12, 13, 14, 15},

{16, 17, 18, 19, 20},

{21, 22, 23, 24, 25}

};

· האתחול סופר כמה איברים מטיפוס מערך[5] של int יש ב matrix.

// Version 1: Compute trace of 5X5 matrix

// pointer arrow is advanced (line_length + 1) elements.

void main()

{

int *arrow, sum = 0;

for (arrow = *matrix; arrow < matrix[0] + 25; arrow += 6)

sum += *arrow;

cout << sum << endl;

}

1. המטריצה מאוחסנת כשטח רציף בזיכרון, שכתובת ההתחלה שלה היא הערך של matrix וגם של matrix[0].
2. matrix וגם matrix[0] הם מטיפוס מצביע, המצביעים לאותו מקום (תחילת המטריצה), אבל matrix הוא מצביע למערך של 5 intים ואילו matrix[0] הוא מצביע ל int.
3. arrow מצביע ל int. בהתחלה מצביע לתחילת המטריצה ומתקדם בכל פעם ב 6 איברים (int). לכן הוא מצביע בכל איטרציה של הלולאה לאיבר האלכסון הבא.

// Version 2: Compute trace of 5X5 matrix

// int arrow is used both for indexing a pointer to line

// and indexing a pointer to element.

void main()

{

int arrow, sum = 0,

for (arrow = 0; arrow < 5; arrow++)

sum += *(*(matrix + arrow) + arrow);

cout << sum << endl;

}

4. התוכנית מחשבת בדיוק אותו הדבר כמו בדוגמא הקודמת.
5. matrix הוא מטיפוס מצביע למערך בגודל 5 intים.
6. matrix+arrow הוא מצביע מאותו טיפוס של matrix רק מקודם ב arrow איברים. כל איבר הוא שורה.
7. *(matrix + arrow) ביטוי מטיפוס מצביע ל int ומצביע לתחילת שורה מספר arrow במטריצה.
8. *(matrix+arrow)+ arrow ביטוי מטיפוס מצביע ל int ומכיל את הכתובת של איבר האלכסון, שבשורה מספר arrow, מספרו הוא arrow.
9. *(*(matrix + arrow) + arrow) ביטוי מטיפוס int שהוא איבר האלכסון מספר arrow.

· הפלט הוא 65 (סכום אברי האלכסון במטריצה)

מחסנית של תווים

המושג מחסנית במדעי המחשב מתאר שיטה לאחסון וגישה לנתונים:

10. המחסנית מכילה אוסף של נתונים; במקרה שלנו כל נתון הוא תו.
11. על המחסנית אפשר לבצע את הפעולות הבאות:

1. להכניס נתון c לראש המחסנית - void push(c)

2. להוציא את הנתון מראש המחסנית - char pop()

3. לשאול אם המחסנית ריקה - bool IsEmpty()

4. לשאול אם המחסנית מלאה - bool IsFull()

12. הנתונים למחסנית נכנסים ויוצאים בשיטת LIFO (Last In First Out)

A

B

A

C

B

A

push(C)

push(B)

push(A)

A

B

A

C

B

A

pop()

pop()

pop()

מימוש מחסנית על ידי מערך

size = 8

·

S:

המצב ההתחלתי

top:

· המצב לאחר הכנסת C.

S:

A

B

C

top:

· המצב לאחר הוצאת C.

S:

A

B

C

top:

· הערך של C לא נמחק, אבל התא שלו נחשב מחוץ למחסנית. אם נדחף תו נוסף למחסנית, הוא יכתב במקום התו C.

CharStack

תכנון

הקובץ CSTACK.h

typedef int bool; // old C++ compiler may not know bool type

const int true = 1;

const int false = 0;

class CharStack {

public:

CharStack(const CharStack& s1); // copy constructor.

CharStack(int sz = 10); // constructor.

~CharStack(); // destructor.

void Push(char c); // pushes c into the head of stack.

char Pop(); // pops up the head of the stack

bool IsEmpty(); // returns true if stack is empty; else false

bool IsFull(); // returns true if stack is full; else false

CharStack& operator=(const CharStack& s1);

private:

char* s; // pointer to array containing stack elements

int size; // number of elements in array s

char* top; // pointer to head of stack

};

הקובץ CSTACK.cpp

#include "CSTACK.H"

CharStack(const CharStack& s1)

{

s = top = new char[size = s1.size];

top += s1.top - s1.s;

for (char *p1 = s, *p2 = s1.s; p1 < top; p1++, p2++)

*p1 = *p2;

}

CharStack::CharStack(int sz)

{

top = s = new char[size = sz]; // All members are initialized

}

CharStack::~CharStack()

{

delete[] s;

}

void CharStack::Push(char c)

{

if (!IsFull())

*top++ = c;

}

char CharStack::Pop()

{

if(!IsEmpty())

return *--top;

return '\0'; // if stack is empty returns dummy result.

}

bool CharStack::IsEmpty()

{

return top == s;

}

bool CharStack::IsFull()

{

return (top == s + size); // top points after last element of s.

}

CharStack& operator=(const CharStack& s1)

{

if (this != &s1) { // beware s = s

delete[] s; // delete old

s = top = new char[size = s1.size]; // copy

top += s1.top - s1.s;

for (char *p1 = s, *p2 = s1.s; p1 < top; p1++, p2++)

*p1 = *p2;

}

return *this;

}

השימוש USE.CPP

// file: use.cpp

// asks the user to enter a word and a number n, and uses a stack to // reverse the first n characters of the entered word.

#include <iostream.h> //

#include <string.h> // strlen()

#include "CSTACK.H"

void main()

{

cout << "Enter a word, shorter than 80 characters:\n";

char w[80];

cin >> w;

cout << "Enter the number of letters you want to reverse:";

int n;

cin >> n;

if (n > 0 && n <= strlen(w))

{

CharStack stack(n); // constructs stack for n elements

char *p = w;

while (!stack.IsFull()) // pushes n characters onto stack

stack.Push(*p++);

p = w;

while (!stack.IsEmpty())// pops the characters from stack

*p++ = stack.Pop();

cout << "The new word is: " << w << endl;

} // stack destructor is called here

else

cout << "You have entered a wrong number\n";

}

המפעיל ->

(*ps).len // same as: s.len

*ps.len // Error: It means: *(ps.len),

// but ps.len is an int, not a pointer!

13. בגלל חוסר הנוחיות בכתיבה ובכדי לפתור בעיות של עדיפות ואסוציאטיביות המציאו את המפעיל ->
14. אם p הוא מצביע, לעצם מטפוס מחלקה או מבנה המכיל חבר בשם m, אזי הביטויים הבאים שקולים:

(*p).m same as p->m

ps->len º s.len

מקדם את len ושקול ל ++(ps->len)

מקדם את ps לפני הגישה ל len

מקדם את ps אחרי הגישה ל len

התו הראשון של str

מקדם את str לתו הבא אחרי הגישה

מקדם את התו ש str מצביע אליו

מקדם את ps אחרי שנגש לתו ש str מצביע אליו

++ps->len

(++ps)->len

ps++->len

*ps->str

*ps->str++

(*ps->str)++

*ps++->str

דוגמא ממחלקות:

Fraction fr, *pfr = &fr;

הפעלת הפונקציות החברות על העצם המוצבע על ידי pfr :

double d = pfr->Evaluate(); // d gets 1.

pfr->Get(); // fr gets a new value from KB

pfr->Show(); // shows on screen new value of fr.

צורה נוספת לשמור נתונים: רשימה מקושרת

NULL

· רשימה מקושרת היא סדרה של גושי נתונים, אשר כל גוש נתונים מצביע על הקודם בתור. הגוש הראשון מצביע ל NULL (לכלום, כי אין לו קודמים).

· כל גוש נתונים כזה נוצר בנפרד ולאחר שיוצרים אותו נותנים למצביע שלו להצביע לגוש הקודם.

חזרה להתחלה

מימוש שני למחסנית

· רוצים להחליף את המחסנית שהוגדרה קודם, שמומשה על ידי מערך, במחסנית שמשתמשת ברשימה מקושרת לשמירת הנתונים.

· אנו נשנה את המימוש מבלי לגעת אפילו בשורה אחת בקוד של הקובץ המשתמש במחסנית : USE.CPP.

· הדבר היחידי שצריך להתבצע על הקובץ USE.CPP הוא הידור מחדש (בגלל #include”CSTACK.H”).

הקובץ CSTACK.h

typedef int bool; // old C++ compiler may not know bool type

const int true = 1;

const int false = 0;

class CharStack {

public:

CharStack(int sz = 10); // constructor.

~CharStack(); // destructor

void Push(char c); // push c to be in the head of stack.

char Pop(); // pops up the head of stack

bool IsEmpty(); // returns true if stack is empty,otherwise false

bool IsFull(); // returns true if stack is full, otherwise false

private:

struct CElem {

char c;

CElem *prev;

};

CElem* top; // top of linked list.

int maxn; // limit for number of elements.

int n; // current number of elements.

};

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

15. הגדרנו טיפוס חדש - פרטי - במחלקת המחסנית: המבנה CElem. מבנה זה הוא טיפוס של יחידה אחת ברשימה המקושרת.
16. top מצביע לראש הרשימה המקושרת.
17. n, maxn משמשים לישום גבול למספר האיברים במחסנית.

הקובץ CSTACK.cpp

#include "CSTACK.H"

const int NULL = 0; // defining NULL.

CharStack::CharStack(int sz)

{

top = NULL; // top points to nothing.

maxn = sz; // set limit

n = 0; // current number of elements.

}

CharStack::~CharStack()

{

while (top != NULL) // deletes all elements in linked-list.

{

CElem* ptmp = top->prev;

delete top;

top = ptmp;

}

}

void CharStack::Push(char c)

{

if (IsFull())

return;

CElem *pe = new CElem;

pe->prev = top;

pe->c = c;

top = pe;

n++;

}

char CharStack::Pop()

{

if (top == NULL)

return '\0'; // if stack is empty returns dummy result.

CElem *pe = top;

char c = top->c;

top = top->prev;

delete pe;

n--;

return c;

}

bool CharStack::IsEmpty()

{

return top == NULL;

}

bool CharStack::IsFull()

{

return n == maxn;

}

חזרה להתחלה

שורת הפקודה - command line arguments main(int argc, char* argv[])

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

נניח כי אנו רוצים לכתוב תוכנית אשר תבצע את מה שפקודת dir הידועה מבצעת:

c:\> dir - prints files list

c:\> dir *.cpp - prints C++ files list

c:\> dir /w /p - prints files list in wide form one page at a time.

בכדי לבצע זאת אנו יכולים (באופן תאורטי) לכתוב תוכנית C++ אשר תקרא dir.exe והיא תדע להדפיס את רשימת הקבצים. אבל בנוסף, עלינו לקבל (ממערכת ההפעלה) את שורת הארגומנטים (הפקודות) אשר עמם אנו מריצים את התוכנית בכדי לקבוע את אופן פעולת התוכנית.

· בשפת C++ מוגדרת אפשרות לקבל ממערכת ההפעלה את שורת הארגומנטים שעמם מורצת התוכנית.

· כאשר מערכת ההפעלה מריצה את התוכנית שלנו היא קוראת לפונקציה main() עם שני ארגומנטים אשר מכילים את המידע הדרוש לנו.

· כאשר מגדירים את הפונקציה main() עם שורת ארגומנטים ריקה מתעלמים מהמידה הזה.

main(int argc, char* argv[])

· הארגומנט הראשון (שנהוג לכנותו argc - argument counter) הוא מטיפוס int ומכיל את מספר הארגומנטים שעמם מריצים את התוכנית.

· הארגומנט השני (שנהוג לכנותו argv - argument vector) הוא מצביע למערך של מחרוזות תווים, כאשר כל מחרוזת מכילה ארגומנט אחד.

#include <iostream.h>

int main(int argc, char *argv[])

{

while(--argc > 0)

cout << *++argv << ( (argc > 1) ? ' ' : '\n') );

cout << endl;

return 0;

}

נניח שקמפלנו את התוכנית וקיבלנו קובץ ריצה a.out ונניח כי ניתן לו שם echo ע"י mv a.out echo

אם נריץ את התוכנית :

echo hello, world הרצת התוכנית:

hello, world הפלט:

0

argc: 3

· argc[0] - שם התוכנית שהרצנו. לכן argc לפחות 1 - אם הוא 1 אין ארגומנטים אחרי שם התוכנית.

argv[0] is "echo"

argv[1] is "hello,"

argv[2] is "world"

argv[3] is argv[argc] is 0 is NULL

· הארגומנט האמיתי הראשון הוא argv[1] והאחרון argv[argc-1] ותמיד argv[argc] הוא 0 או NULL.

· רווחים מפרידים בין הארגומנטים בזמן הקריאה, לכן hello, הוא ארגומנט אחד (גם ה , נכלל).

#include <iostream.h>

#include <string.h>

const int MAXLINE = 1000;

// getline: get line into s, return length

int getline(char *line, int max)

{

int i;

char c;

i = 0;

while(--max > 0 && (cin.get(c)) && c != '\n')

line[i++] = c;

if(c == '\n')

line[i++] = c;

line[i] = '\0';

return i;

}

// find: print lines that match pattern from 1st arg.

int main(int argc, char *argv[])

{

char line[MAXLINE];

long lineno = 0;

int c, except = 0, number = 0, found = 0;

while(--argc > 0 && (*++argv)[0] == '-')

while(c = *++argv[0])

switch(c) {

case 'x':

except = 1;

break;

case 'n':

number = 1;

break;

default:

cerr << "find: illigal option" << c << endl;

argc = 0;

found = -1;

break;

}

if (argc != 1)

cerr << "Usage: find -x -n pattern" << endl;

else

while (getline(line, MAXLINE) > 0) {

lineno++;

if ((strstr(line, *argv) != NULL) != except) {

if (number)

cout << ": " << lineno;

cout << line;

found++;

}

}

return found;

}

תוכנית בשם find אשר קוראת שורות מהקלט התקני ומחפשת האם יש בשורות הללו מופע של מחרוזת מסוימת [יש פקודה דומה ב unix - grep].

אופציות לתוכנית:

נהוג במערכת unix שכאשר ארגומנט מתחיל ב ‘-’ הארגומנט מציין אופציה או פרמטר. בתוכנית שלנו:

· -x פירושו (except) להדפיס את השורות שאין בהן מופע של המחרוזת. אם לא מבקשים -x מדפיסים את השורות שיש בהן מופע של המחרוזת.

· -n פירושו להדפיס את מספר השורה, אחרת לא מדפיסים את מספר השורה.

דוג':

login>: find -x -n abcd < file

login>: find -nx abcd < file

שתי ההרצות שקולות ויגרמו להדפסת כל השורות בקובץ file אשר לא מכילות abcd וגם מדפיס מספר שורה.

login>: find -n abcd < file

מדפיס את כל השורות בקובץ file המכילות את המחרוזת abcd וכולל הדפסת מספר שורה.

פעולת התוכנית:

· בשלב הראשון מזהים אופציות: הלולאה מחפשת את כל הארגומנטים המתחילים ב '-'. לפני כל איטרציה מחסירים מ argc אחד ומקדמים את argv. לכן לאחר סריקת כל הארגומנטים argc צריך להכיל 1 ו argv צריך להצביע על ה pattern (המחרוזת שמחפשים).

· בשלב השני קוראים שורה ומחפשים בה את המחרוזת. פונקציות העזר:

· הפונקציה int getline(char* line, int max) קוראת שורה באורך מקסימלי max ומחזירה את מספר התווים שנקראו.

· ב <string.h> מוצהרת הפונקציה char* strstr(char* s, char* t): מחזירה מצביע למופע הראשון של המחרוזת t במחרוזת s ואם אין מופע כזה מחזירה NULL.

חזרה להתחלה

מצביע לפונקציה חופשית

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

#include <string.h>

void sort (void *base, int n, int sz, int (*cmp)(void*, void*))

{

int i, j, k;

char *pj, *pj1, temp;

for (i = 0;i < n-1; i++){

for (j = n - 1; i < j; j--){

pj = (char *) base + j * sz;

pj1 = pj - sz;

if ((*cmp)(pj, pj1) > 0) {

for (k = 0;k < sz; k++) {

temp = pj[k];

pj[k] = pj1[k];

pj1[k] = temp;

}

}

}

}

}

int ucmp(int *a, int *b) { return *a - *b;}

int dcmp(int *a, int *b) { return *b - *a;}

void main(int argc, char* argv[])

{

int a[] = {2, 4, 1, 5, 3, 6}, i;

int sz = sizeof (a[0]), n = sizeof (a) / sz;

int (*udcmp)(void*, void*);

if (argc == 2 && strcmp(argv[1], "-d") == 0)

udcmp = (int (*)(void*, void*)) dcmp;

else

udcmp = (int (*)(void*, void*)) ucmp;

sort (a, n, sz, udcmp);

for (i = 0 ; i < n ; cout << a[i++] );

}

מיון מתבסס על:

· השוואת שני איברים במערך.

· החלפת זוגות איברים במערך.

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

הפונקציה sort() מקבלת גודל איבר במערך sz (בכדי לדעת כיצד להחליף איבר ומה גודל הצעד במערך). ארגומנט

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

הפונקציה sort() יכולה למיין מערך של כל דבר בתנאי שנותנים לה את sz ו cmp .

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

· התוכנית תמיין את אברי המערך a בסדר עולה או אם הארגומנט לתוכנית -d אזי בסדר יורד.

· a הוא המערך שנמיין, sz הוא גודל של איבר במערך, n מספר האיברים במערך.

· המשתנה udcmp הוא מסוג מצביע לפונקציה המקבלת שני ארגומנטים מטיפוס void*.

· בודקים האם למיין בסדר עולה או יורד:

הפונקציה המוצהרת ב <string.h> : int strcmp(char* s1, char* s2) מחזירה ערך שלילי אם

s1 < s2 אפס אם s1 == s2 ערך חיובי אם s1 > s2 . ההשוואה היא תו תו.

· שם של פונקציה הוא מסוג מצביע לפונקציה (בדומה לשם של מערך). ucmp dcmp הן פונקציות המקבלות ארגומנטים שהם int* ואילו udcmp מצביע לפונקציה שמקבלת ארגומנטים מטיפוס void* לכן כאשר מבצעים השמה חייבים לבצע cast.

· הביטוי (int (*)(void*, void*)) הוא cast שמטרתו להפוך את טיפוס המצביע לפונקציה ucmp או dcmp להיות -- מצביע לפונקציה המקבלת שני ארגומנטים מטיפוס void* ומחזירה int.

· גם כאשר מגדירים מצביע לפונקציה וגם כאשר קוראים לפונקציה חייבים לשים סוגריים מסביב לשם הפונקציה ןה-*:

int (*cmp)(void*, void*) הגדרת המצביע לפונקציה:

(*cmp)(pj, pj1) קריאה לפונקציה:

אם לא היינו שמים סוגריים:

int *cmp(void*, void*) int הגדרת פונקציה המחזירה מצביע ל

*cmp(pj, pj1) פניה דרך המצביע שהפונקציה החזירה -- טעות קומפילציה:

חזרה להתחלה

מצביע לפונקציה חברה במחלקה

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

· p->*m מקשר בין העצם המוצבע על ידי p לבין הפונקציה החברה ש m מצביע עליה.

· obj.*m מקשר בין העצם obj לבין הפונקציה החברה ש m מצביע עליה.

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

class Person {

void (Person::* mood) ();

int mood_num;

public:

void speakup() { (this->*mood)(); }

void good() { cout << "\nHello how are you? " << mood_num;}

void bad() { cout << "\nGet lost! " << mood_num;}

void soso() { cout << "\nhi " << mood_num;}

Person()

{ // rand() choose integral number: 0..MAX_INT

switch ( mood_num = rand()%3)

{

case 0:

mood = good;

break;

case 1:

mood = soso;

break;

case 2:

mood = bad;

break;

}

}

};

// pointer to member function of calss Person

// which gets no arguments and return void.

typedef void (Person::* ptrToPersonMemFunc) ();

void main()

{

srand( (unsigned) time(NULL) ); // initialize rand

Person Avi;

Avi.speakup();

Person* p = &Avi;

ptrToPersonMemFunc mfpt;

mfpt = Person::good;

// ->* binds member function pointed by mfpt to object pointed by p.

(p->*mfpt) ();

// .* bindes member function pointed by mfpt to object Avi.

(Avi.*mfpt) ();

}

חזרה להתחלה

הגדרת טיפוס מסובך

כל טיפוס מסובך הוא נגזר מטיפוס פשוט יותר ע"י זאת שהוא:

· * pointer to מצביע לטיפוס פשוט יותר:

· [] array [size] of מערך [גודל אופציונלי] של טיפוס פשוט יותר:

· () function returning פונקציה המקבלת ארגומנטים ומחזירה ערך מטיפוס פשוט יותר:

השיטה לפענוח:

· בבסיס השם: name.

· בפרוק/הרכבה יש עדיפות למה שצמוד מימין { [ ] או ( ) } :

· אם יש מימין [size] אומרים: array[size] of.

· אם יש מימין (args) אומרים: function (args) returning

· אם אין כלום מימין או שהכול תחום ב ( ) בודקים מה יש משמאל:

· אם יש * משמאל אומרים: pointer to

· אם יש TYPE משמאל אומרים: TYPE

· שים לב כי כאשר מגדירים pointer to בביטוי מסובך כדאי לעטוף את הביטוי בסוגריים.

דוגמא:

lineptr lineptr:

lineptr[6] array[6] of

*lineptr[6] pointer to

char *lineptr[6] char

lineptr lineptr:

*lineptr pointer to

(*lineptr)

(*lineptr)[6] array[6] of

char(*lineptr)[6] char

comp comp

*comp pointer to

(*comp)

(*comp) (void *, void *) function(void *, void *) returning

int (*comp) (void *, void *) int

y y:

y() function() returning

*y() pointer to

(*y())

(*y())[] array[] of

*(*y())[] pointer to

(*(*y())[])

(*(*y())[]) () function() returning

char (*(*y())[]) () char

y y:

y[3] array[3] of

*y[3] pointer to

(*y[3])

(*y[3]) () function returning

*(*y[3]) () pointer to

(*(*y[3]) ())

(*(*y[3]) ())[5] array[5] of

char (*(*y[3]) ())[5] char

דוג':

נגדיר מצביע לפונקציה המקבלת שלושה ארגומנטים מטיפוס מצביע ל int ומחזירה מצביע למערך בגודל 5 של מערך בגודל 4 של double.

f

(*f) pointer to

(*f)(int *, int *, int*) function returning

(*f)(int *, int *, int*)[5] array[5] of

(*f)(int *, int *, int*)[5][4] array[4] of

double (*f)(int *, int *, int*)[5][4]; double

נפרש את הבטוי הבא:

int (*(*(*arr[8])(void*, int))(int))[5];

arr[8] array[8] of

(*arr[8]) pointer to

(*arr[8])(void*, int) function (void*, int) returning

(*(*arr[8])(void*, int)) pointer to

(*(*arr[8])(void*, int))(int) function (int) returning

(*(*(*arr[8])(void*, int))(int)) pointer to

(*(*(*arr[8])(void*, int))(int))[5] array [5] of

int (*(*(*arr[8])(void*, int))(int))[5] int

הגדרת cast מסובך

1. מגדירים name מהטיפוס המסובך.

2. שמים הכול בסוגריים.

3. משמיטים את ה name.

4. מפעילים את ה cast משמאל לביטוי.

דוג':

רוצים לבצע cast למצביע ptr להיות: מצביע למערך בגודל 10 של מצביעים לפונקציה המקבלת שני ארגומנטים מטיפוס int ומחזירה מצביע ל double.

נגדיר את הטיפוס המסובך:

name

(*name) pointer to

(*name)[10] array[10] of

(*(*name)[10]) pointer to

(*(*name)[10])(int, int) function (int, int) returning

*(*(*name)[10])(int, int) pointer to

double *(*(*name)[10])(int, int) double

נשים הכל בסוגריים:

(double *(*(*name)[10])(int, int))

נשמיט את name:

(double *(*(*)[10])(int, int))

נפעיל את ה cast על ptr:

(double *(*(*)[10])(int, int)) ptr

חזרה להתחלה