C++ Programming

/* Program for creating a minimum spanning tree from Kruskal's

algorithm */

#include

#define MAX 20

struct edge

{

int u;

int v;

int weight;

struct edge *link;

}*front = NULL;

int father[MAX]; /*Holds father of each node */

struct edge tree[MAX]; /* Will contain the edges of spanning tree */

int n; /*Denotes total number of nodes in the graph */

int wt_tree=0; /*Weight of the spanning tree */

int count=0; /* Denotes number of edges included in the tree */

/* Functions */

void make_tree();

void insert_tree(int i,int j,int wt);

void insert_pque(int i,int j,int wt);

struct edge *del_pque();

main()

{

int i;

create_graph();

make_tree();

printf("Edges to be included in spanning tree are :\n");

for(i=1;i<=count;i++)

{

printf("%d->",tree[i].u);

printf("%d\n",tree[i].v);

}

printf("Weight of this minimum spanning tree is : %d\n", wt_tree);

}/*End of main()*/

create_graph()

{

int i,wt,max_edges,origin,destin;

printf("Enter number of nodes : ");

scanf("%d",&n);

max_edges=n*(n-1)/2;

for(i=1;i<=max_edges;i++)

{

printf("Enter edge %d(0 0 to quit): ",i);

scanf("%d %d",&origin,&destin);

if( (origin==0) && (destin==0) )

break;

printf("Enter weight for this edge : ");

scanf("%d",&wt);

if( origin > n destin > n origin<=0 destin<=0)

{

printf("Invalid edge!\n");

i--;

}

else

insert_pque(origin,destin,wt);

}/*End of for*/

if(i

{

printf("Spanning tree is not possible\n");

exit(1);

}

}/*End of create_graph()*/

void make_tree()

{

struct edge *tmp;

int node1,node2,root_n1,root_n2;

while( count < n-1) /*Loop till n-1 edges included in the tree*/

{

tmp=del_pque();

node1=tmp->u;

node2=tmp->v;

printf("n1=%d ",node1);

printf("n2=%d ",node2);

while( node1 > 0)

{

root_n1=node1;

node1=father[node1];

}

while( node2 >0 )

{

root_n2=node2;

node2=father[node2];

}

printf("rootn1=%d ",root_n1);

printf("rootn2=%d\n",root_n2);

if(root_n1!=root_n2)

{

insert_tree(tmp->u,tmp->v,tmp->weight);

wt_tree=wt_tree+tmp->weight;

father[root_n2]=root_n1;

}

}/*End of while*/

}/*End of make_tree()*/

/*Inserting an edge in the tree */

void insert_tree(int i,int j,int wt)

{

printf("This edge inserted in the spanning tree\n");

count++;

tree[count].u=i;

tree[count].v=j;

tree[count].weight=wt;

}/*End of insert_tree()*/

/*Inserting edges in the priority queue */

void insert_pque(int i,int j,int wt)

{

struct edge *tmp,*q;

tmp = (struct edge *)malloc(sizeof(struct edge));

tmp->u=i;

tmp->v=j;

tmp->weight = wt;

/*Queue is empty or edge to be added has weight less than first edge*/

if( front NULL) /*Edge to be added at the end*/

tmp->link = NULL;

}/*End of else*/

}/*End of insert_pque()*/

/*Deleting an edge from the priority queue*/

struct edge *del_pque()

{

struct edge *tmp;

tmp = front;

printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);

front = front->link;

return tmp;

}/*End of del_pque()*/

A=8

B=4

C=14

Yes, I know I'm a genius.

Mak - the all knowing one.

MWAHAHAH!

The right-hand operand; the r-value of the operator.

Unary operators have one operand while tertiary operators have three operands. All binary operators have two operands, the l-value and the r-value. The l-value is the operand to the left of the operator while the r-value is the operand to the right of the operator.

Thus, in the expression x + y, x is the l-value while y is the r-value.

When overloading binary operators in a class, you need only specify the r-value. The l-value is the instance of the class to which the operator applies and therefore does not need to be specified. For instance:

class MyClass

{

public:

MyClass(int data=0):m_data(data){} // default constructor

int operator+ (const int rhs) const {return(m_data+rhs);}

private:

int m_data;

};

While this allows you to return the sum of your class instance and an integer, it does not allow you to return the sum of an integer and an instance of your class. For example:

MyClass obj(5);

int x = 10;

int y = obj + x; // OK! y is 15.

int z = x + obj; // Compiler error! No operator exists that accepts an r-value of type MyClass.

To fix this error and allow for two-way addition, you must declare a binary operator overload outside of the class. You cannot do it inside the class because the l-value is an int, not an instance of MyClass.

The external overload requires two parameters, the l-value and the r-value of the operator:

int operator+(const int lhs,const MyClass& rhs) {return(rhs+lhs);}

Note that the implementation simply reverses the operands. This is functionally equivalent to making the following explicit call:

return(rhs.operator+(lhs));

Note also that since MyClass::operator+ is a public operator of MyClass, this overload does not need to be declared a friend of MyClass (a common misconception). However, the overload must be declared in the same file where the class is declared since it is only of relevance to MyClass but should be made available wherever MyClass is accessible.

the decryprtion code function is

void decrypt_mono(char word[],char cypher[])

Not really, but you can have:

- a pointer pointing to a structure (FILE * is an example)

- a pointer pointing to a structure-member (eg: struct tm tm; int *ip= &tm.tm_year)

- a structure-member that is a pointer (any type)

Example:

typedef struct TreeNode {

struct TreeNode *left, *right;

int data;

} TreeNode;

TreeNode *root = (TreeNode *)calloc (sizeof (TreeNode), 1);

The CTRL key is the only difference. What it actually does depends on the currently active program and/or control, and whether or not the key combo has been implemented or not. If not, the shell processes the key combo. On my system (Windows 7), both combos bring up the task switcher.

Add to the front is constant time O(1). Adding to the end is linear time O(n). If the list maintains a pointer to the last node (as well as the first node), insertions can be done at either end in constant time.

It's a bit difficult to show a flowchart using nothing but words, but here goes:

start

let list[] be 100 random values

let best be value of list[0]

let index be 1

repeat

is value of list[index] less than best?

YES: let best be value of list[index] {continue}

NO: {continue}

increment index

is index less than 100?

YES: {go to repeat}

NO: {continue}

print value of best

end

Previous answer:

start test number =100 count = count +1 list number =< test number if true testnumber = list number count = 100 goto end else start end

The previous answer assumes 100 to be largest number in the list. What happens when all of the numbers in the list happen to be greater than 100? Also, previous answer exits the loop prematurely as soon as any number equal or smaller than 100 is located. To locate the smallest number in a list, the entire list must be compared with the current best, which is initially taken to be the first number in the list.

That is like comparing apples and trees...

Visual C++ is a development environment that allows one to program in C++, which is a language.

MFC (Microsoft Foundation Classes) is a library to allows one to use C++ to write MS Windows programs using a particular set of API-like calls. It is a library, not a language.

The two cannot really be compared, as they are too different in scope.

It depends on what the tree is being used for. If the tree is being used to store data that is not going to be modified very much, than AVL trees are probably better. In most other cases, I'd say Red-Black trees are better.

Unlike pointer variables and other variables, references have no storage of their own. A reference is simply an alias for an object that already exists in memory (allowing you to refer to the object by its memory address). Since they have no storage of their own it is impossible to create an array of references. You can of course create an array of objects, each of which can then be referenced. You can also have several references to the same object. But you cannot store those references because there is nothing to physically store other than the object itself, which is already stored. For the same reason you cannot reference references nor can you point to references. You can only refer and point to objects (or point to NULL of course).

5200 + 5000000 = 5005200

In this case recursion is not necessary, an iterative process is more efficient.

Start by pointing at the head node. While this node has a next node, detach its next node and insert that node at the head. Repeat until the original head node has no next node. At that point the head has become the tail and all the nodes are completely reversed.

The following example shows how this can be implemented, where the list object contains a head node (which may be NULL), and each node has a next node. The tail node's next node is always NULL.

void reverse(list& lst)

{

if( node* p=lst.head )

{

while(p->next)

{

node* n=p.next; // point to the next node

p.next=n.next; // detach the next node

n.next=lst.head; // insert the detached node at the head

lst.head=n; // set the new head node

}

}

}

Consult the following program. Three classes are declared, A, B and C, such that B and C both inherit from A. Thus B and C are said to be a "kind of" A. Class A includes a virtual method named action() which is overridden by both B and C. Thus B and C are more specialised than A. All the methods simply print stubs to show which method has been executed.

The main function instantiates one instance of each class and passes all three to the nonpolymorph() function before passing them to the polymorph() function. Both functions accept a reference to an A object and both functions invoke the action() method for that object. Both functions execute the correct method regardless of which type of object is passed.

The nonpolymorphic() function is the least efficient method of enabling runtime polymorphism because the function itself needs to know the exact type of the object being passed in order to invoke the correct method. In this case it examines the last character of the runtime type name and switches accordingly. With more complex class names you might be forced to use nested ifs to compare names, which is even more costly in terms of performance. Once the correct class is determined, a dynamic cast is used for B and C objects to invoke the correct method.

Note that if you should happen to derive new classes from A, you must also update this function to cater for them (adding new cases). In a real program you might have dozens of functions like this and each must be updated accordingly to cater for all new types. This can very quickly become a maintenance nightmare.

The polymorph() function, on the other hand, is not only simpler to implement it requires no additional maintenance whatsoever. It will cater for any class that inherits from A both now and in the future. It is able to achieve runtime polymorphism by virtue of the fact the A class has a virtual function which both B and C override. When you declare a virtual function, you create a virtual table for that class as well as all those that derive from it (that is, one table per class, not one table per object of the class). This consumes a little bit more memory than normal, but the table is simply an array of virtual function pointers that point to the appropriate overrides for that particular class. So the A class table entry will point to A::action(), while the B class table entry will point to B::action(), and so on. Thus you get the expected behaviour without the need for expensive runtime information.

Virtual methods mimic the way objects work in real life to some extent. For instance, imagine the function is you and A, B and C are black box objects that can make a sound at the press of a button on top of the box. Someone places one of these objects in front of you and, although you have no idea what type of object it is, you know you can simply press the button and it will make a sound. In other words you know how the interface works, the object itself decides how that interface is implemented. If the button were not on top of the box then you might have to feel around the box to locate the button. This is akin to using runtime type information to get the additional information you need to use the interface. Sometimes this is required but it is usually a sign of poor design. When interfaces are consistent, then your need to know the type of object is wholly irrelevant.

#include<iostream>

#include<typeinfo>

using namespace std;

struct A

{

virtual void action () { cout << "A::action()\n" << endl; }

};

struct B : A

{

void action () override { cout << "B::action()\n" << endl; }

};

struct C: A

{

void action () override { cout << "C::action()\n" << endl; }

};

void nonpolymorph(A& a)

{

std::string s (typeid(a).name());

switch (s.at( s.size()-1))

{

case ('A'): a.action(); break;

case ('B'): (dynamic_cast<B&>(a)).action(); break;

case ('C'): (dynamic_cast<C&>(a)).action(); break;

}

}

void polymorph(A& a)

{

a.action();

}

int main()

{

A a;

B b;

C c;

nonpolymorph (a);

nonpolymorph (b);

nonpolymorph (c);

polymorph (a);

polymorph (b);

polymorph (c);

}

Arrays cannot be left-shifted. That term applies to bit values (it is a bitwise operator). Although conceptually the same, when we shift an array's elements we must traverse the array from the first to penultimate element, copying the next element in place of the current element as we go. This is usually referred to as shunting, and can be done in either direction (left and right).

It's actually much easier think of a left shunt by one element as simply meaning delete the first element. But in reality what you actually do is shunt all the elements (except the first) one position to the left and delete the last element since it will then be a copy of the penultimate element. Alternatively, after shunting all the elements to the left, you can replace the final element with a default value (akin to filling the last bit with a zero as per a bitwise left shift).

The following example demonstrates both techniques using a C++ vector (which is exactly the same as a dynamic array in C but is considerably easier to implement):

#include <iostream>

#include <vector>

// Type definitions to simplify the code.

typedef std::vector<int> int_array;

typedef int_array::iterator it;

void shift_left(int_array& a)

{

// Shift all elements to the left by one position

// and delete the final element.

if( a.size() )

{

unsigned int idx=0;

for(it i=a.begin()+1; i!=a.end(); ++i)

{

a[idx]=a[idx+1];

++idx;

}

a.pop_back();

a.shrink_to_fit();

}

}

void shift_left(int_array& a, int default_value)

{

// Shift all elements to the left by one position

// and replace the final element with the given

// default value.

if( a.size() )

{

unsigned int idx=0;

for(it i=a.begin()+1; i!=a.end(); ++i)

{

a[idx]=a[idx+1];

++idx;

}

a[idx]=default_value;

}

}

void print_array(int_array& a)

{

using namespace std;

for(it i=a.begin(); i!=a.end(); ++i )

cout<<" "<<*i;

cout<<endl;

}

int main()

{

int_array a;

for(int i=0; i<9; ++i )

a.push_back( i+1 );

print_array( a );

shift_left( a );

print_array( a );

shift_left( a, 0 );

print_array( a );

return(0);

}

Output:

1 2 3 4 5 6 7 8 9

2 3 4 5 6 7 8 9

3 4 5 6 7 8 9 0

A singleton is a class of object from which only one instance of the object can be instantiated within your program. They are generally used to store global variables or to provide some common functionality, such as an application log. They are generally frowned upon because of their global nature, but when you need common functionality there are far worse ways of going about it than with a singleton.

There are several design patterns for a singleton, but probably the simplest and most common form is shown below. Note the private constructors and assignment operator, and the static member method containing a static variable -- the only instance of the class that can ever exist.

Access to the members (not shown) is via a static call:

CSingleton::Instance().<member>

class CSingleton

{

private:

CSingleton() {}; // Prevent construction outside of the class.

CSingleton(const CSingleton&); // Prevent copy-construction.

CSingleton& operator=(const CSingleton&); // Prevent assignment.

public:

static CSingleton& Instance()

{

static CSingleton singleton;

// Created on first access.

// Destroyed on application exit.

return( singleton );

}

// Specific members omitted. Dependant upon purpose of singleton.

};

If the function is inline expanded then it is not invoked at all -- there is no function call. However, if the function is not or cannot be inline expanded, a procedure call is invoked. This pushes the calling function's local values onto the stack, followed by the return address, followed by the callee's argument values in reverse order. Control is then passed to the address of the function. The function then pops the arguments off the stack and assigns them to its local parameters (parameters that are passed by value will automatically invoke the copy constructors of those parameters). The function then executes. When a return statement is encountered, the return address is popped from the stack, the return value (if any) is pushed onto the stack, and control is passed to the return address. When a function returns, the return value (if any) and the local values are popped from the stack, and execution continues from where it left off.