Program No : 1
AIM :
To find the sum of two sparse polynomials using array .
ALGORITHM :
Step 1: Start.
Step 2: Read the number of terms n1 of the first polynomial P1.
Step 3: Input the terms (coeff, expo) of P1 in descending order of exponents.
Step 4: Read the number of terms n2 of the second polynomial P2.
Step 5: Input the terms (coeff, expo) of P2 in descending order of exponents.
Step 6: Initialize indices: i = 0 (for P1), j = 0 (for P2), k = 0 (for result).
Step 7: While i < n1 and j < n2, do the following:
Step 7.1: Compare exponents P1[i].expo and P2[j].expo.
Step 7.2:
If P1[i].expo == P2[j].expo, then:
Calculate sum = P1[i].coeff + P2[j].coeff.
If sum != 0, assign result[k].coeff = sum and
result[k].expo = P1[i].expo.
Increment k, i, and j.
Step 7.3:
Else if P1[i].expo > P2[j].expo, then:
Assign result[k] = P1[i].
Increment k and i.
Step 7.4:
Else (P1[i].expo < P2[j].expo), then:
Assign result[k] = P2[j].
Increment k and j.
Step 8: Copy any remaining terms from P1 to result (while i < n1):
Assign result[k] = P1[i].
Increment k and i.
Step 9: Copy any remaining terms from P2 to result (while j < n2):
Assign result[k] = P2[j].
Increment k and j.
Step 10: Store the total number of terms in result as n3 = k.
Step 11: Print the polynomial represented by result array.
Step 12: Stop.
PROGRAM :
#include <stdio.h>
#define MAX 100
typedef struct {
int coeff;
int expo;
} Term;
void addPolynomials(Term p1[], int n1, Term p2[], int n2, Term result[], int *n3) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (p1[i].expo == p2[j].expo) {
int sum = p1[i].coeff + p2[j].coeff;
if (sum != 0) {
result[k].coeff = sum;
result[k].expo = p1[i].expo;
k++;
}
i++;
j++;
} else if (p1[i].expo > p2[j].expo) {
result[k++] = p1[i++];
} else {
result[k++] = p2[j++];
}
}
while (i < n1) result[k++] = p1[i++];
while (j < n2) result[k++] = p2[j++];
*n3 = k;
}
void printPolynomial(Term poly[], int n) {
for (int i = 0; i < n; i++) {
if (poly[i].expo != 0)
printf("%dx^%d", poly[i].coeff, poly[i].expo);
else
printf("%d", poly[i].coeff);
if (i != n - 1)
printf(" + ");
}
printf("\n");
}
int main() {
Term P1[MAX], P2[MAX], sum[MAX];
int n1, n2, n3;
// Input polynomial 1
printf("Enter number of terms in first polynomial: ");
scanf("%d", &n1);
printf("Enter terms (coeff exponent) in descending order:\n");
for (int i = 0; i < n1; i++) {
printf("Term %d: ", i + 1);
scanf("%d %d", &P1[i].coeff, &P1[i].expo);
}
// Input polynomial 2
printf("Enter number of terms in second polynomial: ");
scanf("%d", &n2);
printf("Enter terms (coeff exponent) in descending order:\n");
for (int i = 0; i < n2; i++) {
printf("Term %d: ", i + 1);
scanf("%d %d", &P2[i].coeff, &P2[i].expo);
}
// Add polynomials
addPolynomials(P1, n1, P2, n2, sum, &n3);
// Print result
printf("Sum of the polynomials: ");
printPolynomial(sum, n3);
return 0;
}
OUTPUT :
Enter number of terms in first polynomial: 3
Enter terms (coeff exponent) in descending order:
Term 1: 5 3
Term 2: 2 1
Term 3: 6 0
Enter number of terms in second polynomial: 3
Enter terms (coeff exponent) in descending order:
Term 1: 3 3
Term 2: 1 2
Term 3: 4 0
Sum of the polynomials: 8x^3 + 1x^2 + 2x^1 + 10
RESULT : The PROGRAM IS EXECUTED AND OUTPUT IS OBTAINED
Program : 2
Aim
To write a program to:
1. Find the transpose of a sparse matrix.
2. Find the sum of two sparse matrices using array representation.
Algorithm
Step 1: Start the program.
Step 2: Read the number of rows, columns, and non-zero elements of the first matrix.
Store in array a with structure fields (row, col, value).
Step 3: Read the details of each non-zero element of the first matrix:
Input row index, column index, and value.
Step 4: Read the second matrix in similar way and store in array b.
Step 5: Transpose of First Matrix
a) Initialize transpose matrix t.
b) Set t[0].row = a[0].col and t[0].col = a[0].row.
c) For each column i from 0 to number of columns:
For each element in matrix a, if a[j].col == i,
Set t[k].row = a[j].col
Set t[k].col = a[j].row
Set t[k].value = a[j].value
Increment k.
Step 6: Addition of Two Sparse Matrices
a) If dimensions do not match, print addition not possible.
b) Otherwise, compare each element of matrices a and b:
If position of a[i] is before b[j], copy a[i] to result.
If position of b[j] is before a[i], copy b[j] to result.
If both are same position, add values and store in result.
c) Copy remaining elements if any.
Step 7: Display
First matrix
Second matrix
Transpose matrix
Sum matrix
Step 8: End the program.
PROGRAM :
#include <stdio.h>
#define MAX 50
// Structure to represent a sparse matrix term
struct term {
int row;
int col;
int value;
};
// Function to read a sparse matrix
void readSparse(struct term mat[], int num) {
printf("Enter row col value for each non-zero element:\n");
for (int i = 1; i <= num; i++) {
scanf("%d %d %d", &mat[i].row, &mat[i].col, &mat[i].value);
}
}
// Function to display a sparse matrix
void displaySparse(struct term mat[]) {
printf("\nRow\tCol\tValue\n");
for (int i = 0; i <= mat[0].value; i++) {
printf("%d\t%d\t%d\n", mat[i].row, mat[i].col, mat[i].value);
}
}
// Function to find transpose of a sparse matrix
void transpose(struct term a[], struct term b[]) {
int n = a[0].value;
b[0].row = a[0].col;
b[0].col = a[0].row;
b[0].value = n;
int k = 1;
for (int i = 0; i < a[0].col; i++) {
for (int j = 1; j <= n; j++) {
if (a[j].col == i) {
b[k].row = a[j].col;
b[k].col = a[j].row;
b[k].value = a[j].value;
k++;
}
}
}
}
// Function to add two sparse matrices
void addSparse(struct term a[], struct term b[], struct term c[]) {
if (a[0].row != b[0].row || a[0].col != b[0].col) {
printf("Addition not possible\n");
return;
}
c[0].row = a[0].row;
c[0].col = a[0].col;
int i = 1, j = 1, k = 1;
while (i <= a[0].value && j <= b[0].value) {
if (a[i].row < b[j].row || (a[i].row == b[j].row && a[i].col < b[j].col)) {
c[k] = a[i];
k++; i++;
} else if (b[j].row < a[i].row || (b[j].row == a[i].row && b[j].col < a[i].col)) {
c[k] = b[j];
k++; j++;
} else {
c[k].row = a[i].row;
c[k].col = a[i].col;
c[k].value = a[i].value + b[j].value;
k++; i++; j++;
}
}
while (i <= a[0].value) {
c[k] = a[i];
k++; i++;
}
while (j <= b[0].value) {
c[k] = b[j];
k++; j++;
}
c[0].value = k - 1;
}
int main() {
struct term a[MAX], b[MAX], c[MAX], t[MAX];
int num1, num2;
// Read first sparse matrix
printf("Enter number of rows, columns and non-zero elements of first matrix: ");
scanf("%d %d %d", &a[0].row, &a[0].col, &a[0].value);
num1 = a[0].value;
readSparse(a, num1);
// Read second sparse matrix
printf("\nEnter number of rows, columns and non-zero elements of second matrix:
");
scanf("%d %d %d", &b[0].row, &b[0].col, &b[0].value);
num2 = b[0].value;
readSparse(b, num2);
// Display input matrices
printf("\nFirst Sparse Matrix:");
displaySparse(a);
printf("\nSecond Sparse Matrix:");
displaySparse(b);
// Transpose of first matrix
transpose(a, t);
printf("\nTranspose of First Sparse Matrix:");
displaySparse(t);
// Sum of two matrices
addSparse(a, b, c);
printf("\nSum of Two Sparse Matrices:");
displaySparse(c);
return 0;
}
OUTPUT :
Enter number of rows, columns and non-zero elements of first matrix: 3 3 3
Enter row col value for each non-zero element:
005
118
229
Enter number of rows, columns and non-zero elements of second matrix: 3 3 3
Enter row col value for each non-zero element:
003
126
214
First Sparse Matrix:
Row Col Value
3 3 3
0 0 5
1 1 8
2 2 9
Second Sparse Matrix:
Row Col Value
3 3 3
0 0 3
1 2 6
2 1 4
Transpose of First Sparse Matrix:
Row Col Value
3 3 3
0 0 5
1 1 8
2 2 9
Sum of Two Sparse Matrices:
Row Col Value
3 3 5
0 0 8
1 1 8
1 2 6
2 1 4
2 2 9
RESULT : The PROGRAM IS EXECUTED AND OUTPUT IS OBTAINED
