Reverse string by words in c

That is, given a sentence like this


Sachin is a good boy


The in place reverse would be


boy good a is Sachin

Method1

First reverse the whole string and then individually reverse the words


Sachin is a good boy
<------------->

yob doog a si nihcaS
<-> <--> <-> <-> <->

boy good a is Sachin



Here is some C code to do the same ....


/*
Algorithm..

1. Reverse whole sentence first.
2. Reverse each word individually.

All the reversing happens in-place.
*/

#include

void rev(char *l, char *r);


int main(int argc, char *argv[])
{
char buf[] = "the world will go on forever";
char *end, *x, *y;

// Reverse the whole sentence first..
for(end=buf; *end; end++);
rev(buf,end-1);


// Now swap each word within sentence...
x = buf-1;
y = buf;

while(x++ <>
{
if(*x == '\0' || *x == ' ')
{
rev(y,x-1);
y = x+1;
}
}

// Now print the final string....
printf("%s\n",buf);

return(0);
}


// Function to reverse a string in place...
void rev(char *l,char *r)
{
char t;
while(l <>
{
t = *l;
*l++ = *r;
*r-- = t;
}
}

Method2

Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------


Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.

Method3

Create a linked list like



| I | -> | <> | -> | am | -> | <> | -> | a | -> | <> | -> | good | -> | <> | -> | boy | -> | NULL |



Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.

#include "stdio"
#include "stdlib"

#include "string"

/* reverse a string in place, return str */
static char* reverse(char* str)
{
char* left = str;
char* right = left + strlen(str) - 1;
char tmp;
while (left < style="color: rgb(0, 51, 0);"> tmp = *left;
*left++ = *right;
*right-- = tmp;
}
return str;
}

static int reverseWords(
const char* instr, /* in: string of words */
char* outstr) /* out: reversed words */
/* (caller must ensure big enough) */
{int k;
char* p;
char* buf;
*outstr = '\0';
if ((buf = (char*)malloc(strlen(instr)+1)) == NULL) {
fprintf(stderr, "oops, out of memory\n");
return -1;
}
strcpy(buf, instr);
reverse(buf);
if ((p = strtok(buf, " \t")) == NULL) {
free(buf);
return 0;
}

strcpy(outstr, reverse(p));
outstr += strlen(p);
while ((p = strtok(NULL, " \t")) != NULL) {
*outstr++ = ' ';

strcpy(outstr, reverse(p));
outstr += strlen(p);
}
free(buf);
return 0;
}

int main()
{
char instr[256];
char outstr[256];
printf("\n enter a string:");
gets(instr);
reverseWords(instr, outstr);
printf("in='%s' out='%s'\n", instr, outstr);
return 0;
}





:::::::::::::::::::::::::::::::::::::::
#include"stdio.h"

/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);

/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */

/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */

/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}

/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end )
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}

/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}

binary tree in c

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
Node *current = this->root;

while ( current != NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}

return false;
}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.

Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like

static Node* Leaf;

bool BinaryTree::Search (int data )
{
Node *current = this->root;

Leaf->data = data;

while ( current->data != lead->data )
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}

return (current != Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.