מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 6

לדף הקורס

תרגיל 6 -מצביעים ומיבנים

q1.c

הקובץ q1.c הבא לקוח מהשיעור האחרון בתוספת קלה:

#include <stdio.h>
#include <stdlib.h> 
 
struct Person {
  int id; 
  char *name; 
};

 
int main() {
  char* names[] = {"Asif","Agam","Tzion","Yasmin","Ela","Maya","Yael"}; 
 
  int N = sizeof(names)/sizeof(char*); 
 
  struct Person* persons = (struct Person*) malloc (N*sizeof(struct Person)); 
 
  int i; 
  for(i=0; i<N; ++i) {
    persons[i].id = 1000+i; 
    persons[i].name = names[i]; 
  }
 
  for(i=0; i<N; ++i) 
    printf("%s %d\n",persons[i].name, persons[i].id); 
 
  ui(persons,N); 

  free(persons); 
 
  return 0;
}

הפונקציה ui (שמשמעותה user interface), אחראית על האינטראקציה עם המשתמשת. המשתמשת תוכל להכניס מספר תעודת זהות והתוכנית תחפש אם קיים בעל מספר תעודת זהות זהה. אם קיים כזה, התוכנית תדפיס את שמו, אם לא, היא תודיע שלא קיים. החיפוש אמור להיות יעיל ,<m> O(\log_2(n)) </m>, ולהסתמך על העובדה שהמערך ממויין לפי מספרי הזהות. קובץ הריצה הזה מגדיר את ההתנהגות הנדרשת מהתכנית שלכם. q1.c שתגישו, יכיל את הקוד הנתון והתוספות שלכם.

q2.c

נתון הקובץ q2.c הבא:

#include <stdio.h> 

// add struct declerations here.. 

int inLimits(int n, int min, int max) {
    return n >= min && n <= max; 
}

void setDate(struct Date* p, int day, int mounth, int year) {
    if( ! inLimits(day,1,31) || ! inLimits(mounth,1,12) || ! inLimits(year,1900,2100)) {
	printf("Invalid date\n");
	return; 
    }
    p->day = day; 
    p->mounth = mounth; 
    p->year = year; 
}

void printDate(struct Date date) {
    printf("%d/%d/%d", date.day, date.mounth, date.year);  
}

void setPhoneBill(struct PhoneBill* p, struct Date date, int insuranceCommission, int airCommission) {
    p->date = date; 
    p->insuranceCommission = insuranceCommission; 
    p->airCommission = airCommission; 
}
 
void printPhoneBill(struct PhoneBill bill) {
    printDate(bill.date); 
    printf("\nAir: %d, Insurance: %d \n",bill.airCommission, bill.insuranceCommission); 
}

int main() {
    struct Date date; 
    setDate(&date,11,6,1970); 
    struct PhoneBill bill; 
    setPhoneBill(&bill,date,127,10000); 
    printPhoneBill(bill); 
    return 0; 
}

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

11/6/1970
Air: 10000, Insurance: 127

עליכם להגיש את q2.c אחרי הוספת ההצהרות.

q3.c

רבקה, אחות של לבן הארמי?

נתון קובץ בשם q3.c המכיל את הקוד הבא:

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

struct MarriedCouple {
    char *husband, *wife;
}; 

struct FatherAndChild {
    char *father, *child;
}; 

struct Family {
    struct MarriedCouple* couples; 
    int couplesNum; 

    struct FatherAndChild *fnc; 
    int fncNum; 
};  

struct Family* createFamily() {
    struct Family *p = (struct Family*) malloc (sizeof(struct Family));
    p->couplesNum = p->fncNum = 0; 

    p->couples = (struct MarriedCouple*) malloc (sizeof(struct MarriedCouple)*1000); 
    p->fnc = (struct FatherAndChild*) malloc (sizeof(struct FatherAndChild)*1000); 
    return p; 
}

void addCouple(struct Family *fam, char *husband, char *wife) {
    struct MarriedCouple cp; 
    cp.husband = husband; 
    cp.wife = wife; 
    fam->couples[fam->couplesNum] = cp; 
    ++ fam->couplesNum;  
}

void addFnc(struct Family *fam, char *father, char *child) {
    struct FatherAndChild fnc; 
    fnc.father = father; 
    fnc.child = child; 
    fam->fnc[fam->fncNum] = fnc; 
    ++ fam->fncNum;  
}

void freeFamily(struct Family *fam) {
    free(fam->couples);
    free(fam->fnc); 
    free(fam); 
}

int main() {
    struct Family *biblicalFamily = createFamily(); 
    addCouple (biblicalFamily, "Abraham","Sarah");
    addCouple (biblicalFamily, "Isaac","Rebekah");
    addCouple (biblicalFamily, "Jacob","Rachel");

    addFnc(biblicalFamily, "Terah","Abraham");
    addFnc(biblicalFamily, "Abraham","Isaac"); 
    addFnc(biblicalFamily, "Isaac","Jacob"); 
    addFnc(biblicalFamily, "Jacob","Joseph");
    addFnc(biblicalFamily, "Laban","Rachel");
    addFnc(biblicalFamily, "Bethuel","Laban");
    addFnc(biblicalFamily, "Bethuel","Rebekah");
    addFnc(biblicalFamily, "Terah", "Haran");
    addFnc(biblicalFamily, "Haran", "Lot"); 

    printDescendants(biblicalFamily, "Rebekah"); 
    printDescendants(biblicalFamily, "Terah"); 

    printAncestors(biblicalFamily,"Isaac"); 
    printAncestors(biblicalFamily,"Joseph"); 

    freeFamily(biblicalFamily);

    return 0; 
}

הקוד מאפשר לתאר קשרי משפחה ואז לשאול שאלות לגביהם. בדוגמה זו מתוארת חלק מהמשפחה התנ"כית. עליכם להוסיף את הפונקציה printDescendants המדפיסה את כל הצאצאים של אדם מסויים ואת הפונקציה printAncestors המדפיסה את כל האבות והאמהות הקדומים שלו\שלה. שימו לב שאב קדמון עלול להופיע יותר מפעם אחת אם הוא אב קדמון במספר דרכים. בתואל, למשל, הוא גם אבא של רבקה, אם יעקוב וגם אבא של לבן, אביה של רחל, אישתו של יעקוב. זאת הסיבה שהוא אב קדמון של יוסף בשתי דרכים שונות.

הפלט של התוכנית שלכם יהיה דומה לפלט הבא:

Descendants of Rebekah are: Jacob, Joseph, 
Descendants of Terah are: Abraham, Isaac, Jacob, Joseph, Haran, Lot, 
Ancestors of Isaac are: Abraham, Terah, Sarah, 
Ancestors of Joseph are: Jacob, Isaac, Abraham, Terah, Sarah, Rebekah, Bethuel, Rachel, Laban, Bethuel,

הסדר של הצאצאים והאבות הקדמונים לא מחייב. אצלכם הוא יכל להיות שונה. ניתן להתרשם מהעץ התנ"כי בתמונה הזאת (וכנראה בעוד הרבה מקומות ברשת)

עליכם להגיש את q3.c המכיל את הקוד הנתון והמימושים שלכם.

q4.c

נתון קובץ בשם q4.c המכיל את הקוד הבא:

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

struct Person {
    int id; 
    char *name; 
    int lastSalariesNum; 
    int *lastSalaries; 
    int lastTotal; 
}; 

struct PersonDataBase {
    int size; 
    struct Person **base; 
}; 

struct PersonDataBase createPersonDataBase() {

    struct PersonDataBase db; 
    
    db.size = 100; 
    
    db.base = (struct Person**) malloc (db.size * sizeof(struct Person*)); 

    struct Person **base = db.base; 

    int i; 
    for(i=0; i< db.size; ++i) {
	base[i] = (struct Person*) malloc (sizeof(struct Person));
	base[i]->id = i; 
	base[i]->name = (char*) malloc (sizeof(char)*50); 
	sprintf(base[i]->name,"Person#%d",i); //        e.i.   write "Person#7" to base[7]->name 
	
	int n,j; 
	n = base[i]->lastSalariesNum = rand()%4+10; 
	base[i]->lastSalaries = (int*) malloc(n * sizeof(int));  
	int sal = (rand()%20+4)*1000; 
	for(j=0; j<n; ++j)
	    base[i]->lastSalaries[j] = sal+sal*(rand()%11-5)/10; 
	
	base[i]->lastTotal = 0; 
    }

    return db; 
}

void printPersonDataBase(struct PersonDataBase db) {
    int i; 
    for(i=0; i< db.size; ++i) {
	printf("%s, id:%d, last salaries: ",db.base[i]->name, db.base[i]->id);
	int j;
	for(j=0; j < db.base[i]->lastSalariesNum; ++j)
	    printf("%d, ",db.base[i]->lastSalaries[j]); 
	printf("  Total:%d\n",db.base[i]->lastTotal); 
    }
}


int main() {
    struct PersonDataBase db = createPersonDataBase();

    // fillTotals(db); 

    // quickSort(db); 

    printPersonDataBase(db); 

    // freePersonDataBase(db); 
    return 0; 
}

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

עליכם להוסיף לקובץ את מימושי כל הפונקציות שהקריאה להם נמצאת כרגע בהערה ב main.

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

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

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

הקובץ q4.c שעליכם להגיש אמור לכלול את כל המימושים של הפונקציות ואת ה main הנתון ללא סמני ההערה (כלומר עם הפעלה של כל אחת מהפונקציות שמימשתם).

הפלט של התוכנית אמור להיות דומה לזה:

Person#78, id:78, last salaries: 3600, 3200, 2000, 4000, 4000, 2000, 2400, 4000, 2400, 5200,   Total:32800
Person#33, id:33, last salaries: 2000, 2800, 4000, 3200, 2000, 4800, 5600, 4400, 4400, 2400, 6000,   Total:41600
Person#98, id:98, last salaries: 2800, 2000, 4800, 6000, 6000, 4400, 2400, 5600, 3600, 4800,   Total:42400
Person#87, id:87, last salaries: 2400, 5600, 3600, 5200, 2400, 2800, 4800, 3600, 2400, 4400, 5600, 3200,   Total:46000
Person#1, id:1, last salaries: 6000, 2800, 2000, 6000, 5200, 4000, 2000, 3600, 4400, 2000, 6000, 3200,   Total:47200
...

כלומר, האנשים ממויינים לפי סכום המשכורות (Total) וכל הזכרון משוחרר כיאות.

q5.c - בונוס (עד 15 נק')

צרו עותק של q3.c שלכם וקיראו לו q5.c. הוסיפו קשרים נוספים מהמשפחה התנ"כית (כ 20 קשרים) ופונקציות של קשרים מעניינים: פונקציה המדפיסה את כל האנשים איתם לאדם מסויים קשר דם, פונקציה המקבלת שני שמות ומספרת מה הקשר המשפחתי בינהם ופונקציה המאתרת מעגלים בעת המשפחתי (כמו זה של בתואל).

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

הגשה

מועד הגשה: יום חמישי ה - 29.12.11, עד סוף היום.

יש להגיש ב"תרגיל שישי" במודל, קובץ ex6.tgz המכיל את q1.c, q2.c, q3.c q4.c ואולי q5.c. אל תשכחו לבדוק את ex6.tgz לפני ההגשה ולוודא שהוא מכיל את כל מה שהוא אמור להכיל ושהכל מתקמפל ורץ.

בהצלחה!

פתרון

q1.c

#include <stdio.h>
#include <stdlib.h> 
 
struct Person {
  int id; 
  char *name; 
};

struct Person* search(struct Person* persons, int N, int n) {
    int i1 = 0; 
    int i2 = N-1,i; 
    while(i1 <= i2) {
	i = (i1+i2)/2;
	if(persons[i].id == n)
	    return & persons[i]; 
	if(n < persons[i].id) 
	    i2 = i-1; 
	else 
	    i1 = i+1; 
    }
    return NULL; 
}

int getNumberFromUser() {
    printf("Please enter an id number (-1 to quit): ");
    int n; 
    scanf("%d",&n);
    return n; 
}

void ui(struct Person *persons, int N) {
  int n; 
  while(1) {
      n = getNumberFromUser(); 
      if(n<0)
	  break; 
      struct Person *p = search(persons,N,n);
      if(!p)
	  printf("No person with id=%d\n",n);
      else
	  printf("* %s * is the person with id=%d\n",p->name,p->id);
  }
}
 
int main() {
  char* names[] = {"Asif","Agam","Tzion","Yasmin","Ela","Maya","Yael"}; 
 
  int N = sizeof(names)/sizeof(char*); 
 
  struct Person* persons = (struct Person*) malloc (N*sizeof(struct Person)); 
 
  int i; 
  for(i=0; i<N; ++i) {
    persons[i].id = 1000+i; 
    persons[i].name = names[i]; 
  }
 
  for(i=0; i<N; ++i) 
    printf("%s %d\n",persons[i].name, persons[i].id); 
 
  ui(persons,N); 

  free(persons); 
 
  return 0;
}

q2.c

#include <stdio.h> 

struct Date {
    int day;    // 1..31 
    int mounth; // 1..12 
    int year;   // 1900..2100 
}; 

struct PhoneBill {
    struct Date date; 
    int insuranceCommission; 
    int airCommission;
}; 

// add struct declerations here.. 

int inLimits(int n, int min, int max) {
    return n >= min && n <= max; 
}

void setDate(struct Date* p, int day, int mounth, int year) {
    if( ! inLimits(day,1,31) || ! inLimits(mounth,1,12) || ! inLimits(year,1900,2100)) {
	printf("Invalid date\n");
	return; 
    }
    p->day = day; 
    p->mounth = mounth; 
    p->year = year; 
}

void printDate(struct Date date) {
    printf("%d/%d/%d", date.day, date.mounth, date.year);  
}

void setPhoneBill(struct PhoneBill* p, struct Date date, int insuranceCommission, int airCommission) {
    p->date = date; 
    p->insuranceCommission = insuranceCommission; 
    p->airCommission = airCommission; 
}
 
void printPhoneBill(struct PhoneBill bill) {
    printDate(bill.date); 
    printf("\nAir: %d, Insurance: %d \n",bill.airCommission, bill.insuranceCommission); 
}

int main() {
    struct Date date; 
    setDate(&date,11,6,1970); 
    struct PhoneBill bill; 
    setPhoneBill(&bill,date,127,10000); 
    printPhoneBill(bill); 
    return 0; 
}

q3.c

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

struct MarriedCouple {
    char *husband, *wife;
}; 

struct FatherAndChild {
    char *father, *child;
}; 

struct Family {
    struct MarriedCouple* couples; 
    int couplesNum; 

    struct FatherAndChild *fnc; 
    int fncNum; 
};  

struct Family* createFamily() {
    struct Family *p = (struct Family*) malloc (sizeof(struct Family));
    p->couplesNum = p->fncNum = 0; 

    p->couples = (struct MarriedCouple*) malloc (sizeof(struct MarriedCouple)*1000); 
    p->fnc = (struct FatherAndChild*) malloc (sizeof(struct FatherAndChild)*1000); 
    return p; 
}

void addCouple(struct Family *fam, char *husband, char *wife) {
    struct MarriedCouple cp; 
    cp.husband = husband; 
    cp.wife = wife; 
    fam->couples[fam->couplesNum] = cp; 
    ++ fam->couplesNum;  
}

void addFnc(struct Family *fam, char *father, char *child) {
    struct FatherAndChild fnc; 
    fnc.father = father; 
    fnc.child = child; 
    fam->fnc[fam->fncNum] = fnc; 
    ++ fam->fncNum;  
}

void freeFamily(struct Family *fam) {
    free(fam->couples);
    free(fam->fnc); 
    free(fam); 
}

int isSameString(char *s1, char *s2) {
    while(1) {
	if(! *s1)
	    if(! *s2)
		return 1; 
	    else
		return 0; 
	else
	    if(! *s2)
		return 0;
	if(*s1 != *s2)
	    return 0; 
	++s1;
	++s2; 
    }
}

void printDescendantsRec(struct Family *fam, char *name) {
    int i; 
    for(i=0; i < fam->fncNum; ++i)
	if(isSameString(name, (fam->fnc[i]).father)) {
	    char *child = fam->fnc[i].child; 
	    printf("%s, ",child); 
	    printDescendantsRec(fam, child);
	}
    for(i=0; i < fam->couplesNum; ++i)
	if(isSameString(name,fam->couples[i].wife))
	    printDescendantsRec(fam,fam->couples[i].husband);
}

void printDescendants(struct Family *fam, char *name) {
    printf("Descendants of %s are: ",name);
    printDescendantsRec(fam,name);
    printf("\n"); 
}

void printAncestorsRec(struct Family *fam, char *name) {
    int i,j; 
    for(i=0; i < fam->fncNum; ++i)
	if(isSameString(name, (fam->fnc[i]).child)) {
	    char *father = fam->fnc[i].father;
	    printf("%s, ",father); 
	    printAncestorsRec(fam,father); 
	    for(j=0; j < fam->couplesNum; ++j) 
		if(isSameString(father,fam->couples[j].husband)) {
		    char *mother = fam->couples[j].wife; 
		    printf("%s, ",mother);
		    printAncestorsRec(fam, mother); 
		}
	} 
}

void printAncestors(struct Family *fam, char *name) {
    printf("Ancestors of %s are: ",name);
    printAncestorsRec(fam,name);
    printf("\n"); 

}

int main() {
    struct Family *biblicalFamily = createFamily(); 
    addCouple (biblicalFamily, "Abraham","Sarah");
    addCouple (biblicalFamily, "Isaac","Rebekah");
    addCouple (biblicalFamily, "Jacob","Rachel");

    addFnc(biblicalFamily, "Terah","Abraham");
    addFnc(biblicalFamily, "Abraham","Isaac"); 
    addFnc(biblicalFamily, "Isaac","Jacob"); 
    addFnc(biblicalFamily, "Jacob","Joseph");
    addFnc(biblicalFamily, "Laban","Rachel");
    addFnc(biblicalFamily, "Bethuel","Laban");
    addFnc(biblicalFamily, "Bethuel","Rebekah");
    addFnc(biblicalFamily, "Terah", "Haran");
    addFnc(biblicalFamily, "Haran", "Lot"); 

    printDescendants(biblicalFamily, "Rebekah"); 
    printDescendants(biblicalFamily, "Terah"); 

    printAncestors(biblicalFamily,"Isaac"); 
    printAncestors(biblicalFamily,"Joseph"); 

    freeFamily(biblicalFamily);

    return 0; 
}

q4.c

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

struct Person {
    int id; 
    char *name; 
    int lastSalariesNum; 
    int *lastSalaries; 
    int lastTotal; 
}; 

struct PersonDataBase {
    int size; 
    struct Person **base; 
}; 

struct PersonDataBase createPersonDataBase() {

    struct PersonDataBase db; 
    
    db.size = 100; 
    
    db.base = (struct Person**) malloc (db.size * sizeof(struct Person*)); 

    struct Person **base = db.base; 

    int i; 
    for(i=0; i< db.size; ++i) {
	base[i] = (struct Person*) malloc (sizeof(struct Person));
	base[i]->id = i; 
	base[i]->name = (char*) malloc (sizeof(char)*50); 
	sprintf(base[i]->name,"Person#%d",i); //        e.i.   write "Person#7" to base[7]->name 
	
	int n,j; 
	n = base[i]->lastSalariesNum = rand()%4+10; 
	base[i]->lastSalaries = (int*) malloc(n * sizeof(int));  
	int sal = (rand()%20+4)*1000; 
	for(j=0; j<n; ++j)
	    base[i]->lastSalaries[j] = sal+sal*(rand()%11-5)/10; 
	
	base[i]->lastTotal = 0; 
    }

    return db; 
}

void printPersonDataBase(struct PersonDataBase db) {
    int i; 
    for(i=0; i< db.size; ++i) {
	printf("%s, id:%d, last salaries: ",db.base[i]->name, db.base[i]->id);
	int j;
	for(j=0; j < db.base[i]->lastSalariesNum; ++j)
	    printf("%d, ",db.base[i]->lastSalaries[j]); 
	printf("  Total:%d\n",db.base[i]->lastTotal); 
    }
}

void freePersonDataBase(struct PersonDataBase db) {
    struct Person **base = db.base; 
    int i; 
    for(i=0; i< db.size; ++i) {
	free(base[i]->name);
	free(base[i]->lastSalaries);
	free(base[i]); 
    }
    free(base); 
}

void fillTotals(struct PersonDataBase db) {
    struct Person **base = db.base; 
    int i; 
    for(i=0; i< db.size; ++i) {
	int a=0,j; 
	for(j=0; j<base[i]->lastSalariesNum; ++j)
	    a += base[i]->lastSalaries[j]; 
	base[i]->lastTotal = a; 
    }
}

void swap(struct Person **i1, struct Person **i2) {
    struct Person *tmp = *i1; 
    *i1 = *i2; 
    *i2 = tmp; 
}

int split(struct Person **array, int pivot, int i1, int i2) {
    swap(&array[pivot], &array[i2-1]);
    int idx = i1,i; 
    for(i= i1; i<i2-1; ++i)
	if(array[i]->lastTotal < array[i2-1]->lastTotal) {
	    swap(&array[i], &array[idx]); 
	    ++idx; 
	}
    swap(&array[idx], &array[i2-1]); 
    return idx; 
}


void qs(struct Person **array, int i1, int i2) {
    if(i2 - i1 <= 1)
	return; 
    int pivot = (i1+i2)/2; 
    pivot = split(array,pivot,i1,i2);
    qs(array,i1,pivot);
    qs(array,pivot+1,i2); 
}

void quickSort(struct PersonDataBase db) {
    qs(db.base, 0, db.size); 
}

int main() {
    struct PersonDataBase db = createPersonDataBase();

    fillTotals(db); 

    quickSort(db); 

    printPersonDataBase(db); 

    freePersonDataBase(db); 
    return 0; 
}

לדף הקורס