Related Blog Items

• Heap Overview
• Swapping variables without additional space
• C++ Advanced Tutorial - Lesson 9
• Binary Search Trees
• Data structures lectures

1. Reverse a singly linked list

//
// iterative version
//
Node* ReverseList( Node ** List )   
{
  Node *temp1 = *List;
  Node * temp2 = NULL;
  Node * temp3 = NULL;
 
  while ( temp1 )
  {
    //set the head to last node
    *List = temp1;       
 
    // save the next ptr in temp2 
    temp2= temp1->pNext; 
 
    // change next to privous
    temp1->pNext = temp3; 
    temp3 = temp1;
    temp1 = temp2;
  }
 
  return *List;
}

2. Delete a node in double linked list

void deleteNode(node *n)
{
  node *np = n->prev;
  node *nn = n->next;
  np->next = n->next;
  nn->prev = n->prev;
  delete n;
}

3. Sort a linked list

//sorting in descending order
struct node
{
  int value;
  node* NEXT;
}
//Assume HEAD pointer denotes the first 
//element in the linked list
//only change the values? don't have to 
//change the pointers
Sort( Node *Head)
{
  node* first,second,temp;
  first= Head;
  while(first!=null)
  {
    second=first->NEXT;
    while(second!=null)
    {
      if(first->value < second->value)
      {
        temp = new node();
        temp->value=first->value;
        first->value=second->value;
        second->value=temp->value;
        delete temp;
      }
      second=second->NEXT;
    }
    first=first->NEXT;
  }
}

4. Reverse a string

void ReverseString (char *String)
{
  char *Begin = String;
  char *End = String + strlen(String) - 1;
  char TempChar;
 
  while (Begin < End)
  {
    TempChar = *Begin;
    *Begin = *End;
    *End = TempChar;
    Begin++;
    End- -;
  }
}

5. Insert a node a sorted linked list

void sortedInsert(Node * head, Node* newNode)
{
  Node *current = head;
 
  // traverse the list until you find 
  //item bigger the new node value
  //   
  while ((current!= NULL) && 
         (current->data < newNode->data))
  {
    current = current->next;
  }
  //
  // insert the new node before the big item
  //
  newNode->next = current->next;
  current = newNode;
}

6. Covert a string to upper case

void ToUpper(char * S)
{
  while (*S!=0)
  {
    *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
    S++;
  }
}

7. Multiple a number by 7 without using * and + operator.

// mulitplied by 2 ^ 3 = 8
NewNum = Num << 3; 
 
// 8 – 1 = 7
NewNum = NewNum - Num;

8. Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.

00f19cc21bbb04e0ce62f044677569af007

9. Print a data from a binary tree - In-order(ascending)

//
// recursive version
//
 
Void PrintTree ( struct * node node )
{
  if ( node == NULL )
    return;
 
  PrintTree(node->left );
  printf("%d", node->data);
  PrintTree(node->right );
}

10. print integer using only putchar

//
//	recursive version
//
void PrintNum ( int Num )
{
  if ( Num == 0 )
    return;
  PrintNum ( Num / 10 );
  puthcar ( '0'+ Num % 10 );
}

11. Find the factorial of number

//
// recursive version
//
 
int Factorial( int Num )
{
  if ( num > 0 )
    return Num * Factorial ( Num –1 ); 
  else
    return 1;
}
 
//
// iterative version
//
 
int Factorial( int Num )
{
  int I
  int result = 1;
 
  for ( I= Num; I > 0; I- - )
  {
    result = result * I;
  }
 
  return result;
}

12. Generate Fib numbers:

// recursive version
int fib( n ) 
{
  if ( n < 2 )
    return 1;
  else
    return fib ( n-1 ) + fib ( n-2 );
}
 
//iterative version
int fib( n ) 
{
  int f1 =1, f2 = 1;
 
  if ( n < 2 )
    return 1;	
  for ( i = 1; i < N; i++)
  {
    f = f1 + f2;
    f1= f2;
    f = f1;
  }
  return f;
}

13. Write a function that finds the last instance of a character in a string

char *lastchar(char *String, char ch)
{
  char *pStr = NULL;
 
  // traverse the entire string
 
  while( * String ++ != NULL ) 
  {
    if( *String == ch ) 
    pStr = String;
  }
 
  return pStr;
}

14. Return Nth the node from the end of the linked list in one pass.

Node * GetNthNode ( Node* Head , int NthNode )
{
  Node * pNthNode = NULL;
  Node * pTempNode = NULL;
  int nCurrentElement = 0;
 
  for ( pTempNode = Head; 
        pTempNode != NULL; 
        pTempNode = pTempNode->pNext )
  {
    nCurrentElement++;			
    if ( nCurrentElement - NthNode == 0 )
    {
      pNthNode = Head;
    }
    else
    if ( nCurrentElement - NthNode > 0)
    {
      pNthNode = pNthNode ->pNext;
    }					
  }
  if (pNthNode )
  {
    return pNthNode;
  }
  else
    return NULL;
}

15. Counting set bits in a number.

//First version:
int CoutSetBits(int Num)
{
  for(int count=0; Num; Num >>= 1)
  {
    if (Num & 1) 
    count++;
  }
  return count;
}
 
//Optimized version:
int CoutSetBits(int Num)
{
  for(int count =0; Num; count++)
  {
    Num &= Num -1;
  }
}

Copyright
(c) 2004-2007 Satish Shetty

Popularity: 24%

You need to log on to convert this article into PDF

Related Blog Items

• Heap Overview
• Swapping variables without additional space
• C++ Advanced Tutorial - Lesson 9
• Binary Search Trees
• Data structures lectures

This entry was written by SatishShetty and posted on April 17, 2007 at 10:35 pm and filed under Algorithms, Data Structures in C/C++, Question Patterns. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.