Sunday 23 January 2011

The C Programming Language (K&R) 01x15—Char Arrays & Functions—Exercise 1-19


There’s one last bit of secton 1.09 of “The C Programming Language” by Brian Kernighan and Dennis Ritchie aka K&R:

Exercise 1-19. Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.

s[] is a character array holding the user’s input. The function will take element 0 and put it in element n and n to 0 and keep going until the string is reversed. There’s many ways this can be done, but the objective is clear: s[]has to contain the reverse order and the array is returned to the caller with the changed data.

If you work simply with the array variable, you can’t copy element n to m without losing m. You need some type of temporary variable.

Approach 1: Use the copy function to create a duplicate of s[]. Then loop through the duplicate to and store the data in s[]. Requires one loop counter, but double the memory for the user data.

Approach 2: Start at s[n], store that data in a temp variable. Move s[0] to s[n] and temp to s[n]. Continue through s[] until you’re at the midpoint.

I’m not certain which approach is faster, but the second clearly uses less memory and even with 4GB or more of RAM, minimizing memory is a good objective.

*   *   *

The highlights show the changes to the code from here.
 

Sample Code.

I am using Visual C++ 2010 and created the sample code as a console application.

// Function prototype.
int getline(char line[], int maxline);
void copy(char to[], char from[]);
void reverse(char s[]);

// The standard library includes the system function.
#include <cstdlib>

// Standard I/O library.
#include <cstdio>

#define MAXLINE 1000 /* maximum input line length */

int main()
{
     int len; /* current line length */
     int max; /* maximum length seen so far */

     char line[MAXLINE]; /* current input line */
     char longest[MAXLINE]; /* longest line saved here */
     max = 0;

     while ((len = getline(line, MAXLINE)) > 0)
           if (len > max) {
           max = len;
           copy(longest, line);
           }

     if (max > 0) /* there was a line */
           reverse(longest);
           printf("%s", longest);

     // Keep console window open.
     system("pause");

     // Return some value.
     return 0;

} // end main

/* getline: read a line into s, return length */
int getline(char s[],int lim)
{
     int c, i;

     for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
           s[i] = c;

     if (c == '\n') {
           s[i] = c;
           ++i;
     }

     s[i] = '\0';

     return i;
}

/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
     int i;
     i = 0;

     while ((to[i] = from[i]) != '\0')
     ++i;
}

// Reverse order of char array.
void reverse(char s[])
{
     // S is a character array.
     // This function will reverse the
     // order of the content.
     // 1 to n, n to 1.

     // Temp hold.
     int c = 0;
     // Counters.
     int iFrom = 0;
     int iTo = 0;

     // Find length of array.
     while (s[iTo] != '\n')
           ++iTo;

     // Calc midpoint.
     int Midpoint = iTo / 2;

     // Char array holds:
     // [user data], [\n], [\0]
     --iTo;

     // Loop through array.
     for (iFrom; iFrom < Midpoint; ++iFrom, --iTo)
     {
           // Temp holder.
           c = s[iTo];
           // Front to back.
           s[iTo] = s[iFrom];
           // Back to front.
           s[iFrom] = c;
     }
} // end reverse


Output.

The longest line, printed in reverse order, is…


No comments:

Post a Comment