My Blog: CPP

Showing posts with label CPP. Show all posts

Linked List Code for Beginners

#include "stdafx.h"
#include <iostream>

#ifndef _DSCLASS_H_
#define _DSCLASS_H_
class linkedlist{
private:
    struct node{
        int data;
        node *link;
    }*list;
public:
    linkedlist();
    ~linkedlist();
    //stack methods
    void push_item(int num);
    void pop_item();

    //queue methods
    void append_item(int num);
    void delete_item();

    //other insertion and deletion methods
    void insert_item(int pos,int num);
    void delete_item(int pos);

    //other operations
    void reverse();
    void merge(linkedlist l1, linkedlist l2);
    linkedlist operator +(linkedlist l1);

    void display();
};
linkedlist::linkedlist()
{
    list = NULL;
}
linkedlist::~linkedlist()
{
    //TODO: yet to be implemented
}

void linkedlist::insert_item(int pos, int num)
{
    
    if (pos<0)    return;
    printf("inserting %d at %dth position...\n", num, pos);
    
    node *newone;
    node *ptr = list;
    
    if (pos==0) 
    {
    newone    = new node();
    newone->data = num;
    newone->link = ptr;
    list = newone;
    return;
    }

    for (int i=0;i<pos-1;i++)
    {    
        if (ptr!=NULL) ptr=ptr->link;
        else return;
    }

    newone    = new node();
    newone->data = num;
        
    if(ptr->link!=NULL) newone->link = ptr->link;
    else newone->link = NULL;
    
    ptr->link =newone;


}

void linkedlist::delete_item(int pos)
{
if (list == NULL && pos<0) return;
printf("deleting item at %d position...\n",pos);
if (pos==0)//deleting the head
{
    node *temp = list;
    list = list->link;
    delete temp;
    return;
}

node *ptr = list;
node *temp;
for (int i=0;i<pos-1;i++)
{
    if (ptr!=NULL)
    {
        temp = ptr;
        ptr = ptr->link;
    }
    else return;
}

if (ptr->link!=NULL)
    temp->link = ptr->link;
else
    temp->link = NULL;

delete ptr;

}

void linkedlist::push_item(int num)
{
    printf("pushing %d..\n",num);
    if (list == NULL)
    {
        list = new node();
        list->data = num;
        list->link = NULL;
    }
    else
    {
        node* t = new node();
        t->data = num;
        t->link = list;
        list =t;
    }

}

void linkedlist::append_item(int num)
{
 printf("appending %d..\n",num);
 if (list == NULL)
 {
     list = new node();
     list->data = num;
     list->link = NULL;
 }
 else
 {
     node* par = list;
     while (par->link != NULL)
     {
        par=par->link;
     }
     //now we are at the end
     node *newone = new node();
     newone->data = num;
     newone->link = NULL;
     par->link = newone;
 }
}


void linkedlist::pop_item()
{
    printf("popping ..\n");
    if (list ==NULL)
    {
        printf("empty list\n");
        return;
    }
    else
    {
        node *del = list;
        list = list->link;
        delete del;
    }
}


void linkedlist::delete_item()
{
    printf("deleting ..\n");
    if (list==NULL)
    {
        printf("empty list\n");
        return;
    }
    else
    {
        node *del = list;
        node *temp = NULL;
        while(del->link!=NULL)
        {
            temp = del;
            del = del->link;
        }
        if (temp!=NULL) temp->link = NULL;
        delete del;
        if(del==list) list = NULL;
        
    }
}
void linkedlist::display()
{
    if (list==NULL)
        return;

    node *dis = list;
    char str[100]="";
    while (dis!=NULL)
    {
     sprintf(str,"%s%d->",str,dis->data);
     dis=dis->link;
    }
    printf("%sNULL\n",str);
}

void linkedlist::reverse()
{
    printf("reversing...");
    if (list == NULL && list->link == NULL) return;
    node *current = list;
    node *prev = NULL;
    node *next = NULL;
    while (current!=NULL)
    {
        next = current->link;
        current->link = prev;
        prev= current;
        current = next;
    }
    list = prev;

}

void linkedlist::merge(linkedlist l1, linkedlist l2)
{

    node *top = l1.list;
    while (top!=NULL)
    {
        append_item(top->data);
        top = top->link;
    }
    top = l2.list;
    while (top!=NULL)
    {
        append_item(top->data);
        top = top->link;
    }
    
}

linkedlist linkedlist:: operator +(linkedlist l1)
{
    linkedlist temp;

    node *top = this->list;
    while (top!=NULL)
    {
        temp.append_item(top->data);
        top = top->link;
    }

    top = l1.list;
    while (top!=NULL)
    {
        temp.append_item(top->data);
        top = top->link;
    }
return temp;
}
#endif

More Code Puzzles

1. Find Second Maximum in an array.

void findSecondMax(int a[])
{
    int max=a[0], secondmax=0;
    int size = sizeof(a)/sizeof(int);//doesnt work here
    for (int i=1;i<10;i++)
    {
        if (max < a[i])
        {    secondmax = max;
            max = a[i];
        }
        else
            if(secondmax<a[i])
            {
                secondmax = a[i];
            }
    }
    printf("second max is %d... max is %d",secondmax,max);

}

2. Remove the duplicates from an array.

void removeDuplicates()
{
    //int a[10]={1,1,1,3,3,5,5,6,6,6};
    int a[10]={1,2,2,3,4,5,5,6,7,8};
    int b[10];
    int size = 10;
    for(int i=0, j=1;j<size;j++) { if(a[i]==a[j])
        {
            for (int k=j;k<size-1;k++)
                a[k] = a[k+1];
            size--;
            j--;
        }
        else
        {
            i++;
        }
    }
    for (int j=0;j<size;j++)
    {
        printf("%d ", a[j]);
    }
}

Code Puzzles

1. Reverse a string

void reverseString()
{
    char r[12]="reversethis";
    char *start = r;
    char *end = r;
    while (*end!=0)end++;
    end--;
    while(start!=end)
    {
        //swap
        char t = start[0];
        *start = *end;
        *end = t;

        start++;
        end--;
    }
    printf("%s",r);
}

2. Traverse a matrix (m X n) spirally

void goSpiral()
{
    int arr[5][6] = {{1,2,3,4,5,50},
                    {6,7,8,9,10,100},
                    {11,12,13,14,15,150},
                    {16,17,18,19,20,200},
                    {21,22,23,24,25,250}
                    };

    int i=0, j=0,ilim=5,jlim=6;
    int till=0;
    int doing = 1;
    while(doing)
    {
        doing =0;
        for (i=till,j=till;j<jlim-till;j++)    doing = printf("%d ",arr[i][j]);
        if(doing==0) break;

        doing =0;
        for(j--,i++;i<ilim-till;i++)    doing = printf("%d ",arr[i][j]);
        if(doing==0) break;

        doing =0;
        for(j=jlim-till-2,i=ilim-till-1; j>=till+0; j--) doing = printf("%d ",arr[i][j]);
        if(doing==0) break;

        doing =0;
        for(j=till+0,i=ilim-till-2; i>=till+1; i--) doing = printf("%d ",arr[i][j]);
        if(doing==0) break;
        till++;
    }


}

3. Sort an array with just 2 types of elements

void sortJustTwoThings()
{
    int a[10]={1,0,1,0,1,0,1,0,1,0};
    int ptr1 = 0; //start of the array
    int ptr0 = 9; //end of the array
    while(ptr1 != ptr0)
    {
    if(a[ptr1]!=0)
    {
        while(a[ptr0]!=0) ptr0--;
        if(ptr1>ptr0) break;
        int t = a[ptr1];
        a[ptr1] = a[ptr0];
        a[ptr0] = t;
        ptr0--;
        if(ptr1==ptr0) break;
    }
    ptr1++;
    }

    for(int i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

}

4. Concatenate 2 strings and remove the overlap. For eg, if string1 is PRAVARABC and string 2 is ABCAKHYA resultant string should be PRAVARAKHYA.

void removeOverlap()
{
    char str1[]="ABCDE";
    char str2[]="DECDGEFGHIJK";
    char strout[500];
    char temp[20]="";
    //first copy the first string
    strcpy(strout,str1);
    int l = strlen(str1);
    int r = 0;
    bool overlap = false;
    for(int i=1;i<=strlen(str2);i++)
    {
        strncpy(temp,str2,i);
        char *s = strstr(str1,temp);
        if (s!=NULL)
        {
            r = l-(int)(s-str1);
            if (i==r)
            {
                for (int m=i; m<strlen(str2);m++)
                    strout[l++] = str2[m];

                strout[l]='\0';
                overlap = true;
                break;
            }
        }
    }

    if(!overlap)
        strcat(strout,str2);

    printf("%s",strout);
}

5. reverse the words in a sentence.

void reverseSentence()
{
    char sent[]= "sun rises in the east and sets in the west";
    int s = strlen(sent);
    for (int i=0; i<s/2; i++)
    {
        char c = sent[i];
        sent[i] = sent[s-1-i];
        sent[s-1-i] = c;
    }
    int cur =0;
    char *c = sent;
    int j =0;
    while (*c != '\0')
    {
        j =0;
        while (*c!=' ')
        {
            if (*c=='\0') break;
            j++;
            c++;
        }
        for(int k = cur, m=0; k<cur + j/2 ; k++,m++)
        {
            char l = sent[k];
            sent[k] = sent[cur+j-m-1];
            sent[cur+j-m-1] = l;
        }

        if (*c=='\0') break;
        c++;
        j++;
        cur += j;
    }

    printf("%s",sent);
}

QuickSort C Code

void testQuickSort()
{
static int a[8]={4,7,8,5,2,6,3,1};
    quickSort(a,0,7);

for(int i=0;i<8;i++)
        printf("%d",a[i]);

}
static void quickSort (int a[], int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    //  partition
    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quickSort(a, lo, j);
    if (i<hi) quickSort(a, i, hi);
}

Empty Constructor or No Constructor?

Here is a good article about the difference in having a class with and empty constructor and no constructor.

Got this article from this blog which also has a couple of interesting CPP articles.

Everything about binary trees

This site has solutions (source code) for problems involving Binary trees. It contains source code in C as well as Java. All the solutions are recursive solutions.

Binary trees are recursive data structures, any operations on the binary trees (traversals, finding depths, search,printing) can be done recursively.

non recursive solutions for a binary tree are much complicated. Pre-order traversal of binary tree can be done easily without using the recursion (using stacks), but post-order and in-order are complicated. post-order and in-order non-recursive traversals require an additional element (visited) added to the binary tree data structure.

These are the notes that I have taken while reading a lot of technical books. The below text is straight from my notes and is not in any particular sequence:

1. MFC maps are dictionaries with key and value pairs
2. CDocTemplate = Docs + Views + FrameWindows
3. Activation is finding class objects, there are three ways of activation:
1. Object Binding - CoGetClassObject
2. Creating an instance of the class - CoCreateInstance
3. Getting the persistant object - CoGetInstanceFromFile
Activation also means finding class objects, loading the COM DLL, and starting the Server process.

There are two types of Activation:
1. In-process activation
2. Out-of-process activation

4. IClassFactory will have createInstance() and LockServer() methods
5. CoCreateInstanceEx = CoGetClassObject() + CreateInstance() + Release()
6. A Moniker is a locator object which finds/creates objects. A Display name is the textual representation of a moniker.

7. Inner class method calling:

carPlane::XCar::GetMaxSpeed();

8. AddRef() -> InterlockedIncrement()

Release() -> InterlockedDecrement()

9. Aggregation is a technique of exposing a binary subcomponent to a client

10. IUnknown is the most inportant interface in COM. All interfaces should be derived from IUnknown. It has three methods:

1. QueryInterface()

2. AddRef()

3. Release()

11. Containment: Outer object just forwards the call to the inner object.

12. Function pointer: Its an address of the entry point of the function

int (*funcCompare)(const char *, const char *)

funcCompare = strcmp; //assign to another function

(*funcCompare)("hello","hell"); //calling

13. argc and argv: int main(int argc, char* argv[]);

14. structures and unions: members of union share same memory location.

15. strutures and classes: by default members of structure are public and that of class are private.

16. typedef float balance: balance can be used interchangeably with float.

17. friend functions are for access to private and protected members of the class.

Notes from my Notebook

7. Inner class method calling:
carPlane::XCar::GetMaxSpeed();
8. AddRef() -> InterlockedIncrement()
Release() -> InterlockedDecrement()
9. Aggregation is a technique of exposing a binary subcomponent to a client
10. IUnknown is the most inportant interface in COM. All interfaces should be derived from IUnknown.

My Blog