Google Ads

Thursday, December 3, 2009

PROGRAMMING MODEL

WINDOWS PROGRAMMING MODEL



Message processing:


 When writing MS – DOS program the only required function is main.

 When windows operating system launches a program, it calls WinMain function.

 Its task is to create the application’s main window which has its own code to process messages that windows sends to it.

 Windows based program processes user input via messages from the operating system.

 For example
 WM_CREATE message is sent when a window is being created.
 WM_LBUTTONDOWN message is sent when the user presses the left mouse button.
 WM_CHAR message is sent when the user types a character.
 WM_CLOSE message is sent when the user closes the window.

Windows Graphics Device Interface:

 Windows provides a layer of abstraction called graphics device interface.

 Instead of addressing the hardware, program calls the GDI functions that reference a data structure called a device context.

 Windows maps the device context structure to a physical device and issues appropriate input / output instructions.

Resource Based Programming:

 In windows the data is stored in a resource file using a number of established format.

 The linker combines the binary resource file with the C++ compiler’s output to generate an executable program.

 Resource files can include bitmaps, icons, menu definitions, dialog based layouts and strings.

Dynamic Link Libraries:

 Windows allows dynamic linking, means that specially constructed libraries can be loaded and linked at runtime.

 Multiple applications can share dynamic link libraries which saves memory and disk space.

 DLL increases program modularity – since it can be compiled and tested separately.

AppWizard:

 Is a code generator that creates a workspace frame of a windows application with features, class names and source code file names.

ClassWizard:

 Is a program that’s accessible from visual C++ view menu.





Application Framework:

 Is an integrated collection of object oriented software components that offers all that needed for a generic application.

 It defines the structure of the program.

 By convention, MFC library class names begin with the letter C.

View:
 A view is an ordinary window that the user can size, move and close in the same way as any other windows – based application window.
 From the programmer’s angle, a view is a C++ object of a class derived from the MFC library CView class.

Single Document Interface (SDI):
 An SDI application has only one window, only one document can be loaded at a time. Notepad is an example for single document interface.

Multiple Document Interface (MDI):
 An MDI application has multiple child windows, each corresponds to an individual document. Microsoft word is an example for MDI.

VIEW WINDOW



DRAWING INSIDE THE VIEW WINDOW

OnDraw member function:

Ø Is a virtual member function of the CView class that the application framework calls every time the view window needs to be repainted.

Windows device context:

Ø Windows doesn’t allow direct access to the display hardware but communicates through an abstraction called a “device context” that is associated with the window.

Ø In the MFC library, the device context is a C++ object of class CDC that is passed as a parameter to OnDraw function.

Steps to build the application:

1.Run AppWizard to generate SDI application source code.

Ø Choose New from visual C++ File menu & then click Projects tab in the resulting New dialog box.

Ø Make sure that MFC AppWizard (exe) is selected and specify the path in the Location textbox finally specify Project Name and click OK.

Ø In the sequence of AppWizard screens select the following:

v Single Document Interface.

v Accept the default in the next four screens.

v In the last screen check the project name, class name and click Finish.

v It displays the New Project Information dialog box, click OK button.

Ø The AppWizard starts to create application’s subdirectory and a series of files in that subdirectory.


FILE

DESCRIPTION

Filename.dsp

A project file that allows Visual C++ to build the application.

Filename.dsw

A workspace file that contains a single entry for the .dsp file.

Filename.rc

An ASCII resource script file.

filenameView.cpp

A view class implementation file that contains class member functions.

filenameView.h

A view class header file that contains the class declaration.

Filename.opt

A binary file that tells Visual C++ which files are open for this project and how the windows are arranged. (not created until project is saved.

Readme.txt

A text file that explains the purpose of generated files.

Resource.h

A header file that contains #define constant declaration.



2. Edit the OnDraw function in the filenameView.cpp:

Ø Find the AppWizard generated OnDraw function in View.cpp and add the following code.

void CfilenameView::OnDraw(CDC* pDC)

{

CfilenameDoc* pDoc = GetDocument();

ASSERT_VALID(pDoc);

pDC->TextOut(0,0,”Hello World!”); // prints in default font & //size, top left corner.

pDC->SelectStockObject(GRAY_BRUSH); // selects a brush for //the circle interior.

pDC->Ellipse(CRect(0,20,100,120)); // draws a gray circle 100 //units in diameter.

}

3. Compile & test the file.




PROGRAM TO HANDLE BASIC EVENTS

PROGRAM TO HANDLE BASIC EVENTS

MESSAGE MAP,
SAVING THE VIEW’S STATE,
INITIALIZING A VIEW CLASS DATA MEMBERS.



Message map:

 When the user presses the left mouse button in a view window, windows sends a message “WM_LBUTTONDOWN” to that window.

 If the program needs to take an action in response to WM_LBUTTONDOWN, view class must have a member function that looks like:

Void CMyView::OnLButtonDown(UINT nFlags, CPoint point)
{
// event processing code here
}

 Class header file must also have the prototype:

afx_msg void OnLButtonDown (UINT nFlags, CPoint point);

the afx_msg is a “no-op” that alerts that this is a prototype for a message map function.

Saving the View’s state:

 The view’s OnDraw function draws an image based on the view’s current state and user actions can alter that state.

 Two view class members used often are m_rectEllipse and m_nColor.

 m_rectEllipse is an object of class CRect, which holds the current bounding rectangle of an ellipse.

 m_nColor is an integer that holds the current ellipse color value.

 By convention, MFC library nonstatic class data member names begin with m_.

Initializing a view class data member:

 The most efficient place to initialize a class data member is in the constructor:

CMyView::CMyView:m_rectEllipse(0,0,200,200)
{
………..
}

Steps to create the application:

1. Run AppWizard to create second application.
2. Add the m_rectEllipse and m_nColor data members to secondView.
 In the workspace window set to ClassView, right click the secondView class, select Add Member variable and then insert the data members:
private:
CRect m_rectEllipse;
int m_nColor;
3. Use ClassWizard to add a secondView class message handles.
 Choose ClassWizard by right-click on the source window.
 Select
Class Name: secondView
Object ID: SecondView
Messages: WM_LBUTTONDOWN (double-click)

the OnLButtonDown function name should appear in the Member functions list box.

4. Edit the OnLButtonDown code in secondView.cpp.

 Click the edit code button in the ClassWizard and the code here:

void secondView::OnLButtonDown (UINT nFlags, CPoint point)
{
if (m_rectEllipse.PtInRect(point))
{
if (m_nColor == GRAY_BRUSH)
{
m_nColor = WHITE_BRUSH;
}
else
{
m_nColor = GRAY_BRUSH;
}
InvalidateRect (m_rectEllipse);
}
}







5. Edit the constructor and the OnDraw function in secondView class.

secondView :: secondView() : m_rectEllipse(0,0,200,200)
{
m_nColor = GRAY_BRUSH;
}

void secondView :: OnDraw (CDC* pDC)
{
pDC -> SelectStockObject (m_nColor);
pDC -> Ellipse (m_rectEllipse);
}

6. Build and run the program.

INTERFACE OBJECTS



GRAPHICS DEVICE INTERFACE OBJECTS



1. Run AppWizard to generate the third project.

2. Use ClassWizard to override the OnPrepareDC function in the thirdView class.

void thirdView :: OnPrepareDC (CDC* pDC, CPrintInfo* pInfo)

{

pDC -> SetMapMode (MM_ANISOTROPHIC);

pDC -> SetWindowExt (1440, 1440);

pDC -> SetViewPortExt (

pDC -> GetDeviceCaps (LOGPIXELSX),

pDC -> GetDeviceCaps (LOGPIXELSY));

}

3. Add a private ShowFont helper function to the view class. (thirdView.h)

private:

void ShowFont (CDC* pDC, int& nPos, int nPoints);

then add the function in thirdView.cpp

void thirdView :: ShowFont (CDC* pDC, int& nPos, int nPoints)

{

TEXTMETRIC tm;

CFont fontText;

CString strText;

CSize sizeText;

fontText.CreateFont (nPoints * 20, 0,0,0,400,FALSE,FALSE,0,

ANSI_CHARSET, OUT_DEFAULT_PRECIS,

CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH | FF_SWISS, “Arial”);

CFont* pOldFont = (CFont* ) pDC -> SelectObject (&fontText);

pDC -> GetTextMetrics (&tm);

TRACE (“points = %d, tmHeight = %d, tmExternalLeading = %d”,”tmExternalLeading = %d\n”, nPoints, tm.tmHeight, tm.tmInternalLeading, tm.tmExternalLeading);

strText.Format(“This is %d – point Arial”,nPoints);

sizeText = pDC -> GetTextExtent (strText);

TRACE(“string width = %d, string height = %d\n”, sizeText.cx, sizeText.cy);

pDC -> TextOut (0,nPos, strText);

pDC -> SelectObject (pOldFont);

nPos -= tm.tmHeight + tm.tmExternalLeading;

}

4. Edit the OnDraw function in thirdView.cpp

void thirdView :: OnDraw (CDC* pDC)

{

int nPosition = 0;

for ( int i = 6; i <= 24; i +=2)

{

ShowFont (pDC, nPosition, i);

}

TRACE (“LOGPIXEL = %d, LOGPIXEL = %d\n”,

pDC -> GetDeviceCaps (LOGPIXELSX),

pDC -> GetDeviceCaps (LOGPIXELSY));

TRACE (“HORZSIZE = %d, VERTSIZE = %d\n”,

pDC -> GetDeviceCaps (HORZSIZE),

pDC -> GetDeviceCaps (VERTSIZE));

TRACE (“HORZRES = %d, VERTRES = %d\n’,

pDC -> GetDeviceCaps ( HORZRES),

pDC -> GetDeviceCaps (VERTRES));

}

5. Build and run the program.


VIEW ARCHITECTURE

DOCUMENT – VIEW ARCHITECTURE


1. Run the AppWizard to generate a project called sixth.
2. Use the resource editor to edit the application’s main menu.
- click on the Resource View tab in the workspace window.
- edit the IDR_MAINFRAME menu resource to add a separator and a Clear Document item to the Edit menu.
- add a transfer menu and then define the following items:
Menu Caption Command ID

Edit Clear & Document ID_EDIT_CLEAR_ALL

Transfer &Get Data from Document\tF2 ID_TRANSFER_GETDATA

Transfer &Store Data from Document\tF3 ID_TRANSFER_STOREDATA
3. Use the resource editor to add keyboard accelerators.
Accelerator ID Key
ID_TRANSFER_GETDATA VK_F2
ID_TRANSFER_STOREDATA VK_F3
4. Use the ClassWizard to add the view class command and update command UI message handlers.
- add the following member functions to sixthView class:
Object ID Message Member Function
ID_TRANSFER_GETDATA COMMAND OnTransferGetData
ID_TRANSFER_STOREDATA COMMAND OnTransferStoreData
ID_TRANSFER_STOREDATA UPDATE_COMMAND_UI
OnUpdateTransferStoreData
5. Use ClassWizard to add the document class command and update command UI message handlers.
- add the following member functions to sixthDoc class.
ObjectID Message Member Function
ID_EDIT_CLEAR_ALL COMMAND OnEditClearDocument
ID_EDIT_CLEAR_ALL UPDATE_COMMAND_UI
OnUpdateEditClearDocument

6. Add a CString data member to the sixthDoc class.
- edit the sixthDoc.h file
public:
CString m_strText;
7. Edit the document class member functions in sixthDoc.cpp
BOOL sixthDoc :: OnNewDocument()
{
if (!CDocument :: OnNewDocument())
return FALSE;
m_strText = “Hello (from sixthDoc :: OnNewDocument)”;
return TRUE;
}

void sixthDoc :: OnEditClearDocument()
{
m_strText.Empty();
}


void sixthDoc :: OnUpdateEditClearDocument(CCmdUI* pCmdUI)
{
pCmdUI -> Enable (!m_strText.IsEmpty());
}

8. Add a CRichEditCtrl data member to the sixthView class.
- edit the sixthView.h class
public:
CRichEditCtrl m_rich;
9. Use the ClassWizard to map the WM_CREATE and WM_SIZE messages in the sixthView class.

int sixthView :: OnCreate (LPCREATESTRUCT lpCreateStruct)
{
CRect rect (0,0,0,0);
if (CView :: OnCreate (lpCreateStruct) == -1)
return -1;
m_rich.Create (ES_AUTOVSCROLL | ES_MULTILINE |
ES_WANTRETURN | WS_CHILD | WS_VISIBLE |
WS_VSCROLL ,rect,this,1);
return 0;
}

void sixthView :: OnSize (UINT nType, int cx, int cy)
{
CRect rect;
CView OnSize (nType, cx, cy);
GetClientRect (rect);
m_rich.SetWindowPos (&wndTop, 0, 0, rect.right – rect.left,
rect.bottom – rect.top, SWP_SHOWWINDOW);
}
10. Edit the menu command handler functions in sixthView.cpp

void sixthView :: OnTransferGetData()
{
sixthDoc* pDoc = GetDocument();
m_rich.SetWindowText (pDoc -> m_strText);
m_rich.SetModify (FALSE);
}

void sixthView :: OnTransferStoreData()
{
sixthDoc* pDoc = GetDocument();
m_rich.GetWindowText (pDoc -> m_strText);
m_rich.SetModify (FALSE);
}

void sixthView :: OnUpdateTransferStroeData (CCmdUI* pCmdUI)
{
pCmdUI -> Enable (m_rich.GetModify());
}

11. Build and Test the sixth application.

TOOL BARS



TOOL BARS


  1. Run AppWizard to generate toolbar application.
  2. Use the resource editor to edit the application’s main menu.

- In resource view, double – click on IDR_MAINFRAME.

- create a new menu called draw with the following names & command ID’s

Menu Caption Command ID

Draw Circle ID_DRAW_CIRCLE

Draw Square ID_DRAW_SQUARE

Draw Pattern ID_DRAW_PATTERN

3. Use ClassWizard to add toolbarView class message handlers.

Object ID Message Member Function

ID_DRAW_CIRCLE COMMAND OnDrawCircle

ID_DRAW_CIRCLE UPDATE_COMMAND_UI OnUpdateDrawCircle

ID_DRAW_PATTERN COMMAND OnDrawPattern

ID_DRAW_PATTERN UPDATE_COMMAND_UI OnUpdateDrawPattern

ID_DRAW_SQUARE COMMAND OnDrawSquare

ID_DRAW_SQUARE UPDATE_COMMAND_UI OnUpdateDrawSquare

4. Add three data members to the toolbarView class.

- edit the file toolbarView.h

private:

CRect m_rect;

BOOL m_bCircle;

BOOL m_bPattern;

5. Edit the toolbarView.cpp file

CtoolbarView :: CtoolbarView() : m_rect (0,0,100,100)

{

m_bCircle = TRUE;

m_bPattern = FALSE;

}

Edit the OnDraw function.

void CtoolbarView :: OnDraw (CDC* pDC)

{

CBrush brush(HS_BDIAGONAL, 0L);

if (m_bPattern)

pDC -> SelectObject (&brush);

else

pDC -> SelectStockObject (WHITE_BRUSH);

if (m_bCircle)

pDC -> Ellipse (m_rect);

else

pDC -> Rectangle (m_rect);

pDC -> SelectStockObject (WHITE_BRUSH);

}

Edit the OnDrawCircle, OnDrawSquare and OnDrawPattern function.

void CtoolbarView :: OnDrawCircle()

{

m_bCircle = TRUE;

m_rect += CPoint (25,25);

InvalidateRect (m_rect);

}

void CtoolbarView :: OnDrawSquare()

{

m_bCircle = FALSE;

m_rect += CPoint (25,25);

InvalidateRect (m_rect);

}

void CtoolbarView :: OnDrawPattern()

{

m_bPattern ^= 1;

}

Edit the OnUpdateDrawCircle, OnUpdateDrawSquare and OnUpdateDrawPattern function

void CtoolbarView :: OnUpdateDrawCircle (CCmdUI* pCmdUI)

{

pCmdUI -> Enable (!m-bCircle);

}

void CtoolbarView :: OnUpdateDrawSquare (CCmdUI* pCmdUI)

{

pCmdUI -> Enable (m_bCircle);

}

void CtoolbarView :: OnUpdateDrawPattern (CCmdUI* pCmdUI)

{

pCmdUI -> SetCheck (m_bPattern);

}

8. Build and Test the application.


STATUS BARS

STATUS BARS




1. Run AppWizard to generate statusbar application.

1. Use the string editor to edit the application’s string table resource.
- double click on the string table icon in the string table folder on the ResourceView page to bring up the string editor.
- then double click on the empty entry at the end of the list.
- assign the ID and string value in the dialog as:

String ID String Caption
ID_INDICATOR_LEFT LEFT
ID_INDICATOR_RIGHT RIGHT
3. Use Visual C++ to edit the application’s symbols.
- choose Resource symbols from the View menu.
- add the new status bar identifier, ID_MY_STATUS_BAR and accept the default value.

4. Use ClassWizard to add View menu command handlers in the class CMainFrame.
- add the following message handlers

Object ID Message Member Function
ID_VIEW_STATUS_BAR COMMAND OnViewStatusBar
ID_VIEW_STATUS_BAR UPDATECOMMAND_UI
OnUpdateViewStatusBar
5. Add the function prototypes to MainFrm.h file

afx_msg void OnUpdateLeft (CCmdUI* pCmdUI);
afx_msg void OnUpdateRight (CCmdUI* pCmdUI);

add the message handler statements inside the AFX_MSG brackets so that ClassWizard will access and edit the code later.

6. Edit the MainFrm.cpp file
- replace the original indicators array with the following code
static UINT indicators[] =
{
ID_SEPARATOR,
ID_SEPARATOR,
ID_INDICATOR_LEFT,
ID_INDICATOR_RIGHT< }; - edit the OnCreate member function if (!m_wndStatusBar.Create (this, WS_CHILD | WS_VISIBLE | CBRS_BOTTOM | ID_MY_STATUS_BAR) || !m_wndStatusBar.SetIndicators (indicators, sizeof (indicators) / sizeof(UINT))); { TRACE0(“Failed to create status bar\n”); return -1; } Add the following message map entries for the class CMainFrame. ON_UPDATE_COMMAND_UI (ID_INDICATOR_LEFT, OnUpdateLeft) ON_UPDATE_COMMAND_UI (ID_INDICATOR_RIGHT, OnUpdateRight) Add the following CMainFrame member function that updates the two status indicators. void CMainFrame :: OnUpdateLeft (CCmdUI* pCmdUI) { pCmdUI -> Enable (::GetKeyState (VK_LBUTTON) <> Enable (::GetKeyState (VK_RBUTTON) <0);> SetCheck(m_wndStatusBar.GetStyle() &
WS_VISIBLE) != 0);
}
8. Edit the OnDraw function in statusView.cpp
void CstatusView :: OnDraw (CDC* pDC)
{
pDC -> TextOut (0,0, “Watch the status bar”);
}
9. Add a WM_MOUSEMOVE handler in the CstatusView class
void CstatusView :: OnMouseMove (UINT nFlags, CPoint point)
{
CString str;
CMainFrame* pFrame = (CMainFrame*) AfxGetApp() ->m_pMainWnd;
CStatusBar* pStatus = &pFrame -> m_wndStatusBar;
if (pStatus){
str.Format (“X =%d”, point.x);
pStatus -> SetPaneText (0, str);
str.Format (“Y=%d”, point.y);
pStatus -> SetPaneText(1,str);
}
}

Finally add the statement

#include “MainFrm.h”

near the top of the file statusView.cpp

9. Build and test the application.

INTERFACE WITH DATABASE



INTERFACE WITH DATABASE

1. Create a database named stud in MS Access.

2. Run the ODBC Data Source administrator to install the stud data source.

- click on the ODBC icon in the windows control panel.

- click the Add button and choose Microsoft Access Driver in the Add Data Source dialog box.

- select the database by clicking the Select button and then press OK.

3. Run AppWizard to create student application.


Thursday, September 24, 2009

INSERTION SORT

INSERTION SORT



Program

#include"stdio.h"
#include"conio.h"
int i,j,a[20],n;

void main()
{
clrscr();
printf("\n INSERTION SORT \n");
printf("Enter The Number Of Elements :");
scanf("%d",&n);
for(i=0;i < n;i++)
scanf("%d",&a[i]);
insert(a,n);
printf("The Sorted List Is :\n");
for(i=0;i < n;i++)
printf("%d\n",a[i]);
getch();
}

insert(a,n)
int a[],n;
{
int i,k,y;
for(k=1;k < n;k++)
{
y=a[k];
for(i=k-1;i > =0 &&y < a[i];i--)
a[i+1]=a[i];
a[i+1]=y;
}
return;
}


OUTPUT


INSERTION SORT
Enter The Number Of Elements :5
4
2
8
5
3
The Sorted List Is :
2
3
4
5
8












Friday, September 4, 2009

Index DS using C++

Data Structures Using C++


POLYNOMIAL DIFFERENTIATION

PRINTING NODE DETAILS IN LEVEL WISE

MATRIX USING BINARY SEARCH

KNAPSACK PROBLEM

BINARY TREE TRAVERSAL

TRAVELLING SALESMAN PROBLEM

KRUSKAL ALGORITHM

RED BLACK TREES

MINIMUM SPANNING TREE

POLYNOMIAL DIFFERENTIATION

POLYNOMIAL DIFFERENTIATION



#include”iostream.h”
#include”conio.h”
struct node
{
int coeff;
int pow;
struct node *next;
};

class polydiff
{
struct node *head;
struct node *i;
public:
void creation();
void display();
void differen();
polydiff();
};
polydiff::polydiff()
{
head=NULL;
}

void polydiff::creation()
{
char res;
struct node *temp;
head=new struct node();
cout<<"Enter the 1st term in the polynomial with coeff & Power";
cin>>head->coeff;
cin>>head->pow;
head->next=NULL;
cout<<"do u want to add another node\n";
cin>>res;
while(res=='y'res=='Y')
{
temp=new struct node();
cout<<"Enter coeff & power\n";
cin>>temp->coeff;
cin>>temp->pow;
temp->next=NULL;
for(i=head;i->next!=NULL;i=i->next);
i->next=temp;
cout<<"Interested in adding another node\n";
cin>>res;
}
}

void polydiff::display()
{
for(i=head;i!=NULL;i=i->next)
{
if(i->pow!=0)
{
cout<coeff<<"X^";
cout<pow<<"+";
}
else
cout<coeff;
}
}

void polydiff::differen()
{
for(i=head;i!=NULL;i=i->next)
{
if(i->pow!=0)
{
i->coeff=i->coeff*i->pow;
i->pow--;
}
else
{
i->coeff=0;
i->pow=0;
}
}
}

void main()
{
clrscr();
polydiff p;
printf(“POLYNOMIAL DIFFERENTIATION\n”);
p.creation();
p.display();
cout<<"\n\nDifferentiation is\n";
p.differen();
p.display();
getch();
}



OUTPUT:


POLYNOMIAL DIFFERENTIATION

Enter the 1st term in the polynomial with coeff & Power
25 4
do u want to add another node
y
Enter coeff & power
12 3
Interested in adding another node
y
Enter coeff & power
1 1
Interested in adding another node
y
Enter coeff & power
10
0
Interested in adding another node
n
25X^4+12X^3+1X^1+10

Differentiation is
100X^3+36X^2+10






PRINTING NODE DETAILS IN LEVEL WISE

PRINTING NODE DETAILS IN LEVEL WISE


#include”iostream.h”
#include”conio.h”
#include”malloc.h”
#include”math.h”
#include”process.h”
class binary
{
private:
struct node
{
int data;
node *left,*right;
}*root;
node *queue[30];
int rear,front,size;
public:
void insert(node *);
struct node *remove();
int qnotempty();
void create();
void traverse();
};

void binary::insert(node *temp)
{
queue[rear++]=temp;
}

struct binary::node *binary::remove()
{
node *temp=queue[front];
front++;
if(front==rear)
{
front=rear=0;
}
return temp;
}

int binary::qnotempty()
{
if(front==0 && rear==0)
{
return(0);
}
else
{
return(1);
}
}

void binary::create()
{
int i=1;
node *new1, *temp;
root=NULL;
rear=front=0;
cout<<"Enter the size of the tree\t";
cin>>size;
new1=new node();
new1->left=new1->right=NULL;
cout<<"Enter the"< cin>>new1->data;
root=new1;
insert(root);
//insert(root);
for(i=2;i<=size;i++)
{
temp=remove();
new1= new node();
new1->left=new1->right=NULL;
cout<<"Enter the "< cin>>new1->data;
if(temp->left==NULL)
{
temp->left=new1;
}
else
if(temp->right==NULL)
{
temp->right=new1;
}
insert(new1);
//insert(new1);
}
}
void binary::traverse()
{
int level=0;
int count=0;
rear=front=0;
node *temp=root;
insert(temp);
cout<<"\nLevel"< do
{
temp=remove();
if(temp!=NULL)
{
cout<<"\t"<data;
insert(temp->left);
//insert(temp->right);
}
count++;
if(pow(2,level)==count && pow(2,level+1) <= size)
{
level++;
cout< count=0;
}
}while(qnotempty()==1);
}

void main()
{
int ch;
binary b;
clrscr();
for(;;)
{
cout<<"\n\n1.Create\n2.LevelWise Traverse\n3.Exit\n";
cout<<"Enter choice\n";
cin>>ch;
switch(ch)
{
case 1:
b.create();
break;
case 2:
b.traverse();
break;
case 3:
exit(0);
}
}
}






OUTPUT:

PRINTING NODE DETAILS IN LEVEL WISE



1.Create
2.LevelWise Traverse
3.Exit
Enter choice
1
Enter the size of the tree 6
Enter the1Element 34
Enter the 2Element 54
Enter the 3Element 67
Enter the 4Element 23
Enter the 5Element 43
Enter the 6Element 99


1.Create
2.LevelWise Traverse
3.Exit
Enter choice
2

Level0 34

Level1 54 67

Level2 23 43 99


1.Create
2.LevelWise Traverse
3.Exit
Enter choice
3

MATRIX USING BINARY SEARCH

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH



#include”iostream.h”
#include”conio.h”
class matrix
{
int a[50][50],m,n,i,j,low,mid,high,h;
public:
void getdata();
void putdata();
void binsearch(int);
};

void matrix::getdata()
{
cout<<"\nEnter the row & Column"< cin>>m>>n;
cout<<"Enter the elements in increasing order\n";
if(m==n)
for(i=0;i for(j=0;j cin>>a[i][j];
}

void matrix::putdata()
{
cout<<"\nMatrix is\n\n";
for(i=0;i {
for(j=0;j {
cout< }
cout< }
}

void matrix::binsearch(int s)
{
for(i=0;i {
low=1;
high=m;
while(low<=high)
{
mid=(low+high)/2;
if(s==a[i][mid-1])
{
cout<<"\nElement is in the list\n"< cout<<"Position of the element\t"<<++i<<"\t"< h=1;
break;
}
else if(s high=mid-1;
else
low=mid+1;
}
}
if(h==0)
cout<<"\nElement not in the list";
}

void main()
{
clrscr();
int search;
matrix m;
m.getdata();
m.putdata();
cout<<"\nEnter the element to be searched\t";
cin>>search;
m.binsearch(search);
getch();
}
















OUTPUT:

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH

Enter the row & Column
3
3
Enter the elements in increasing order
10
20
30
40
50
60
70
80
90

Matrix is

10 20 30
40 50 60
70 80 90

Enter the element to be searched 50

Element is in the list

Position of the element 2 2

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH

Enter the row & Column
2
2
Enter the elements in increasing order
90
80
70
60

Matrix is

90 80
70 60

Enter the element to be searched -10

Element not in the list

KNAPSACK PROBLEM

KNAPSACK PROBLEM


#include”iostream.h”
#include”conio.h”
#include”process.h”
int Capacity;
int profit[40],weight[40],n;
float ratio[40],temp[40],temp1[40],soln[40];
class knapsack
{
public:
void getdata();
void sort();
void display();
void calculatesoln();
float getmaxprofit();
};

void knapsack::getdata()
{
clrscr();
cout<<"\nEnter the Capacity of Bag\n";
cin>>Capacity;
//cout< cout<<"Enter the number of objects\n";
cin>>n;
//cout< cout<<"Enter the profit\n\n";
for(int i=0;i cin>>profit[i];
cout< cout<<"Enter the weight\n\n";
for(i=0;i cin>>weight[i];
cout< for(i=0;i {
ratio[i]=(float)profit[i]/(float)weight[i];
temp[i]=ratio[i];
temp1[i]=ratio[i];
}
}

void knapsack::sort()
{
float t;
for(int i=0;i {
for(int j=i+1;j {
if(ratio[i] {
t=ratio[i];
ratio[i]=ratio[j];
ratio[j]=t;
}
}
}
}

void knapsack::calculatesoln()
{
int maxcapac=0;
for(int i=0;i {
for(int p=0;p if(temp[p]==ratio[i])
{
if((maxcapac+weight[p])<=Capacity)
{
soln[p]=1.0;
maxcapac+=weight[p];
temp[p]=-1.0;
}
/* else
{
soln[p]=(float)(Capacity-maxcapac)/weight[p];
maxcapac+=Capacity-maxcapac;
temp[p]=-1.0;
}*/
break;
}
if(maxcapac==Capacity)
break;
}
}


float knapsack::getmaxprofit()
{
knapsack k;
float maxprofit=0.0;
k.calculatesoln();
k.display();
for(int i=0;i maxprofit+=(soln[i]*profit[i]);
return maxprofit;
}

void knapsack::display()
{
clrscr();
cout<<"\nKNAPSACK PROBLEM\n";
cout<<"----------------";
cout<<"\nWeight of each Node\n";
for(int i=0;i cout< cout<<"\n";
cout<<"\nProfit of each node\n";
for(i=0;i cout< cout<<"\n";
cout<<"\n\n Profit Ratio Pi/Wi is\n\n";
for(i=0;i cout< cout<<"\nValues \tProfit/Weight\n";
for(i=0;i {
cout<<"\nx"< }
}

void main()
{
clrscr();
knapsack kp;
kp.getdata();
kp.sort();
cout<<"\n\nMaximum Profit="< getch();
}














OUTPUT:

KNAPSACK PROBLEM

Enter the Capacity of Bag
10
Enter the number of objects
5
Enter the profit
80
60
75
20
10
0
Enter the weight
2
1
5
2
2

KNAPSACK PROBLEM

Weight of each Node
2 1 5 2 2

Profit of each node
80 60 75 20 10

Profit Ratio Pi/Wi is

60 40 15 10 5

Values Profit/Weight
x0 1 40
x1 1 60
x2 1 15
x3 1 10
x4 0 5

Maximum Profit=235






BINARY TREE TRAVERSAL

BINARY TREE TRAVERSAL


#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
struct node
{
int data;
struct node *left;
struct node *right;
}*root;

class btraverse
{
public:
btraverse()
{
root=NULL;
}
void create(int);
void preorder(struct node *);
void inorder(struct node *);
void postorder(struct node *);
};

void btraverse::create(int data)
{
struct node *newnode=new node;
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
struct node *prev,*temp;
prev=temp=root;
while(temp!=NULL)
{
if(data==temp->data)
{
cout<<"\nData already exists"; return; } else { if(datadata)
{
prev=temp;
temp=temp->left;
}
else
{
prev=temp;
temp=temp->right;
}
}
}
if(root==NULL)
root=newnode;
else if(datadata)
prev->left=newnode;
else
prev->right=newnode;
}

void btraverse::preorder(struct node *t)
{
if(t!=NULL)
{
cout<<" "<data;
preorder(t->left);
preorder(t->right);
}
}

void btraverse::inorder(struct node *t)
{
if(t!=NULL)
{
inorder(t->left);
cout<<" "<data;
inorder(t->right);
}
}

void btraverse::postorder(struct node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
cout<<" "<data;
}
}



void main()
{
btraverse bt;
int ch,item,n,i;
clrscr();
while(ch<=5) { cout<<"\n"; cout<<"\n1.Create"; cout<<"\n2.Preorder"; cout<<"\n3.Inorder"; cout<<"\n4.Postorder"; cout<<"\n5.Exit"; cout<<"\nEnter ur choice:\t"; cin>>ch;
cout<<"\n"; switch(ch) { case 1: cout<<"\nEnter the total items\n"; cin>>n;
cout<<"Enter the data\n\n"; for(i=0;i>item;
bt.create(item);
}
break;
case 2:
bt.preorder(root);
break;
case 3:
bt.inorder(root);
break;
case 4:
bt.postorder(root);
break;
case 5:
exit(0);
}
}
getch();
}





OUTPUT:
BINARY TREE TRAVERSAL
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 1
Enter the total items
8
Enter the data
30
12
40
10
20
35
50
60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 2
30 12 10 20 40 35 50 60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 3
10 12 20 30 35 40 50 60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 4
10 20 12 35 60 50 40 30
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 5

TRAVELLING SALESMAN PROBLEM

TRAVELLING SALESMAN PROBLEM




#include”iostream.h”
#include”conio.h”
int n,a[50][50],bpath[50],list[50],i,j,bcost,tbcost;
void calculate(int list[])
{
int t;
tbcost=0;
for(j=1;j {
t=a[list[j-1]][list[j]];
if(t!=0)
tbcost+=a[list[j-1]][list[j]];
else
tbcost=bcost+1;
}
}

void snap(int &x, int &y)
{
int temp;
temp=x;
x=y;
y=temp;
}

void permute(int k, int x)
{
int temp,i,j;
if(k==x)
{
calculate(list);
if(bcost==0)
bcost=tbcost+1;
if((tbcost {
bcost=tbcost;
for(j=0;j bpath[j]=list[j];
}
}
else
{
for(i=k;i<=x;i++)
{
snap(list[k],list[i]);
permute(k+1,x);
snap(list[k],list[i]);
}
}
}

void main()
{
clrscr();
cout<<"Enter the number of cities\n";
cin>>n;
for(i=0;i for(j=0;j {
if(i!=j)
{
cout<<"\nEnter the cost of travelling from"<<"("< cin>>a[i][j];
}
else
a[i][j]=0;
}
for(i=0;i list[i]=i;
permute(1,n-1);
cout<<"\nBest path is\n\n";
for(i=0;i cout< cout<<"\n\n Cost of best path is: "<< bcost+a[bpath[n-1]][0];
getch();
}





Enter the number of cities
4
Enter the cost of travelling from(1to2)6

Enter the cost of travelling from(1to3)0

Enter the cost of travelling from(1to4)8

Enter the cost of travelling from(2to1)4

Enter the cost of travelling from(2to3)3

Enter the cost of travelling from(2to4)0

Enter the cost of travelling from(3to1)0

Enter the cost of travelling from(3to2)5

Enter the cost of travelling from(3to4)10

Enter the cost of travelling from(4to1)2

Enter the cost of travelling from(4to2)0

Enter the cost of travelling from(4to3)6

Best path is

1 2 3 4

Cost of best path is: 21


KRUSKAL ALGORITHM

MINIMUM SPANNING TREE
KRUSKAL ALGORITHM


#include”iostream.h”
#include”conio.h”
class kruskal
{
struct node
{
int s;
int e;
int c;
};
node a[10],b[10];
int n,p[10],r[10];
public:
int getdata();
int findset(int);
void mintree(int);
void makeset(int);
void uni(int,int);
void link(int,int);
};

int kruskal::getdata()
{
int i,j,d,cn=0;
cout<<"Enter the number of vertices\n\n";
cin>>n;
for(i=0;i {
makeset(i);
for(j=i+1;j {
if(i!=j)
{
cout<<"Enter the cost of "<<"("< cin>>d;
if(d!=0)
{
a[cn].s=i+1;
a[cn].e=j+1;
a[cn].c=d;
cn++;
}
}
}
}
for(i=0;i {
for(j=i;j {
if(a[i].c>a[j].c)
{
int temp=a[i].s;
a[i].s=a[j].s;
a[j].s=temp;

temp=a[i].e;
a[i].e=a[j].e;
a[j].e=temp;

temp=a[i].c;
a[i].c=a[j].c;
a[j].c=temp;
}
}
}
cout<<"\nStart\tEnd\tCost\n";
for(i=0;i cout<<"\n"< return(cn);
}

void kruskal::makeset(int x)
{
p[x]=x;
r[x]=0;
}

void kruskal::uni(int x,int y)
{
int a=findset(x);
int b=findset(y);
link(a,b);
}

void kruskal::link(int x,int y)
{
if(r[x]>r[y])
p[y]=x;
else
p[x]=y;
if(r[x]==r[y])
r[y]=r[y]+1;
}

int kruskal::findset(int x)
{
if(x!=p[x])
p[x]=findset(p[x]);
return(p[x]);
}

void kruskal::mintree(int a1)
{
int i,j,u,v,ctr=0;
for(i=0;i {
u=a[i].s;
v=a[i].e;
if(findset(u)!=findset(v))
{
uni(u,v);
b[ctr].s=u;
b[ctr].e=v;
b[ctr].c=a[i].c;
ctr++;
}
}
cout<<"Edges in the minimum spanning tree\n";
for(i=0;i cout<<"\nEdge:"<<"("<}

void main()
{
kruskal k;
clrscr();
int a1=k.getdata();
k.mintree(a1);
getch();
}

Tuesday, September 1, 2009

INDEQUE

INDEQUE

/* Input-restricted deque program using array. */

#include “stdio.h”
#include
#include

#define MAX 10

struct dqueue
{
int arr[MAX] ;
int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatend ( struct dqueue *, int item ) ;
int delqatbeg ( struct dqueue * ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatend ( &dq, 12 ) ;
addqatend ( &dq, 13 ) ;
addqatend ( &dq, 14 ) ;
addqatend ( &dq, 15 ) ;
addqatend ( &dq, 16 ) ;
addqatend ( &dq, 17 ) ;
addqatend ( &dq, 18 ) ;
addqatend ( &dq, 19 ) ;
addqatend ( &dq, 20 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;
display ( dq ) ;

addqatend ( &dq, 19 ) ;
addqatend ( &dq, 20 ) ;
addqatend ( &dq, 21 ) ;
addqatend ( &dq, 22 ) ;
addqatend ( &dq, 23 ) ;
addqatend ( &dq, 24 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
int i ;

p -> front = p -> rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )
p -> arr[i] = 0 ;
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
int i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> rear == -1 && p -> front == -1 )
{
p -> rear = p -> front = 0 ;
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
return ;
}

if ( p -> rear == MAX )
{
for ( i = k = p -> front - 1 ; i <> rear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
p -> arr[k] = 0 ;
else
p -> arr[k] = p -> arr[i + 1] ;
}
( p -> rear )-- ;
( p -> front )-- ;
}
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
}

/* deletes item from begining of dqueue */
int delqatbeg ( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

item = p -> arr[p -> front] ;
p -> arr[p -> front] = 0 ;
( p -> front )++ ;

if ( p -> front == MAX )
p -> front = -1 ;

return item ;
}

/* deletes item from end of dqueue */
int delqatend ( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

( p -> rear )-- ;
item = p -> arr[p -> rear] ;
p -> arr[p -> rear] = 0 ;

if ( p -> rear == 0 )
p -> rear = -1 ;
return item ;
}

/* displays the queue */
void display ( struct dqueue dq )
{
int i ;

printf ( "\n front -> " ) ;

for ( i = 0 ; i < MAX ; i++ )
printf ( "%d\t", dq.arr[i] ) ;
printf ( " <- rear" ) ;
}

/* counts the number of items in dqueue */
int count ( struct dqueue dq )
{
int c, i ;

for ( i = c = 0 ; i < MAX ; i++ )
{
if ( dq.arr[i] != 0 )
c++ ;
}
return c ;
}

OUTDEQUE

OUTDEQUE

/* Output-restricted deque program using array. */

#include “stdio.h”
#include
#include

#define MAX 10

struct dqueue
{
int arr[MAX] ;
int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatbeg ( struct dqueue *, int ) ;
void addqatend ( struct dqueue *, int ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatbeg ( &dq, 10 ) ;
addqatend ( &dq, 12 ) ;
addqatbeg ( &dq, 9 ) ;
addqatend ( &dq, 13 ) ;
addqatbeg ( &dq, 8 ) ;
addqatend ( &dq, 14 ) ;
addqatbeg ( &dq, 7 ) ;
addqatend ( &dq, 15 ) ;
addqatbeg ( &dq, 6 ) ;
addqatend ( &dq, 16 ) ;
addqatbeg ( &dq, 5 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;

display ( dq ) ;

addqatbeg ( &dq, 5 ) ;
addqatbeg ( &dq, 4 ) ;
addqatbeg ( &dq, 3 ) ;
addqatbeg ( &dq, 2 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
int i ;

p -> front = p -> rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )
p -> arr[i] = 0 ;
}

/* adds item at begining of dqueue */
void addqatbeg ( struct dqueue *p, int item )
{
int c, i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> front == -1 && p -> rear == -1 )
{
p -> front = p -> rear = 0 ;
p -> arr[p -> front] = item ;
return ;
}

if ( p -> rear != MAX )
{
c = count ( *p ) ;
k = p -> rear ;

for ( i = 1 ; i <= c ; i++ )
{
p -> arr[k] = p -> arr[k - 1] ;
k-- ;
}

p -> arr[k] = item ;
p -> front = k ;
( p -> rear )++ ;
}
else
{
( p -> front )-- ;
p -> arr[p -> front] = item ;
}
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
int i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> rear == -1 && p -> front == -1 )
{
p -> rear = p -> front = 0 ;
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
return ;
}

if ( p -> rear == MAX )
{
k = p -> front - 1 ;

for ( i = p -> front - 1 ; i <> rear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
p -> arr[k] = 0 ;
else
p -> arr[k] = p -> arr[i + 1] ;
}
( p -> rear )-- ;
( p -> front )-- ;
}

p -> arr[p -> rear] = item ;
( p -> rear )++ ;
}

/* deletes item from end of dqueue */
int delqatend( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

( p -> rear )-- ;
item = p -> arr[p -> rear] ;
p -> arr[p -> rear] = 0 ;

if ( p -> rear == 0 )
p -> rear = -1 ;

return item ;
}

/* displays the queue */
void display( struct dqueue dq )
{
int i ;

printf ( "\n front -> " ) ;

for ( i = 0 ; i < MAX ; i++ )
printf ( "\t%d", dq.arr[i] ) ;

printf ( " <- rear " ) ;
}

/* counts the number of items in dqueue */
int count( struct dqueue dq )
{
int c, i ;
for ( i = c = 0 ; i < MAX ; i++ )
{
if ( dq.arr[i] != 0 )
c++ ;
}
return c ;
}