CATEGORIES:
BiologyChemistryConstructionCultureEcologyEconomyElectronicsFinanceGeographyHistoryInformaticsLawMathematicsMechanicsMedicineOtherPedagogyPhilosophyPhysicsPolicyPsychologySociologySportTourism
Inserting in order into an arrayIf you have a sorted array to which you wish to add values in order, you will need a procedure which will search for the correct place in which to insert the new value. In an array there are three different places in which a new value can be inserted.
Consider the character array,
Figure 1 - Arrays : Inserting in order This array contains characters in order. If the character 'a' was to be inserted the procedure would need to move all the contents of the array along and then insert the 'a' character in the first element. The code fragment below is all that is required to perform the test. IF (new_character < character_array[I]) THEN { move them along }If this statement is true when I is equal to one, then the new value is less than all other values in the sorted array and therefore should be inserted in the first element. This means that each element of the array must be moved along one place before the new value is inserted in the first element. A problem occurs though when we try to insert a new_character which is greater than all the other values in the array. This is the situation when the array is empty or when in the above figure the algorithm is looking at element [6]. What is in an empty array element? What do you compare the new_character? A solution to this problem is to initialise all the elements of the array with the ASCII null character using a FOR loop. So that if the inserting algorithm is looking at a null character it is always ok just to insert the new_character directly into that element, and do nothing else. This null character is one of the non-printing characters of the ASCII character set, and because of this you must refer to it by its ordinal number of 0 (zero). Now if you wanted to put the '@' character into an array you could use the lines, FOR I := 1 TO MAX DO character_array[I] := '@';This will do the same job as if the code were, FOR I := 1 TO MAX DO character_array[I] := CHR(64);therefore to put the ASCII null character into the array you will need, FOR I := 1 TO MAX DO character_array[I] := CHR(0);this is in fact what I have done in the main program. Remember that ORD returns the ordinal number of its argument, and CHR returns the character associated with its numerical argument. { ------------------------------------------------------- } PROCEDURE insert(VAR character_array : AN_ARRAY; new_character : CHAR); { this procedure will : insert a character into an array in order unless all the elements are less than the new_character, meaning there is no place to insert. If the new_character is less than an element in the array, the element in character_array[I] will be over written by the character in character_array[I - 1]} VAR { declare local variables } I, J : INTEGER; inserted : BOOLEAN; BEGIN I := 1; inserted := FALSE; WHILE (I <= MAX) AND NOT(inserted) DO BEGIN IF (character_array[I] = CHR(0)) THEN { see NOTE below } BEGIN character_array[I] := new_character; inserted := TRUE; END ELSE { move contents of array along and insert new_character into character_array[I] } IF (new_character < character_array[I]) THEN BEGIN FOR J := MAX DOWNTO (I + 1) DO character_array[J] := character_array[J - 1]; character_array[I] := new_character; inserted := TRUE; END ELSE I := I + 1; END; END; { procedure insert } { ------------------------------------------------------- }NOTE :- This line of code IF (character_array[I] = CHR(0)) THENis called a special case. The boolean condition will be true if and only if the array is either completely empty or the search has reached the end of the occupied elements. In which case, the inspected element will contain the ASCII null character. Therefore if this condition is true, then insertion always takes place at that element. The rest of the procedure takes care of all the other cases. That of inserting a character somewhere in between the top and bottom of the occupied array. The FOR loop, FOR J := MAX DOWNTO (I + 1) DO character_array[J] := character_array[J - 1];is what moves all the elements along to allow a character to be inserted in order. How it does this is by starting at the top of the array, where J = MAX, and copying the contents of the element character_array[J - 1] into the element character_array[J]. Since this is a DOWNTO loop it starts at the top and works its way down to I + 1. I say I + 1 because if it were just I, then J could equal 1 at some point and the line, character_array[J] := character_array[J - 1];would make the program try to access the element [1 - 1] which is zero and which does not exist and the program would crash. This way if I equals 1 the minimum possible value of J is 2. So now we will look at a small program which will use this procedure to fill an array with characters in order. Program 3 PROGRAM array_insert(INPUT,OUTPUT); { this is a demonstration program which uses the procedure fill_array } CONST MAX = 10; TYPE AN_ARRAY = ARRAY[1..MAX] OF CHAR; VAR I, count : INTEGER; a_character : CHAR; character_array : AN_ARRAY; { -------------------------------------------------------------- } PROCEDURE insert(VAR character_array : AN_ARRAY; new_character : CHAR); { this procedure will : insert a character into an array in order unless all the elements are less than the new_character, meaning there is no place to insert. If the new_character is less than an element in the array, the element in character_array[I] will be over written by the character in character_array[I - 1]} VAR { declare local variables } I, J : INTEGER; inserted : BOOLEAN; BEGIN I := 1; inserted := FALSE; WHILE (I <= MAX) AND NOT(inserted) DO BEGIN IF (character_array[I] = CHR(0)) THEN { see NOTE below } BEGIN character_array[I] := new_character; inserted := TRUE; END ELSE { move contents of array along and insert new_character into character_array[I]} IF (new_character < character_array[I]) THEN BEGIN FOR J := MAX DOWNTO (I + 1) DO character_array[J] := character_array[J - 1]; character_array[I] := new_character; inserted := TRUE; END ELSE I := I + 1; END; END; { procedure insert } { -------------------------------------------------------------- }The program will quit if a <return> is entered at the prompt, or when count reaches MAX. That is what the line WHILE (a_character <> ' ') AND (count < MAX) DOis for. { -------------------------------------------------------------- } BEGIN { MAIN PROGRAM } { first initialise each element of the array to the ASCII null character } FOR I := 1 TO MAX Do character_array[I] := CHR(0); WRITE('Please enter a character : '); READLN(a_character); count := 0; WHILE (a_character <> ' ') AND (count < MAX) DO BEGIN count := count + 1; writeln('Count is ',count); insert(character_array, a_character); WRITELN('+---+---+---+---+---+---+---+---+---+---+'); FOR I := 1 TO MAX DO WRITE('|',character_array[I]:2,' '); WRITELN('|'); WRITELN('+---+---+---+---+---+---+---+---+---+---+'); WRITE('Please enter a character : '); READLN(a_character); END; END. { program array_insert }You may remember that the code which writes out the contents of the array is a similar piece of code to that which wrote out the contents of the array in program sort_array in chapter 5. The next part to be added to this program would be a procedure which would remove an entry from the array. I'm not going to do it for you because it is really a very simple procedure. I will however give you some help.
You really should be able to add this procedure to the program yourself. Date: 2016-03-03; view: 829
|
