1
\$\begingroup\$

We have a linklist which is made of alphabets. We have to shift the vowels towards the end of the linklist, without changing the order in which they appear. So,

A->C->E->F->G->O

should become

C->F->G->A->E->O

This is the code I have written

#include<iostream>

using namespace std;

struct node
{
    char ch;
    node *next;
};

void enqueue (node **head, node **tail, char val)
{
    node *newn = (node *)malloc(sizeof(node));
    newn->ch = val;
    newn->next = NULL;

    if (*head == NULL)
    {
        *head = newn;
        *tail = newn;
    }

    (*tail)->next = newn;
    (*tail) = newn;

}

void print (node *head)
{
    while (head!=NULL)
    {
        cout<<head->ch<<" ";
        head = head->next;
    }
    cout<<endl;
}

bool isVowel (char ch)
{
    ch = ch | 32;

    if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
        return true;
    return false;

}



node* segregateVowels (node *head, node *tail)
{
    if (head == NULL || head->next == NULL)
        return head;


    node *temp = head;
    node *fin = tail;

    while (temp->next!=fin)
    {
        cout<<temp->ch<<" "<<fin->ch<<endl;
        if (isVowel(temp->next->ch))
        {
            node *shift = temp->next;
            temp->next = temp->next->next;
            tail->next = shift;
            shift->next = NULL;
            tail = shift;
        }
        else
            temp = temp->next;

    }

    if (temp->next!=NULL && isVowel(temp->next->ch))   /* Handling the case where the last element is a vowel   */
    {
        node *toMove = temp->next;
        temp->next = temp->next->next;
        tail->next = toMove;
        toMove->next = NULL;

    }
    else
        temp = temp->next;

    if (isVowel(head->ch))                  /*  Handling the case where the first element is a vowel    */
    {
        node *toMove = head;
        head = head->next;
        toMove->next = temp->next;
        temp->next = toMove;
    }

    return head;

}


int main()
{
    srand(time(NULL));

    node  *head = NULL, *tail = NULL;

    int i = 20;

    while (i>=0)
    {
        enqueue (&head, &tail, rand()%26+65);
        i--;
    }

    print(head);


    head = segregateVowels (head, tail);


    print(head);
}

Although this does seem to give me correct results, but I have to explicitly check for two edge cases. Also I feel there is a better solution for this problem or a better approach which I seem to be missing. The problem can be handled by creating two separate Link Lists too, and then joining them together. But what modifications do you suggest in the above program?

\$\endgroup\$
  • \$\begingroup\$ Your formatting is really consistent (especially for new lines). Also, can you explain your bit manipulation in isVowel() ? \$\endgroup\$ – SylvainD Jul 16 '13 at 14:24
  • \$\begingroup\$ I don't quite follow what you mean when you say that the formatting is consistent. The bit manipulation in isVowel() is just to turn 'A-Z' to 'a-z'. In case if I ever expand the problem to input both small and capital alphabets. \$\endgroup\$ – user2560730 Jul 16 '13 at 14:30
  • \$\begingroup\$ Ok, thanks, that what I thought. I meant 'inconsistent' as you sometimes skip a few lines for no obvious reasons. \$\endgroup\$ – SylvainD Jul 16 '13 at 15:12
  • \$\begingroup\$ Okay thanks, will keep that in mind. But I think I do that intentionally. I tend to divide my program on modules. Now these are the modules which come to my head when I think upon the implementation of the problem or the algorithm of the problem. So when I give spaces, I segregate those modules. It sometimes helps in debugging, and helps in figuring out if I am making a common mistake over and over again. \$\endgroup\$ – user2560730 Jul 16 '13 at 15:27
  • 1
    \$\begingroup\$ @user2560730: This is still C code (you may be using a couple of C++ objects std::cout etc). But the style is C. Note: C++ is a mulch-paradiam language not just OO but there are ways to use the language that avoid the bad parts of C. \$\endgroup\$ – Martin York Jul 16 '13 at 23:22
2
\$\begingroup\$

Don't do using namespace std

Here's a SO question which should provide you more information about this.

For loops are here to help you

You could write

int i = 20;
while (i>=0)
{
    enqueue (&head, &tail, rand()%26+65);
    i--;
}

in a much clearer way using a for-loop : for (int i=20; i>=0; i--) or for (int i=0; i<21; i++). I prefer the latter because I tend to count forward and not backward and it makes much clearer the fact that you want 21 iterations.

Avoid boilerplate and useless code

if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
    return true;
return false;

could be simply written :

return (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u');

Avoid magic numbers

Even if I can guess them, I don't want to learn the ascii code for the different characters. You could rewrite enqueue (&head, &tail, rand()%26+65); in a more explicit way : enqueue (&head, &tail, rand()%26+'A');

Be consistent with your brackets

Using brackets for single statement is a personal preference but if you do use them for the then-block, then please use them for the else-block as it makes things look "balanced".

Add a bit of documentation I know it's tedious and not so interesting and I usually try to avoid to ask for it but here, I am getting a but confused by the two functions taking two lists as parameters and trying to understand what is intended for both of them.

This being said, I have to go and I'll try to have a deeper look later on.

In the meantime, here's your code with the comments above taken into account :

#include<iostream>

struct node
{
    char ch;
    node *next;
};

void enqueue (node **head, node **tail, char val)
{
    node *newn = (node *)malloc(sizeof(node));
    newn->ch = val;
    newn->next = NULL;

    if (*head == NULL)
    {
        *head = newn;
        *tail = newn;
    }

    (*tail)->next = newn;
    (*tail) = newn;
}

void print (node *head)
{
    while (head!=NULL)
    {
        std::cout<<head->ch<<" ";
        head = head->next;
    }
    std::cout<<std::endl;
}

bool isVowel (char ch)
{
    ch |= 32; // make it lowercase
    return (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u');
}

node* segregateVowels (node *head, node *tail)
{
    if (head == NULL || head->next == NULL)
        return head;

    node *temp = head;
    node *fin = tail;

    while (temp->next!=fin)
    {
        std::cout<<temp->ch<<" "<<fin->ch<<std::endl;
        if (isVowel(temp->next->ch))
        {
            node *shift = temp->next;
            temp->next = temp->next->next;
            tail->next = shift;
            shift->next = NULL;
            tail = shift;
        }
        else
        {
            temp = temp->next;
        }
    }

    if (temp->next!=NULL && isVowel(temp->next->ch))   /* Handling the case where the last element is a vowel   */
    {
        node *toMove = temp->next;
        temp->next = temp->next->next;
        tail->next = toMove;
        toMove->next = NULL;

    }
    else
    {
        temp = temp->next;
    }

    if (isVowel(head->ch))                  /*  Handling the case where the first element is a vowel    */
    {
        node *toMove = head;
        head = head->next;
        toMove->next = temp->next;
        temp->next = toMove;
    }

    return head;
}


int main()
{
    srand(time(NULL));

    node  *head = NULL, *tail = NULL;

    for (int i=0; i<21; i++)
    {
        enqueue (&head, &tail, rand()%26+'A');
    }

    print(head);

    head = segregateVowels (head, tail);

    print(head);
}
\$\endgroup\$
  • \$\begingroup\$ I am not really sure which two lists you are talking about. Because there is just one list in the program. Head is pointing to the head of the list and tail is pointing to the tail of the list. \$\endgroup\$ – user2560730 Jul 16 '13 at 16:47
  • \$\begingroup\$ Why do you need two entry points for your list ? This is what is confusing me quite a lot. \$\endgroup\$ – SylvainD Jul 16 '13 at 17:22
  • \$\begingroup\$ Well as I am adding at the end of a link list, I would have to traverse the entire length of the list before adding a new element. But if I save the tail pointer, I could just append at the end of the tail pointer, and update the tail pointer. \$\endgroup\$ – user2560730 Jul 16 '13 at 17:39
2
\$\begingroup\$

A few comments to add to those of @Josay

The main one is that the program fails if there is a vowel at the end but no others (losing the trailing vowel), eg the list Z->Z->A is truncated to Z->Z. This happens (I think) because the code handling the vowel-at-end case assumes that a vowel has already been found - ie. that temp->next->next is not NULL.


Some minor points to add:

In segregateVowels:

  • Why the different variable names shift and toMove for things that do the same thing?

  • The tail pointer in the caller is not updated.

  • I think the if (temp->next!=NULL ... condition is redundant

  • only the vowel-at-head case needs to be handled outside the loop, not the vowel-at-end case, for example

    node *n = head;
    node *prev = head;
    node *last = tail;
    while (n != last) {
        if (isVowel(n->ch)) {
            tail->next = n;
            tail = n;
            if (head == n) {
                head = n->next;
            } else {
                prev->next = n->next;
            }
            n = n->next;
            tail->next = 0;
        } else {
            prev = n;
            n = n->next;
        }
    }
    if (isVowel(last->ch) && (tail != last)) {
        tail->next = last;
        if (head == last) {
            head = last->next;
        } else {
            prev->next = last->next;
        }
        last->next = 0;
        tail = last;
    }
    

    In this example I have used two pointers to walk through the list, prev (for 'previous') and n. n is no less meaningful than your temp and is shorter. This code fixes the error mentioned above. Note that the (tail != last) could be omitted (ie. it works without) but it is more clearly correct if present.


EDIT - actually if you pass in the size of the list, you can do everything in the loop:

node* segregateVowels (node *head, node *tail, int size)
{
    if (head == NULL || head->next == NULL)
        return head;

    node *n = head;
    node *prev = head;

    for (int i = 0; (n != NULL) && (i < size); ++i) {
        if (isVowel(n->ch)) {
            tail->next = n;
            tail = n;
            if (head == n) {
                head = n->next;
                prev = head;
            } else {
                prev->next = n->next;
            }
            n = n->next;
            tail->next = 0;
        }
        else {
            prev = n;
            n = n->next;
        }
    }
    return head;
}
\$\endgroup\$
  • \$\begingroup\$ This is a helpful response, and a much cleaner and simplistic approach. But your program will go into an infinite loop when the list consists of only vowels. \$\endgroup\$ – user2560730 Jul 17 '13 at 3:19
  • \$\begingroup\$ It doesn't infinite-loop for me (tested by 'enqueue'ing a number of vowels explicitly instead of using random chars). But it did chop off all but the last vowel. I have fixed it. \$\endgroup\$ – William Morris Jul 17 '13 at 11:33

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.