This question is to develop a program that solves systems of linear equations. Assume the number of equations is always the same as the number of unknowns. The general form of such a system is as follows:

*a*11*x*1 + *a*12*x*2 + … + *a*1*n**xn* = *b*1,

*a*21*x*1 + *a*22*x*2 + … + *a*2*n**xn* = *b*2,

…

*an*1*x*1 + *an*2*x*2 + … + *annxn* = *bn*.

Your program first asks the user to enter the number *n* of unknowns. Then ask the user to enter the coefficients and the constant term of each equation, one equation in one line. For instance, if *n* is 3, the user may enter the following:

120 -32.1 20.4 50

1.6 -3.5 2.7 1

-0.2 0.15 0.09 0

This input represents the following system of equations

120*x*1 -32.1*x*2 + 20.4*x*3 = 50,

1.6* x*1 -3.5* x*2 + 2.7* x*3 = 1,

-0.2*x*1 + 0.15*x*2 + 0.09* x*3 = 0.

A 2-dimensional array is built dynamically to store the input data (so-called the *augmented matrix* of the system of equations). Then use an algorithm, called *scaled Gauss elimination with backward substitution*, to solve this system of equations. The algorithm is as follows:

First, divide each of the equations by the coefficient that has the largest absolute value (not including the constant term) to convert this system to a so-called *normalized* system of equations. Then use the Gauss elimination algorithm:

Suppose the normalized system is as follows:

*a*11*x*1 + *a*12*x*2 + … + *a*1*n**xn* = *b*1,

*a*21*x*1 + *a*22*x*2 + … + *a*2*n**xn* = *b*2,

…

*an*1*x*1 + *an*2*x*2 + … + *annxn* = *bn*.

Find the coefficient in the first column (*a*11, *a*21, …, *an*1) with the largest absolute value. If *ai*1 is the largest, swap equation 1 with equation *i*. Then, we may assume *a*11 has the largest absolute value. If this value is zero, this system does not have a unique solution. Output an error message and terminate the program. Otherwise, denote the *i*-th equation by *Ei*. Replace *Ei* by *Ei* - *E*1 * (*ai*1 / *a*11), *i* = 2, 3, …, *n*. After that, in the first column, all coefficients under *a*11 become 0. The system has the following form:

*a*11*x*1 + *a*12*x*2 + … + *a*1*n**xn* = *b*1,

*a*22*x*2 + … + *a*2*n**xn* = *b*2,

…

*an*2*x*2 + … + *annxn* = *bn*.

Next, find the coefficient among *a*22, *a*32, …, *an*2 that has the largest absolute value. If *aj*2 has the largest absolute value, interchange *E*2 and *Ej*. Then we may assume *a*22 has the largest absolute value. If this value is zero, this system does not have a unique solution. Output an error message and terminate the program. Otherwise, Replace *Ei*, *i* = 3, 4, …, *n*, by *Ei* - *E*2 * (*ai*2 / *a*22). Then all coefficients under *a*22 become zero.

Keep doing this. Finally, we have a system that has the so-called *echelon* form:

*a*11*x*1 + *a*12*x*2 + *a*13*x*3 + … + *a*1*n**xn* = *b*1,

*a*22*x*2 + *a*23*x*3 + … + *a*2*n**xn* = *b*2,

…

* annxn* = *bn*,

where *aii* are not zero, *i* = 1, 2, …, *n*.

In the last step, find the values backwards: Form the last equation, we have

*xn* = *bn* / *ann*.

Substituting this value into the second last equation, we have

*xn*-1 = (*bn*-1- *an*-1, *n**xn*-1) / *an*-1, *n*-1.

In this way, we can find *xn*-2, *xn*-3, … . Finally,

*x*1 = (*b*1 - *a*12*x*2 - *a*13*x*3 - … - *a*1*n**xn*) / *a*11.

To make your calculation more accurate, all coefficients should be of the type **long double**. In this algorithm, we need to check whether a coefficient is zero. However, it is not good to compare a double value with zero because a real number may not be expressed by a binary number accurately. You should consider a value being zero if its absolute value is less than, say, 10-10.

At the end of the program, don't forget to free the memory used by the dynamic array.

2. This question is to review how to manipulate c-strings and linked lists. (Do not use C++ class string in this question).

You know that there is a method called *tokenize* in Java, which separates a string into parts according to a set of specified characters called delimiters. Unfortunately, there is no such built-in function in C++. This question is to write such a function *tokenize*( ). This function accepts two strings. The first string is to be tokenized, and the second string contains all delimiters. For instance, if the first string is "sin(x)+cos(y)-tan(z)", and the second string is "+_()", then this function should separate the first string into the following *tokens*:

"sin", "(", "x", ")", "+", "cos", "(", "y", ")", "-", "tan", "(", "z", ")"

Each delimiter is also regarded as a token.

Note that, if you have two delimiters side by side (as ")+" and ")-" in the previous example, you should not have an empty token between them.

Your function should return a linked list that stores the tokens of the input string in the same order as they are in the input string. The node of the linked list has the type

struct Node

{

char * token;

Node * link;

};

The member *token* should point to a dynamic string on the heap.

You will write another function, called *sort *( ), that creates another linked list that stores the tokens in the first string but in increasing order. Use the function strcmp ( ) to compare the strings. The tokens stored in the second list should be independent of the ones stored in the first list. In other words, the nodes in the second list should use operator new to create a new memory location, and copy the token from a node in the first list to a node in the second list.

In function main ( ), the program first asks the user to enter the delimiter string, and then enter the string to be tokenized. Use a separate function read_string ( ) to read these strings so that they are stored in dynamic strings on the heap with just enough space. In this read_string ( ) function, you may assume the length of the input strings is no more than 100. Then call function tokenize ( ) and function sort ( ) to build two lists of tokens. After these linked lists are constructed, output the tokens in the order as they are in these lists. In other words, the first output is the tokens in the same order as they are in the input string, and the second output is the tokens in an increasing alphabetical order.

You should deal with the case that one or both input strings are empty.

Don't forget to free the memory used by the strings and the nodes of the lists on the heap.