kenics.net

Technical notes on perl, python, php, sql, cgi, c/c++, q/kdb+, unix/shell, revision control tools, data structures & algorithms, and their applications into web services and other various forms of software engineering.

Array data structure

 
################## 
###   array   #### 
################## 
 
an array strucutre is the most basic data structure. 
 
- used for handling a series of data. 
- indexed in contiguous memory space. useful for random access. but not suitable when you need to resize, or insert/remove elements in the middle, etc. (more discussion to follow in comparision with linked list) 
- need to make sure the access is within the allocated scope. otherwise null ptr exception aka segmentation fault. 
- often used as an underlying structure for more complex data structure like stack, queue, hash, tree, etc. 
 
 
there are a few ways to declare, and initialize. but ultimately this sort of detail comes down to the nuance of each language's syntax/standards. 
 
e.g. 
-------------------- 
int arr[5]; 
 
for (int i = 0; i < 5 ;i++) 
   arr[i] = i; 
-------------------- 
int arr[5] = {1,2,3,4,5}; 
-------------------- 
int arr[] = {1,2,3,4,5};  // this will automatically make arr size 5 
int arr2[5] = {3};        // this will only initialize the first elem 
-------------------- 
int* arr = new int[5];                // C++ 
for (int i = 0; i < 5 ; i++, arr++ ) 
   *arr = i;                          // since arr is essentially just a pointer to a contiguous chunk of mem, we can treat it as such and do *arr, arr++ 
-------------------- 
 
 
 
 
 
################################### 
###   multi dimensional array   ### 
################################### 
 
int arr[5][3]; 
 
this means, we have a size=5 array, and each element is a size=3 array. 
 
---------------------- 
arr [0][1][2][3][4] 
    [1][1][1][1][1] 
    [2][2][2][2][2] 
---------------------- 
 
still it is just a contiguous chunk. 
 
arr[0][0] 
arr[0][1] 
arr[0][2] 
arr[1][0] 
arr[1][1] 
...        // and so on. 
 
 
------------------ // test.cpp 
#include <iostream> 
using namespace std; 
 
int main() 

  int arr[5][3]; 
  for(int i =0; i< 5; i++) 
    for(int j =0; j< 3;j++) 
      cout << &arr[i][j] << endl; 

------------------ 
 
======>  will print the below. notice it's all 4bytes increment. 
( int = 4bytes in this case. would be 1-byte increment if we used char.) 
 
0x7fff26242d60 
0x7fff26242d64 
0x7fff26242d68 
0x7fff26242d6c 
0x7fff26242d70 
0x7fff26242d74 
0x7fff26242d78 
0x7fff26242d7c 
0x7fff26242d80 
0x7fff26242d84 
0x7fff26242d88 
0x7fff26242d8c 
0x7fff26242d90 
0x7fff26242d94 
0x7fff26242d98 
 
=========> this means, depending on the cache scheme, accessing row-by-row is faster than column-by-column. 
 
 
if you wanna initialize, do it like below 
 
--------------------------------------- 
int arr[3][2] = { {1,2},{3,4},{5,6} } 
--------------------------------------- 
 
 
====> three dimensional array is essentially the same. 
 
 
######################## 
###   jagged array   ### 
######################## 
 
there may be a situation in which you may want to declare non-recutangular array like below. 
it is called a jagged array. 
 
--------------------- 
arr [0][1][2][3][4] 
    [1][1][1][1][1] 
    [2]   [2][2][2] 
    [3]   [3]   [3] 
          [4] 
--------------------- 
 
 
===>  the most common usage is when you have an array of names. 
 
e.g. 
 
--------------------------------  //  jagarr.cpp 
#include <iostream> 
#include <cstring>     // needed for strcpy 
using namespace std; 
 
int main() 

  char* name[2]; 
 
  name[0] = new char[4]; 
  name[1] = new char[5]; 
 
  name[0][0] = 'k'; 
  name[0][1] = 'e'; 
  name[0][2] = 'n'; 
  name[0][3] = 0; 
 
  strcpy(name[1],"will"); 
 
  cout << name[0] << endl;    //  ken 
  cout << name[1] << endl;    //  will 
 
  return 0; 

 
-------------------------------- 
 
 
 
################################# 
####    vector/ArrayList     #### 
################################# 
 
an array that grows(shrinks) as you add(del) elements is called vector(in C++) or ArrayList(in java). 
it is convenient. a single add/del operation can be O(n) but amortized complexity can be O(1) if you double up/down the size as you resize. 
 
shrink(resizing down) is not mandatory, and in fact, it doesnt have to happen when LF<0.5, maybe resize only when LF<0.25, to avoid too much thrashing between resizing up and down. 
 
 
 
########################## 
####  size of array   #### 
########################## 
 
 
int input[] = {2,4,8,1,23,5,2,7,3,9};  // 10 elems 
 
int asize = sizeof(input);              // 40 
size      = sizeof(input)/sizeof(int);  // 10 
 
NOTE: this sizeof() trick can only be used within the immediate scope of the array declaration. e.g. below code is illegal. 
------------------------- 
#include <iostream> 
using namespace std; 
 
void print(int a[])                      // int a[] will be interpreted as (int* a) 

int size = sizeof(a)/sizeof(a[0]);   // sizeof(a) will be the size of a pointer to an interger, which is 4 or 8 
for(int i = 0; i< size; i++)         // so int size will be always 1 
cout << arr[i] << ' '; 
cout << endl; 

 
int main() 

    int arr[5] = {11,22,33,44,55}; 
cout << sizeof(arr) << endl;      // 20 
cour << sizeof(arr[0]) << endl;   // 4   (on 32-bit machine) 
print(arr); 
return 0; 

 
------------------------- 
 
unfortunately, there is no certain way to determine the array size. so you have to pass the size as a parameter if you are passing an array to a function. 
 
e.g. 
----------------------------------- 
#include <iostream> 
using namespace std; 
 
void print(int a[],int size) 

    for(int i = 0; i< size; i++) 
        cout << arr[i] << ' '; 
    cout << endl; 

 
int main() 

    int arr[5] = {11,22,33,44,55}; 
int size = sizeof(arr)/sizeof(arr[0]); 
    print(arr,size); 
    return 0; 

--------------------------------------------- 
 
 
 
(ref) 
http://za.toypark.in/html/2009/12-22.html 
https://www.jpcert.or.jp/sc-rules/c-arr01-c.html 
http://www.pickatutorial.com/tutorial/csharpprogramming/csharp_arrays.htm  // c# but a very simple example of jagged array 
 
 

  1. 2014-06-06 00:51:21 |
  2. Category : data_structure
  3. Page View:

Google Ads