3
\$\begingroup\$

I'm a Python programmer / teacher who was a CIS major in college. I'm going back to school to get my masters in CS probably, and the first course is a prerequisite Intro to Programming in C / C++. I've decided to work through the K&R book to prepare myself, and this is quite the learning experience!

For this particular review, I'm hoping you can help me identify unnecessary or potentially risky elements of this string reversal code. I'm using some inspiration from an earlier problem I solved in the book, but I was able to figure out the reversal on my own after looking up how to do a decrementing for loop properly and how to return a character array (or a pointer to it? - I haven't made it to the pointers stuff yet haha).

I'm also not getting why I need this particular if statement handling the newline, which was part of the original code in the book's example. How is this any different than what's happening in the for loop for the get_line() function?

Certainly there are other deficiencies, I'm happy to hear them.

Lastly, I've read a couple of related answers, and some folks are mentioning that the K&R book is perhaps suboptimal. Any recommendations on alternatives? I prefer to work harder if it means I learn more, but not so hard that I am hamstringing myself for the future :D.

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

String Reversal Code

#include <stdio.h>

#define MAXLINE 1000

int get_line(char line[], int maxline);
char* reverse(char from[], int len, char reversed[]);

main() 
{
  int len;    /* length of the line */
  char line[MAXLINE];
  char reversed[MAXLINE];
  char *final;
  
  while ((len = get_line(line, MAXLINE)) > 0)
    final = reverse(line, len, reversed);
  printf("%s", final);
    
  return 0;

}

int get_line(char line[], int lim)
{
  int c, i;

  for (i = 0; i < lim-1 && (c = getchar())!=EOF && c!= '\n'; ++i)
    line[i] = c;
  if (c == '\n') {
    line[i] = c;
    ++i;
  }
  line[i] = '\0';
  return i;

}

char* reverse(char from[], int len, char reversed[])
{
  unsigned i;
  int k, last_char_index;

  k = 0;
  last_char_index = len-1;

  for (i = last_char_index; i-- > 0;)
  {
    reversed[k] = from[i];
    k++;
  }
  return reversed;
}
\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

Programming like it's 1980? Got one of those "micro" computer thingies, or are you using a timeshareing system at a university?

Seriously, a lot has changed since K&R was published in 1978. The C language evolved a lot, including the very way functions are declared. I see you're using the ANSI style for reverse but (as another answer has noted) you have a legacy definition for main with an implicit-int return type.

A big change you are not aware of is the repeal of the need to declare all local variables before any code in the function. As of C99, you can mix variable declarations and other statements. This is a very good idea. So it's quite silly to write:

int k, last_char_index;

k = 0;
last_char_index = len-1;

clearly you want:

int k= 0;
int last_char_index = len-1;

Another thing that was already figured out by the publication of K&R is the "nul-terminated string" convention. Your reverse function should look for a '\0' at as a terminating character, not take a length argument.

If your reading has not covered this yet: The literal string syntax "Hello" (double quotes) creates an array of char, like this:

static const char __InternalName[] = {'H','e','l','l','o','\0'};

So if you write: const char *s = "Hello"; then s is a pointer to the character containing the value 'H'.

Not having strings as a first-class value type casts a huge shadow. You need naming conventions to indicate the ownership of strings returned, and whether or not new (dynamic memory) strings are created at all. Your function: appears to take an "out" parameter so the caller supplies storage for the result... but it also returns a char* so what is that for?

For example, if you have the function declared as char *name (params); (no conventions apparent) vs. establishing a convention that functions ending in Copy return allocated strings that the caller owns and must free, but functions ending in View are handed pointers that are owned elsewhere and must not be freed. The caller of name has no idea whether he needs to call free.


Concentrate on one thing. If you are learning basic algorithms like how to reverse a string, your code should be only for that. Use standard library and other library functions for the rest of the framework whose only purpose is to host your exhibition. You don't have to write all the primitive things from scratch, all at once!

You don't even need to worry about Input. Use fixed test cases in a test driver, or take a string to reverse on the command line (or both!). Just don't worry about "get line". That is a huge can of worms to get right, and that's not what your problem is all about.


If you want to learn C today, first get some up-to-date documentation. That would mean textbooks and references that are less than 11 years old, in order to cover the 2011 standard.

Also ask yourself why you want to use C. Is it for microcontroller projects where you want low-level pointers and such to be a big part of why you need it? Or what reasons (as opposed to learning C++)?

Also, learn that there is a standard library of functions and many conventions, hand-in-hand with learning the language itself. Otherwise you'll end up with very weird stuff.


requirements

You want to write a "reverse" string function. In-place or copying? If the latter, will it allocate a string or be provided storage?

Since the point is to do the reversing, doing it in-place avoids these added complexities. So, the function would be declared as:

void reverse (char* s); // reverse nul-terminated string in place

coding

You are to write a string reversing function. You're not to be distracted by writing semi-robust user input handling or a full GUI from scratch for that matter. Write only this function! So how do you package it up to see it work and test it?

test harness

You can call it and check the results using pre-defined values. In fact, write these first!

   test ("hello",  "olleh");
   test ("", "");
   test ("whatever", "whatever");

The test function would make the call and print the result to begin with, and then make the call and automatically check the result for correctness.

Tip: You'll have to copy the parameter in order to reverse in-place

ad-hoc calls

If you want to call it on an arbitrary string you supply, don't do user-as-a-file input. Do it the way real UNIX programs work: on the command line. E.g. if the program is called reverse then from the prompt type reverse hello and get back olleh on the terminal. That is, just call the function with (a copy of) argv[1].

Closing

Good luck. Keep at it!

my solution

Here's how I might write it if I had to. I don't have to, because C++ has a reverse and a reverse_copy in its standard library.

void reverse (char* s)
{
    char* e = s+strlen(s);  // points at nul terminator
    if (s==e) return;
    --e;  // last char of actual string contents
    while (s < e) {
       // swap these two characters
       char tmp = *s;
       *s = *e;
       *e = tmp;
       // advance pointers inward
       --e;
       ++s;
    }
}

In other languages you would do this with subscripts on a string object (or native value as implemented implicitly as part of the language). You might mimic that in C, but it would actually require more registers to do that. Use the pointers! Strings are not first class value-based objects, but pointers. So go with its strengths in this case.

The difficult part is getting the boundary conditions right, and keeping it elegant without extra testing or duplicated steps. It helps to follow it along on paper or a whiteboard, showing where each pointer is.

Just what are the boundary conditions?

  • NULL pointer for s. Not my problem, the function is documented to take a pointer to the beginning of a nul-terminated string, and does not have NULL as part of its domain.

  • empty string. This is a real issue because pointing to the first and last chars will not work. So this is tested first. Now, proceeding forward, the main algorithm implementation can assume there is at least 1 character that can be pointed to.

That's enough to write the forward and backward pointers without further special cases.

  • where the s and p meet — how to stop? The loop drops out if they meet or cross, so it handles both odd and even length strings, and naturally doesn't bother swapping the middle character with itself.

The pointer movement (--e) is done after the test tells it to go; that is, at the top of the loop that does one character. That way it will never try to back up the e pointer when it's at the beginning (think about a single-character string!)

These same issues are involved in many of the algorithms you will be studying, so this is indeed good practice. Remember: think about boundaries, and arrange the code so that you don't need extra tests or duplicated logic.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ the array of program-arguments and the arguments themselves are always modifiable, so no need to dupe them. \$\endgroup\$ Feb 3 at 12:23
  • 1
    \$\begingroup\$ This is very helpful! This clarified / reinforced several things and raised some questions. 1. After hearing this refrain about the K&R book, I got Effective C from NoStarch - it is better! 2. The paragraph of yours which begins: "You need naming conventions..." is confusing to me. I know what a naming convention is, however I'm not connecting the dots to what you're saying. 3. char* e = s+strlen(s); is odd to me. I understand this creates a pointer to e of type char. I do not get the s+strlen(s) portion, other than the obvious purpose of the strlen() function. \$\endgroup\$ Feb 10 at 13:03
  • \$\begingroup\$ @QuincyTennyson perhaps you didn't get to that point in the learning yet: A[x] (subscript) is defined as *(A+x). Subscripting is always pointer arithmetic. The convention for "strings" is that s is a char* to the first character, and the string is terminated by a '\0' character. So, e is initialized to point to the '\0' at the end of that string. It helps if you draw it out; the string "Hello\0" with letters in individual boxes representing consecutive bytes. \$\endgroup\$
    – JDługosz
    Feb 10 at 15:09
  • \$\begingroup\$ Re naming conventions I've seen e.g. on the Mac where the C-based API used words as part of the function name to indicate whether the return pointer is something the caller needs to be responsible for (or not), and whether a char* parameter is copied or captured or whatnot. You can't tell these responsibilities from the signature. \$\endgroup\$
    – JDługosz
    Feb 10 at 15:16
  • 1
    \$\begingroup\$ @JDługosz thank you for clarifying. The subscripting part came up in Effective C as well, and I had to do some serious Googling to figure that out. I get it now, though. I happened upon a little university PDF about alignment, and that helped me understand a bit more about why the subscripting works in that way. This language is giving me a new appreciation for computer / code interaction. \$\endgroup\$ Feb 17 at 13:19
1
\$\begingroup\$

Don't rely on old-style defaulting of function return types. Make your functions modern:

int main(void)

It's good that you have defined separate functions. You should declare them with static linkage as good practice (though there's little practical benefit when the program comprises a single translation unit). If we define them before main(), there's no need for any forward declarations.

The get_line() function seems to do the same thing as the standard library fgets() - it's better to use the library function if possible. We'd then need to use strlen() to get the length, given the difference in return value.

You could avoid repeating the assignment to line[i] for the newline, by breaking out of the loop after assignment in that case:

static int get_line(char line[], int lim)
{
    int i = 0;
    int c;
    while (i < lim-1  &&  (c = getchar()) != EOF) {
        line[i++] = c;
        if (c == '\n') {
            break;
        }
    }
    line[i] = '\0';
    return i;
}

I think you should be printing each line that's reversed, rather than only the last one. It seems silly to do the work but then ignore the result.

Given that we ignore the last character on each line (hint: what happens with an input that doesn't end in newline?), we should insert appropriate newlines when we print.

I get unexpected results when my input lines are of differing lengths:

$ printf 'abc\ndefg\nhi' | stackexchange/review/273672 | od -c
0000000   h   f   e   d
0000004

It seems that although we're only printing the reverse of the last line, we're including characters from the preceding line. This suggests a missing null-terminator.

\$\endgroup\$
1
\$\begingroup\$

Tiny addition to what others said:

If your variable name is so unclear that it requires a comment, that means you should improve the variable name.

E.g. this comment:

int len;    /* length of the line */

If you just called it line_length, then this comment wouldn’t be necessary.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.