You cannot copy content of this page.

Category Archive Arrays

Program for representing multiple stacks in one array



Multiple Stacks in an array

Program for representing multiple stacks in one array

/*Implementing multiple stacks in a single array*/



#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

void push(int,int[],int,int);
int pop(int,int[],int);
void display(int,int[],int);

/*array to top index for each stack*/
int t[MAX];
int top[MAX];

void main()
{
int arr[MAX],n,totstk,index;
int i,j,k=0,span,no,ch,num;
/*Input total elements of the array*/
/*This array may be divided into multiple stacks*/
printf(“nEnter size of the array?”);
scanf(“%d”,&n);

/*Input total stacks to be created in above array*/
printf(“nEnter total stacks to create?”);
scanf(“%d”,&totstk);

/*t[] array will contains totstk indexes for top*/
/*since total stacks to be created are totstk*/
/*Initializing t[] array with -1*/
for(i=0;i<totstk;i++)
t[i]=-1;

/*computes size of one stack*/
span=n/totstk;

/*store top of each stack in the array*/
/*this top serves as index for push/pop operations*/

top[k++]=0;
for(i=0;i<totstk-1;i++,k++)
top[k]=top[k-1]+span;

/*displaying elements of indexed array*/
for(i=0;i<totstk;i++)
printf(“%dt”,top[i]);
do{
clrscr();
printf(“nStacks-Menu (n stacks:1 array)”);
printf(“n1. Push”);
printf(“n2. Pop”);
printf(“n3. Display”);
printf(“n4. Quit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);

if(ch!=4)
{
printf(“nEnter stack number (0 to %d)?”,totstk-1);
scanf(“%d”,&index);
}

switch(ch)
{
case 1:
printf(“nEnter number to push?”);
scanf(“%d”,&no);
push(index,arr,span,no);
break;
case 2:
num=pop(index,arr,span);
printf(“nPopped element from stack %d is %d”,index,num);
break;
case 3:
display(index,arr,span);
break;
case 4:
exit(0);
}
getch();
}while(1);
}



void push(int index,int arr[],int n,int num)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==topid+n-1)
{printf(“nStack Full! Overflow.”);
return;
}
topelement=++t[index];
arr[topid+topelement]=num;
}
int pop(int index,int arr[],int n)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return -1;
}
t[index]–;
return(arr[topid+topelement]);
}
void display(int index,int arr[],int n)
{
int i,topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return;
}
for(i=topid+topelement;i>=topid;i–)
printf(“%dt”,arr[i]);
}


Tags, ,

Conversion of a Linked List into Array

Conversion of a Linked List into Array

The conversion process involves creation of a linked list.  Then the list is read from the first node till the last node such that each node value is stored in an array and the node is removed by freeing its memory.  The array is then displayed as an output.

/*Conversion of a linked list into array*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

typedef struct list
{int info;
list *next;
}list;

list *create()
{list *temp=(list *)malloc(sizeof(list));
if(temp==NULL)
{printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

list *makenode(int x)
{list *ptr=create();
ptr->info=x;
ptr->next=NULL;
return ptr;
}

list *insertend(list *head,int x)
{list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
return head;
}

void display(list *head)
{
list *temp;
if(head==NULL)
{printf(“List is empty.”);
return;
}
temp=head;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

int count(list *head)
{list *temp;
int ct=0;
temp=head;
while(temp!=NULL)
{ct++;
temp=temp->next;
}
return ct;
}

list *dispose(list *head)
{
list *temp;
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

list *convertlist_to_array(list *head,int arr[])
{int i=0;
list *temp=head;
while(temp!=NULL)
{arr[i++]=temp->info;
temp=temp->next;
}
head=dispose(head);
return head;
}

void main()
{
list *head=NULL;
int i,ch,num,size,arr[MAX]={0};
while(1)
{
clrscr();
printf(“nMenu”);
printf(“nn1. Create List”);
printf(“n2. Display List”);
printf(“n3. Convert List to Array”);
printf(“n4. Display Array”);
printf(“n5. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number?”);
scanf(“%d”,&num);
head=insertend(head,num);
break;
case 2:
display(head);
break;
case 3:
size=count(head);
printf(“nConverting List to Array…”);
head=convertlist_to_array(head,arr);
break;
case 4:
printf(“nDisplaying array elements: “);
for(i=0;i<size;i++)
printf(“%dt”,arr[i]);
printf(“bb “);
break;
case 5:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

 

Tags, ,

Sparse Matrix representation for polynomials

Sparse Matrix representation for polynomials

Program to represent two polynomials using Sparse Matrix representation using arrays, compute sum of two polynomials and represent the result using sparse matrix:

/* Sparse Matrix Representation for Polynomials */

#include <stdio.h>
#include <stdlib.h>

#define MAX 15

int main(){
int poly1[MAX][MAX]={0},poly2[MAX][MAX]={0},poly3[MAX][MAX]={0};
int i,j,k,m,n,nrows,nrows1,nrows2,nrows3,ncols,ct=0,ct1=0,ct2=0;
int spmat1[MAX][MAX]={0},spmat2[MAX][MAX]={0},spmat3[MAX][MAX]={0};
int deg,deg1,deg2,deg3;
printf(“nEnter degree of first polynomial?”);
scanf(“%d”,&deg1);
printf(“nEnter degree of second polynomial?”);
scanf(“%d”,&deg2);
deg3=(deg1>deg2)?deg1:deg2;

printf(“nFor first polynomial:”);
for(i=0;i<=deg1;i++){
printf(“nEnter coefficient for exponent %d> “,i);
scanf(“%d”,&poly1[0][i]);
if(poly1[0][i] != 0)
ct1++;
}
nrows1 = ct1 + 1;
ncols = 3;
spmat1[0][0] = 1;
spmat1[0][1] = deg1 + 1;
spmat1[0][2] = ct1;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg1+1;j++){
if(poly1[i][j] != 0){
spmat1[m][n++]=i;
spmat1[m][n++]=j;
spmat1[m][n]=poly1[i][j];
m++;
n=0;
}
}
}
for(i=0;i<nrows1;i++){
for(j=0;j<ncols;j++)
printf(“%dt”,spmat1[i][j]);
printf(“n”);
}
ct2=0;
printf(“nFor second polynomial:”);
for(i=0;i<=deg2;i++){
printf(“nEnter coefficient for exponent %d> “,i);
scanf(“%d”,&poly2[0][i]);
if(poly2[0][i] != 0)
ct2++;
}
nrows2 = ct2 + 1;
ncols = 3;
spmat2[0][0] = 1;
spmat2[0][1] = deg2+1;
spmat2[0][2] = ct2;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg2+1;j++){
if(poly2[i][j] != 0){
spmat2[m][n++]=i;
spmat2[m][n++]=j;
spmat2[m][n]=poly2[i][j];
m++;
n=0;
}
}
}
for(i=0;i<nrows2;i++){
for(j=0;j<ncols;j++)
printf(“%dt”,spmat2[i][j]);
printf(“n”);
}
printf(“nGenerating sum of polynomials…!”);
printf(“nPress any key to continue…”);

deg = deg1<deg2?deg1:deg2;
for(i=0;i<=deg;i++){
poly3[0][i]=poly1[0][i]+poly2[0][i];
ct++;
}
for(;i<=deg1;i++){
poly3[0][i]=poly1[0][i];
ct++;
}
for(;i<=deg2;i++){
poly3[0][i]=poly2[0][i];
ct++;
}
nrows = ct+1;
ncols = 3;
spmat3[0][0]=1;
spmat3[0][1]=ct;
spmat3[0][2]=ct;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg+1;j++){
if(poly3[i][j] != 0){
spmat3[m][n++]=i;
spmat3[m][n++]=j;
spmat3[m][n]=poly3[i][j];
m++;
n=0;
}
}
}
printf(“nnAddition Result:nn”);
for(i=0;i<nrows;i++){
for(j=0;j<3;j++)
printf(“%dt”,spmat3[i][j]);
printf(“n”);
}
for(i=0;i<=deg1;i++)
printf(“(%d*x^%d)->”,poly1[0][i],i);

printf(“bb n”);

for(i=0;i<=deg2;i++)
printf(“(%d*x^%d)->”,poly2[0][i],i);

printf(“bb n”);

for(i=0;i<=deg3;i++)
printf(“(%d*x^%d)->”,poly3[0][i],i);

printf(“bb n”);

}

Tags, ,

Program to represent two polynomials using arrays and compute their sum

Sparse Polynomial representation and addition

Program to represent two polynomials using arrays and compute their sum

/* Representation of Polynomials using arrays */
/* Addition of two Polynomials */

#include <stdio.h>

#define MAX 10

int main(){
int poly1[MAX]={0},poly2[MAX]={0},poly3[MAX]={0};
int i,deg1,deg2,deg3;
printf(“nEnter degree of first polynomial?”);
scanf(“%d”,&deg1);
printf(“nEnter degree of second polynomial?”);
scanf(“%d”,&deg2);

printf(“nFor first polynomial:”);
for(i=0;i<deg1;i++){
printf(“nEnter Coefficient for Exponent %d> “,i);
scanf(“%d”,&poly1[i]);
}
printf(“nFor second polynomial:”);
for(i=0;i<deg2;i++){
printf(“nEnter Coefficient for Exponent %d> “,i);
scanf(“%d”,&poly2[i]);
}
printf(“nGenerating sum…!”);
printf(“nPress any key to continue…”);

deg3 = (deg1>deg2)?deg1:deg2;

for(i=0;i<deg3;i++)
poly3[i] = poly1[i] + poly2[i];
printf(“nnAddition Result:nn”);

for(i=deg1-1;i>=0;i–)
printf(“(%dx^%d)+”,poly1[i],i);
printf(“b n”);

for(i=deg2-1;i>=0;i–)
printf(“(%dx^%d)+”,poly2[i],i);
printf(“b n”);

for(i=deg3-1;i>=0;i–)
printf(“(%dx^%d)+”,poly3[i],i);
printf(“b n”);

}

Tags, ,

Sparse Polynomial representation and addition

Sparse Polynomial representation and addition:

Polynomial is an expression which is composed of terms, wherein terms are composed of coefficient and exponent.  An example of a polynomial is: 4x3+5x2+6x+9.  This polynomial is composed of four terms with the following sets of coefficient and exponent – {(4,3), (5,2), (6,1), (9,0)}.  Thus representation of a polynomial using arrays is straightforward.  The subscripts of the array may be considered as exponents and the coefficients may be stored at an appropriate place referred to by the subscript.  Array representation for the above example is:

arr:                9          6        5        4         coefficients

subscripts: 0         1        2         3          exponents

The above representation works fine for the above example, but for polynomials such as 5×6+7, array representation is considered feasible on account of memory usage, since it results in a sparse arrangement as follows:

 

arr    7         0         0        0        0        0          5

         0          1          2        3         4        5          6 (Subscripts)
Sparse matrix representation may be considered for the above matrix as given below:

Rows                     Cols                       Value
———————————————————–

1                              7                              2              (Total)

0                              0                              7

0                              6                              5

For addition of two polynomials using arrays, subscript-wise elements may be added to result in the polynomial containing result of addition of two polynomials.

Example:

Polynomial 1:     4x3 + 5x2 + 6x + 7

Polynomial 2:     3x3 + 4x2 + 2x + 2

———————–

7x3 + 9x2 + 8x + 9

———————–

Array Representation:

Subscripts:           0              1              2              3

———————————————————

Polynomial 1:     7              6              5              4

Polynomial 2:     2              2              4              3

Result of sum:   9              8              9               7

 
Program to represent two polynomials using arrays and compute their sum

Tags, ,

Program to represent Sparse Matrix using singly linked list (One dimensional list)

Sparse Matrix representation using singly Linked List:

/* Sparse Matrix representation using linked list */
#include <stdio.h>
#include <stdlib.h>

typedef struct list{
int rows, cols, value;
struct list *next;
}list;

list *create(){
list *temp = (list *)malloc(sizeof(list));
if(temp==NULL){
printf(“nMemory Allocation Error !”);
exit(1);
}
return temp;
}

list *makenode(int r, int c, int val){
list *temp = create();
temp->rows = r;
temp->cols = c;
temp->value = val;
temp->next = NULL;
return temp;
}

list *insert(list *head, int r, int c, int val){
list *ptr, *temp = head;
if(head == NULL){
head = makenode(r,c,val);
}
else{
while(temp->next != NULL)
temp = temp->next;
ptr = makenode(r,c,val);
temp->next = ptr;
}
return head;
}

void display(list *head){
list *temp;
if(head == NULL){
printf(“nList is empty.”);
exit(1);
}
temp = head;
while(temp != NULL){
printf(“(%d,%d,%d->)->”,temp->rows,temp->cols,temp->value);
temp = temp->next;
}
printf(“bb “);
}

int main(){
int arr[3][4],i,j,m,n,ct=0;
list *head = NULL;
for(i=0; i<3; i++){
printf(“nEnter the values for row %d?”, i+1);
for(j=0;j<4;j++){
scanf(“%d”,&arr[i][j]);
if(arr[i][j] != 0)
ct++;
}
}
head = makenode(3,4,ct);
for(i=0;i<3;i++){
for(j=0;j<4;j++){
if(arr[i][j] != 0)
head = insert(head,i,j,arr[i][j]);
}
}
printf(“nList representation of Sparse Matrix is: n”);
display(head);
getch();
}

Tags, ,

Program to represent Sparse Matrix using arrays

Program to represent Sparse Matrix using arrays:

/* Sparse Matrix representation using arrays */

#include <stdio.h>
#include <stdlib.h>

#define MAX 15

int main(){
int arr[3][4],i,j,m,n,nrows,ncols,ct=0;
int sparse_matrix[MAX][MAX];
for(i=0;i<3;i++){
printf(“nEnter values for row %d?”,i+1);
for(j=0;j<4;j++){
scanf(“%d”,&arr[i][j]);
if(arr[i][j] != 0)
ct++;
}
}
nrows = ct+1;
ncols = 3;
sparse_matrix[0][0] = 3;
sparse_matrix[0][1] = 4;
sparse_matrix[0][2] = ct;
m=1;
n=0;
for(i=0;i<3;i++){
for(j=0;j<4;j++){
if(arr[i][j]!=0){
sparse_matrix[m][n++]=i;
sparse_matrix[m][n++]=j;
sparse_matrix[m][n]=arr[i][j];
m++;
n=0;
}
}
}
printf(“nThe new sparse matrix in 3-tuple representation is:n”);
for(i=0;i<nrows;i++){
for(j=0;j<ncols;j++){
printf(“%dt”,sparse_matrix[i][j]);
}
printf(“n”);
}
}

Tags, ,

Sparse Matrix

Sparse Matrix:

A matrix that has minimum number of non-zero elements is called a sparse matrix i.e. very few elements are sparsely distributed in the matrix.

Example: An array of order 3 x 4 containing sparsely located non-zero elements.

0

1

2

3

0

0

25

0

7

1

0

0

2

8

2

0

0

1

0

(Order 3 x 4)

In the above example, out of 12 elements only 5 elements contain non zero values.  Such a matrix is called sparse matrix.

Representation of Sparse Matrix:

  • 3-Tuple Representation
  • List Representation

1.  3-Tuple Representation: An array of three columns is required.  The size of the array is the number of non-zero elements plus one.  First row is called the header row that contains total number of rows, total number of columns and non-zero element’s value i.e.

Header Row:    Row    |      Column     |     Element

rows

columns

Elements (non zero)

0

3

4

5

1

0

1

25

2

0

3

7

3

1

2

2

4

1

3

8

5

2

2

1

Sparse Matrix representation for the array given above

Number of rows:  3

Number of columns:  4

Number of elements:  5

Order of Sparse Matrix = (5+1) x 3 = 6 x 3.

 

2.  List Representation:  Each row is converted to a node in linked representation where each node contains, row subscripts, column subscript and non-zero element.  The first node returns the total number of rows, columns and elements.

Example:

3|4|5 -> 0|1|25 -> 0|3|7 -> 1|2|2 -> 1|3|8 -> 2|2|1 -> NULL

Array representation of Sparse Matrix
Linked representation of Sparse Matrix

 

Tags,

Array Representation – Column-major & Row-major

Array Representation:

  • Column-major
  • Row-major

Arrays may be represented in Row-major form or Column-major form.  In Row-major form, all the elements of the first row are printed, then the elements of the second row and so on upto the last row.  In Column-major form, all the elements of the first column are printed, then the elements of the second column and so on upto the last column.  The ‘C’ program to input an array of order m x n and print the array contents in row major and column major is given below.  The following array elements may be entered during run time to test this program:

Input:     Rows: 3;  Columns: 3;

1     2     3

4     5     6

7     8     9

Output:

Row Major:

1     2     3

4     5     6

7     8     9

Column Major:

1     4     7

2     5     8

3     6     9

 



/* Program to input an array and display in row-major and column major form */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX][MAX],m,n,i,j;
printf(“nEnter total number of rows?”);
scanf(“%d”,&m);
printf(“nEnter total number of columns?”);
scanf(“%d”,&n);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“nEnter number?”);
scanf(“%d”,&arr[i][j]);
}
}
printf(“nnRow-Major Order:n”);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“%dt”,arr[i][j]);
}
printf(“n”);
}
printf(“nnColumn-Major Order:n”);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“%dt”,arr[j][i]);
}
printf(“n”);
}
}

Tags,

Program to delete a value from a given array such that array remains sorted

Sorted Deletion in an Array:

Deletion is same as in previous post with the only difference that if the given array is sorted, then the deletion automatically will result in a sorted array.

/* Sorted Deletion */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],n,i,num;
printf(“nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“nEnter the number to delete?”);
scanf(“%d”,&num);
for(i=0;i<n;i++){
if(arr[i] == num)
break;
}
if(i == n){
printf(“nNumber not found”);
return;
}
for(;i<n;i++)
arr[i] = arr[i+1];
printf(“nArray after deletion:”);
for(i=0;i<n-1;i++)
printf(“%dt”,arr[i]);
}

 

Tags

x Close

Like Us On Facebook