Sequential Organization
Array
Array
Array
Array
Advantages of Array
Limitations of Array
Example of Array
Data Type Default Value
bool false
char 0
int 0
float 0.0
double 0.0f
void
wchar_t 0
Following program traverses and prints the elements of an array:
#include <stdio.h>
main()
{
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Following is the implementation of the Insertion Operation −
#include <stdio.h> while( j >= k)
main() { {
int LA[] = {1,3,5,7,8}; LA[j+1] = LA[j];
int item = 10, k = 3, n = 5; j = j - 1;
int i = 0, j = n; }
printf("The original array elements are LA[k] = item;
:\n"); printf("The array elements after insertion
for(i = 0; i<n; i++) :\n");
{ for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]); {
} printf("LA[%d] = %d \n", i, LA[i]); }
n = n + 1; }
Output
The original array elements are : The array elements after insertion :
LA[0] = 1 LA[0] = 1
LA[1] = 3 LA[1] = 3
LA[2] = 5 LA[2] = 5
LA[3] = 7 LA[3] = 10
LA[4] = 8 LA[4] = 7
LA[5] = 8
Algorithm:
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to delete an element available
at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Algorithm:
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to find an element with a
value of ITEM using sequential search.
1. Start
2. 2. Set J = 0
3. 3. Repeat steps 4 and 5 while J < N
4. 4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. 5. Set J = J +1
6. 6. PRINT J, ITEM
7. 7. Stop
Algorithm:
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to update an element
available at the Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. 3. Stop
The various types of arrays are as follows.
• One dimensional array
• Multi-dimensional array
A one-dimensional array is also called a single dimensional
array where the elements will be accessed in sequential order.
This type of array will be accessed by the subscript of either a
column or row index.
When the number of dimensions specified is more than one,
then it is called as a multi-dimensional array. Multidimensional
arrays include 2D arrays and 3D arrays.
A two-dimensional array will be accessed by using the subscript of
row and column index. For traversing the two-dimensional array,
the value of the rows and columns will be considered. In the two-
dimensional array face [3] [4], the first index specifies the number
of rows and the second index specifies the number of columns and
the array can hold 12 elements (3 * 4).
Similarly, in a three-dimensional array, there will be three
dimensions. The array face [5] [10] [15] can hold 750 elements (5 *
10 * 15).
// A sample program for Array Declaration
#include <stdio.h>
int main()
{
int one_dim [10]; # declaration of 1D array
int two_dim [2][2]; #declaration of 2D array
int three_dim [2][3][4] = {
{ {3, 4, 2, 3}, {0, -3, 9, 11}, {23, 12, 23, 2} },
{ {13, 4, 56, 3}, {5, 9, 3, 5}, {3, 1, 4, 9} }
}; #declaration of 3D array. Here the elements are also defined.
return 0;
}
In this we enter an elements in any two array and then
these two array (elements of array) are store in third
array.
#include<stdio.h> scanf("%d",&b[i]);
#include<conio.h> }
void main() printf("\nElements of Array After Merge: ");
{ for(i=0;i<10;i++)
int a[10],b[10],c[20],i; {
clrscr(); c[i]=a[i];
printf("Enter Elements in 1st Array: "); c[i+10]=b[i];
for(i=0;i<10;i++) }
{ for(i=0;i<20;i++)
scanf("%d",&a[i]); {
} printf(" %d",c[i]);
printf("Enter Elements in 2nd Array: "); }
for(i=0;i<10;i++) getch();
{ }
Given two sorted arrays, the task is to merge them in a sorted manner.
Examples:
Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}
Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8}
Output: arr3[] = {4, 5, 7, 8, 8, 9}
The structure of an ordered list is a collection of items
where each item holds a relative position that is based
upon some underlying characteristic of the item. The
ordering is typically either ascending or descending and we
assume that list items have a meaningful comparison
operation that is already defined.
We will now consider a type of list known as an ordered list.
For example, if the list of integers shown above were an
ordered list (ascending order), then it could be written as
17, 26, 31, 54, 77, and 93. Since 17 is the smallest item, it
occupies the first position in the list. Likewise, since 93 is
the largest, it occupies the last position.
The ordered list of integers given above (17, 26, 31, 54, 77,
and 93) can be represented by a linked structure as shown
in Figure. Again, the node and link structure is ideal for
representing the relative positioning of the items.
A polynomial is composed of different terms where each of
them holds a coefficient and an exponent.
The simple way is to represent a polynomial with degree 'n'
and store the coefficient of n+1 terms of the polynomial in
the array. So every array element will consist of two values:
Coefficient and. Exponent.
A polynomial p(x) is the expression in variable x which is in
the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k fall in
the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.
An essential characteristic of the polynomial is that each
term in the polynomial expression consists of two parts:
• One is the coefficient
• Other is the exponent
There may arise some situation where you need to evaluate many
polynomial expressions and perform basic arithmetic operations like
addition and subtraction with those numbers. For this, you will have
to get a way to represent those polynomials. The simple way is to
represent a polynomial with degree 'n' and store the coefficient of
n+1 terms of the polynomial in the array. So every array element will
consist of two values:
1. Coefficient
2. Exponent
Two Steps:
• Place like terms together
• Add the like terms
Example: Add 2x2 + 6x + 5 and 3x2 - 2x - 1
Start with: 2x2 + 6x + 5 + 3x2 − 2x − 1
Place like terms together: 2x2+3x2 + 6x−2x + 5−1
Which is: (2+3)x2 + (6−2)x + (5−1)
Add the like terms: 5x2 + 4x + 4
Here are the steps required for Multiplying Polynomials:
Step 1: Distribute each term of the first polynomial to every
term of the second polynomial. Remember that when you
multiply two terms together you must multiply the
coefficient (numbers) and add the exponents.
Step 2: Combine like terms (if you can).
Example 1 – Multiply: 3x2(4x2 – 5x + 7)
Step 1: Distribute each term of the first polynomial to every term of the
second polynomial. In this case, we need to distribute the 3x2.
Step 2: Combine like terms. In this case, there are no like terms.
A matrix is a two-dimensional data object made of m rows
and n columns, therefore having total m x n values. If most
of the elements of the matrix have 0 value, then it is called
a sparse matrix.
• Storage: There are lesser non-zero elements than zeros
and thus lesser memory can be used to store only those
elements.
• Computing time: Computing time can be saved by
logically designing a data structure traversing only non-
zero elements.
Example: Representing a sparse matrix by a 2D
array leads to wastage of lots of memory
00304 as zeroes in the matrix are of no use in
00570 most of the cases. So, instead of storing
zeroes with non-zero elements, we only
00000
store non-zero elements. This means
02600 storing non-zero elements with triples-
(Row, Column, value).
Sparse Matrix Representations can be done in many ways
following are two common representations:
1. Array representation
2. Linked list representation
2D array is used to represent a sparse matrix in which there
are three rows named as
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is
located
Value: Value of the non zero element located at index –
(row, column)
0
0123 4
Given two sparse matrices perform operations such as add,
multiply or transpose of the matrices in their sparse form
itself. The result should consist of three sparse matrices,
one obtained by adding the two input matrices, one by
multiplying the two matrices and one obtained by
transpose of the first matrix.
To Add the matrices, we simply traverse through both
matrices element by element and insert the smaller
element (one with smaller row and column value) into the
resultant matrix. If we come across an element with the
same row and column value, we simply add their values and
insert the added data into the resultant matrix.
Example of Addition : Note that other entries of matrices will be
zero as matrices are sparse.
Result of Addition: (4X4)
Row Column Value
Matrix 1: (4X4) Matrix 2: (4X4) 1 2 10
Row Column Value Row Column Value 1 3 8
1 2 10 1 3 8 1 4 12
1 4 12 2 4 23 2 4 23
3 3 5 3 3 9 3 3 14
4 1 15 4 1 20 4 1 35
4 2 12 4 2 25 4 2 37
To Transpose a matrix, we can simply change every column
value to the row value and vice-versa, however, in this case,
the resultant matrix won’t be sorted as we require.
Example of Transpose : Note that other entries of matrices will
be zero as matrices are sparse.
Matrix 1: (4X4) Result of Transpose: (4X4)
Row Column Value Row Column Value
1 2 10 1 4 15
1 4 12 2 1 10
3 3 5 2 4 12
4 1 15 3 3 5
4 2 12 4 1 12
As its name suggests, it is a faster way to transpose a sparse and also a
little bit hard to understand. Time complexity is O(Number of columns +
Number of terms ). Here, we require 2 arrays, namely, count and
position.
1. Count array mainly stores the values of columns present in sparse
matrix.
Eg. If we have conventional matrix of size [3 x 4], then our count array
will be {0,1,2,3,4}
2. Position array stores the position of the first occurrence of the values
present in column of sparse. It is later incremented in the program.
To Multiply the matrices, we first calculate transpose of the
second matrix to simplify our comparisons and maintain
the sorted order. So, the resultant matrix is obtained by
traversing through the entire length of both matrices and
summing the appropriate multiplied values.
Example of Multiplication : Note that other entries of matrices
will be zero as matrices are sparse.
Result of Multiplication: (4X4)
Matrix 1: (4X4) Matrix 2: (4X4) Row Column Value
Row Column Value Row Column Value 1 1 240
1 2 10 1 3 8 1 2 300
1 4 12 2 4 23 1 4 230
3 3 5 3 3 9 3 3 45
4 1 15 4 1 20 4 3 120
4 2 12 4 2 25 4 4 276
A space-time or time-memory tradeoff is a way of solving a problem
or calculation in less time by using more storage space (or memory),
or by solving a problem in very little space by spending a long time.
Most computers have a large amount of space, but not infinite space.
Also, most people are willing to wait a little while for a big calculation,
but not forever. So if your problem is taking a long time but not much
memory, a space-time tradeoff would let you use more memory and
solve the problem more quickly. Or, if it could be solved very quickly
but requires more memory than you have, you can try to spend more
time solving the problem in the limited memory.
Example :
A space-time tradeoff can be used with the problem of data
storage. If data is stored uncompressed, it takes more space but
less time than if the data were stored compressed (since
compressing the data decreases the amount of space it takes,
but it takes time to run the compression algorithm).