pointers advanced

מבוא למדעי המחשב: 

מבוא למדעי המחשב מערך של מצביעים דוגמאות

מצביעים ומערכים דו-מימדיים: 

int a[10][20] int* b[10]; מצביעים ומערכים דו-מימדיים 200 int cells 10 pointers חייבים אתחול [row][col]=>20*row+col [row][col]=>20*row+col

מצביעים ומערכים דו-מימדיים: 

int a[10][20]; - int *b[10]; - כדי להשתמש ב-b כמערך, חייבים להקצות זיכרון: int **c; - כדי להשתמש ב-c כמערך, חייבים להקצות זיכרון: מצביעים ומערכים דו-מימדיים מקצה 200 int מקצה 10 int* for (i=0; i<10; i++) { b[i]=(int*)malloc(20* sizeof(int)); } מקצה int אחד c = (int**)malloc(10* sizeof(int*)); for (i=0; i<10; i++) { c[i]=(int*)malloc(20* sizeof(int)); }

מצביעים ומערכים דו-מימדיים: 

מצביעים ומערכים דו-מימדיים מערך דו-ממדי: char month[13][15]={“illegal_month”,”January”,”February”,…,”December”} מערך של פוינטרים: char *pmonth[ ]={“Illegal”,”January”,”February”,…,”December”} זיכרון מבוזבז מאפשר לעשות שורות של מערך בגדלים שונים

מערך של מצביעים: 

דוגמא: כתוב פונקציה שממיינת שורות של טקסט לפי סדר אלפביתי. צריכים מבנה נתונים כדי להחזיק מחרוזות בגדלים שונים. מערך של מצביעים grass dog char* lineptr[MAXLINES] 0 1 2 lineptr[2] – pointer to string crocodile

מערך של מצביעים: 

נשמור מחרוזות במערך של מצביעים. כל מצביע במערך זה מצביע למחרוזת מסוימת. המיון נעשה ע"י השוואה של מחרוזות בעזרת פונקציה strcmp(*char, *char) מערך של מצביעים grass dog crocodile 0 1 2 strcmp(lineptr[0], lineptr[2]) נשווה בין

מערך של מצביעים: 

“crocodile”<“grass” לכן נחליף בינן. במקום העתקות מיותרות משנים ערכם של מצביעים מערך של מצביעים grass dog crocodile 0 1 2

שלבי האלגוריתם : 

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

מבנה של התוכנית: 

מבנה של התוכנית main readlines qsort writelines getline strcpy createCharArray partition swap strcmp

Slide10: 

המשך

Slide11: 

המשך

Slide12: 

המשך

Slide13: 

מתקדם לשורה הבאה

Qsort של מחרוזות : 

Qsort של מחרוזות נשנה את QSORT מההרצאה על מיון כך שיוכל למיין מחרוזות בסדר לקסיקוגרפי. void quicksort(int array[], int lower, int upper) { int pivotIndex; if (lower < upper) { pivotIndex = partition(numArray, lower, upper); quicksort(array, lower, pivotIndex - 1); /* sort left side*/ quicksort(array, pivotIndex + 1, upper); /* sort right side*/ } } char* array[]

Slide15: 

Qsort של מחרוזות

Slide16: 

int partition(int array[], int lower, int upper) { int pivot, left, right, tmp; pivot = array[lower]; left = lower; right = upper; while (left < right) { /* scan from left, skipping items that belong there*/ while ((array[left] <= pivot) && (left < upper)) left++; /* scan from right, skipping items that belong there */ while (array[right] > pivot) right--; if (left < right) { tmp=array[left]; array[left]= array[right]; array[right]=tmp; } } array[lower]=array[right]; array[right] = pivot; return right; /* return the pivot index*/ }

Slide17: 

int partition(int array[], int lower, int upper) { int pivot, left, right, tmp; pivot = array[lower]; left = lower; right = upper; while (left < right) { /* scan from left, skipping items that belong there*/ while ((array[left] <= pivot) && (left < upper)) left++; /* scan from right, skipping items that belong there */ while (array[right] > pivot) right--; if (left < right) { tmp=array[left]; array[left]= array[right]; array[right]=tmp; } } array[lower]=array[right]; array[right] = pivot; return right; /* return the pivot index*/ } swap swap char* array[] נחליף את ההשוואות הרגילות של איברי המערך בstrcmp(…) - מיותר, נתן להשתמש ב array[lower] ישירות

Slide18: 

חדש

Slide19: 

חדש

Slide20: 

Free lines memory