Session 3 Arrays




Yüklə 108.68 Kb.
tarix28.02.2016
ölçüsü108.68 Kb.


Session 3




Arrays




During this session you will learn about:



  • Some applications of Arrays.

  • Polynomial representation for one variable and two variables.

  • String Handling – Array of characters.

  • Two-dimensional arrays- Matrices.

  • Sparse Matrices.

  • Multidimensional Arrays.



3.1. Introduction
All the discussion in this book will be in context to the language C. Our main interest is to use memory effectively.
We have already learnt in the first session that when we need many data members of same type, which are related, we use arrays to represent them.
Now let us discuss some applications where arrays can be used.

3.2. Evaluation of Polynomials
3.2.1. Polynomial in a single variable
Polynomial is a expression of type :
P(x) = P0 + P1 X^1 + P2 X^2 + . . . . + Pn X^n.
Where n is called the degree of that polynomial.
One thing is very clear from the expression, which contain only one variable x, is that we will require storing for each item its coefficient and its power. The following structure would serve the purpose:
struct polyno

{

float coef;



int pw;}

Then we may proceed with the declaration of an array of structures.


struct polyno P[SIZE];
Array as a data structure will have many applications and also very important facilities. But size limitations will appear as a setback for this choice. The degree of the polynomial will decide the size of the array.
( size of the polynomial ) = (degree of polynomial ) + 1
But as we are going to input any polynomial, the size i.e. the degree is not known. Hence let us decide the array size bigger than the normal value polynomial say 10 or 100. We have to keep this limitation in mind when using the program.
Now also observe that the degree of each term is an integer and so is the index of the array. Now we may say that the position of the coefficient in the array itself is the degree of x with it. Then we may not even require the array of structures, but even a float array of coef will work.
e.g.

coef[0] is coefficient of x^0

coef[1] is coefficient of x^1

:

:



coef[i] is coefficient of x^i
The input may be taken in two ways:


  1. Ask for coefficient, every time display the power of x i.e.

Please input the coefficient of [x^0]:

Please input the coefficient of [x^1]:
Here it will be totally the user’s responsibility to give the coefficient as zero if a particular power is absent.


  1. Ask the user to input the power and coefficient. Here the user should carefully input all values without repeating any power because we will be directly storing the coefficient at the power location. Here user doesn’t have to input all the zero coefficients. It is the programmer’s responsibility now to initialize the array with zeroes so that if a particular power is not entered then its coefficient is automatically zero.

Now, we can declare the array as :

float coef[SIZE];


3.2.2. Polynomial in Two variables

Now if we are given a polynomial having two variables per term, i.e. for example :


P( x, y) = 3x3y – 4x2y4 + 6x – 7y3 + 18 xy
Here we cannot employ the previous method and so we have to go back for declaring a structure as follows :
struct poly2

{

float coef;



int pwx, pwy;

};

The following is the program, which deals with the polynomials in one variable. It is implemented using array of structures. The terms are stored in the sequence given by the user. Hence we have to scan the second polynomial to match the power when we perform addition. Also, we are required to remember whether a particular term is added or not. We can use a flag for this purpose.



Program 3.2.2. Addition of polynomials in single variable
# include

# include

# define size 10
int n1, n2, n3;
struct polyx

{

float coef; /*coefficient of each term, with sign */



int pw, flag;

}p1[size],p2[size],p3[size];


void read_poly( struct polyx p[], int n); /* to read

polynomial of size n*/
int add_poly(struct polyx p1[],int n1,

struct polyx p2[], int n2,

struct polyx p3[]);
int find_pos( struct polyx p[], int n, int power);
void print_poly( struct polyx p[], int n);
float pwr( float x, int n); /* to evaluate x to

the power n */


main()

{

clrscr();



printf(“Enter the no of terms:”);

scanf(“%d”,&n1);

printf(“\n Enter the data for first polynomial\n”);

read_poly(p1,n1);


printf(“Enter the no of terms:”);

scanf(“%d”,&n2);

printf(“\n Enter the data for second polynomial\n”);

read_poly(p2,n2);


n3= add_poly(p1,n1,p2,n2,p3);
printf(“ The first polynomial is….\n”);

print_poly(p1,n1);


printf(“ The second polynomial is….\n”);

print_poly(p2,n2);


printf(“ The resultant polynomial is….\n”);

print_poly(p3,n3);


} /* main ends */

/*********** function to read polynomial ************/


void read_poly(struct polyx p[], int n)

{

int i=0;


for( i= 0; i

{

printf(“ Give power…”);



scanf(“%d”,&p[i].pw);

printf(“Give coeff…”);

scanf(“%d”, &p[i].coef);

p[i].flag=0;

}

}

/************** Addition of poly*********************/


int add_poly(struct polyx p1[],int n1,struct polyx p2[],

int n2,struct polyx p3[])

{

int i=0, j=0,k=0,n3=0;


n3 = n1;
do

{

j = find_pos(p2,n2,p1[i].pw); /* having power*/



/* p1[i].pw in p2*/

if( j == -1) /* -1 indicates it is absent */

{

p3[k].pw = p1[i].pw;



p3[k].coef = p1[i].coef;

p1[i++].flag = 1;

}

else


{

p3[k].pw = p1[i].pw; /*when the term is */

present */

p3[k].coef = p1[i].coef;/* coef added*/

p1[i++].flag = 1; /* flag set to 1*/

p2[j++].flag = 1; /* flag indicates that

/* the tern has*/ /*been considered */

k++;


}

}while( j
j= 0;
while( j < n2)

{

if(p2[j].flag = = 0) /* search for the term in p2 */



/* whose flag is 0 */

{ /* add such a term */

p3[k].pw = p2[j].pw;

p3[k].coef = p2[j].coef;

k++;

n3++;


}
j++;

}

return ( n3);



}

/** find the position of the term, which has the given power **/


int find_pos( struct polyx p[], int n, int power)

{

int i =0;



while( i < n)

{

if( p[i].pw == power)



return(i);

else


i++;

}

return(-1);



}

/************* prints the polynomial ******************/


void print_poly( struct polyx p[], int n)

{

int i=0;



for(i=0;i

if(p[i].coef != 0 )

printf(“%2.2f[x^%d]+”, p[i].coef,p[i].pw);

printf(“%2.2f[x^%d]\n”, p[i].coef,p[i].pw);

}

/********to evaluate x to the power n *****************/



/* ( considers positive as well as negative powers ) */
float pwr( float x, int n)

{

int i=0, m;



float p=1;

if(n <0 )

m= -n;

else


m=n;
while(i < m)

{

p=p*x;



i++;

}

if( n >=0)



return p;

else


return (1/p);

}

Output:


Enter the no of terms: 3
Enter the data for first polynomial

Give power…1

Give coef… 3.000000

Give power…4

Give coef… -4.000000

Give power…3

Give coef… 2.000000
Enter the no of terms: 2
Enter the data for second polynomial

Give power…4

Give coef… -1.000000

Give power…2

Give coef… 1.000000
The first poly is….

3.00[x^1] + -4.00[x^4] + 2.00[x^3] + 0.00[x^0]


The second poly is….

-1.00[x^4] + 1.00[x^2] + 0.00[x^0]


The resultant polynomial is.. .

3.00[x^1] + -5.00[x^4] + 2.00[x^3] + 1.00[x^2]+ 0.00[x^0]


You can try other operations like subtraction and multiplication of two polynomials on these. You may write programs to perform these functions on polynomials with two variables.

3.3. Strings
A string is an array of characters. They can contain any ASCII character and are useful in many operations. A character occupies a single byte. Therefore a string of length N characters requires N bytes of memory. Since strings do not use bounding indexes it is important to mark their end. Whenever enter key is pressed by the user the compiler treats it as the end of string. It puts a special character ‘\0’ (NULL) at the end and uses it as the end of the string marker there onwards.

When the function scanf() is used for reading the string, it puts a ‘\0’ character when it receives space. Hence if a string must contain a space in it we should use the function gets().



3.4. String Functions
Let us first consider the functions, which are required for general string operations. The string functions are available in the header file “string.h”. We can also write these ourselves to understand their working. We can write these functions using


  1. Array of Characters

  2. Pointers



3.4.1. String Length
The length of the string is the number of characters in the string, which includes spaces, and all ASCII characters. As the array index starts at zero, we can say the position occupied by ‘\0’ indicates the length of that string. Let us write these functions in two different ways mentioned earlier.
3.4.1.1. Using Arrays
int strlen1(char s[])

{

int i=0;



while(s[i] != ‘\0’)

i++;


return(i);

}

Here we increment the positions till we reach the end of the string. The counter contains the size of the string.




3.4.1.2. Using Pointers

int strlen1(char *s)

{

char *p;


p=s;

while(*s != ‘\0’)

s++;

return(s-p);



};
The function is called in the same manner as earlier but in the function we accept the start address in s. This address is copied to p. The variable s is incremented till we get end of string. The difference in the last and first address will be the length of the string.

3.5. String Copy : Copy s2 to s1


In this function we have to copy the contents of one string into another string.
3.5.1. Using Arrays
void strcopy(char s1[], char s2[])

{

int i=0;



while( s2[i] != ‘\0’)

s1[i] = s2[i++];

s1[i]=’\0’;

}
Till ith character is not ‘\0’ copy the character s and put a ‘\0’ as the end of the new string.

3.5.2. Using Pointers
void strcopy( char *s1, char *s2)

{

while( *s2)



{

*s1 = *s2;

s1 ++;

s2 ++;


}

*s1 = *s2;

}

3.6. String Compare


3.6.1. Using Arrays
void strcomp(char s1[], char s2[])

{

int i=0;



while( s1[i] != ‘\0’ && s2[i] != ‘\0’)

{

if(s1[i] != s2[i])



break;

else


i++;

}

return( s1[i] – s2[i]);



}

The function returns zero , if the two strings are equal. When the first string is less compared to second, it returns a negative value, otherwise a positive value.


The reader can write the same function using the pointers.

3.7. Concatenation of S2 to the end of S1



At the end of string one add the string two. Go till the end of the first string. From the next position copy the characters from the second string as long as there are characters in the second string and at the end close it with a ‘\0’ character. This is left as an exercise for the student.

3.8. Two Dimensional Arrays


We have already seen how a two dimensional array can be represented in C, in session 1. Now we can see how it is represented in the memory.
Like we have a linear array with single index, we can also have multidimensional arrays with n indexes. At present we will discuss about two-dimensional array, Matrix. They are identified with two indices, one is row index and another is the column index. If there are m rows and n columns in the matrix we say the matrix is of the order (m x n). The pictorial representation is:
0 1 2 3 n-2 n-1



0 Position(1,n-1)

1

m

rows


m-1 Pos(m-1, n-1)
n columns
fig 1. Matrix of size m x n
While indicating the position (i,j), i will always be row and j will always be the column number. The names i and j are not important but their position is always very important.

We should always put the condition on the number of variables i.e. row number and column number up to the maximum row and column number. This is very essential to avoid undesirable errors. As we have already seen that the address arithmetic row number will start from 0 up to (m-1) and column numbers will start from 0 to (n-1).


Let us see how they are stored in the memory. They may be stored row-wise( row major) or column-wise( column major). Most of the languages use row major method. This is required because memory of the computer is always one-dimensional. Therefore for a matrix a linear memory of size (m x n) will be allocated. Hence in the first n locations we will have 0th row, in the next n location we will have 1st row and so on.

0th row 1st row m-1th row










































0 1 2 . . . . n-1 n n+1. . . . 2n-1. . . (m-1)n . . . . mn-1

(0,0)(0,1). . .(0,n-1). . . (1,0)(1,1). . .(1,n-1). . .

(m-1,0)(m-1,1) . . .(m-1,n-1)


fig 2. memory representation of a two dimensional array

Now we can even find from the position (i,j) , the actual location of in the one-dimensional memory. When we are in the ith row, we know that (i-1) rows are before it and each having n memory locations. Therefore (i-1)*n memory locations should be skipped to reach ith row. It may appear to be confusing as when we refer to ith row, the row number is actually (i-1) and ( as our counting begins at 0 rather than 1) hence 1st row will be row number 0 which means that the row number itself will indicate as how many rows are complete prior to it.


e.g.
Row number 3 i.e. 0,1,2,3, is actually the 4th row and therefore 3 rows are completed before we reach it.
Hence to reach position (i,j), we should skip (i * n) locations of complete rows and j locations for filled locations in that row. Hence the relative address will be ( i*n+j).
(0,0)-> (0*n+0) -> 0

(1,4)-> (1*n+4) -> n+4

(5,2)-> (5*n+2) -> 5n+2 … etc.

(m-1,n-1)-> ((m-1)*n + (n-1))

-> mn – n + n +1

Now we may also be required to reverse the job, i.e. if we are given a position in one-dimensional memory, we should be able to find row number and column number. If p is the position, then the row number will be ( p / n+0) and the column number will be ( p % n).


Consider some basic definitions related to matrices.


  1. Matrix is said to be square if number of rows is equal to the number of columns . i.e. m=n.

  2. When only the diagonal elements of the square matrix are 1, and every other element is zero, it is called as Identity matrix.

  3. In a square matrix, position wise the elements are divided as :

    • Diagonal elements

    • Lower triangle, i.e. elements below the diagonal.

    • Upper triangle, i.e. elements above the diagonal.


Upper Triangle

Lower

Triangle



Diagonal
Fig 3. two dimensional matrix with classifications.


  1. Reading or referring to the elements row wise. In this we will refer the elements in a particular row one by one, i.e. row number remains same in the process but the column numbers will vary. Similarly we can also refer to the elements column-wise.

  2. Transpose of the matrix is changing the row elements to the column elements. i.e. the element in the (i,j) position will occupy (j,i) position in the transpose. The transpose matrix will have the size n x m.

  3. Symmetric matrix is a square matrix whose transpose is

identical to the original matrix.

Some functions you may use with respect to matrices :



  1. Read a matrix row-wise/ column-wise.




    1. When the number of rows and columns are read outside the function .

void readmat(int a[][SIZE], int m, int n)

{

int i,j;
for(i=0;i

for(j=0; j

{

printf(“ Enter elements for a[%d][%d]=”,i,j);



scanf(“%d”,&a[i][j]);

}

}




    1. When the number of rows and columns are read inside the function. Since these changes have to be reflected back to calling function we use pointer variables as arguments.

Void readmat(int a[][SIZE], int *m, int *n)

{

int i,j;
printf(“ Enter the order of the matrix “ );



scanf(“%d %d”,m,n);

for(i=0;i< *m;i++)

for(j=0; j< *n;j++)

{

printf(“ Enter elements for a[%d][%d]=”,i,j);



scanf(“%d”,&a[i][j]);

}

}




  1. Print the matrix.

Void printmat(int a[][SIZE], int m, int n)

{

int i,j;
for(i=0;i

{

printf(“ Enter elements for a[%d][%d]=”,i,j);

printf(“%d”,a[i][j]);

}

}





  1. Find the sum of the upper triangle , diagonal and lower triangle matrix elements.

int lowmat(int a[][SIZE], int n)

{

int i,j,sum1=0;


for(i=0;i

for(j=0;j

{

sum1=sum1+a[i][j];



}

return(sum1);

}
The above function considers a square matrix of size n . To find the sum of the upper triangle elements just interchange i and j in the statement sum1=sum1+a[i][j] and make it sum1=sum1+a[j][i]. To find the sum of the diagonal elements put a check condition of whether it is equal to j before finding the sum1. These two functions are left to the students.


  1. Checking whether a matrix is symmetric or not.

For this, the matrix has to be a square matrix and the element at every position (i,j) must be same as that of the element at the position (j,i).


Int sym_mat(int a[][SIZE], int n)

{

int i,j;


for(i=0;i

for(j=0;j

{

if(a[i][j] != a[j][i])



return(0);

else


return(1);

}

}





  1. Printing the transpose/ storing the transpose.

To interchange ith row with jth row, we should swap( exchange) the elements in the columns:


void swap_row(int a[][SIZE],int i, int j, int n)

{

int k,temp;


for(k=0;k

{

temp = a[i][k];



a[i][k]= a[j][k];

a[j][k]=temp;

}

}

3.9. Sparse Matrix


A matrix in which majority of the elements are zeroes they are known as Sparse matrices.
Generally in scientific calculations, a matrix with hundreds of rows and columns may be required. The elements required could be very few and remaining positions are filled with zeroes. For example, in a 10 x 10 matrix, only 15 elements are non-zero and the remaining 85 locations contain zeroes. In such cases we can store the matrix in a different form. The representation we will be using is a one-dimensional array where each data item is required to store three things.
1. Row number 2. Column number 3. Value
Hence, we will use a structure for this case :
struct sparse

{

int row, col, val;



}sp[SIZE]; /* SIZE is declared as required */
Here, we are declaring sp as one-dimensional array of structures. Now this array can represent a matrix having any number of rows and columns but the only restriction is that the number of nonzero elements should not exceed SIZE.
e.g.

matrix A Row/Col 0 1 2 3 4





  1. 2 0 0 -3 0

  2. 0 0 11 0 0

  3. 0 -7 0 0 1

3 –4 0 0 0 0
fig 4. matrix of order 4 X 5

Sparse Representation:


0 1 2 3 4 5 6 7



row 4 0 0 1 2 2 3 3


col 5 0 3 2 1 4 0 4
val 7 2 -3 11 -7 1 -4 9

fig 5. sparse representation of fig 4.


Here the position 0 in the sparse matrix representation actually informs about the total number of rows , total number of columns and number of non-zero elements.
Figure 5 shows as to how a particular matrix has been stored in rows, columns and val form. Here we should preferably take the row number in ascending manner and for each row we must take the columns in ascending manner. This is not a rule but it helps in a number of applications.
The next question is how to take the input from the user. One way is to accept the full matrix and then converting it to the sparse form. The other way is to ask the user to input the row number, col number and val.
Now for the first method it is a simple matrix reading.

for(i=0; i

for(j=0; j

{

scanf(“%d”,&a[i][j]);


if(a[i][j] != 0)

{

sp[k].row=i;



sp[k].col=j;

sp[k].val=a[i][j];

k++;

}

}


[OR]
ans = 1;

do

{



scanf(“%d %d%d”,&sp[k].row,&sp[k].col,&sp[k].val);

k++;


printf(“ \n Any more values ? ( 1= Yes / 0=No)”);

scanf(“%d”,&ans);

}while(ans==1);
Both these operations will work in an identical way and will generate sp array correctly. Now once the matrix is read properly, the next job is to perform operations like addition, multiplication etc.
Algorithm


  1. To add two sparse matrices, every time we will check whether row numbers are same.

  2. If not then copy the smaller row value element into the resultant and increment in that array.

  3. Otherwise check the column number, if they are not same, then again copy the smallest element into the resultant and increment that array.

  4. When the row numbers and the column numbers are same , we will add the elements and store them into the resultant.

The advantage of the addition of the two sparse matrices is that irrespective of their size we can add two matrices. We can understand this concept by checking the working of the following program.

# define

# define SIZE 10


/* new data type SPR with three elements has been defined */


typedef struct sparse

{

int row,col,val;



} SPR;
/* this function reads the matrix in normal form */
void readmat(int a[][SIZE], int m, int n)

{

int i,j;



for(i=0; i

for(j=0; j

scanf(“%d”,&a[i][j]);

}


/* a function which converts the matrix into sparse form */

int make_sparse( int a[][SIZE], int m, int n, SPR s1[])

{

int i,j,k=1;


for(i=0; i

for(j=0; j

if(a[i][j] != 0)

{

s1[k].row=i;



s1[k].col=j;

s1[k].val=a[i][j];

k++;

}
s1[0].row=m; /* first position contains */



s1[0].col=n; /* no of rows, columns and */

s1[0].val=k; /* non-zero elements */

return(k);

}

/* a function which displays sparse form of the matrix */


disply_spr(SPR s[], int n)

{

int i;



printf(“ Row \t Col \t Val \n”);

printf(“----------------------\n”);


for(i=0;iprintf(“%d\t%d\t%d\n”,s[i].row,s[i].col,s[i].val);

}

/********** main() *********/


main()

{

int a[SIZE][SIZE], b[SIZE][SIZE],i,j,k,m,n,i1,i2,n1,n2,i3,n3;



SPR s1[SIZE][SIZE],s2[SIZE][SIZE], s3[SIZE][SIZE] ;

i1=i2=i3=1;

clrscr();
printf(“Enter the matrix A:\n”);

printf(“Size of matrix A:”);

scanf(“%d %d”,&m,&n);

printf(“Please input the matrix A:\n”);

read_mat(a,m,n);

n1= make_sparse(a,m,n,s1);

display_spr(s1,n1);
printf(“Enter the matrix B:\n”);

printf(“Size of matrix B:”);

scanf(“%d %d”,&m,&n);

printf(“Please input the matrix A:\n”);

read_mat(b,m,n);

n2= make_sparse(b,m,n,s2);

display_spr(s2,n2);
s3[0].row = s1[0].row > s2[0].row ? s1[0].row : s2[0].row;

s3[0].col = s1[0].col > s2[0].col ? s1[0].col : s2[0].col;


while( i1 < n1 && i2 < n2) /* till none of the sparse */

{ /* matrix ends /

if(s1[i1].row == s2[i2].row)

{

if(s1[i1].col == s2[i2].col)



{

s3[i3].row=s1[i1].row; /* when row and col */

s3[i3].col=s1[i1].col; /* are same copy them */

s3[i3].val = s1[i1].val + s2[i2].val; /* add

them*/
i1++;

i2++;


i3++;

}

else if( s1[i1].col < s2[i2].col)



{

s3[i3].row=s1[i1].row; s3[i3].col=s1[i1].col;

s3[i3].val = s1[i1].val;
i1++;

i3++;


/* when col.no of first is less than the*/

/* col.no of second copy the 1st element */

}

else


{

s3[i3].row=s2[i2].row; s3[i3].col=s2[i2].col;

s3[i3].val = s2[i2].val;
i2++;

i3++;


/* when col.no of first is more than the*/

/* col.no of second copy the 2nd element */

}

}

else if( s1[i1].row < s2[i2].row)



{

s3[i3].row=s1[i1].row; s3[i3].col=s1[i1].col;

s3[i3].val = s1[i1].val;
i1++;

i3++;


/* when row.no of first is less than the*/

/* row.no of second copy the 1st element */


}

else


{

s3[i3].row = s2[i2].row;

s3[i3].col = s2[i2].col;

s3[i3].val = s2[i2].val;


i2++;

i3++;


/* when row.no of first is more than the*/

/* row.no of second copy the 2nd element */

}

}

}


while( i2 < n2)

{

s3[i3].row = s2[i2].row;



s3[i3].col = s2[i2].col;

s3[i3].val = s2[i2].val;


i2++;

i3++;


/* when the first matrix ends */

/* but the second does not then */

/* copy the remaining elements of */

/* 2nd matrix */

}
while( i1 < n1)

{

s3[i3].row = s1[i1].row;



s3[i3].col = s1[i1].col;

s3[i3].val = s1[i1].val;


i1++;

i3++;


/* when the second matrix ends */

/* but the first does not then */

/* copy the remaining elements of */

/* first matrix */

}

n3 = i3;


s3[o].val=n3;

printf(“ADDED MATRIX IS ...\n”);

display_spr(s3,n3);

}
Output:

Enter the matrix A:
Size of matrix A: 4 5
Please input the matrix:
2 0 0 -3 0

0 0 4 0 -1

0 0 0 5 0

0 6 0 0 0


Row Col Val

--------------

5 4 7

0 0 2


0 3 -3

1 2 4


1 4 -1

2 3 5


3 1 6
Enter the matrix B:
Size of matrix B: 3 4
Please input the matrix:
2 0 0 0

0 -3 -2 0

0 0 0 11
Row Col Val

--------------

4 3 5

0 0 2


1 1 -3

1 2 -2


2 3 11
ADDED MATRIX IS . . .

Row Col Val

--------------

5 4 8


0 0 4

0 3 -3


1 1 -3

1 2 2


1 4 -1

2 3 16


3 1 6

3.10. Multiplication of the sparse matrices:


Now let us consider a problem of multiplying two sparse matrices. It probable could be very difficult as we do not even know the size of the matrices. Secondly, the other matrix, to which the first matrix is going to be multiplied should satisfy the condition, i.e. number of columns of the first matrix must be equal to the number of rows of the second matrix. In sparse matrix we can always add a row of zeroes or a column of zeroes so that the size barrier doesn’t exist. Another thing is that we should take transpose of the second matrix or arrange it column-wise so that during multiplication, instead of row of the first into column of the second, we may have row-to-row multiplication and the result will be the same.
First we should write a function of taking the transpose of the sparse matrix. If you look at the definition of the transpose, which says that (i,j) element in the original matrix will have the position(j,i) in transpose, we get the idea that we should interchange the row number and the column number. This can be very easily done as given below:

for(i=0; i

{

temp = sp[i].row;



sp[i].row = sp[i].col;

sp[i].col = temp;

}
But then it won’t follow the sorted nature of the matrix, i.e. row wise arrangement of elements. hence, we will have to sort sp. Now, the two matrices , sp1 and sp2, are ready for multiplication and the result is to be stored in the matrix sp3.
The pseudo code is given below. You may write the program and implement it.


  1. sp1 is first matrix and sp2 is the second matrix in the transpose form.

  2. Let M1 and M2 be number of elements in the matrices sp1 and sp2.

  3. i and j are positions of sp1 and sp2 and k for sp3.

  4. i=0, j=0, k=0

  5. sp3[k].row = i

sp3[k].col = j

sp3[k].val = 0



  1. if(sp1[i].col = sp2[j].col)

{

sp3[k].val += sp1[i].bval * sp2[j].val;

i++;

j++;


}


  1. if(sp1[i].col < sp2[j].col)

i++;

else


j++;

  1. if((sp1[i].row = sp3[k].row) &&

( sp2[j].row=sp3[k].row))

goto step 6;


Using the above steps, the user is advised to write a program for the multiplication of the sparse matrices.

3.11. Multidimensional Arrays:



We can have three dimensional array or even more. The three dimensional arrays will have as usual two indexes for row number and column number and the third index for page number.
Column

Row









Page

Fig 6. Multidimensional array

We normally read data page wise. This will be used only in case of specific applications where all the data under consideration is related to each other by the position specification. By three dimensional or more dimensional array, the physical interpretation is rather difficult to imagine. When we learn about other data structures and after considering the memory requirement, compared to the utilization of the memory in multidimensional arrays, we may choose some other data structure (very effective) related to the specific application.

Exercises:




  1. Write a program to add an element into the array and delete an element from the array.

  2. Write a program to add and multiply two matrices in normal form.

  3. Write a program to multiply two matrices in Sparse representation for which the algorithm is given in the chapter.

  4. WAP (write a program ) for the transpose of the sparse matrix.

  5. Discuss the limitations and advantages of the array as a data structure.

Data Structures with ‘c’




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə