Arrays in C++

A linear array is a list of finite homogeneous data elements i.e. the data elements are of same type. The array's elements are referenced respectively by an index set of n consecutive numbers. The elements of array are stored respectively in successive memory locations.  

Length= UB - LB+ 1 

Representation of linear arrays in memory 

Linear array elements are stored in successive memory cells. The address of the first element, called the base address (base (LA)), helps the computer calculate any element's address using the formula-  

LOC (LA [K]) = Base (LA) + W (K - LB) 

where W = number of words per memory cell for LA. 

Traversing linear arrays 

Traversing array means accessing each element of the array only once. 

Algorithm - 

 Traversing a linear array.  

Suppose LA is linear array with lower bound LB and upper bound UB. This algorithm applies PROCESS to each element of LA.  

A) Initialize counter 

            Set K =LB  

B) Repeat steps 3 and 4 while K <= UB 

C) Visit element 

Apply PROCESS to LA [K]  

D)Increase counter  

Set K = K + 1 [End of step 2 loop]  

E) Exit

Inserting and deleting 

Inserting refers to the operation of adding another element to the existing elements.  

Algorithm - Inserting element into linear array.  

INSERT (LA, N, K, ITEM)  

Here LA is linear array with N elements and K is positive integer such that K<= N. This algorithm inserts an element ITEM into the Kth position in LA.  

1. Initialize counter. Set J = N 

2. Repeat steps 3 and 4 while J>=K. 

3. Move Jth element downward .

Set LA [J + 1] = LA [J]  

4.Decrease the counter. Set J = J -1.

5.Insert the element Set LA [K] = ITEM 

6.Reset N. N=N+1. 

7. EXIT.

The algorithm for deleting element from array is given below:  

Algorithm - Deleting element from linear array.  

DELETE (LA, N, K, ITEM)  

Here LA is linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from LA. 

1. Set ITEM = LA [K] 

2. Repeat for J = K to N - 1 

Move J +1st element upward.  

Set LA [J] = LA [J + 1]  

[End of loop].  

3. Reset N N=N-1.

4. EXIT.

Sorting (Bubble Sort) 

Note: Algorithm - Bubble sort.  

Sort (DATA, N)  

Here DATA is an array with N elements. This algorithm sorts the elements in DATA.  

1. Repeat steps 2 and 3 for K = 1 to N - 1 
2. Set PTR = 1 
3. Repeat while PTR <= N - K:

        (a) If DATA [PTR] >DATA [PTR + 1] then:  

        Interchange DATA [PTR] and DATA [PTR + 1] 

        [End of IF structure]  

       (b) Set PTR = PTR + 1  

         [End of inner loop]  

      [End of step 1 outer loop]  

4. EXIT.

Here the data elements are compared with adjacent data items. The smaller data element is shifted towards the left. 

Searching 

Note: Searching refers to the operation of finding the location of given element in the list. The search is said to be successful if an item is found. 

Linear Search: 

In linear search the given element is compared with each element of list one by one. This method is also called sequential search. 

Algorithm - Linear search  

LINEAR (DATA, N, ITEM, LOC)  

Here DATA is a linear array with N elements, and ITEM is given element. This algorithm finds the location LOC of ITEM in DATA or sets LOC = 0 if search is unsuccessful.  

1. Insert ITEM at the end of DATA.

             Set DATA [N + 1] =ITEM  

2. Initialize counter. 

           Set LOC = 1  

3. Search for item 

         Repeat while DATA [LOC] ITEM:  

         Set LOC = LOC + 1 

        [End of loop]  

4. If LOC = N + 1, then set LOC = 0 
5. EXIT.

Binary search: 

Suppose a list sorted in increasing order is given and an element for searching is given. In such a case we can use an efficient algorithm called binary search. 

Algorithm - Binary search  

Binary (DATA, LB, UB, ITEM, LOC)  

Here DATA is sorted array with lower bound LB and upper bound UB. ITEM is given element . BEG denotes beginning, MID denotes middle and END denotes end location s of segment of DATA. This algorithm finds the location LOC of ITEM in DATA or set LOC=NULL.  

1. Set BEG = LB, END = UB and MID = INT ((BEG + END) I 2) 
2. Repeat steps 3 and 4 while BEG<= END and DATA [MID] ITEM. 
3. IF ITEM <DATA [MID], then :

          Set END= MID-1 .  

          ELSE: Set BEG = MID + 1  

         [End of IF structure] 

4. Set MID = INT ((BEG + END)/ 2) 

         [End of step 2 loop] 

5. If DATA [MID ] =ITEM, then: Set LOC = MID 

         ELSE: Set LOC = NULL  

         [End of IF structure] 

 6 . EXIT. 

Pointer arrays 

A variable is called pointer if it points to an element in list. The pointer variable contains the address of an element in the list. An array is called pointer array if each element of array is a pointer.

An array is a contiguous set of same-type objects identified by an index. Its fixed dimension is set at declaration, and indexing starts at zero. Arrays efficiently represent composite data of similar items. Accessing an out-of-bounds element causes a runtime error (called 'index out of bounds error) 

Array Of Characters (strings) 

A C++ string is an array of characters with a terminating null character. Enclosed in double quotes, a string literal's size includes the characters plus one for the null terminator. 

Passing array to the function & Multidimensional Arrays 

An array can be passed to a function by providing its name, which represents the address of the first element. The function uses this address to access the array contents. The array size can also be specified. 

An array of arrays is referred to as multidimensional array, An array may have more than one dimension (i.e., two, three, or higher). The organization of the array in memory is still the same (a contiguous sequence of elements), but the programmer perceives it differently.