Flowcharts that walk along a list
Published . By the DiagramDesk team.
Once a program holds more than a few values, it keeps them in a list, called an array in C, and reaches each one by its position. The loop from the previous page becomes a walk along those positions. Three exercises cover the patterns worth knowing: keep the best so far, stop when you find it, and work in from both ends.
PositionsLargest in a listLinear searchReverse a string
Writing positions in a flowchart
Python and C both count positions from 0, so a list of n values runs from position 0 to position n − 1. Flowcharts have no agreed way to write "the value at position i". Pseudocode usually writes x[i]; the charts on this page say "x at i" in words, which reads the same and cannot be mistaken for anything else. Whichever your course uses, use it the same way throughout.
Every loop here starts its counter at 0 or 1 on purpose, and ends it with a test against n. Getting either end wrong by one, the off-by-one error, is the commonest bug in list code, and a flowchart is a good place to catch it: trace the loop with a list of two items and count the passes.
The largest number: keep the best so far
The idea is the one anyone would use by hand: remember the biggest number seen so far, look at each of the others in turn, and replace the one you are remembering whenever you meet a bigger one.
Pseudocode
START
READ n
READ x[0] … x[n − 1]
largest ← x[0]
FOR i ← 1 TO n − 1 DO
IF x[i] > largest THEN
largest ← x[i]
END IF
END FOR
PRINT largest
ENDPython
n = int(input())
x = [int(input()) for _ in range(n)]
largest = x[0]
for i in range(1, n):
if x[i] > largest:
largest = x[i]
print(largest)C
#include <stdio.h>
int main(void) {
int n, x[100];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &x[i]);
int largest = x[0];
for (int i = 1; i < n; i++)
if (x[i] > largest)
largest = x[i];
printf("%d\n", largest);
return 0;
}The inputs each version handles
- Python
- At least one number: with none there is no largest, and x[0] fails.
- C
- Between 1 and 100 numbers, the size of the array x. With none, x[0] is read before anything is stored in it; with more, the numbers run past the end of the array.
The starting value is where marks go. Starting largest at 0 looks harmless and works on every test with a positive number in it; give it −7, −2 and −9 and it prints 0, a number that is not in the list. Starting from the list's own first value is always right, and it means the loop can begin at position 1, since position 0 has already been looked at. The test cases this page was checked with include that all-negative list for exactly this reason.
Linear search: stop when you find it
A linear search looks at each value in turn until it finds the one it wants, or runs out. The answer is a position, and it needs a value meaning "not found": −1 is the usual choice, since no real position is negative. The loop's test has two halves, joined by and: keep going while there are values left and nothing has been found yet.
Pseudocode
START
READ n
READ x[0] … x[n − 1]
READ target
position ← −1
i ← 0
WHILE i < n AND position = −1 DO
IF x[i] = target THEN
position ← i
END IF
i ← i + 1
END WHILE
IF position = −1 THEN
PRINT "Not found"
ELSE
PRINT position
END IF
ENDPython
n = int(input())
x = [int(input()) for _ in range(n)]
target = int(input())
position = -1
i = 0
while i < n and position == -1:
if x[i] == target:
position = i
i = i + 1
if position == -1:
print("Not found")
else:
print(position)C
#include <stdio.h>
int main(void) {
int n, x[100], target;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &x[i]);
scanf("%d", &target);
int position = -1;
for (int i = 0; i < n && position == -1; i++)
if (x[i] == target)
position = i;
if (position == -1)
printf("Not found\n");
else
printf("%d\n", position);
return 0;
}The inputs each version handles
- Python
- Any number of values, none included.
- C
- Up to 100 values, the size of the array x; more run past its end.
The classic mistake is putting "Print Not found" inside the loop, on the No branch of the comparison. The program then announces "not found" for every value that does not match, often several times before it finds the one that does. Only after the loop has finished can the program know the value is not there, which is why the chart decides what to print in a separate diamond, below the loop. Stopping at the first match also settles which position is reported when a value appears twice: with 8, 3, 5, 3, 1, searching for 3 gives position 1.
Reverse a string: work in from both ends
A string is a list of characters, so the same position arithmetic applies. Reversing one in place uses two counters: i starts at the first character and j at the last. Swap the two characters they point at, move both one step towards the middle, and stop when they meet.
Pseudocode
START
READ s
i ← 0
j ← LENGTH(s) − 1
WHILE i < j DO
SWAP s[i], s[j]
i ← i + 1
j ← j − 1
END WHILE
PRINT s
ENDPython
s = list(input())
i = 0
j = len(s) - 1
while i < j:
s[i], s[j] = s[j], s[i]
i = i + 1
j = j - 1
print("".join(s))C
#include <stdio.h>
#include <string.h>
int main(void) {
char s[100];
if (fgets(s, sizeof s, stdin) == NULL)
return 0;
s[strcspn(s, "\n")] = '\0';
int i = 0, j = (int)strlen(s) - 1;
while (i < j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
i++;
j--;
}
printf("%s\n", s);
return 0;
}The inputs each version handles
- Python
- One line of any length. It reverses the characters (strictly, Unicode code points), so é stays é.
- C
- One line of up to 99 bytes, spaces included; the rest of a longer line is not read. It reverses bytes, not letters, so a letter that takes more than one byte in UTF-8, such as é, comes out garbled.
The loop test is i < j, and it is easy to get wrong in an instructive way. A loop that instead runs i along the whole length swaps every pair twice, once on the way to the middle and once on the way back, and hands the string back unchanged. The chart makes the halfway stop visible, which is a good reason to draw it before writing the code. In Python, strings cannot be changed in place, so the code turns the text into a list of characters, swaps in the list, and joins it back; in C the characters are swapped in the array directly, through a temporary variable. The C reads the whole line with fgets, spaces included, and swaps bytes, which is why the note under the code warns about accented letters.
That is the last of the three pages. The guide to making a flowchart covers charts for processes rather than programs, and the symbols guide has a sheet of the shapes to print.