Arrays

An array is a collection of the same type of object stored together under one common name. The individual elements are accessed using a subscript. We will only consider linear arrays or 1 dimensional arrays as they are also known. There is often a great deal of confusion about arrays because if we have an array called data then in C++ the first element is data[0]. Here the numbers are the subscripts that identify the individual elements of the array. Arrays have a predetermined size and any algorithms that we consider must not try to "write past the end of the array" otherwise the compiler will complain or the program will crash.

An array should be initialized (all elements given a value) when it is declared and then entries are inserted into the array by accessing the individual elements one at a time. An array element can be treated just like a simple variable of whatever type was declared for the array - it can be assigned and re-assigned a value at any point in the program. Commonly a looping structure is used to scroll through the array one element at a time - in this case the subscript of the array is represented by a variable too which is incremented by the loop

int Ages[10] ={0};	// initialized to zero
int age;

for (int x=0;  x<10;  x++)	// loop runs from 0 to 9
	{
	cout << "Input age " << x+1 << " :";	// asks for the age
	cin >> age;
	Ages[x] = age;
	} 

Similarly to delete and entry from an array, assign some null value to the element in question.

(Go Up)

Strings

A string is a series of characters and strings are often implemented using arrays. A string is what we more commonly know as a word or text or a sentence etc but in computer speak all these sequences of characters, whether they mean anything or not, are strings. Most programming languages provide convenient tools for manipulating strings (apart from inputting and outputting them) - and other tools can be written if you have specific needs.

• Concatenation is the joining together of two strings into one - for example joining a "first name" string and a "surname" string together to produce a "full name" string - the operation involves writing the strings, one after another, into a new string and dealing appropriately with (removing) any end-of-string characters that would no longer be at the end of the string
• Truncation is where part of a string is removed, usually from the end - for example removing city information from an "address" string to leave only street names - the operation involves moving the required section of the string to a new shorter string and then adding any appropriate end-of string characters
• Extraction of substrings involves removing a part of the string, not necessarily parts that are adjacent, to form a new string - the operation has to preserve and end-of-string characters

(Go Up)

Searching and Sorting

Dealing once again with arrays it is often necessary to search for a given element, sort the array or a combination of both. There are many different sorting and searching algorithms, each with their merits and requirements. Searching and sorting small arrays is trivial given the massive computer processing power available, but large arrays, multi-dimensional arrays and database structures often need more careful consideration. If data is entered into the array randomly then sorting algorithms can be used to produce ordered lists and provide analysis of the data, similarly searching algorithms allow certain types or areas of the data to be accessed and analyzed

The Sequential (linear) search and the Binary search are two searching techniques considered, the linear search is a direct brute force approach that can be used on any array but it does require a lot of processor operations to complete the search meaning that it can be very slow on large arrays, the Binary search is tremendously more efficient in terms of processing time but does require that the array be sorted which may not be an easy task in itself! The relative efficiency of the two searches depends upon the arrays to which they are applied. The Selection sort and Bubblesort are two sorting techniques considered, the selection sort is very direct and easy to program but for larger arrays the bubblesort requires less processor power, the bubblesort also has the advantage that if the array is partially sorted or composed of similar data then it can be made to finish immediately the array is sorted rather than continuing blindly through to the end of the algorithm as the selection sort is required to do. Again the relative efficiency of the two methods depends on the arrays to be sorted.

(Go Up)

Sources

L.A1lison, Dept. of Computer Science UWA 1984,
School of Computer Science & Software Engineering, Monash 1999