Data_structures_rev

Linked list reverse

struct node * reverse(struct node * head){

     struct node *prev = NULL,*cur,*next;

     cur = head;

     while(cur!=NULL){

         next=cur ->next;
         cur->next= prev;
         prev = cur ;
         cur = next;

     }

     //return head
     return prev;


}
---------------------------------------------------------------------

rotate a linked list


struct node * reverse(struct node * head , int rol){

     int i = 0;
     struct node * nhead, *ntail, *tail , *temphead = head;


     while (i < rol) {

        head = head ->next;

     }

     ntail = head;

     nhead = head ->next;

     while (head->next ! = NULL) {


         head = head - >next ;
     }

     head -> next = temphead;
     ntail->next = NULL;


     //return head
     return nhead ;


}
-----------------------------------------------------------------------------------

Add two linked lists

struct node * Add ( struct node * first, struct node * second ) {


   int sum = 0 ,carry = 0;

   struct node *new ,*head = null,prev;


   while(first != null || second != null) {


   sum = carry + (if(first)?first->data : 0) + (if(second)?second ->data:0);

   carry = if(sum > = 0) ? 1 : 0;

   sum = sum % 10;

   new = (struct node *) malloc (sizeof(struct node));

   if (!head)
   {
       new->data = sum;
       new->next = null;
       head = new;

   }
   else
   {
       new->data= sum;
       new->next = null;

       prev ->next= new
   }

   prev = new ;

   first = first->next;
   second = second -> next ;

 }

 if (carry > 0 ){

    new = (struct node *) malloc (sizeof(struct node));
    new->data = sum;
    new->next = null;
    prev ->next= new ;
 }
  return head;

}


--------------------------------------------------------------------------

Generic linked list


struct node {

   void *data;
   struct node * next;

};


void push( struct node **headref , void * data , int size){



   struct node *new;

   new = (struct node * ) malloc(sizeof(struct node ));
   new->data= malloc(size);

   new->data= *headref;

   for(i=0;i<size;i++)
      *(char *)(new->data + i ) =  *(char *)(data + i );


   *headref = new ;

}

------------------------------------------------------------------------------------------

Tree

struct node {

   int data;

   struct node *left;
   struct node *right;
};

properties of BT


1) Max number of nodes in a level = 2^(level - 1) .

2) Max number of nodes in a BT of given height = 2^(height) - 1.

3) For a given set of nodes N , the min height = log(N+1) (log to base 2 )

----------------------------------------------------------------------------------------------

Inorder traversal

left -> root -> right


void inorder(struct node *head){

     if (head == NULL)
         return;

     inorder(head->left);

     printf("%d ",head->data);

     inorder(head->right);

}


preorder

 root ->left->right



void preorder(struct node *head){

     if (head == NULL)
         return;

     printf("%d ",head->data);
     preorder(head->left);
     preorder(head->right);

}

postorder

left->right->root


void postorder(struct node *head){

     if (head == NULL)
         return;


     postorder(head->left);
     postorder(head->right);
     printf("%d ",head->data);

}
-----------------------------------------------------------------------------------------------------------------------

Reverse string using stack


struct Stack {

   int top;
   int capacity;
   char *array;

};


struct stack* Createstack(int len){

    struct Stack *stack = (Stack *) malloc (sizeof(struct stack));

	stack->top = -1;
	stack -> capacity = len + 1;

	stack->array = (char *)malloc(sizeof(char) * len);

	return stack;


}


int Isfull(struct Stack *stack){

     return stack->top==stack->capacity -1 ;

}


int Isempty(struct Stack *stack){

     return stack->top== -1 ;

}


void push(struct Stack *stack,char ch) {

     if(Isfull(stack))
	    return;

	 stack->array[++(stack->top)] = ch;

}

char pop(struct Stack *stack) {

   if(Isempty(stack))
	    return;

	return  stack->array[(stack->top)--] ;

}
void reverse(char str[]) {


   int len = strlen(str);

   struct node *stack = Createstack(str);

   for(i = 0 ; i< len ; i++)
       push(stack,str[i]);

   for(i =0 ;i <len ; i ++)
       str[i]=pop(stack);

}
---------------------------------------------------------------------------------------------------
reverse string



void swap(char *in1,char * in2){

    char temp = *in1;

	*in1 = *in2;

	*in2 = temp;


}

void reverse(char in[]){

   int len = strlen(in);

   for(i=0 ; i< len/2 ; i++)
       swap(&in[i],&in[len-i-1]);


}

--------------------------------------------------------------------------------------------------------

Queue using two stacks


struct stack {

   int data;
   struct stack *next;

};


struct queue {

   struct stack *stack1;
   struct stack *stack2;

};


void push(struct stack **top, int data ){

   struct stack * node = (struct stack *) malloc (sizeof(struct stack));
   node->data = data;
   node->next=*top;
   *top = node;

}

int pop(struct stack **top) {

    struct stack *temp = *top;
	int data = temp->data;
	*top= temp->next;
	free(temp);
	return data;
}


void enqueue (struct queue *q, int data ){

     push(&q->stack1,data);


}

int dequeue(struct queue *q) {

     int x ;
    if(q->stack1 == NULL || q->stack2 == NULL) {

	    printf("Queue is empty ");
		return NULL;
	}

	 if(q->stack2 == NULL) {

		 while(q->stack1 ! = NULL){

		    x = pop(&q->stack1);
			push(&q->stack2,x);

		 }

	 }

     x = pop(&q->stack2);
	 return x ;
}