数据结构的基础作业，编写Vector类，以及该类的方法。
Purpose
The purpose of this exercise is to give you more practice with the first few
items listed below. Additionally, I will introduce some concepts having to do
with vector spaces, including the Gram-Schmidt process for orthonormalizing a
vector set. This will lead you down the path of discovery that theoretically
sound mathematical algorithms can fail when applying a numerical method
without consideration to detail (in particular, numerical representation and
round-off error).
- templated classes
- templated functions
- overloading operators
- the STL; in particular, the vector class
- the concept of possibly implementing algorithms as classes
- the Gram-Schmidt process for orthonormalizing a set of vectors
The Concept
As will be discussed in class, you (will) know that a n-dim vector space can
be spanned by a set of n linearly independent vectors. If this set is
orthogonal, all the better. If they are orthonormal, better yet. This spanning
set is called a “basis” for the space. You are familiar with this concept from
calc III, as i, j, and k, the unit vectors in the x, y, and z, directions,
form a basis for R3. Thus, v = (4,5,6) can be written as a linear combination
of the basis vectors i, j, and k, v = 4i + 5j + 6k. You can do this with any
arbitrary vector V = (X,Y,Z). A basis doesn’t have to be a set of unit vectors
(length = 1), nor do they have to be orthogonal vectors. It is good to have a
basis for a vector space, but it is better to have an orthonormal basis. This
is where the Gram-Schmidt process comes into play. This process will turn an
arbitrary basis for a real vector space into a orthonormal basis. Cool! I will
discuss how it works in class.
Program Specifications
You are to implement the Gram-Schmidt process. You will start by writing your
own vector class. I suggest you model your vector class after the array class
I presented in class; start with that and develop it. You decide on the
details of the implementation. Make it good: include adequate constructors
(including a move), overloaded functions (operators), etc. In considering the
implementation of the Gram-Schmidt, you will have to think about the
functionality of this class (inner products? scalar products?).
You will use the STL vector class to contain objects of your own class-type
vectors. Thus, you will be manipulating a Vector of vectors to accomplish what
the Gram-Schmidt process does. Your design here is not going to stray too far
from that of the previous assignment. You will represent the process as a
class again.
Among other considerations for this assignment, you will have to give
attention to memory dynamics – the allocation and use of that very resource.
Consider how you will use memory, how you will program your vector class, how
STL Vectors use memory.
Again, I want you to have your program read in data from a file. The data to
run your program on is:
1 0 1 2 1
0 1 0 1 1
1 1 0 1 2
2 0 0 0 1
1 0 1 1 1
The format of the file(s) to be read in will be as follows:
first value is an int specifying the number of elements in each vector and the
number of vectors in the file.
the vectors will be listed in the file one vector to a row. example:
3 6 8 0
1 2 3 4
4 6 8 9
2 0 5 7
the vector components may be float types
Make your program accept command-line arguments so that a user can specify the
name of the file to be read from. Your program is to output the
orthonormalized set of vectors in some easy to read format. It should also
output the inner product of each of these vectors with each of the other
vectors. If the number of vectors is n, then you should have n2(n square) real
numbers to output here. What should their values be? Does your program work?
Deliverables
- Code: I will test that the code you submit does indeed compile and run. You are to submit all your source code along with a makefile. How to do this is explained in Submission procedure.
- makefile: Supply the makefile which compiles and builds your program as detailed above. I really suggest that you play around with and use the third of the makefiles I posted.
- Your gradesheet and UML (during class).
- And here is a note from your grader about formatting your output:
- Go ahead and output the vectors you read in, one per line
- Next, output the orthonormal basis, again one per line
- Lastly, output the inner product between each vectors, again one per line.
As before, you may put notes preceded by # or followed by :, and blank lines
are OK.
