Further Links Contact Us Search Help

Syllabus | Exams | Assessment | Resources | Site reviews | Careers

Software Design and Development

Home > Software Design and Development > Core > Software Development Cycle > Standard Algorithms: Arrays and strings

Standard array and string manipulation algorithms used in software solutions

This material describes and implements the standard array and string manipulation logic required by the syllabus for use in software solutions using pseudocode.

Syllabus outcomes

H4.2 A student applies appropriate development methods to solve software problems.

H4.3 A student applies a modular approach to implement well-structured software solutions and evaluates their effectiveness.

H5.2 A student creates and justifies the need for various types of documentation required for a software solution.

H5.3 A student selects and applies appropriate software to facilitate the design and development of software solutions.

Students must learn to recognise the logic of specified standard approaches, apply those standard approaches as part of the solution to a complex problem and document the logic required to solve a problem using both pseudocode and flowcharts.

The following headings may help you navigate:

Low level functions for array manipulation

Finding the maximum and minimum values in arrays

Low level functions for character manipulation

Processing strings to extract, insert and delete characters

Low level functions for array manipulation

A number of low level array processing functions are available in most languages. Some of these functions are useful to write standard algorithms. A very useful function calculates the size of an array. Array size is set by the programmer, but most arrays are not full, they contain blank records at the end. This is necessary because records must be added to arrays and deleted from arrays. The function ARRAYLENGTH is available with variations in most languages. It accesses (or reads) an array and returns the index position of the last element in the array. It is used in many of the standard algorithms which follow.

Finding the maximum and minimum values in arrays

Objective: The objective of this standard procedure is to read all elements in an unsorted array and return the maximum (or minimum) element stored in the array.

Concept: The idea behind this algorithm is to read the array sequentially once (i.e. make one pass or traverse through the array) and find (or return) the required element in a variable. As we read the array we store the largest (or smallest) element encountered so far in a variable. Call it maxval (or minval). We compare the value in maxval with the element in each other index position we read. If the element in the new index position is larger than the value in maxval it becomes our new maximum value by overwriting the value in maxval with the new maximum. When we have finished reading the file, comparing the elements to the maximum value encountered so far and overwriting maxval, as necessary, the final value in maxval will be the largest value (or element) in the array.

Algorithm

BEGIN FINDMAX
	highindex = ARRAYLENGTH(element)
	index = 1
	maxval = element(index)
	WHILE index <= highindex
		IF element(index) > maxval
			THEN maxval = element(index)
		ENDIF
	index = index + 1
	ENDWHILE
	DISPLAY "The maximum element is " maxval
END FINDMAX

Activity: Find maximum or minimum value in an array

1. Using the test data in the table below complete a desk check of the algorithm by filling in the trace table provided.
   
   Test data FINDMAX
   
   

   index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   element	56	63	75	12	54	60	69	47	55	57	61	78	51

   
   Trace Table FINDMAX
   
   

   highindex	index	element	maxval	action

   
   
2. Modify this algorithm to find both the maximum and minimum element in the array.
3. Modify this algorithm to find the maximum value and the index position of the maximum element in the array.
4. Describe how you would modify this algorithm if there was more than one occurrence of the maximum value.

Check your answers

Low level functions for character manipulation

A number of low level string processing functions are available in most languages. Some of these low level functions are useful to write functions to extract, delete and insert characters in string data. Indeed functions to extract, delete and insert in string data are also available but it is necessary for you to understand the logic behind these standard methods and be able to construct algorithms to extract, delete and insert characters.

STRINGLENGTH An array rarely contains exactly the number of indexed positions as there are characters in a string. The array is padded with trailing spaces. The function STRINGLENGTH reads the array, computes the length of the character string and returns the length as a variable. It is similar to ARRAYLENGTH.

FIRSTNAME

Index	1	2	3	4	5	6	7	8	9	10
Value	W	I	L	L	I	A	M

In the example above STRINGLENGTH((FIRSTNAME(index)) returns 7.

SURNAME

Index	1	2	3	4	5	6	7	8	9	10
Value	B	A	T	E	S

In the example above STRINGLENGTH((SURNAME(index)) returns 5.

CONCATENATESTRING Concatenate means join. This function will join two or more strings into a new string.

FULLNAME = CONCATENATESTRING(FIRSTNAME,SURNAME)

Using the example above.

FULLNAME

index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
value	W	I	L	L	I	A	M				B	A	T	E	S

Obviously this is not quite what we wanted. We must use the function below, TRIMSTRING, before using CONCATENATESTRING.

TRIMSTRING Removes unwanted leading and trailing spaces from string data.

FNAME = TRIMSTRING(FIRSTNAME)

SNAME = TRIMSTRING(SURNAME)

FULLNAME = CONCATENATE(FNAME,SNAME)

Using the example above.

FULLNAME

Index	1	2	3	4	5	6	7	8	9	10	11	12
Value	W	I	L	L	I	A	M	B	A	T	E	S

Obviously this is not quite what we wanted either.

Control of spaces: This technique allows the programmer to set spaces in string manipulation. It involves creating an array, traditionally called SPACE, containing just one value, A space (set as " ") and inserting it when required.

SPACE(1) = " "

PARTNAME = CONCATENATE(FNAME,SPACE)

FULLNAME = CONCATENATE(PARTNAME,SNAME)

Using this technique the desired result is obtained because the programmer has control of the spaces.

FULLNAME

index	1	2	3	4	5	6	7	8	9	10	11	12	13
element	W	I	L	L	I	A	M		B	A	T	E	S

Now that we have some basic understanding of string data and low level functions to manipulate string data, let's look at the standard algorithms prescribed in the syllabus.

Processing strings to extract, insert and delete characters

Objective: To extract, insert and delete characters in a string of characters stored in an array.

Concept: The idea behind these algorithms is manipulating character data in arrays. A great deal of data of the type text (character or alphanumeric) is processed by software. This data must be kept in its input sequence to remain meaningful. This is referred to as a string of characters and it is often shown by enclosing in "quote marks like this". Strings of characters are stored and processed in arrays.

Extract data from a string

This procedure does not change the original string but copies the required portion. To extract characters from a string we must know the name of the array holding the data and the index of the start and the stop positions for extracting the data.

Deleting characters from a string

This function "cuts" characters from a string reducing the length of the string by the number of characters removed. It is necessary to know the name of the array, the index of the start position and the index of the stop position in the array. The algorithm uses the EXTRACT function and the CONCATENATE function. The characters up to the start index are extracted and temporarily stored. The characters after the stop index are then extracted and added to the temporary string.

Inserting characters in a string

This function "pastes" characters into a string increasing the length of the string by the number of characters inserted. We need to know the name of the array, the extra string and the start index position where the characters are to be inserted. Again the functions EXTRACTSTRING and CONCATENATESTRING are used. We extract those characters before the start index, concatenate them with the inserted characters then concatenate this larger string with the remainder of the original string.

Bibliography

Brookshear, J. Glenn. (1994) Computing Science an overview Fourth Edition, The Benjamin/Cummings Publishing Company.

Stephens, R (1998) Ready-to-Run Visual Basic Algorithms Second Edition,

Wiley Computer Publishing

Further Resources

Fowler, A (2000) Software Design and Development, First Edition, Heinemann

This work was prepared by

Jennifer Thomson