Archive for March 5, 2012

Priority Queue

Posted: March 5, 2012 in Uncategorized

QUEUE.CPP

#include "queue.h"
Node::Node(int data, Node* next){
  _data = data;
  _next = next;
}
Queue::Queue(){
  _head = (Node*)0;
}
Queue::~Queue(){
  while(!isEmpty()) remove();
}
int Queue::remove(int pos){
  int ret = 0;
  Node* cur = _head;
  Node* prev = (Node*)0;
  bool flag = false;
  int i = 1;
  while(cur && i != pos){
    prev = cur;
    cur = cur->_next;
    i++;
  }
  if (i == pos && cur){
    ret = cur->_data;
    if (!prev){
      _head = _head->_next;
      delete cur;
    }
    else{
      cur = cur->_next;
      delete prev->_next;
      prev->_next = cur;
    }
  }
  return ret;
}
bool Queue::add(int val, int pos){
  Node* cur = _head;
  Node* prev = (Node*)0;
  bool flag = false;
  int i = 0;
  while(cur && i != pos){
    prev = cur;
    cur = cur->_next;
    i++;
  }
  if(pos == -1) pos = i;
  if(i == pos){
    if (i == 0){
      _head = new Node(val, _head);
      flag = true;
    }
    else{
      prev->_next = new Node(val, cur);
      flag = true;
    }
  }
  return flag;
}
bool Queue::isEmpty(){
  return !_head;
}

QUEUE.H

#ifndef __TV_QUEUE_H__
#define __TV_QUEUE_H__

class Queue;

class Node{
  int _data;
  Node* _next;
  Node(int data, Node* next = (Node*)0);
  friend class Queue;
};

class Queue{
  Node* _head;
public:
  Queue();
  virtual ~Queue();
  int remove(int pos=1);
  bool add(int, int pos = -1);
  bool isEmpty();
};

QUEMAIN.CPP

#include <iostream>
using namespace std;
#include "queue.h"
int main(){
  Queue Q;
  for(int i = 10;i<101;i+=10){
    Q.add(i);
  }
  cout<<"Removed the "<<Q.remove(1)<<endl;
  cout << "append at 9th is: ";
  cout<<(Q.add(2222, 9)?"SUCCESS":"FAIL")<<endl;
  while(!Q.isEmpty()){
    cout<<Q.remove()<<endl;
  }
  getchar();
  return 0;
}

Sorted Queue

Posted: March 5, 2012 in OOP344

QUEUE.H

#ifndef __TV_QUEUE_H__
#define __TV_QUEUE_H__

class Queue;

class Node{
  int _data;
  Node* _next;
  Node(int data, Node* next = (Node*)0);
  friend class Queue;
};

class Queue{
  Node* _head;
public:
  Queue();
  virtual ~Queue();
  int remove();
  void add(int val);
  bool isEmpty();
};

#endif

QUEUE.CPP

#include "queue.h"

Node::Node(int data, Node* next){
  _data = data;
  _next = next;
}
Queue::Queue(){
  _head = (Node*)0;
}
Queue::~Queue(){
  while(!isEmpty()) remove();
}
int Queue::remove(){
  int ret = _head->_data;
  Node* toDel = _head;
  _head = _head->_next;
  delete toDel;
  return ret;
}
void Queue::add(int val){
  Node* cur = _head;
  Node* prev = cur;
  bool done = false;
  while(!done){
    if(!_head || _head->_data >= val){
      _head = new Node(val, _head);
      done = true;
    }
    else if(cur->_data >= val){
      prev->_next = new Node(val, cur);
      done = true;
    }
    else if(!cur->_next){
      cur->_next = new Node(val);
      done = true;
    }
    else {
      prev = cur;
      cur = cur->_next;
    }
  }
}
bool Queue::isEmpty(){
  return !_head;
}

QUEUEMAIN.CPP

#include <iostream>
using namespace std;
#include "queue.h"
#include <ctime>

int main(){
  Queue Q;
  for(int i = 1; i<25 ;i++){
    Q.add(rand()%10000+1);
  }
  while(!Q.isEmpty()){
    cout<<Q.remove()<<endl;
  }
  return 0;
}

CIRCULAR LEFT SHIFT

Posted: March 5, 2012 in Uncategorized

QUESTION

A circular left shift removes the bits from left and inserts them to right side of the integer:

1001 1100  after one circular shift to left will be:  0011 1001

void CirShiftLeft(unsigned int* val, int NoOfShifts);

Example (assuming int size is 2 bytes):

unsigned int a = 0xB52A; /*1011010100101010 */
CirShiftLeft(&a, 3);
Printf(“%X”, a);
Output:

A955    that is: 1010100101010101

void CirShiftLeft(unsigned int* val, int NoOfShifts){
  char bin[80]="";
  int i = 0;
  int tmp = *val;
  while(tmp){
    bin[i++] = (tmp % 2) ;
    tmp /= 2;
  }
  for(int j = i - 1 - NoOfShifts; j >= 0 ; j--){
    tmp = tmp * 2 + bin[j];
  }
  for(int j = i-1; j > i - 1 - NoOfShifts  ; j--){
    tmp = tmp * 2 + bin[j];
  }
  *val = (unsigned int)tmp;
}