Massachusetts Institute of Technology
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 4 – Solutions
Pointers. Arrays. Strings. Searching and sorting algorithms.
Out: Friday, January 15, 2010. Due: Tuesday, January 19, 2010.
Problem 4.1
Consider the insertion sort algorithm described in Lecture 5 (slides 21-23). In this problem, you
will re-implement the algorithm using pointers and pointer arithmetic.
(a) The function shift element() takes as input the index of an array element that has been
determined to be out of order. The function shifts the element towards the front of the array,
repeatedly swapping the preceding element until the out-of-order element is in the proper
location. The implementation using array indexing is provided below for your reference:
/∗ move p r e v i o u s e l e m e n t s down u n t i l
i n s e r t i o n p o i n t r e a c h e d ∗/
void s h i f t e l e m e n t ( unsigned i n t i ) {
int i v a l u e ;
/∗ guard a g a i n s t g o i n g o u t s i d e a r r a y ∗/
f o r ( i v a l u e = a r r [ i ] ; i && a r r [ i −1] > i v a l u e ; i −−)
a r r [ i ] = a r r [ i − 1 ] ; /∗ move e l e m e n t down ∗/
a r r [ i ] = i v a l u e ; /∗ i n s e r t e l e m e n t ∗/
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
/∗ i n s e r t code h e r e ∗/
}
Answer: Here’s one possible implementation:
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
i n t i v a l u e = ∗ pElement ;
f o r ( i v a l u e = ∗ pElement ; pElement > a r r && ∗ ( pElement −1) > i v a l u e ; pElement−−)
∗ pElement = ∗ ( pElement −1);
∗ pElement = i v a l u e ;
}
(b) The function insertion sort() contains the main loop of the algorithm. It iterates through
elements of the array, from the beginning, until it reaches an element that is out-of-order. It
calls shift element() to shift the offending element to its proper location earlier in the array
and resumes iterating until the end is reached. The code from lecture is provided below:
1
, /∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
unsigned i nt i , l e n = a r r a y l e n g t h ( a r r ) ;
f o r ( i = 1 ; i < l e n ; i ++)
i f ( a r r [ i ] < a r r [ i −1])
shift element ( i );
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
Use the shift element() function you implemented in part (a).
Answer: Here’s one possible implementation:
/∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
i n t ∗ pElement , ∗pEnd = a r r + a r r a y l e n g t h ( a r r ) ;
f o r ( pElement = a r r +1; pElement < pEnd ; pElement++)
i f ( ∗ pElement < ∗ ( pElement −1))
s h i f t e l e m e n t ( pElement ) ;
}
Problem 4.2
In this problem, we will use our knowledge of strings to duplicate the functionality of the C standard
library’s strtok() function, which extracts “tokens” from a string. The string is split using a set of
delimiters, such as whitespace and punctuation. Each piece of the string, without its surrounding
delimiters, is a token. The process of extracting a token can be split into two parts: finding the
beginning of the token (the first character that is not a delimiter), and finding the end of the token
(the next character that is a delimiter). The first call of strtok() looks like this:
char ∗ strtok(char ∗ str, const char ∗ delims);
The string str is the string to be tokenized, delims is a string containing all the single characters
to use as delimiters (e.g. " \t\r\n"), and the return value is the first token in str. Additional
tokens can be obtained by calling strtok() with NULL passed for the str argument:
char ∗ strtok(NULL, const char ∗ delims);
Because strtok() uses a static variable to store the pointer to the beginning of the next token,
calls to strtok() for different strings cannot be interleaved. The code for strtok() is provided
below:
char ∗ s t r t o k ( char ∗ t e x t , const char ∗ d e l i m s ) {
/∗ i n i t i a l i z e ∗/
i f ( ! text )
t ext = pnexttoken ;
/∗ f i n d s t a r t o f t o ken i n t e x t ∗/
t e x t += s t r s p n ( t e x t , d e l i m s ) ;
i f ( ∗ t e x t == ’\0 ’ )
return NULL;
/∗ f i n d end o f t o ken i n t e x t ∗/
pnexttoken = text + s t r c s p n ( text , delims ) ;
/∗ i n s e r t n u l l −t e r m i n a t o r a t end ∗/
i f ( ∗ p n e x t t o k e n != ’\0 ’ )
∗ p n e x t t o k e n++ = ’\0 ’ ;
return t e x t ;
}
2
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 4 – Solutions
Pointers. Arrays. Strings. Searching and sorting algorithms.
Out: Friday, January 15, 2010. Due: Tuesday, January 19, 2010.
Problem 4.1
Consider the insertion sort algorithm described in Lecture 5 (slides 21-23). In this problem, you
will re-implement the algorithm using pointers and pointer arithmetic.
(a) The function shift element() takes as input the index of an array element that has been
determined to be out of order. The function shifts the element towards the front of the array,
repeatedly swapping the preceding element until the out-of-order element is in the proper
location. The implementation using array indexing is provided below for your reference:
/∗ move p r e v i o u s e l e m e n t s down u n t i l
i n s e r t i o n p o i n t r e a c h e d ∗/
void s h i f t e l e m e n t ( unsigned i n t i ) {
int i v a l u e ;
/∗ guard a g a i n s t g o i n g o u t s i d e a r r a y ∗/
f o r ( i v a l u e = a r r [ i ] ; i && a r r [ i −1] > i v a l u e ; i −−)
a r r [ i ] = a r r [ i − 1 ] ; /∗ move e l e m e n t down ∗/
a r r [ i ] = i v a l u e ; /∗ i n s e r t e l e m e n t ∗/
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
/∗ i n s e r t code h e r e ∗/
}
Answer: Here’s one possible implementation:
/∗ i n t ∗ pElement − p o i n t e r t o t h e e l e m e n t
i n a r r ( typ e i n t [ ] ) t h a t i s out−o f −p l a c e ∗/
void s h i f t e l e m e n t ( i n t ∗ pElement ) {
i n t i v a l u e = ∗ pElement ;
f o r ( i v a l u e = ∗ pElement ; pElement > a r r && ∗ ( pElement −1) > i v a l u e ; pElement−−)
∗ pElement = ∗ ( pElement −1);
∗ pElement = i v a l u e ;
}
(b) The function insertion sort() contains the main loop of the algorithm. It iterates through
elements of the array, from the beginning, until it reaches an element that is out-of-order. It
calls shift element() to shift the offending element to its proper location earlier in the array
and resumes iterating until the end is reached. The code from lecture is provided below:
1
, /∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
unsigned i nt i , l e n = a r r a y l e n g t h ( a r r ) ;
f o r ( i = 1 ; i < l e n ; i ++)
i f ( a r r [ i ] < a r r [ i −1])
shift element ( i );
}
Re-implement this function using pointers and pointer arithmetic instead of array indexing.
Use the shift element() function you implemented in part (a).
Answer: Here’s one possible implementation:
/∗ i t e r a t e u n t i l out−o f −o r d e r e l e m e n t found ;
s h i f t t h e element , and c o n t i n u e i t e r a t i n g ∗/
void i n s e r t i o n s o r t ( void ) {
i n t ∗ pElement , ∗pEnd = a r r + a r r a y l e n g t h ( a r r ) ;
f o r ( pElement = a r r +1; pElement < pEnd ; pElement++)
i f ( ∗ pElement < ∗ ( pElement −1))
s h i f t e l e m e n t ( pElement ) ;
}
Problem 4.2
In this problem, we will use our knowledge of strings to duplicate the functionality of the C standard
library’s strtok() function, which extracts “tokens” from a string. The string is split using a set of
delimiters, such as whitespace and punctuation. Each piece of the string, without its surrounding
delimiters, is a token. The process of extracting a token can be split into two parts: finding the
beginning of the token (the first character that is not a delimiter), and finding the end of the token
(the next character that is a delimiter). The first call of strtok() looks like this:
char ∗ strtok(char ∗ str, const char ∗ delims);
The string str is the string to be tokenized, delims is a string containing all the single characters
to use as delimiters (e.g. " \t\r\n"), and the return value is the first token in str. Additional
tokens can be obtained by calling strtok() with NULL passed for the str argument:
char ∗ strtok(NULL, const char ∗ delims);
Because strtok() uses a static variable to store the pointer to the beginning of the next token,
calls to strtok() for different strings cannot be interleaved. The code for strtok() is provided
below:
char ∗ s t r t o k ( char ∗ t e x t , const char ∗ d e l i m s ) {
/∗ i n i t i a l i z e ∗/
i f ( ! text )
t ext = pnexttoken ;
/∗ f i n d s t a r t o f t o ken i n t e x t ∗/
t e x t += s t r s p n ( t e x t , d e l i m s ) ;
i f ( ∗ t e x t == ’\0 ’ )
return NULL;
/∗ f i n d end o f t o ken i n t e x t ∗/
pnexttoken = text + s t r c s p n ( text , delims ) ;
/∗ i n s e r t n u l l −t e r m i n a t o r a t end ∗/
i f ( ∗ p n e x t t o k e n != ’\0 ’ )
∗ p n e x t t o k e n++ = ’\0 ’ ;
return t e x t ;
}
2
