際際滷

際際滷Share a Scribd company logo

Array Data Structures

Download as PPTX, PDF
S
Soni Gupta

This document discusses arrays as a linear data structure in C language. It defines an array as a collection of similar elements of the same data type stored in contiguous memory locations. The document covers declaration and initialization of arrays, representation of arrays in memory, pointers and arrays, 2-dimensional arrays in row-major and column-major order, and examples of different types of matrices represented as arrays. It also notes some disadvantages of arrays such as fixed size and difficulty of insertion/deletion.

1 of 29
Download to read offline
Array A Linear Data Structure SONI GUPTA ASSISTANT PROFESSOR (NPIU-TEQIP III ) HBTU KANPUR, UP TEQIP -III
Topics to be covered What is an array? Declaration of an array Initialization of an array Examples Representation of an array in memory Pointers and array 2-dimensional array Representation in row major order and column major order Example: Representation of Lower triangular matrix Example: Representation of tri diagonal matrix Example: Representation of X-matrix Disadvantage TEQIP -III
Array Array is a collection of similar elements having same data type, accessed using a common name. The elements of an array occupy contiguous memory locations. 100 104 108 112 116 120 TEQIP -III
Dimension of an array: In C language there is no limitation on the dimension on an array 1-Dimensional List Vector 2-dimensional Table Matrix 3-dimensional 3-d matrix TEQIP -III
Declaration of an array Type-name variable-name [size]; The array is indexed from 0 to size-1 The size (in brackets) must be an integer literal or a constant variable.) Based on the size declared the compiler determine how much space to allocate in memory. TEQIP -III
Examples: int list[5]; // an array of 5 integers list list[0]=4, list[1]=6, list[2]=1, list[4]=50 char name[5]; // an array of 5 characters name TEQIP -III 4 6 1 100 50 a i o u e
int table[2][3]; // a two dimensional array of integers table table[0][0]=5, table[0][1]=9, table[1][2]=5, Int location[5][5][10]: // a three dimensional array of integer Int *a[4] // an array of pointer/address a 5 9 14 1 3 5 1004 1008 1120 1222 TEQIP -III
Initializing an Array int list[5]={1,2,5,6,1}; char [20]={a,r,w,q,q,t}; // all uninitialized values will set to zero. int table[2][3]={{2,3,8}{3,4,9}}; int count[ 100 ] = { 1, 2, 3, [10] = 10, 11, 12, [60] = 50, [42] = 500 }; TEQIP -III
Representation of an array in memory 0 1000 (Base address) 1 1004 2 1008 3 1012 4 1016 IndexValues Address (in Byte) 4 6 1 100 50 TEQIP -III
Pointers and Array An array variable is actually a pointer which hold the address of the first element of the array. We can access array value by array notations or pointer value. a[0]=*a a[1]=*(a+1) a[2]=*(a+2) TEQIP -III
a = a+0 = &a[0] a+1 = &a[1] a+i = &a[i] &(*(a+i)) = &a[i] = a+i *(&a[i]) = *(a+i) = a[i] Address of an element i of array a = a + i * sizeof(element) TEQIP -III
2-dimensional Array Suppose a 2-d array A[i][j]; Row major order Location of A[i][j] = A + ( Number of rows * i + j )*sizeof(element) For Column Major Order Location of A[i][j] = A + ( Number of Columns * j + i )*sizeof(element) A[i][j]= *(*(A + i) + j)= *(A[i] + j) = (*(A+i))[j] &A[i][j]= *(A + i) + j = A[i] + j TEQIP -III
Row major order Row major order TEQIP -III TEQIP -III
Row major order for (i=1,i<=3,i++) for (j=1,j<=3,j++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
Column major order Column major order TEQIP -III TEQIP -III
Column major order for (j=1,j<=3,j++) for (i=1,i<=3,i++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
Row major order for (i=1,i<=3,i++) for (j=1,j<=3,j++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
Character Strings as Arrays of Characters Strings are stored in an array of character (char) type along with the null terminating character "0" at the end char name[ ] = { I', N', D',I', A', 'O'}; OR char name[ ] = INDIA"; '0' is not necessary. C inserts the null character automatically. length of string= 5 size of string=6 TEQIP -III
Example : Lower Triangular Matrix 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 TEQIP -III
Column major order TEQIP -III
Column major order 0-element 1-element 3=1+2 element 6=1+2+3 element TEQIP -III
Colum major order 0-element 1-element 3=1+2 element 6=1+2+3 element (2)(1) 2 + + 2 th element Where N is number of row/column 0 2 81 7 93 4 5 6 TEQIP -III
Row major Order TEQIP -III
Row major order 1-element 3=1+2 element 6=1+2+3 element (2)(1) 2 + + 2 th element Where N is number of row/column 0 2 81 7 93 4 5 6 TEQIP -III
Example: Tri-diagonal matrix 0 0 0 0 0 TEQIP -III
Row major order 0 1 2 3 4 5 6 7 8 9 TEQIP -III
Example: Diagonal Matrix 0 0 0 0 0 0 0 TEQIP -III
Example: Diagonal Matrix 0 0 0 0 0 0 0 TEQIP -III
Disadvantage The number of element must be known in advance. Array is static in nature i.e array size is fixed and it is allocated at compile time. The memory which is allocated to array can not be increased or decreased. If we will allocate memory more than required then space will be wasted. The elements of an array are stored in consecutive memory locations. Therefore insertion and deletion is difficult and time consuming. TEQIP -III

More Related Content

Array Data Structures

  • 1. Array A Linear Data Structure SONI GUPTA ASSISTANT PROFESSOR (NPIU-TEQIP III ) HBTU KANPUR, UP TEQIP -III
  • 2. Topics to be covered What is an array? Declaration of an array Initialization of an array Examples Representation of an array in memory Pointers and array 2-dimensional array Representation in row major order and column major order Example: Representation of Lower triangular matrix Example: Representation of tri diagonal matrix Example: Representation of X-matrix Disadvantage TEQIP -III
  • 3. Array Array is a collection of similar elements having same data type, accessed using a common name. The elements of an array occupy contiguous memory locations. 100 104 108 112 116 120 TEQIP -III
  • 4. Dimension of an array: In C language there is no limitation on the dimension on an array 1-Dimensional List Vector 2-dimensional Table Matrix 3-dimensional 3-d matrix TEQIP -III
  • 5. Declaration of an array Type-name variable-name [size]; The array is indexed from 0 to size-1 The size (in brackets) must be an integer literal or a constant variable.) Based on the size declared the compiler determine how much space to allocate in memory. TEQIP -III
  • 6. Examples: int list[5]; // an array of 5 integers list list[0]=4, list[1]=6, list[2]=1, list[4]=50 char name[5]; // an array of 5 characters name TEQIP -III 4 6 1 100 50 a i o u e
  • 7. int table[2][3]; // a two dimensional array of integers table table[0][0]=5, table[0][1]=9, table[1][2]=5, Int location[5][5][10]: // a three dimensional array of integer Int *a[4] // an array of pointer/address a 5 9 14 1 3 5 1004 1008 1120 1222 TEQIP -III
  • 8. Initializing an Array int list[5]={1,2,5,6,1}; char [20]={a,r,w,q,q,t}; // all uninitialized values will set to zero. int table[2][3]={{2,3,8}{3,4,9}}; int count[ 100 ] = { 1, 2, 3, [10] = 10, 11, 12, [60] = 50, [42] = 500 }; TEQIP -III
  • 9. Representation of an array in memory 0 1000 (Base address) 1 1004 2 1008 3 1012 4 1016 IndexValues Address (in Byte) 4 6 1 100 50 TEQIP -III
  • 10. Pointers and Array An array variable is actually a pointer which hold the address of the first element of the array. We can access array value by array notations or pointer value. a[0]=*a a[1]=*(a+1) a[2]=*(a+2) TEQIP -III
  • 11. a = a+0 = &a[0] a+1 = &a[1] a+i = &a[i] &(*(a+i)) = &a[i] = a+i *(&a[i]) = *(a+i) = a[i] Address of an element i of array a = a + i * sizeof(element) TEQIP -III
  • 12. 2-dimensional Array Suppose a 2-d array A[i][j]; Row major order Location of A[i][j] = A + ( Number of rows * i + j )*sizeof(element) For Column Major Order Location of A[i][j] = A + ( Number of Columns * j + i )*sizeof(element) A[i][j]= *(*(A + i) + j)= *(A[i] + j) = (*(A+i))[j] &A[i][j]= *(A + i) + j = A[i] + j TEQIP -III
  • 13. Row major order Row major order TEQIP -III TEQIP -III
  • 14. Row major order for (i=1,i<=3,i++) for (j=1,j<=3,j++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
  • 15. Column major order Column major order TEQIP -III TEQIP -III
  • 16. Column major order for (j=1,j<=3,j++) for (i=1,i<=3,i++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
  • 17. Row major order for (i=1,i<=3,i++) for (j=1,j<=3,j++) { Printf(Enter the element); Scanf(%d,A[i][j]); } TEQIP -III
  • 18. Character Strings as Arrays of Characters Strings are stored in an array of character (char) type along with the null terminating character "0" at the end char name[ ] = { I', N', D',I', A', 'O'}; OR char name[ ] = INDIA"; '0' is not necessary. C inserts the null character automatically. length of string= 5 size of string=6 TEQIP -III
  • 19. Example : Lower Triangular Matrix 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 TEQIP -III
  • 21. Column major order 0-element 1-element 3=1+2 element 6=1+2+3 element TEQIP -III
  • 22. Colum major order 0-element 1-element 3=1+2 element 6=1+2+3 element (2)(1) 2 + + 2 th element Where N is number of row/column 0 2 81 7 93 4 5 6 TEQIP -III
  • 24. Row major order 1-element 3=1+2 element 6=1+2+3 element (2)(1) 2 + + 2 th element Where N is number of row/column 0 2 81 7 93 4 5 6 TEQIP -III
  • 25. Example: Tri-diagonal matrix 0 0 0 0 0 TEQIP -III
  • 26. Row major order 0 1 2 3 4 5 6 7 8 9 TEQIP -III
  • 27. Example: Diagonal Matrix 0 0 0 0 0 0 0 TEQIP -III
  • 28. Example: Diagonal Matrix 0 0 0 0 0 0 0 TEQIP -III
  • 29. Disadvantage The number of element must be known in advance. Array is static in nature i.e array size is fixed and it is allocated at compile time. The memory which is allocated to array can not be increased or decreased. If we will allocate memory more than required then space will be wasted. The elements of an array are stored in consecutive memory locations. Therefore insertion and deletion is difficult and time consuming. TEQIP -III

Editor's Notes

  • #6: Array variables are declared identically to variables of their data type, except that the variable name is followed by one pair of square [] brackets for each dimension of the array. Space is allocated only once, at the time the array is declared. The array does NOT change sizes later if the variable used to declare it changes.
  • #9: We can declare an array as we declare a variable. Simply list the array values in set notation { } after the declaration If an array is to be completely initialized, the dimension of the array is not required. The compiler will automatically size the array to fit the initialized data. If the size of the array is not given, then the largest initialized position determines the size of the array.