Sort linked list

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define N 12    //number of elements in the array
typedef bool (*CompareFunction)(void *, void *);

typedef struct Node{
      int data;
      char str[20];
      struct Node * next;
      } Node;

/*
* create a linked list from an array of elements
*/
void createLinkedList(int array[], int length, Node **head)
{
  int i;
  Node *current;
  Node *p;
  if(length == 0)
      return ;//;NULL;
  for(i = 0; i < length; i++)
  {
      if(i == 0)
      {
          *head = (Node*) malloc(sizeof(Node));
          (*head)->data = array[i];
          snprintf((*head)->str, 10,"%d",array[i]);
          (*head)->next = NULL;
          current = *head;
      }
      else
      {
          p = (Node*) malloc(sizeof(Node));
          p->data = array[i];
          snprintf(p->str, 10, "%d", array[i]);
          p->next = NULL;
          current->next = p;
          current = p;
      }
  }
}

/*
*   integer compare
*/
bool compareint(void *a, void *b)
{
  int x = *(int*)a;
  int y = *(int*)b;
  return (x > y);
}
/*
*   string compare
*/
bool comparechar(void *a, void *b)
{
  char *x = (char*)a;
  char *y = (char*)b;
  return strcmp(x, y) < 0 ? 1:0;
}

/*
*  print the linked list
*/
void printLinkedList(Node *head)
{
  Node *p = head;
  while(p != NULL)
  {
      printf("(%d,", p->data);
      printf("%s),", p->str);
      p=p->next;
  }
  printf("\n");
}


bool sort(Node **head, CompareFunction cmpFunc)
{
  Node *s = *head;    //start node
  Node *t = s->next;  //iterating node
  Node *t_parent = s; //parent of iterating node
  Node *index = NULL; // max or min node index
  Node *index_parent = NULL;
  Node *current = NULL;

  //iterate all nodes
  while(s->next != NULL)
  {
      index = s;
      t = s->next;
      t_parent = s;
      // find the max/min node
      while( t != NULL)
      {
          if(cmpFunc(&(index->data), &(t->data)))
          {
              index = t;
              index_parent = t_parent;
          }
          t_parent = t;
          t = t->next;
      }

      //printf("index=%d\t,", index->data);

      //move the seletced max/min to sorted list
      if(current == NULL)
      {
          current = index;
          *head = current;
      }
      else
      {
          current->next = index;
          current = current->next;
      }

      //remove the selected node from the unsorted list
      if(index == s)
          s = s->next;
      else
          index_parent->next = index->next;

      current->next = NULL;
  }
  //add the last single node in the original list to the sorted list
  if(current != NULL)
      current->next = s;
  return true;
}



int main()
{

  int array[N]={10,4,2,11,4,8,7,3,5,9,-1,2};
  Node *root;
  createLinkedList(array, N, &root);
  printLinkedList(root);
  sort(&root, &compareint);
  printf("Sorted List\n");
  printLinkedList(root);

      return 0;
}

Integer Expression Evaluator code

/*
* Expression evaluator. It supports +,-,*,/ and (), and integers.
* Example: 2*((5+4)/2)*6=48
* This code does not evaluate unary expression, such as -1
*
*/
#include <iostream>
#include <stack>
using namespace std;

enum OPR{ADD='+', SUB='-', MUL='*', DIV='/', PAR='('};

int eval(const string &exp);
int calc(int, int, OPR);
int rank(OPR r1);

int main(int argc, char *argv[])
{
    string exp;
 
    if(argc > 1)
         exp = argv[1];
    else
         exp = "2*((5+4)/2)*6+(2)";
    int result = eval(exp);
    cout << exp << "=" << result << endl;
}

/*
*     Evaluates a math expression
*/

int eval(const string & exp)
{
 
    stack<int> Opd;     //stack for operands
    stack<OPR> Opr;     //stack for operators
    int opd1;
    int opd2;
    OPR opr1;
    int result = 0;
    int i = 0;
    int Len = exp.length();
    for(i = 0; i < Len; i++)
    {
         //end of a parentheses
         if(exp[i] == ')')
         {
              while(Opr.top() != PAR)          //If last pushed opeator is not (, then evaluate
              {
                   opr1 = Opr.top();
                   Opr.pop();
                
                   opd1 = Opd.top();
                   Opd.pop();
                
                   opd2 = Opd.top();
                   Opd.pop();
                
                   Opd.push(calc(opd1,opd2,opr1));
              }
              Opr.pop();     // pop '('
         }  
         else if(isdigit(exp[i]))     //if a number, push to operand stack
         {
              Opd.push(exp[i] - '0');
         }
         else
         {
              //If current element is an operator, and operator stack is not empty
              //compare their precedence.
              if(!Opr.empty())
              {
                   opr1 = Opr.top();  
                   if(opr1 != '(' && rank(opr1) >= rank(static_cast<OPR>(exp[i])) )
                   {
                        opd1 = Opd.top();
                        Opd.pop();
                        opd2 = Opd.top();
                        Opd.pop();
                        result = calc(opd1,opd2, opr1);
                        Opr.pop();
                        Opd.push(result);
                   }
              }
              Opr.push(static_cast<OPR>(exp[i]));
         }
 
    }
 
    //Evaluate the last binary expression remainig in the stack
    while(!Opr.empty())
    {
         opr1 = Opr.top();
         Opr.pop();
         opd1 = Opd.top();
         Opd.pop();
         opd2 = Opd.top();
         Opd.pop();
         Opd.push(calc(opd1,opd2,opr1));
    }  
 
    return  Opd.top();
}

/*
*     Evaluates an binary expression such as 1+2
*/
int calc(int opd1, int opd2, OPR opr1)
{
    int c;
    switch(opr1)
    {
         case ADD:
              c = opd2 + opd1; break;
         case SUB:
              c = opd1 - opd2; break;
         case MUL:
              c = opd1 * opd2; break;
         case DIV:
              c = opd2 / opd1; break;
    }
    return c;
}
/*
*     Operator Precedence
*/
int rank(OPR opr1)
{
    int r = 0;
    switch(opr1)
    {
         case ADD:
         case SUB:
              r = 1; break;
         case MUL:
         case DIV:
              r = 2; break;
         case PAR:
              r = 3; break;
    }
 
    return r;
}

C++ Trie

/*
*     Name: Trie
*     Author: Anwar Mamat
*     Date: 12/2011
*/

#include <iostream>
#include <vector>
using namespace std;

/*
*     Trie Node
*/
class Node{
public:
  Node(){ mContent=' '; marker=false; mPrefix = 1;}
  ~Node(){}
  Node*      findChild(char c) const ;
  void      addChild(Node * child) {children.push_back(child);}
  void      setMarker(bool t){marker=t;}
  bool      getMarker() const {return marker;}
  char      content() const {return mContent;}
  void      setContent(char c) { mContent = c;}
  void      setPrefix(int p){mPrefix = p;}
  int      getPrefix() {return mPrefix;}
  int      countChild() const {return children.size();}
  bool      deleteChild(char c);
  Node *      getChild(int index){
             rd">if(index >=0 && index < countChild())
             ="kwrd">return children[index];
            }
else
            }
    return NULL;
                 }
  void      setChild(Node *t, int index){
                                                  if(index>=0 && index< countChild())
                                                         children[index]=t;
                                               }
private:
  char mContent;
  bool marker;
  vector<Node*> children;
  int mPrefix;          //how many words this node prefixes
};

ostream& operator << (ostream& output, Node & node)
{
  output << node.content();
  return output;
}

/*
*          Trie class
*/
class Trie
{
public:
  Trie(){root = new Node();}
  ~Trie();
  void     addWord(const string & word);
  bool     findWord(const string  & word) const;
  bool      deleteWord(const string &  word);
  void     print() const;
  void      sort() const;
private:
  Node      *root;
  void      printWords(Node*, char *, int length) const;
  void      sortTrie(Node *) const;
  void      deleteSubTrie(Node *);
};

/*
     Sort the trie words in alaphabetic order
*/

void Trie::sort() const
{
  sortTrie(root);
}


void Trie::sortTrie(Node *current) const
{
  int i;
  int j;
  Node *t;

  //sort the children of current node level
  for(i = 0; i < current->countChild()-1; i++)
       for(j=i+1; j < current->countChild(); j++)
            if(current->getChild(i)->content() > current->getChild(j)->content())
            {
                 t = current->getChild(i);
                 current->setChild(current->getChild(j), i);
                 current->setChild(t, j);
            }

  //recursively sort children
  for(i = 0; i < current->countChild(); i++)
  {
       sortTrie(current->getChild(i)); 
  }
}
/*
*     Enumerate all words in the trie
*/
void Trie::print() const
{
  char word[256]={""};

  printWords(root,word, 0);

}

void Trie::printWords(Node *current, char *word, int index) const
{
  int i;
  if(current == root)
       index = 0;
  for(i = 0; i < current->countChild(); i++)
  {
       Node *child = current->getChild(i);
       word[index] = child->content();

       if(child->getMarker())
       {
            word[index+1]='\0';
            cout << word << endl;
       }

       printWords(child, word, index+1);
  }
}

/*
*     Trie deconstructor
*/
Trie::~Trie()
{
  deleteSubTrie(root);
}

/*
*     delete a child of a node
*/
bool Node::deleteChild(char c)
{
  int i;
  for(i = 0; i < children.size(); i++){
       if(children[i]->content() == c)
            children.erase(children.begin() + i);
  }
}

/*
*     Find a child of a node
*     input: single char
*     return: child if exists, NULL if does not exist
*/

Node* Node::findChild(char c) const
{
  int i;
  for(i=0; i < children.size(); i++)
       if(children[i]->content() == c)
            return children[i];
  return NULL;

}

/*
*
*     Add a word to the trie
*/
void Trie::addWord(const string  & word)
{
  int i;
  char c;
  Node *current= root;
  if(word.length() == 0)
  {
       current->setMarker(true);
       return;
  }

  for(i=0; i < word.length(); i++)
  {

       Node* child = current->findChild(word[i]);

       if(child != NULL)
       {
            child->setPrefix(child->getPrefix() + 1);
            current = child;
       }
       else
       {
            Node * tmp = new Node();
            tmp->setContent(word[i]);
            current->addChild(tmp);
            current = tmp;
       }

       if(i == word.length() - 1 )
       {
            current->setMarker(true);
       }
  }
}

/*
*     delete a sub trie
*/
void Trie::deleteSubTrie(Node *current)
{ 
  for(int i = 0; i < current->countChild(); i++)
  { 
       deleteSubTrie(current->getChild(i));
  }

       delete current;

}

/*
*     Find a word from the trie
*/
bool     Trie::findWord(const string & word) const
{

  Node *current = root;

  int i;
  for(i = 0; i < word.length(); i++)
  {
       current = current->findChild(word[i]);
       if(current == NULL)
            return false;
  }

  if(current->getMarker())
       return true;
  else
       return false;
}

/*
*          delete a word from the trie
*/
bool Trie::deleteWord(const string & word)
{
  //if the word exists
  if(!findWord(word))
       return false;

  Node *current = root;
  int i;
  for(i = 0; i < word.length(); i++)
  {
       Node* child = current->findChild(word[i]);
       //cout << *child << " \t" <<child->getPrefix() << endl;
       if (child == NULL)
            return false;
       else if(child->getPrefix() == 1)
       {
            current->deleteChild(child->content());
            deleteSubTrie(child);
            return true;
       }
       else
       {
            child->setPrefix(child->getPrefix() - 1);
            current = child;
       }
  }
  //remove the word marker
  current->setMarker(false);

}

int main()
{ 

  Trie *t = new Trie();

  t->addWord("BOB");
  t->addWord("ABCDEF");
  t->addWord("ABCD");

  t->print();

  t->sort();
  cout << "After sort" << endl;
  t->print();


  t->deleteWord("ABCD");
  cout << "ABCD is deleted" << endl; 

  t->print();


  //cout << "delete tree" << endl;
  delete(t);
  t = NULL;

}

Reverse each word is a string

/********************************************************
* *
* Reverse each word is a string *
* *
* *
*********************************************************/
#include "iostream"
using namespace std;
void reverse(char *, int , int);
int main()
{
char src[] = "My name is Abc Xyz. My dog's name is Max.";

int len = strlen(src);

int s = 0; //start index of a word
int t = 0; //end index of a word

while(t < len){
while((isalpha(src[t]) || src[t] == '\'') && t < len) t++; //find the end index of a word
reverse(src,s,t-1); //reverse the word at [s, t-1]
while(!isalpha(src[t]) && t < len) t++; //find the start index of next word
s = t; // set the start index of the next word
}
cout << src << endl;


}

/****************************************
* *
* reverse a word *
* *
*****************************************/
void reverse(char *str, int s, int t)
{
char temp;
while (s < t){
temp = str[s];
str[s] = str[t];
str[t] = temp;
t--;
s++;
}

}

C word count program

/*
Word Count Program (delimiter is the space)
Author: Anwar Mamat
Date: 1/27/2011

*/

#define LENGTH 200

#include "stdio.h"

int main()
{
char words[LENGTH] = {"The test of a first-rate intelligence is the ability to hold two opposed ideas in mind at the same time and still retain the ability to function."};

char *p = words;
int wordcount = 0;

while(*p){
//skip spaces
while(*p++ == ' ') {
//if a space is the last, terminate the loop
if(!*p) goto done;
}
//word found
wordcount++;
//skip the word
while(*p != ' ' && *p) p++;
}
done:
printf("%s\n", words);
printf("Number of words = %d\n", wordcount);
}

Reverse each word in a string

/*************************************************** *
* Reverse each word is a string
*
*
*****************************************************/
#include "iostream"
using namespace std;
void reverse(char *, int , int);
int main()
{
char src[] = "My name is Abc Xyz. My dog's name is Max.";

int len = strlen(src);

int s = 0; //start index of a word
int t = 0; //end index of a word

while(t < len){
while((isalpha(src[t]) || src[t] == '\'') && t < len) t++; //find the end index of a word
reverse(src,s,t-1); //reverse the word at [s, t-1]
while(!isalpha(src[t]) && t < len) t++; //find the start index of next word
s = t; // set the start index of the next word
}
cout << src << endl;


}

/****************************************
* *
* reverse a word *
* *
*****************************************/
void reverse(char *str, int s, int t)
{
char temp;
while (s < t){
temp = str[s];
str[s] = str[t];
str[t] = temp;
t--;
s++;
}

}

K Reverse linked list

Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.

The following are the constraints given:

• You have to retain the memory address of the nodes without modifying it i.e. you can’t just interchange the values in the nodes
• Only constant memory is allowed

For example the linked list given is as follows:

Linked List : 1->2->3->4->5->6->7->8->9->10->11 -> null

For k = 2

Return Value: 2->1->4->3->6->5->8->7->10->9->11 ->null

For k = 3

Return value: 3->2->1->6->5->4->9->8->7->10->11 -> null

Solution:

#include "iostream"
using namespace std;

const int N = 10;

//Linked List Class
class LinkedList
{
private:
struct Node{
int data;
struct Node *next;
Node(){next = NULL;};
};
struct Node * Head;
public:
LinkedList();
bool create();
void print();
void reverse(int k);
};

//Print the List
void LinkedList::print()
{
Node *p = Head;
while(p)
{
cout <<>data << " ";
p = p->next;
}
cout << endl;
}

//CTR
LinkedList::LinkedList()
{
Head = NULL;
}

//Create the Linked List 1->2->3->4->5->6->7->8->9->10
bool LinkedList::create()
{
Head = new (struct Node);
Head->data = 1;
Node *p=Head;
Node *t;
for(int i = 2; i <= N; i++){
t = new (struct Node);
t->data = i;
p->next = t;
p = p->next;
}
return true;

}

//Reverse the Linked List within K nodes
void LinkedList::reverse(int k)
{
Node *p = Head;
Node *q = Head;
Node *t = p->next;
Node *r = p->next;
Node *last = p;
p->next = NULL;
int i = 1;
bool flag = false;
while(r)
{
//reverse the list
r = r->next;
t->next = p;
q->next = r;
p = t;
t = r;

i++;
// when k nodes are reversed, start from the next k nodes
if(i >= k||r == NULL){
i = 1;
if(!flag){
Head = p;
flag = true;
}
else
last->next = p;

last = q; // link the last k nodes to the next k nodes
p = r;
q = r;
if(p){
r = p->next;
t = p->next;
}
else{
r= NULL;
t = NULL;
}
}

}
}


int main(int argc, char* argv[])
{
LinkedList L;
L.create();
L.print();
L.reverse(4);
L.print();
return 0;
}