נשלח בתאריך: 14 April 2009 בשעה 20:57 | | IP רשוּם
|
|
|
|
בסדר הסתדרתי עם השאלה תודה...
יש לי בעיה עם שאלה אחרת :
. הגדירו מבנה נקודה (Point) המכיל שתי קואורדינאטות (x,y).
כעת, כתבו פונקציה המקבלת מערך של נקודות, וממיינת אותו בשיטת Merge Sort רקורסיבי, כך שבמערך הממויין, הנקודות מסודרות לפי ערכי x מהקטן לגדול. את הנקודות בעלות אותו ערך x יש למיין לפי ערכי y, מהקטן לגדול.
לדוגמא, עבור המערך הבא (כל נקודה רשומה כזוג x,y)) ):
(4,5) |
(1,4) |
(6,7) |
(4,6) |
(1,2) |
(6,2) |
נקבל מערך ממויין:
(1,2) |
(1,4) |
(4,5) |
(4,6) |
(6,2) |
(6,7) |
הנחיות:
- תחילה כתבו פונקצית compare אשר מקבלת שתי נקודות, ומחזירה אחד משלושת הערכים {1,0,-1}. המספר 1 מסמל כי הנקודה השנייה גדולה מהראשונה, 0 מסמל כי שתי הנקודות זהות, ו -1 מסמל כי הנקודה השנייה קטנה מהראשונה. חתימת הפונקציה:
int Compare(Point *p1, Point *p2);
- כעת, כתבו פונקציה המקבלת שני מערכים המכילים נקודות ממויינות (בסדר שתואר לעיל), וממזגת ביניהם. (ניתן להשתמש בלולאות למימוש פונקציה זו). חתימת הפונקציה:
void MergePoints(Point A[], int n, Point B[], int m, Point C[]);
- כעת, כתבו את הפונקציה הרקורסיבית הממיינת מערך של נקודות. הפונקציה תשתמש במערך עזר tmpArray, לשמור תוצאות ביניים. חתימת הפונקציה:
void InternalPointSort(Point *pArray, int n, Point *tmpArray);
- לסיום, כתבו את פונקציית המעטפת, המריצה את הפונקציה הרקורסיבית. פונקציה זו תקבל מערך של נקודות, ותמיין אותן. חתימת הפונקציה.
void PointSort(Point *pArray, int n);
- בידקו שהפונקציה עובדת כראוי(יש לכתוב את הפונקציה ראשית לצורך זה). הגדירו מערך עם הנקודות ומיינו אותו בעזרת הפונקציה PointSort.
תודה מראש
__________________ eyal
|