Handout #61S CS106A Summer 2002 August 12,2002 Alex Khomenko Practice Final Solutions Problem 1:Strings. /Solution 1:implement strcspn,then use that for strpbrk * int strcspn(char *cs,char *ct) { char *pos; int n 0; while (*cs !=\0'&&strchr(ct,*cs)==NULL) cs++; n++; } return n; char *strpbrk(char *cs,char *ct) char *pos; int prefixLen; prefixLen strcspn(cs,ct); if (prefixLen =strlen(cs)) return NULL; return cs prefixLen; /Solution 2:implement strpbrk,then implement strcspn * char *strpbrk(char *cs,char *ct) while (*cs !=\0') if (strchr(ct,*cs)!=NULL) return cs; else Cs++; return NULL;
Handout #61S Summer 2002 August 12, 2002 Alex Khomenko Practice Final Solutions Problem 1: Strings. /* Solution 1: implement strcspn, then use that for strpbrk */ int strcspn(char *cs, char *ct) { char *pos; int n = 0; while (*cs != '\0' && strchr(ct, *cs) == NULL) { cs++; n++; } return n; } char *strpbrk(char *cs, char *ct) { char *pos; int prefixLen; prefixLen = strcspn(cs, ct); if (prefixLen == strlen(cs)) return NULL; return cs + prefixLen; } /* Solution 2: implement strpbrk, then implement strcspn */ char *strpbrk(char *cs, char *ct) { while (*cs != '\0') { if (strchr(ct, *cs) != NULL) return cs; else cs++; } return NULL; } CS106A
2 int strcspn(char *cs,char *ct) { char *pos; pos strpbrk(cs,ct); if (pos =NULL) return strlen(cs); return pos -cs; Problem 2:Arrays void FireSToA(int s[],int sA[][N_S_TO_A],int a[]) { int i,j; clearArray(a,N_AUNITS); for (i=0;i=THRESHHOLD) for (j=0;j<N_RUNITS;j++) x[j]+=aR[i][j]: int classifyPattern(int r[]) { int max,iMax,i; max =-1; for (i=0;i<N RUNITS;i++) if (r[i]max) max r[i]; iMax i; } return iMax; void clearArray(int arr[],int n) { int i; for (i=0;i<n;i++) arr[i]=0;
2 int strcspn(char *cs, char *ct) { char *pos; pos = strpbrk(cs, ct); if (pos == NULL) return strlen(cs); return pos - cs; } Problem 2: Arrays void FireSToA(int s[], int sA[][N_S_TO_A], int a[]) { int i, j; ClearArray(a, N_AUNITS); for (i = 0; i = THRESHHOLD) for (j = 0; j max) { max = r[i]; iMax = i; } return iMax; } void ClearArray(int arr[], int n) { int i; for (i = 0; i < n; i++) arr[i] = 0; }
3 Problem 3:Function trace STACK HEAP main Orphaned! Hi\0 julia Hithere\0 jacques martin 3 2 Endive joann simca lydia charlie delia y
3 Problem 3: Function trace STACK HEAP julia jacques main joann simca Endive lydia charlie 3 Orphaned! martin Hithere\0 Hi\0 3 2 5 delia i 3
Problem 4:Useful Pointers jArrayT *CreateJaggedArray(int n) { iArrayT *iA; int i; jA GetBlock(sizeof (jArrayT)); jA->sizes GetBlock(n sizeof(int)); jA->rows GetBlock(n sizeof(int *)) jA->nRows n; for (i=0;i n;i++) jA->sizes[i]0; jA->rows [i]NULL; return jA; void SetElement(jArrayT *jArr,int row,int col,int value) { int i,*newRow; if (row 0 row >jArr->nRows) Error("Invalid row index"); /If current row is too small if (jArr->sizes[row]col 1) /Allocate a new row * newRow GetBlock((col 1)*sizeof(int)); /Copy existing elements * for (i=0;isizes[row];i++) newRow[i]jArr->rows [row][i]; /Init the rest to 0 * for i rows [row]!NULL) FreeBlock(jArr->rows [row]) /Set new row and its size t/ jArr->rows [row]newRow; jArr->sizes[row]col +1; jArr->rows [row][col]value;
4 Problem 4: Useful Pointers jArrayT *CreateJaggedArray(int n) { jArrayT *jA; int i; jA = GetBlock(sizeof (jArrayT)); jA->sizes = GetBlock(n * sizeof(int)); jA->rows = GetBlock(n * sizeof(int *)); jA->nRows = n; for (i = 0; i sizes[i] = 0; jA->rows[i] = NULL; } return jA; } void SetElement(jArrayT *jArr, int row, int col, int value) { int i, *newRow; if (row = jArr->nRows) Error(“Invalid row index”); /* If current row is too small */ if (jArr->sizes[row] sizes[row]; i++) newRow[i] = jArr->rows[row][i]; /* Init the rest to 0 */ for ( ; i rows[row] != NULL) FreeBlock(jArr->rows[row]); /* Set new row and its size */ jArr->rows[row] = newRow; jArr->sizes[row] = col + 1; } jArr->rows[row][col] = value; }
5 int GetElement(jArrayT *jArr,int row,int col) if (row 0 II row >jArr->nRows) Error("Invalid row index"); if (col 0 II col >jArr->sizes[row]) Error("Invalid column index"); return jArr->rows[row][col]; Problem 5:Data Structures (a) 1.studentT* schoolPtr->dorms [3]->students [school.dorms [3]->nStudents -1] 2.courseT** schoolPtr->students[5].quarters[4][2]->courses 3 3.quarterT*** (*(school.dorms[4]->students))->quarters 4.int (sschool)->courses[3].qtr 5.double schoolPtr->courses->classList->score 6.Error (*(&schoolptr))->dorms (b) void GetcsResults(studentT *student,int year,int qtr, double *points,int *numclasses) quarterT *quarter; courseT *course; int i; quarter student->quarters[year -student->firstYear][qtr]; *numclasses =0; *points 0; for (i=0;inCourses;i++){ course quarter->courses[i]; if (StringEqual(course->dept,CS_DEPT)){ (*numclasses)++; (*points)+=Getscore(course,student);
5 int GetElement(jArrayT *jArr, int row, int col) { if (row = jArr->nRows) Error(“Invalid row index”); if (col = jArr->sizes[row]) Error(“Invalid column index”); return jArr->rows[row][col]; } Problem 5: Data Structures (a) 1. studentT* schoolPtr->dorms[3]->students[school.dorms[3]->nStudents - 1] 2. courseT** schoolPtr->students[5].quarters[4][2]->courses + 3 3. quarterT*** (*(school.dorms[4]->students))->quarters 4. int (&school)->courses[3].qtr 5. double schoolPtr->courses->classList->score 6. Error (*(&schoolPtr))->dorms (b) void GetCSResults(studentT *student, int year, int qtr, double *points, int *numClasses) { quarterT *quarter; courseT *course; int i; quarter = student->quarters[year – student->firstYear][qtr]; *numClasses = 0; *points = 0; for (i = 0; i nCourses; i++) { course = quarter->courses[i]; if (StringEqual(course->dept, CS_DEPT)) { (*numClasses)++; (*points) += GetScore(course, student); } } }
6 double Getscore(courseT *course,studentT *student) int i; for (i=0;i course->nStudents;i++){ if (student->studentID =course->classList[i].studentID) return (course->classList[i].score); /Don't need to handle the case when student not found * } (c) double DormCSAvg(dormT*dorm,int year,int qtr) double points; int numclasses; double sumofAverages =0; int i; for (i 0;inStudents;i++) GetCSResults(dorm->students[i],year,qtr, &points,&numclasses); if (numclasses >0){ sumofAverages +=(points numclasses); } return (sumofAverages dorm->nstudents); (④ string BestCSDorm(schoolT *school,int year,int qtr) { string bestDorm =" double avg,bestAvg =0; int i; for (i 0;inDorms;i++){ avg DormCSAvg(school->dorms[i],year,qtr); if (avg bestAvg){ bestAvg avg; bestDorm school->dorms [i]->name; } return (bestDorm);
6 double GetScore(courseT *course, studentT *student) { int i; for (i = 0; i nStudents; i++) { if (student->studentID == course->classList[i].studentID) return (course->classList[i].score); } /* Don’t need to handle the case when student not found */ } (c) double DormCSAvg(dormT* dorm, int year, int qtr) { double points; int numClasses; double sumOfAverages = 0; int i; for (i = 0; i nStudents; i++) { GetCSResults(dorm->students[i], year, qtr, &points, &numClasses); if (numClasses > 0) { sumOfAverages += (points / numClasses); } } return (sumOfAverages / dorm->nStudents); } (d) string BestCSDorm(schoolT *school, int year, int qtr) { string bestDorm = “”; double avg, bestAvg = 0; int i; for (i = 0; i nDorms; i++) { avg = DormCSAvg(school->dorms[i], year, qtr); if (avg > bestAvg) { bestAvg = avg; bestDorm = school->dorms[i]->name; } } return (bestDorm); }
