一个简单的证明

今天上概率课，有一个简单的问题，老师没有在课堂上证明，只是用venn diagram来说明。

P[(A∩B')∪(A'∩B)] == P(A) + P(B) - 2P(A∩B)

如图：所要求得概率就是两个圆扣除相交部分。

我的证明：

left hand = P(A∩B')+ P(A'∩B)             as (A∩B')and (A'∩B) are mutually exclusive events as (A∩B')belongs to A;

                                   (A'∩B)belongs to A', and A and A' are mutually exclusive events, so use Postulate3

= P(Ф∪(A∩B'))+ P(Ф∪(A'∩B))                       Identity Law

= P((A∩A')∪(A∩B'))+ P((B∩B')∪(A'∩B))              Negation Law

= P(A∩(A'∪B')) + P((B∩(A'∪B'))                     Distributive Law

= P(A∩(A∩B)') + P(B∩(A∩B)')                       De Morgan's Law

= 1 - P((A∩(A∩B)')') + 1- P((B∩(A∩B)')')          Theorem 2.3

= 1 - P(A'∪(A∩B)) + 1 - P(B'∪(A∩B))              De Morgan's Law

= 1 - (P(A') + P(A∩B) - P(A'∩(A∩B))) + 1 -(P(B') + P(A∩B) - P(B'∩(A∩B)))  Theorem 2.7

= (1- P(A')) + (1 - P(B')) - 2P(A∩B) + P(Ф∩B) + P(Ф∩A)       Associative Law & Negation Law

= P(A) + P(B) - 2P(A∩B) + 2P(Ф)                       Theorem 2.3 and Domination Law

= P(A) + P(B) - 2P(A∩B) = right hand                Theorem 2.4

proved!

　C++的小错误

To: Professor Ms. Leila Kosseim

Dear Madam Kosseim,

I am your student in course COMP248 and I found out there is a  small mistake in your class.

In class you use 

    cout<<setf(ios::showpoint);

    cout<<setf(ios::fixed);

    cout<<precision(2);

In fact, it is wrong, you should use cout's member function setf(), instead of operator "<<" as followoing:

    cout.setf(ios::showpoint);

    cout.setf(ios::fixed);

    cout.precision(2);

or if you really prefer to using the parameterized manipulator, you have to include "iomanip" and like this:

    cout<<setiosflags(ios::showpoint|ios::fixed);

    cout<<setprecision(3);

Thank you for your time in advance.

B.Rgds

Qingzhe Huang

Here is the reply from Madam:

yes.  I verified it and you are right. I mixed up setf and setiosflags. I will correct the mistake in class Friday.

thanks for telling me.

LK

Is it still correct for your suggested expression of theorem?

Hi Doctor,

In today's class you clarified some points about "logically equivalence", and I checked with my notes and found out that in previous class you gave an expression of theorem as following:

(p≡q) ≡ (p←→q ≡ T)

However, you erased it later and said it was not correct. After your clarification about "equivalence", I wonder if it IS INDEED CORRECT after all. The following is the truth table I made, I am not sure if it is right or not. Can you check it? 

p       q           p≡q    p←→q      p←→q≡T

T    T      T         T            T

T    F      F         F            F

F    T      F         F            F

F    F      T         T            T

As "T" is itself a proposition with truth value that is always true, right? Therefore according to definition of "equivalence" that only when the two proposition "p←→q" and "T" have the same truth value, they are equivalence. So, only when proposition "p←→q" is true, compound proposition (p←→q ≡ T) has true value or in other words that it is true that p←→q is equivalent to proposition TRUE. So, we observe that proposition (p≡q) has same truth table as proposition (p←→q ≡ T). Then they are logically equivalent or (p≡q) ≡ (p←→q ≡ T) is true.

Is above correct?

Thank you for your time and patience.

B.Rgds,

Qingzhe Huang

　            A small doubt about 2's complement...

Dear Professor Hina,

I am a student in your section NN and I have a small question about 2's complement.

After 2's complement, a negative number will be tranformed into its positive counter-part, so does the positive. But how about the lowest negative one?

For example of 4bit, the lowest negative is 1000 which is equal to -8. However, after 2's complement, it becomes 1000 again! Does it suggest that the lowest negative one is an exception of 2's complement rule? Or when we encounter the lowest of negative number and want to find out its positive counterpart, how should we do?

Thank you for your time,

QingZhe Huang

        My assignment here...

//****************************************************//
// First Assignment for Comp248						  //	
// Program Title: Ice Cream Experiment				  //	
// Author: Qingzhe Huang							  //
// Section: X                                         //
// Student ID: 5037735                                //
//****************************************************//

#include <iostream>

using namespace std;

const double SweetPerLiter = 0.35;  //sweetner weight per liter of ice cream

void display(double, double, double);

int main()
{
	double mouse, dieter, lethal;
	char choice[10];  //to store user's input choice to decide if repeat inputting

	//set up a menu to ask user if repeat input is desired
	cout<<"\nInput or Quit?(quit)\n";
	cin>>choice;
	while (strcmp(choice, "quit")!=0)//use 'quit' to determine if quit
	{
		cout<<"\nEnter the weight of the mouse in grams: ";
		cin>>mouse;
		cout<<"\nEnter the lethal dose for the mouse in grams: ";
		cin>>lethal;
		cout<<"\nEnter the desired weight of the dieter, in Kilograms: ";
		cin>>dieter;

		//a display subroutine to make easy reading
		display(mouse, lethal, dieter);

		//ask user if repeat input is desired
		cout<<"\nInput or Quit?(quit)\n";
		cin>>choice;
	}

	return 0;
}

//a routine for display of result with 3 parameters of input data

void display(double mouse, double lethal, double dieter)
{
	double temp;  //temperarily store the lethal dose in order to calculate icecream liter
	long preFlag; //previous display format should be saved and restored after display

	temp = dieter / mouse * lethal;  //the lethal weight for dieter

	cout<<"\nFor these parameters:\n";
	cout<<"\tmouse weight: "<<mouse<<" grams\n";
	cout<<"\tlethal dose for the mouse: "<<lethal<<" grams\n";
	cout<<"\tdesired dieter weight: "<<dieter<<" kilograms\n";

	//set up display format to make precision of 3 and fixed format;
	preFlag = cout.setf(ios::fixed);
	prePrec = cout.precision(3);
	cout<<"The lethal dose for sweetener is "<<temp<<"kilograms\n";
	cout<<"The leathal quantity of ice cream is "<< temp* SweetPerLiter<<" kiloliters\n";

	//restore previous display format flag and precision
	cout.flags(preFlag);
}

　 Here it is asked...

    Here it is answered...

Hi,

> I am student from your class of COEN244.
> Just to clear the little doubt of declaration of pointer in your class,
> see following is from your slides:
>
> int number=10, int* pNumber = &number;
>
> Actually the second "int" after comma is unneccessary, after
> compilation the warning of VC++
> "warning C4518: 'int ' : storage-class or type specifier(s) unexpected
> here; ignored"
>


Thank you for the clarification.  I will correct myself next class.


> Sorry for my fussy on details as I am Computer Science student with
> "Software System" option and I treat this course very seriously. I feel
> a bit sad that most students in class are from "Hardware" options which
> probably means that programming is only an option for them.


Actually, in engineering it is a mandatory course.  The way I teach this
course will not differ due the students background.  They will have to
learn how program using OO methodology.


> The unexpected "EARLY" termination of first lecture worries me a lot. I do
> hope you understand that very few software-optioned students do treat
> your lectures very seriously.


Don't worry about the "EARLY" termination.  I had that planned before I
got in there... I have to "EASE" people (including myself) into a summer
course :)


> Here is my answer to your question in class: "What do you expect to get
> after this course?"
> I run into many doubts and confusions in programming from time to time,
> and it is expected that this course can systematically show me the
> answer.

That is exactly my plan!  My lectures are to guide and inspire you
to practice programming.  Learning to program well is really up to the
individual.  But we will look into some "systematic" ways to solve
programming problems.

Regards,
Chris
　

　 Here it is asked...

On Tue, 8 Jul 2003, Hotmail wrote:

> Hi sir,
>
> Thank you so much for your reply.
> As I was doing assignment 1, once again I spent a fruitless afternoon to
> solve my old, long-term painful problem:
>
> I was supposed to ask user to input a number (int , float or whatever). The
> usual way is to use cin>>aVariable;
> But suppose the naughty user key in a character, say 'q' or whatever. The
> program crash.
>  I searched MSDN for ways to "peek" the character before assign value to the
> "aVariable". However, there is no way to "assign" value. I AM able to check
> character by character by using cin.get() or peek(). But it seems that I
> need to re-implement "char"-to-"int" or "char"-to-"float" which I don't want
> to.
>
> I run into this problem from time to time, and cannot find a proper way to
> handle. Can you give me some suggestion?
>
> Thank you for your patience,
>
> B.Regards,
>
> Nick Huang
　

    Here it is answered...

Ok!  I've come up with this solution:

================================================================
#include <iostream>

using std::cin ;
using std::cout ;
using std::endl ;

void main() {

int variable ;

cin >> variable ;

// Check the failbit error flag
if ( ! cin.fail() )
cout << "This is the integer " << variable << endl ;
else {
cout << "This is NOT an integer!" << endl ;
// Clear error flags
cin.clear() ;
// Empty input buffer
cin.get() ;
}
}
========================================================================

Hope this helps!

Best Regards,
Chris Taillefer
　

　    here goes the unexpected result...

           Can you tell who is who?

class MyClass
{
	friend MyClass& operator<<(MyClass& , int );
public:
	MyClass& operator<<(int);
};

int main()
{
	MyClass M;
	M<<45;
	return 0;
}

MyClass& operator<<(MyClass& dummy, int number)
{
	cout<<"this is friend!";
	return dummy;
}

MyClass& MyClass::operator <<(int number)
{
	cout<<"this is members";
	return *this;
}

	The explanation...

This code is ambiguous because when you call the function similar to

MyClass aClass ;
aClass << 5 ;

the operator<< function that is call must have the "signature" of a
MyClass object on the LHS and an int on the RHS.  Both function have the
same signature.  So the compiler does not know which one to use.

	So private member function is indeed accessible

> Hi sir,
>
> Maybe I didn't express myself clearly in class because I asked you the question that is it possible for "friend" function to access member functions of class?
> Because when you mentioned that a friend function to a class is accessable to the private MEMBERS of the class, I arbitarily regarded MEMBER FUNCTIONS are also
> part of MEMBERS. And your answer is positive, if my memory is correct, though I am not sure.
> So, can you confirm me about this issue? Because the error message of compiler shows that there is no way to access PRIVATE MEMBER FUNCTIONS OF A CLASS BY FRIEND FUNCTIONS.
>

Private member functions and data are accessable to friend functions.  You
must have done something else wrong.  Here is a peice of code I used to
test your claim...


class Test {
        friend void foo(Test&) ;
private:
        char* foobar() { return "This is a test!"  ; }
} ;

void foo(Test& tmp) {
        cout << tmp.foobar() ;
}

void main() {

        Test object ;
        foo( object ) ;

}

Hi Nick.  You were right about your previous example, but only on windows.
I compiled on Unix and it gave me a warning but still worked anyway.

I believe that this particular mechanism is operating system dependent.
Hence it is not good way to program.  I will give more in class on Monday.

Best Regards,
Chris Taillefer
P/T Faculty
　

Your tutorial is great! And I just want to say thank you for your great job!

		A little tip about "conversion constructor"

We all know that C++ will automatically try to convert a function call with closest argument, for example, when we overloaded

the operator= of member function of class String. When we call String = "a char string"; compiler will try to convert "a char 

string" into an object of String, see below:

#include <iostream>

using namespace std;

class String
{
private:
	char* sPtr;
	int length;
public:
	String(const char * =" " );
	char* getStr() const;
	~String();
	const String & operator=(const String&);
	void print(){cout<<sPtr<<endl;}
};

int main()
{
	String S("string S");
	S.print();
	S = "change to this!";
	S.print();
	return 0;
}

char* String::getStr() const
{
	 return sPtr;
}


const String& String::operator =(const String& right)
{
	delete [] sPtr;
	length = strlen(right.getStr());
	sPtr = new char[length+1];
	strcpy(sPtr, right.getStr());
	return *this;
}



String::~String()
{
	delete []sPtr;
	length = -1;
}

String::String(const char* str)
{
	length= strlen(str);
	sPtr = new char[length+1];
	strcpy(sPtr, str);
}

The result is like following:

string S
change to this!
Press any key to continue

But keep in mind that it will not always succeed in conversion unless you define your overloaded function properly. That is

it works only if you define the parameter of operator = as const. Otherwise it won't work.

for composition object, initialization is only optional!

Can you confirm this?

> > 2.  See your lecture slides in class2(COEN244Class2.pdf) of compostion
> > example, the Date class has a composition object Time class time, in the
> > constructor, you simply call the object time.setTime(sec, min, hour);
>
> This is a set method, NOT A CONSTRUCTOR CALL. There were no set methods
> provided to you in the prototype!

Even there is no set method provided in prototype, an overloaded assign
operator = is provided in prototype. So, it can be regarded as an set method
plus we use conversion constructor:

msg = data;   //operator= is used and data is converted to be temperary
object by conversion constructor

Of course, as I said in my mai, this is not efficient way since object msg
is initialized first to be empty string, then assigned secondly. But I think
it works. Can you confirm this?

Thank you for your time,

Nick Huang/Qingzhe Huang

it would work, albeit inefficient!

Hi Nick, it would work, albeit inefficient!

Chris

Is conversion constructor involved here? I doubt it...

Hi,

1.  As promised in tutorial, I tried to test to see if conversion constructor is playing any role in following:

class Shape
{
protected:
 double data;
public:
 Shape(double d=1):data(d){cout<<"shape constructor\n";}
};


class Square: public Shape
{
private:
 double side;
public:
 Square(double side=3):side(side), Shape(side){cout<<"square constructor\n";}
};

int main()
{
 Shape aShape;
 aShape =Square(7);

 return 0;
}

2.  The running result is like following:
shape constructor
shape constructor
square constructor
Press any key to continue

3. The first line obviously belongs to aShape construction, and 2nd, 3rd line is due to Square(7). But I am still not sure about whether conversion constructor is involved here. So, I change the main function a little bit:

int main()
{
 Shape aShape;
 aShape =7;

 return 0;
}

4. The new running result is like following: and it is a REAL CONVERSION CONSTRUCTOR HERE. 

shape constructor
shape constructor
Press any key to continue

5. So, it seems to me that the code "aShape =Square(7);" is only doing member-wise copy and no conversion constructor is playing any role here. Though I am not quite sure about this, what do you think?

Thank you for your time,

Nick Huang/Qingzhe Huang

		Do we lose the file pointer?

As simple as following code, what would you expect? Does file "test2.txt" was created? And what is written in file "test1.txt"?

The answer is that "test2.txt" was not created and nothing was written into "test1.txt". Do you believe?

	int main()

	{

		ofstream f;
		f.open("test1.txt");
	
		f.open("test2.txt");
		f<<5;

		return 0;

	}

	My question for final

#include <iostream>

using namespace std;

template<class T, class X>
class Base
{
public:
		virtual X pubTest(T t);
};

template<class X, class T>
class Derived: public Base<T, X>
{
public:
		virtual X pubTest(T t);
};

int main()
{
	Base<int, char> *pB = new Derived<char, int>;
	try
	{
		pB->pubTest('A');
	}
	catch(int i)
	{
		cout<<"catch int "<<i<<endl;
	}
	catch(char c)
	{
		cout<<"catch char "<<c<<endl;
	}
	return 0;
}

template<class T, class X>
X Base<T, X>::pubTest(T t)
{
	throw t;
	return t;
}

template<class X, class T>
X Derived<X, T>::pubTest(T t)
{
	X x = 'A';
	try
	{
		Base<T, X>::pubTest('A');
	}
	catch(T)
	{
		throw x;
	}
	catch(X)
	{
		throw t;
	}
	return x;
}

A const demo

#include <iostream>

using namespace std;

class Demo
{
private:
	int data;
	//the "ptr" pointing to "data"
	int* ptr;

	//const data member is nothing but const values, so, they must be 
	//initialized by initializer BEFORE constructor
	const int constData;

public:
	//even reference is given you still cannot change "data"
	const int& constValueRef(){ return data;} 
	//you have the pointer by its reference, and similarly you cannot change data,
	//but you can change the pointer---"ptr"
	const int*& constValuePtr() { return ptr;}
	//the pointer itselft---ptr--cannot be changed, but the data
	//which pointed to can be changed. In this case, you can change "data"
	//but not "ptr"
	int*  const& constPtr() { return ptr;}

	//even you have the access to constant data by reference, you
	//still cannot change it. What's more, compiler force you to declare 
	//return value as "const int"
	const int& getConstData(){	return constData;}

	//a const member function only for const object to be called
	int getData() const { cout<<"this is const function, should be called by a const"
		<<" object"<<endl; return data;} 

	//it is an overloading to the const version of "getData"
	int getData(){cout<<"this is not const version, so, when const object call"
		<<"getData(), it won't be called\n"; return data;}

	//you cannot overload a function only by different type of "return value"
//	const int getData() {return data;} //error, cannot overload

	void test();

	Demo();

};

//a test function with const object as parameter
void testConst(const Demo& D);

//a wild test 
void testWild(Demo& D);


int global = 100;

int main()
{
	Demo D;
	D.test();
	testConst(D);
	testWild(D);
	return 0;
}

//const data should be initialized before constructor
Demo::Demo() : constData(global)
{
	data = 10;
	ptr = &data;
}

void Demo::test()
{
//	constValueRef() = 12; //Error, try to modify const value
//	*(constValuePtr()) = 13;// Error,try to modify const value
	constValuePtr() = &global; //OK, only change pointer, not data;
//	constPtr() = &global; //Error, try to modify pointer
	*constPtr() = global; //OK, only change the data

//	getConstData() = 11;//Error, you cannot change a const

}


void testConst(const Demo& D)
{
	//can you guess which version of getData() is called here?
	D.getData();
	//obviously, the const version is called, even you don't specify which one.
}

void testWild(Demo& D)
{
	//can you guess which version of getData() is called here?
	D.getData();
	//originally I expect the sequence of function declared may have effect.
	//but it turned out that non-const object call non-const member functions.

	//if you do want to call the const version of "getData()":
	//then change the object to be type of "const object"
	((const Demo)(D)).getData();
	
}

Re: I am not asking for something,

but I do want to make it clear that I finished assignment 6 early last week...

The friend function of a template class can only be defined in formate of inline function, right?

This is really ridiculous! I understand that there might be some difficulty in designing compiler, but there should be some ways!

	Is it a bug with VC++???

See following, it is as simple as an overloading of operator by friend function of a simple class. But compiler continually gives

a strange error: 

fatal error C1001: INTERNAL COMPILER ERROR
(compiler file 'msc1.cpp', line 1786) 

I tried all my way and cannot solve it. It seems a strange error with friend function, since when I changed the friend function 

with no operator overloading, there is no error again. 

#include <iostream>

using namespace std;

class  MyClass
{
	friend int operator +(int i, const MyClass& M);
private:
	int data;
public:
};


int main()
{
	return 0;
}

int operator +(int i, const MyClass& M)
{
	return i+M.data;
}

No operator overload:

class  MyClass
{
	friend int add(int i, const MyClass& M);
private:
	int data;
public:
	MyClass(int i=10): data(i) {;}
};


int main()
{
	MyClass M;
	cout<<add(5, M);
	return 0;
}

int add(int i, const MyClass& M)
{
	return i+M.data;
}

I think there must be some mistakes in question 8...

> Regarding the assignment 1, I think there are quite a few mistakes.

I announced the mistakes in class and put a corrected version of the 
assignment on the course website.

> 1.  Taking question 8 as an example, the integrate formular is obviously 
> incorrect. As the correct one should be 1/2[f(a)+f(b)]*(b-a), instead of 
> 1/2[f(a)+f(b)]/(b-a).  Because the dividing makes really no senses, right?

Yes.

> 2. Secondly "trapezoidal rule" works well if the function f in  interval 
> [a,b] is linear. This implies that we should compare the "SLOPE" of  two 
> half interval  of functions, that is,  if [f(b) - f(m)]/(m-a) is close 
> to [f(b) - f(m)]/(b-m), is it right?

The trapezoidal rule assumes that the function is linear.  However, 
computing the slope is not a good way of finding out whether it is accurate.

> So, my solution is like following:
>  
> --this trape function is the integrate formular, corrected from "divide" 
> to "multiply"
> trape f a b = (f a + f b)*(b-a)*0.5

Yes.

> --this slope function calculate the function f's "slope" at interval [a,b]
> slope f a b = (f b - f a)/(b-a)

Not needed: compare the results of integrating the whole interval [a,b] 
with the sum of the integrals of the half intervals [a,m] and [m,b].

> --if the slope of two interval is close within a tolerance e=0.001, we 
> return one of the integrate formular, of course it should
> --multiply by 2. If not, recursively call integrate function again.

This might work; I am not sure.

> integrate f a b =  if abs (slope f a (half a b) - slope f (half a b) b) <e
>    then (trape f a (half a b))*2
>    else integrate f a (half a b) + integrate f (half a b) b  where e =0.001
> --the result is like following which is quite close to your test:
>  
> A1> integrate sin 0 pi
> 2.0

If you can get answers as close as that, go for it.

Peter

So it is mentioned in class...

Hi,

Actually our prof. corrected this mistake in Q8 in the
class, together with 2 other mistakes in Q1 and Q2. 
You can get the corrected version of assignment from
his web.
I use a slightly different algorithm with yours: my
first approximation simply uses the trapeziodal rule;
second(better) approximation is to split the interval
into two equal parts, then apply trapeziodal rule to
both and then take their summation -- I don't mutiply
the result of one half by 2 and take it as result --
that's the difference from yours.  The rest of the
algorithm is same.  In case of e=0.001, I got the same
result also.

Cheers,
Linda   

The declaration of an object should not add parentheses after constructor

#include <iostream>

using namespace std;

struct Node
{
	Node* next;
	int data;
};

int dataArray[10] = {1, 3, 2, 9, 4, 5, 8, 7, 0, 6};

Node* initialize(int array[], int size);
void print(Node* head);
void deleteKey(Node* head, int K);

int main()
{
	Node* head;
	head = initialize(dataArray, 10);
	print(head);
	cout<<"now delete key=3:\n";
	deleteKey(head, 3);
	print(head);
	cout<<"now delete key=2:\n";
	deleteKey(head, 2);
	print(head);
	cout<<"can we actually delete the head of which the key=1?\n";
	deleteKey(head, 1);
	print(head);//is head still OK?
	return 0;
}

//establish a link list and assign value by input int array to each node
Node* initialize(int array[], int size)
{
	Node* head=NULL, * ptr;
	
	for (int i=0; i<size; i++)
	{
		//first item
		if (head ==NULL)
		{
			head = new Node;
			ptr = head;
			ptr->data = array[i];
			ptr->next = NULL;
		}
		else
		{
			//all other node is the next one.
			ptr->next = new Node;
			ptr = ptr->next;
			ptr->data = array[i];
			ptr->next = NULL;
		}
	}
	return head;
}

void print(Node* head)
{
	Node* ptr=head;
	int index=0;
	while (ptr!=NULL)
	{
		cout<<"index no.:"<<index<<" and value:"<<ptr->data<<endl;
		ptr = ptr->next;
		index++;
	}
}

void deleteKey(Node* head, int K)
{
	Node* first=head, *second, *temp;

	while (first!=NULL)
	{
		//first is the one to be deleted
		if (first->data==K)
		{
			temp = first;
			first=first->next;
			delete temp;
		}
		else
		{
			break;
		}
	}
	//the ends of link list
	if (first==NULL)
	{
		return;
	}

	//now first is not the key
	second = first->next;
	while (second!=NULL)
	{
		if (second->data==K)
		{
			temp = second;//hold it then delete it.
			first->next = second->next;
			second = first->next;
			delete temp;
		}
		else
		{
			first=second;
			second=first->next;
		}
	}
}


                         So, I am correct.

Hi,
You're correct. I overlooked this detail. Please give me your
midterm and I'll correct this error in marking.

Thomas.

Can you show me something?

Hi sir,

Thank you for your praise and I wish in future you might be kind enough to
give me some advice if I run into some problems in programming.

By the way, just at the time I write this message, I solved a small problem
of my doubt with template functions.
http://www.staroceans.com/templateArray.htm

The question is like this: suppose we have a series of template functions,
say various sorting algorithms, all with same parameter type. It is
convenient for us to put them in a function array for continual calling
during the comparison of different algorithms. (This is actually an
assignment of comp352.) But for VC++, compiler simply won't compile or even
check template function until the last minute. So, there is no way to
initialize function array with these template functions. See following:

//three different sorting function declared in template
template <class Elem>
void bubbleSort(Elem array[], int size);

template <class Elem>
void selectSort(Elem array[], int size);

template <class Elem>
void quickSort(Elem array[], int size);

And the following won't work! We cannot initialize array with these template
functions.
void (*sortFun[3])(int array[], int size)={bubbleSort<int>, selectSort<int>,
quickSort<int>};

I have to declare 3 function pointers to represent these template functions.
And then put these pointers into array:
//here I have to declare function pointer to "instanciate the template"
//otherwise compiler won't start compile template until it is in use
void (*fun1)(int array[], int size)=bubbleSort<int>;
void (*fun2)(int array[], int size)=selectSort<int>;
void (*fun3)(int array[], int size)=quickSort<int>;

//this is really what I intend to use---to declare a function array to
//hold the function pointer to
void (*sortFun[3])(int array[], int size)={fun1, fun2, fun3};



Conclusion: I remembered in your notes, you asked a question that is C++
template really passing type as parameter? (Something like this, I am not
sure.)  Any relation between these?

Thank you for your time,

Have a nice day,

Nick Huang/Qingzhe Huang

#include <iostream>
using namespace std;

class Test
{
public:
	Test(int n, char c='N') : val(n), name(c)
	{
		id = ++idNum;
		cout << "Construct " << id << " " << val <<"     "<<name<< endl;
	}

	Test(const Test & x) : val(x.val)
	{
		id = ++idNum;
		cout << "Copy " << id << " " << val <<"     "<<x.name<< endl;
	}

	~Test()
	{
		cout << "Delete " << id << " " << val <<"     "<<name<< endl;
	}
private:
	int id;
	int val;
	static int idNum;
	char name;
};

int Test::idNum = 0;

Test fun(Test t)
{
	t = Test(5);
	cout<<"-----------------\n";
	return t;
}

void main()
{
	Test a(3, 'a');
//	fun(a);
	cout<<"-----------------\n";
	Test b = fun(a);
}

运行结果：

Construct 1 3 a
-----------------
Copy 2 3 a
Construct 3 5 N
Delete 3 5 N
-----------------
Copy 4 5 N
Delete 3 5 N
Delete 4 5
Delete 1 3 a
Press any key to continue

问题：Could you figure out why there are two lines of "Delete 3 5 N"?

Is template in C++ implemented by a preprocessor?

Templates are expanded more or less like macros, that is, with no 
semantic processing.  Roughly, variables like <class T> are replaced by 
actual class names.  Then the whole mess is paased over to the compiler.

The problem with this is that the compiler's error messages relate to 
the expanded text.  If you write tricky template code, the error 
messages can be hard to understand.

<example>
error C2440: 'initializing' : cannot convert from 'class 
std::_Tree<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,struct std::set<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,struct std::less<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >::_Kfn,struct std::less<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >::const_iterator' to 'class std::_Tree<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,struct 
std::set<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,struct 
std::less<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > >,class 
std::allocator<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > > >::_Kfn,struct 
std::less<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > >,class 
std::allocator<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > > >::iterator'

No constructor could take the source type, or constructor overload 
resolution was ambiguous
</example>

Another problem with templates is that there is no standard way that 
compilers handle them.  As you say, some compilers require template 
declarations to be in the .h file, but this is not always true.

Blitz++ is a modern template library for numeric programming:

http://www.oonumerics.org/blitz/

If you click on "supported platforms", you will see that only some 
compilers can handle blitz code.  For Visual C++ 6.0, it says:

"Does not support member templates outside of class declarations, and 
crashes (CRASHES!) if you try to do so. Definitely not recommended."

A problem with tempates in header files is that the compiler may expand 
them every time it reads the header file, leading to the well-known 
phenomenon of "code bloat".

Hope this helps,
Peter


Hotmail wrote:
> Hi Professor,
>  
> I remembered that you said "c++ compiler doesn't understand template".  
> As I am taking comp442 compiler design, it hits me that maybe template 
> is only implemented with a preprocessor of c++ which treats template 
> more or less like a complicated Macro. Because only the semantic 
> analyzer understand the meaning of  program and the preprocessor is only 
> a scanner and parser. And what's more, the template part of codes can 
> never be compiled to object code for others. If we want to include a 
> template, we have to write it in the .h file. Whileas for other code, we 
> can compile the code to be .obj file and give out .h file for 
> interface.  Therefore, I highly suspect that template is only a kind of 
> Macro by a special preprocessor to convert.
>  
> I have a blur impression that you mentioned something about this in 
> lecture, but not quite sure.
>  
> Thank you for your time,
>  

If it is our professor's typical, luxury method of wasting precious memory by declaring useless

data structures as usual,  then just forget my question.

operator void*()

Please see following code segment:

	ifstream in("fileName");
	if (!in)
	{
		cout<<"file fileName  cannot open\n";
	}
	char buffer[256];
	while (in)
	{
		in.getline(buffer, 256);
		if (!in)
		{
			break;
		}
		cout<<buffer<<endl;
	}

This is quite simple code, and I believe almost everybody can tell me what is going on except for the "red line" part----    while (in)

Can anybody explain this line? ((///Disregard the following paragraph because what I want to say is not here.)

It is not so simple after you think carefully. You see a name for an instance is just like a variable which by

default has value of its address. We all know this by "cout<<in;" which will output an address. How can we break

the while loop by this "if" statement. The address of variable "in" never changes and will never become 0 unless

the file open operation fails. But if it DID FAIL, then it would never enter "while" loop, right?

It seems to make no sense, but this code works!!!

So, what on earth is going on? (The following is true even the above paragraph looks like garbage.)

The answer is overloading of "operator void*", I guess most of you have never heard about that because it is the

first time I hear about it today. :)  Let's use a simple example to explain it:

#include <iostream>

using namespace std;

class myTest
{
private:
	int data;
public:
	myTest(int num=5);
	void setData(int num){ data=num;}
	operator void*();  //operator void*
};


myTest::myTest(int num)
{
	data=num;
}

myTest::operator void *()
{
	if (data=4)
	{
		return NULL;
	}
	return this;
}

int main()

{

	myTest T;
	cout<<"ususally T will return its address---'this' pointer:"<<T<<endl;
	cout<<"but if you set data to be 4 and it will return NULL"<<endl;
	T.setData(4);
	cout<<(T==NULL?"it is NULL":"it is not null")<<endl;

        return 0;

}

1. There is such kind of "operator void*" that it almost makes the function like an variable itself. This is

also called "user-defined convertion operator".  This member function will only be invoked if you try to

evaluate it as an pointer. So, the "if" statement actually invoked the function.

2. IOSTREAM overloading the "operator void*" member function to make it return "NULL" ONLY IF the read operation

fails or the internal "failbit" is set. You can get detail about this by browsing the help on "basic_ios::fail".

(The following are also true...)        Sorry, I made some mistakes about above question...

    if (!in) ...    and while(in) are calling completely different functions of "ifstream" class:

"if (!in)" is calling "operator !()" and will return same value of "fail()" which is a bool-value-member method.

"while(in)" calling "operator void*()" which is only converted to 0 when "fail()&rdstate()".

    how to merge two sorted link list ?

void List::mergeTwoSortedLinkedLists(const List& aList,const List& bList)
{
	ListNode* mPtr, *aPtr=aList.head, *bPtr=bList.head, *nxtPtr;
	bool first=true;
	head=NULL;//you don't have to, but it is safe
	while (aPtr!=NULL||bPtr!=NULL)//at least one is not null
	{
		//to determine the next ptr to be inserted
		if (aPtr==NULL)//
		{
			nxtPtr=bPtr;
			bPtr=bPtr->next;//move to next
		}
		else
		{
			if (bPtr==NULL)
			{
				nxtPtr=aPtr;
				aPtr=aPtr->next;
			}
			else
			{
				//both are not NULL
				if (aPtr->item<bPtr->item)//suppose you have overloaded operator "<"
				{
					nxtPtr=aPtr;
					aPtr=aPtr->next;
				}
				else
				{
					nxtPtr=bPtr;
					bPtr=bPtr->next;
				}
			}
		}
		//we have to do the first specially
		if (first)
		{
			head=new ListNode;			
			head->item=nxtPtr->item;
			head->next=NULL;//initialize
			mPtr=head;
			first=false;
		}
		else
		{
			mPtr->next=new ListNode;
			mPtr=mPtr->next;
			mPtr->item=nxtPtr->item;
			mPtr->next=NULL;
		}
	}//end while
}

			
A simple example of initializing constant in class

#include <iostream>

using namespace std;

const int DefaultRoomNumber=10;

class Room
{
private:
	const int RoomNumber;
public:
	Room(int roomNumber=DefaultRoomNumber);
	void display();
};

class Floor
{
private:
	const int FloorNumber;
	Room room;
public:
	Floor(int floorNumber, int roomNumber);
	void display();
};



class APT
{
private:	
	Floor floors;
	const int APTNumber;
public:
	APT(int aptNumber, int floorNumber, int roomNumber);
	void display();
};


int main()
{
	APT apt(6644, 2, 4);
	apt.display();
	return 0;
}

Floor::Floor(int floorNumber, int roomNumber):room(roomNumber), FloorNumber(floorNumber)
{
	;
}

void Floor::display()
{
	cout<<"My floor number is "<<FloorNumber<<endl;
	room.display();
}

Room::Room(int roomNumber):RoomNumber(roomNumber)
{
	;
}

void Room::display()
{
	cout<<"My room number is "<<RoomNumber<<endl;
}

APT::APT(int aptNumber, int floorNumber, int roomNumber):
APTNumber(aptNumber), floors(floorNumber, roomNumber)
{
	;
}

void APT::display()
{
	cout<<"my address is apt# "<<APTNumber<<endl;
	floors.display();
}

The running result is like following:

my address is apt# 6644
My floor number is 2
My room number is 4
Press any key to continue

	The base class usually need a default constructor, but not always...

Question: Do you need a default constructor for your base class?

Answer: You do need a default constructor for your base class as your derived class need to choose a constructor of his 

"father's" unless you make some adjustment in constructor of derived class. See below:

#include <iostream>

using namespace std;


class Father
{
protected:
	char* name;
public:
	Father(const char* theName);
	void display();
	//Father();//you don't need a default constructor
};

class Son : public Father
{
public:
	Son(const char* theName);
};

int main()
{
	Son S("nick huang");
	S.display();
	return 0;
}

Father::Father(const char* theName)
{
	name=new char[strlen(theName)+1];
	strcpy(name, theName);
}

void Father::display()
{
	cout<<name<<endl;
}

//You need to initialize the base class's constructor properly
Son::Son(const char* theName):Father(theName)
{

}

The running result:

nick huang
Press any key to continue

	How to reverse a linked list?

question: You are given a linked list, or more precisely the pointer of type Link which points to the beginning of a linked list.

Write a function to reverse the elements in list.

void reverse(Node* head);

for example, the linked list is originally -1,41,67,34,0,69,24,78,58,62,64,
now reverse -1,64,62,58,78,24,69,0,34,67,41.

The -1 represents the head pointer. 

answer: There are many possible ways to solve this simple question, however, I found I am completely rely on compiler and tracer.

#include <iostream>

using namespace std;


struct Node
{
	Node* next;
	int data;
};

const int MaxNumber=10;

ostream& operator<<(ostream& out, Node* ptr);

void createNode(Node* head);
void destroyNode(Node* head);
void reverse(Node* ptr);

int main()
{
	Node head;
	head.data=-1;
	createNode(&head);
	cout<<&head<<endl;
	cout<<"now reverse\n";
	reverse(&head);
	cout<<&head<<endl;
	destroyNode(&head);

	
	return 0;
}

//to reverse a linked list, you first need to find the 
//new head and insert one by one.
void reverse(Node* ptr)
{
	//there are three cases that you don't have to do anything:
	//1. there is no head
	//2. there is no element in linked list
	//3. there is only one element in total linked list
	if (ptr==NULL ||ptr->next==NULL||ptr->next->next==NULL)
	{
		return;
	}
	Node* head, *tail, *oldTail, *oldHead;
	//tail is pointing to the first of linked list
	tail=ptr->next;
	head=ptr;
	//try to pin point head to the end of linked list
	while (head->next!=NULL)
	{
		head=head->next;
	}
	//remember the head
	ptr->next=head;
	//loop until the tail meets head...
	while (tail!=head)
	{
		//you need to remeber the sublist after new head
		oldHead=head->next;
		//you also need to remember the old sublist after tail
		oldTail=tail->next;
		//insert tail after head
		head->next=tail;
		tail->next=oldHead;
		//tail goes to next
		tail=oldTail;
	}
	//head->next=NULL;
}

//this is a good habit to release all those
//dynamic memory allocation
void destroyNode(Node* head)
{
	Node* temp1=head->next, *temp2;
	if (temp1==NULL)
	{
		return;
	}
	temp2=temp1->next;
	while (temp2!=NULL)
	{
		delete temp1;
		temp1=temp2;
		temp2=temp1->next;
	}
	delete temp1;
	head->next=NULL;
}

void createNode(Node* head)
{
	Node* temp=head;
	for (int i=0; i<MaxNumber; i++)
	{
		temp->next=new Node;
		temp=temp->next;
		temp->data=rand()%100;
		temp->next=NULL;
	}
}


ostream& operator<<(ostream& out, Node* ptr)
{
	Node* temp=ptr;
	while (temp!=NULL)
	{
		out<<temp->data<<",";
		temp=temp->next;
	}
	return out;
}

The running result is like following:

-1,41,67,34,0,69,24,78,58,62,64,
now reverse
-1,64,62,58,78,24,69,0,34,67,41,




    Even C++ forbids you to create instance of abstract class, but they don't forbid you to do it by array...

	See below, I can even instantiate it! 

#include <iostream>

using namespace std;

const int DefaultAge=20;
const int ArraySize=3;

class Father
{
protected:
	char* name;
public:
	Father(const char* theName);
	virtual void display()=0;
	void speak(){cout<<name<<endl;}
	//Father();//you don't need a default constructor
};

class Son : public Father
{
private:
	int age;
public:
	Son(const char* theName);
	void setAge(int theAge){age=theAge;}
	void display();
};

int main()
{
	Father fatherArray[ArraySize]=
	{
		Son("zhu chunming"), Son("huang yong"), Father("nick huang")
	};
	for (int i=0; i<ArraySize; i++)
	{
		fatherArray[i].speak();
	}	
	
	//Father F("okok");
	return 0;
}

Father::Father(const char* theName)
{
	name=new char[strlen(theName)+1];
	strcpy(name, theName);
}

/*
void Father::display()
{
	cout<<name<<endl;
}
*/

void Son::display()
{
	//Father::display();
	cout<<"my age is:"<<age<<endl;
}

//You need to initialize the base class's constructor properly
Son::Son(const char* theName):Father(theName)
{
	age=DefaultAge;
}

The running result is like this:

zhu chunming
huang yong
nick huang
Press any key to continue

        The template of VC6.0 has many problems, at least it is my personal view

The following simple example shows you how to pass with undetermined number of parameters and how to get them.

The macro in VC6.0 simply hide you the way they cope with different platform and compiler. In win32, vc6.0, you

can simply treat the parameter as null-terminated string and move the pointer with size of type, if the

alignment is what you immagined.

/* VA.C: The program below illustrates passing a variable
 * number of arguments using the following macros:
 *      va_start            va_arg              va_end
 *      va_list             va_dcl (UNIX only)
 */

#include <stdio.h>
#include <stdarg.h>

const int MaxItemLength=20;



class IntTest
{
public:
	void set(int first, ...);
};

class sonTest: public IntTest
{

};

int main()
{
	sonTest I;
	I.set(23, 45, 67, 3, -1);
	return 0;
}

void IntTest::set(int first, ...)
{
	int count = 0, i = first, test;
	va_list marker;
	char* ptr;
	ptr=(char*)(&first);
	
	//printf("%s\n", ptr);
	va_start( marker, first );     // Initialize variable arguments. 
	while( i != -1 )
	{
		test=*((int*)(ptr));
		printf("no. %d is:%d\n", count+1, i);
		printf("no. %d is:%d\n", count+1, test);
		ptr+=sizeof(int);
		count++;
		i = va_arg( marker, int);
	}
	va_end( marker );              // Reset variable arguments.      
 
}

The result is like this:

no. 1 is:23
no. 1 is:23
no. 2 is:45
no. 2 is:45
no. 3 is:67
no. 3 is:67
no. 4 is:3
no. 4 is:3
Press any key to continue

However, when I try to use template class, there is a problem. See the below code, the trick of char pointer

doesn't work!!! You will be only retrieve the first parameter. I have no idea why it happens except to attribute

it to the bugs of VC6.0.

/* VA.C: The program below illustrates passing a variable
 * number of arguments using the following macros:
 *      va_start            va_arg              va_end
 *      va_list             va_dcl (UNIX only)
 */

#include <stdio.h>
#include <stdarg.h>

const int MaxItemLength=20;

template<class T>
class VarList
{	
private:
	T buffer[MaxItemLength];
protected:
	virtual bool isEnd(T& item) =0;
public:
	T* set(const T& items, ...);
	virtual void display(T* list)=0;
};



class IntList : public VarList<int>
{
protected:
	virtual bool isEnd(int& item){ return item==-1;}
public:
	virtual void display(int* list);
};



int main( )
{
	
	IntList L;
	int* temp;
	temp=L.set(34,45, 23, 0, 9, -1);
	
	L.display(temp);
	
	return 0;
}


void IntList::display(int* list)
{
	int count=0;
	//item=list[count];
	while (!isEnd(list[count]))
	{
		printf("no. %d is: %d\n", count+1, list[count]);
	}
}

template<class T>
T* VarList<T>::set(const T& items, ...)
{	
	int count=0;
	char* ptr;
	ptr=(char*)(&items);
	
	//buffer[count]=items;
	//va_list marker;
	//va_start(marker, items);
	while (!isEnd(buffer[count])) 
	{
		
		for (int i=1; i<10; i++)
		{
			char* temp=ptr;
			int j;
			temp+=i;
			j=*((T*)(temp));
			printf("offset %d is:%d\n", i, j);
		}
		ptr+=sizeof(T)*2;
		buffer[++count]=*((T*)(ptr));
		
		//buffer[++count]=va_arg(marker, T);
	}
	//va_end(marker);
	return buffer;
}
		

 It is my greatest honour to receive encouragement from respectable professor Mr. Cliff Shaffer

Sorry to be so long in replying to your email!

Thank you for sharing your project code with me. I hope you learned from
doing this, and from the book.

Its a bit of a struggle to decide what to include in the book and what not
to include. Space is of course an issue. So is keeping focus for the
students by limiting what I include. One consideration is that I leave
enough potential exercises for students to work on. There's a lot of data
structures that I do not include code for in the book, but which I
mention. AVL trees is one of those. Certainly there are implementations of
AVL trees on the Internet. But I don't, and wouldn't, gather together a
collection of implementations for all of the data structures I mention.
Because if I did, that would reduce the number of good projects that
students could work on to learn things. 2-3 trees is another example where
I include some code but deliberately leave parts out. Because I, or
another instructor, might need a project to give out to the students. Or
an energetic student like yourself might wish to do the work on their own
so as to learn more.

Good luck with your studies!

--
Cliff Shaffer, Associate Professor          Phone: (540) 231-4354
Department of Computer Science              Email: shaffer@cs.vt.edu
Virginia Tech, Blacksburg, VA 24061-0106    WWW:   www.cs.vt.edu/~shaffer
-------------------------------------------------------------------------


On Wed, 14 Jul 2004, nick huang wrote:

Re: It is said that everyone can contribute a word, so my version of AVLTree maybe has some usage for others...

> Dear Professor Shaffer,
>
> It is difficult and disturbing to make a decision on whether to write to you or not.
> It has been almost one year since I study your book <A Practical Introduction to Data Structures and Algorithm Analysis> for my undergraduate "data structure" course in Concordia University, Montreal, Canada. I was so deeply impressed by your sample code which is so compact and concise, clear and clean that I practised for a lot.  However, for the AVLTree, you didn't give a sample code for implementation and I try to write some code following your theme. The insertion operation is OK, but the deletion is quite beyond my ability since no algorithm is introduced in your book. My modest wish is just to share my little experience and work with other students.  Of course I realized how naive the idea seems to be, however, it is the enthusiasm for C++ programming and computer science that encourage me to do this.
> The following link is my little code page of AVL tree:
> http://www.staroceans.com/AVLTree-remove.htm
>
> Thank you for your time and attentio