The generalization of the algorithm, you may have experienced these pits! | Zhou Ligong teaches you to learn software design

The first chapter is the basis of programming. This article is 1.6.3 generic programming.

> > > >   1.   Generic programming

In the following, we will further investigate the generalization of the algorithm by taking a simple loop lookup as an example. Suppose you want to write a findValue() function, looking for a specific int value in the array array, as shown in Listing 1.29.

Listing 1.29 findValue() lookup function (1)

1 int *findValue(int *arrayHead, int arraySize, int value)

2 {

3 for(int i =0; i < arraySize; ++i)

4 if(arrayHead[i] == value)

5 break;

6 return &(arrayHead[i]);

7 }

The function looks up the value in a range and returns a pointer to the first qualified element it finds. If not found, returns the next position (address) of the last element. "The next position of the last element" is called end, its role is to return end to say "find no results", why not return null? Because the end pointer can have a generalization effect on other kinds of data structures, this is not possible with null.

When learning arrays, we are warned not to go beyond the scope of the subscript, but in fact a pointer to the array element can not only legally point to any position in the array, but also to any position other than the end of the array. However, when the pointer points to a position other than the end of the array, it can only be used to compare with other array pointers, and cannot indirectly reference its value. The findValue() function is used as follows:

Const int arraySize = 7;

Int array[arraySize] = {0, 1, 2, 3, 4, 5, 6};

Int *end = array + arraySize;

Int *ip = findValue(array, sizeof(array) / sizeof(int), 4);

If(ip == end)

Return false;

Else

Return true;

Obviously, the findValue() function exposes the implementation details of the array, such as arraySize, which is too dependent on a particular data structure. So how do you design an algorithm that works for most data structures? Or how do you implement all the operations correctly on the unknown data structure that will be processed? In fact, a sequence has a beginning and an end. You can use ++ to get the next element, or you can use "*" to get the value of the current element.

Obviously, it is important for someone reading the code to understand your intentions to take a name that is not misleading. For inclusion ranges, commonly used first and last. For inclusion/sorting ranges, commonly used begin and end. For example, for most arrays that require fragmentation, using begin and end to indicate inclusion/excluding ranges is the best option. Unfortunately, ambiguous English words like limit, filter, and length can be confusing, and max_ and min_ are good prefixes when defining the upper or lower bounds of a value.

In order for the findValue() function to work with all types of data structures, the operation should be more abstract, let the findValue() function accept two pointers as arguments, indicating an operation scope, as shown in Listing 1.30.

Program list   1.30   findValue() find function (2)

1 int *findValue(int *begin, int *end, int value)

2 {

3 while(begin != end && *begin != value)

4 ++begin;

5 return begin;

6 }

Since the return value of the findValue function begin is a pointer, the function is a function that returns a pointer, that is, a pointer function. This function looks up the value in the "before, after" range (containing the current element of the begin iterator and the previous element of the end iterator) and returns a pointer to the one it finds. The first eligible element, if not found, returns end. The reason here is to use "!=" instead of "<" to determine if the end of the array is reached, because this is more accurate. The findValue() function is used as follows:

Const int arraySize = 7;

Int array[arraySize] = {0, 1, 2, 3, 4, 5, 6};

Int *end = array + arraySize;

Int *ip = findValue(array, end, 4);

If(ip == end)

Return false;

Else

Return true;

Of course, the findValue() function can also be easily used to find the sub-scope of array:

Int *ip = findValue(array + 2, array + 5, 3);

If(ip == end)

Return false;

Else

Return ture;

Thus, there is no operation in the findValue() function for a specific integer array, that is, as long as the type of the operation object is abstracted and the representation of the operation object and the movement behavior of the scope object are abstracted, the whole Algorithms can work on the same level of abstraction. The process of the entire algorithm is usually referred to as the generalization of the algorithm, referred to as generalization. The purpose of generalization is to use the same findValue() function to handle various data structures and to create reusable code through abstraction.

If a sequence is ordered, you don't need to use findValue() to find it from the starting position. You can use the bsearch() binary search algorithm provided by standard C. For a longer sequence, the binary search is also faster than the findValue() linear search method. Even if there are only 10 elements in the sequence, it is enough to reflect the comparative advantage of binary search. For a sequence of 1000 elements, a maximum of 10 comparisons is required, which is 200 times faster.

Obviously, the best way to find the maximum value of an element in an array is to specify the range of elements by passing 2 pointers. One pointer identifies the beginning of the array and the other pointer identifies the end of the array. such as:

Int iMax(const int *begin, const int *end);

Obviously, if you just pass the pointer, the data is likely to be modified. If you don't want the data to be modified, pass a pointer to an integer constant. An example of using a for loop is as follows:

For(ptr = begin; ptr != end; ptr++)

Total = total +*ptr;

Set ptr to a pointer to the first element to be processed (the element pointed to by begin) and add *ptr (the value of the element) to total. The loop then increments the ptr by incrementing it to point to the next element. As long as ptr is not equal to end, the process will continue. When ptr is equal to end, it will point to the position after the last element in the range, at which point the loop ends. Second, notice how different function calls specify different ranges in the array. such as:

Int array[] = {39, 33, 18, 64, 73, 30, 49, 51, 81};

Int n = sizeof(array) / sizeof(array[0]);

Int *past = array + n;

Int max = iMax(array, array + n);

Int max = iMax(array, array + 3);

Int max = iMax(array +3, array + 8);

The pointer array+n points to a position after the last element (the array has only n elements, and the address of the last element is array+n-1), so the range [array, array+n] specifies the entire array. The same array, array+3 specifies the first 3 elements, and so on. Note that according to the pointer subtraction rule, the expression end–begin is an integer value equal to the number of elements in the array.