上海交通大学：《程序设计基础》课程教学资源（习题集）05年期末习题_Pointer Review Solution

CS106A Handout #38 Summer 2003 August 7,2003 Pointer Practice Solutions 1)Pointer Tracing a stack heap 4 cherry orange stack frame for main ? 3.0 8.0 12.0 pineapple lime stack frame for Rainbowsherbet Q 0.0 0.0 1.0 frozen

CS106A Handout #38 Summer 2003 August 7, 2003 Pointer Practice Solutions 1) Pointer Tracing a) stack heap stack frame for main 4 i cherry orange ?? 3.0 8.0 12.0 3 frozen lime pineapple stack frame for RainbowSherbet 0.0 0.0 1.0

-2- D Stack Heap array 0 3 42 p1 1 P2 2 c) Stack Heap i branner 3 6.0 1.5 2.0 kimball

- 2 - b) i p1 Stack Heap array p2 0 1 2 3 42 c) i Stack Heap 3 kimball 6.0 1.5 2.0 branner

-3- 2)Pointers Arrays a /* Function:CountEvensAndOdds CountEvensAndOdds examines the specified array of the specified size,calculates the number of odd and even numbers in the array,and effectively returns both counts by placing them at the two addresses specified as arguments three and four. */ void CountEvensAndodds(int array []int n,int *numEvens,int *numodds) { int i; *numEvens 0; *numodds =0; for(i=0;i<n;1++){ if(array[i]号2==0){ (*numEvens)++; else (*numodds)++; b) /★ Function:Partition ★ Partition takes an array and its size as arguments one and two and allocates two new integer arrays and returns each by reference. After Partition is called,the first new array,referenced by evens,contains all those elements of the original array,and the integer referenced by numEvens stores the size of the evens array. similarly,odds and numodds reference an array of odd integers and the size of the array referenced by odds,respectively. ★/ void Partition(int array[],int n, int **evens,int *numEvens,int **odds,int *numodds) int i,evensPlaced,oddsPlaced; CountEvensAndodds(array,n,numEvens, numodds); *evens NewArray(*numEvens,int); *odds NewArray(*numodds,int); evensPlaced oddsPlaced =0; for (i=0;i<n;i++){ if(array[i]号2==0){ (*evens)[evensPlaced++]array[i]; else (*odds)[oddsPlaced++]array[i]; c Notice that at the time Partition gets called,the variables odds,evens,numodds, and numEvens are all uninitialized.All four are variables that store pointers,and but no legitimate addressed have been stored in any of them

- 3 - 2) Pointers & Arrays a) /* * Function: CountEvensAndOdds * --------------------------- * CountEvensAndOdds examines the specified array of * the specified size, calculates the number of odd and * even numbers in the array, and effectively returns both * counts by placing them at the two addresses specified * as arguments three and four. */ void CountEvensAndOdds(int array[], int n, int *numEvens, int *numOdds) { int i; *numEvens = 0; *numOdds = 0; for (i = 0; i < n; i++) { if (array[i] % 2 == 0) { (*numEvens)++; } else { (*numOdds)++; } } } b) /* * Function: Partition * ------------------- * Partition takes an array and its size as arguments one and * two and allocates two new integer arrays and returns each by reference. * After Partition is called, the first new array, referenced * by evens, contains all those elements of the original array, and the * integer referenced by numEvens stores the size of the evens array. * Similarly, odds and numOdds reference an array of odd integers and * the size of the array referenced by odds, respectively. */ void Partition(int array[], int n, int **evens, int *numEvens, int **odds, int *numOdds) { int i, evensPlaced, oddsPlaced; CountEvensAndOdds(array, n, numEvens, numOdds); *evens = NewArray(*numEvens, int); *odds = NewArray(*numOdds, int); evensPlaced = oddsPlaced = 0; for (i = 0; i < n; i++) { if (array[i] % 2 == 0) { (*evens)[evensPlaced++] = array[i]; } else { (*odds)[oddsPlaced++] = array[i]; } } } c) Notice that at the time Partition gets called, the variables odds, evens, numOdds, and numEvens are all uninitialized. All four are variables that store pointers, and but no legitimate addressed have been stored in any of them

-4- We could dynamically allocate space for two ints and two int *s,but the more intelligent thing to do is to declare the two ints and the two int *s on the stack and then use the operator to take the addresses of them when calling Partition.Once Partition has finished,the four variables would then contain meaningful results.Here's the correct way (shown below)!Make sure you understand why this one works and why the second one does not. main() int numbers[1000]; int *odds,*evens; /note the new int numOdds,numEvens; /declarations Init(numbers,1000); Partition(numbers,1000, &evens,&numEvens,&odds,&numodds); FreeBlock(evens); FreeBlock(odds); 3)Concat a int StringLength(string s) char*pch; if (s =NULL)return -1; for (pch s;*pch !=\0';pch++)/*loop until at end of string * return (pch -s);

- 4 - We could dynamically allocate space for two ints and two int *s, but the more intelligent thing to do is to declare the two ints and the two int *s on the stack and then use the & operator to take the addresses of them when calling Partition. Once Partition has finished, the four variables would then contain meaningful results. Here's the correct way (shown below)! Make sure you understand why this one works and why the second one does not. main() { int numbers[1000]; int *odds, *evens; // note the new int numOdds, numEvens; // declarations Init(numbers, 1000); Partition(numbers, 1000, &evens, &numEvens, &odds, &numOdds); FreeBlock(evens); FreeBlock(odds); } 3) Concat a) int StringLength(string s) { char* pch; if (s == NULL) return -1; for (pch = s; *pch != '\0'; pch++) /* loop until at end of string */ ; return (pch - s); }

-5- b) string Concat(string s1,string s2) string result; int lenl,len2,i; if (s1 =NULL s2 =NULL)return NULL; len1 StringLength(s1); len2 StringLength(s2); result =(string)GetBlock((len1 len2 1)*sizeof(char)); fox(i=0:i<1en1;i++){ result[i]s1[i]; } for (i =0;i<len2;i++){ result[i+len1]s2[i]; result[len1 len2]='\0'; return result; 4)Common pointer mistakes a)There are two mistakes in this example.First,array bounds must be constant.Thus,the declaration int array[n] is illegal.Second,even if this line worked,however,the function would still attempt to return a value on the stack rather than one on the heap.That memory is deallocated immediately upon the return from the function. b)This function allocates no memory for the array.The only value available is the pointer,so it is illegal to assign to array elements using the pointer value

- 5 - b) string Concat(string s1, string s2) { string result; int len1, len2, i; if (s1 == NULL || s2 == NULL) return NULL; len1 = StringLength(s1); len2 = StringLength(s2); result = (string)GetBlock((len1 + len2 + 1) * sizeof(char)); for (i = 0; i < len1; i++) { result[i] = s1[i]; } for (i = 0; i < len2; i++) { result[i + len1] = s2[i]; } result[len1 + len2] = '\0'; return result; 4) Common pointer mistakes a) There are two mistakes in this example. First, array bounds must be constant. Thus, the declaration int array[n] is illegal. Second, even if this line worked, however, the function would still attempt to return a value on the stack rather than one on the heap. That memory is deallocated immediately upon the return from the function. b) This function allocates no memory for the array. The only value available is the pointer, so it is illegal to assign to array elements using the pointer value

-6- 5)Program Tracing:Meet the cast of Friends Drawing of the state of memory just prior to the call to Friends: the stack the heap oeyo??☑ C h a nd le r r四es阿 ?22? ?2? ?? ?? 4 main's stack frame Drawing of the state of memory just after the call to the Friends function: the stack the heap Jo e b o bo? >h a n d l e o C h a n d 1 e rr u l e s o main's stack frame y o]

- 6 - 5) Program Tracing: Meet the cast of Friends Drawing of the state of memory just prior to the call to Friends: J o e y \0 ? ? ? C h a n d l e r r u l e s \0 4 the stack main’s stack frame the heap ???? ???? ???? ???? ???? Drawing of the state of memory just after the call to the Friends function: J o e b o b \0 ? C h a n d l e r r u l e s \0 2 the stack main’s stack frame the heap ???? h a n d l e \0 y \0