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<N SUNITS;i++) for (j=0;j<N_S_TO_A;j++) a[sA[i][j]]++: void FireAToR(int a[],int aR[][N_RUNITS],int r[]) { int i,j; ClearArray(r,N_RUNITS); for (i=0;i<N AUNITS;i++) if (a [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 < N_SUNITS; i++) for (j = 0; j < N_S_TO_A; j++) a[sA[i][j]]++; } void FireAToR(int a[], int aR[][N_RUNITS], int r[]) { int i, j; ClearArray(r, N_RUNITS); for (i = 0; i < N_AUNITS; i++) if (a[i] >= THRESHHOLD) for (j = 0; j < N_RUNITS; j++) r[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; }
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;i<jArr->sizes[row];i++) newRow[i]jArr->rows [row][i]; /Init the rest to 0 * for i <col;i++) newRow [i]=0; Free old row if necessary if (jArr->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 < 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; i < jArr->sizes[row]; i++) newRow[i] = jArr->rows[row][i]; /* Init the rest to 0 */ for ( ; i <= col; i++) newRow[i] = 0; /* Free old row if necessary */ if (jArr->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;i<quarter->nCourses;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 < 0 || row >= jArr->nRows) Error(“Invalid row index”); if (col < 0 || 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 < quarter->nCourses; i++) { course = quarter->courses[i]; if (StringEqual(course->dept, CS_DEPT)) { (*numClasses)++; (*points) += GetScore(course, student); } } }