Mastering Algorithms With C - Kyle Loudon [16]
Q: The operation list_rem_next removes an element from a linked list (see Chapter 5). If iptr is an integer pointer we would like set to an integer removed from a list, how might we call list_rem_next as an alternative to the approach presented in the chapter? A prototype for the function is shown here, where list is the list, element references the element preceding the one to remove, and upon return, data references the data removed.
int list_rem_next(List *list, ListElmt *element, void **data);
A: An alternative way to call list_rem_next is shown here. In this approach, iptr is cast to a void pointer instead of a pointer to a void pointer. This method is acceptable because void pointers are compatible with all others. However, our original approach is clearer because it is consistent with the prototype of list_rem_next.
retval = list_rem_next(&list, element, (void *)&iptr);
Related Topics
C++
An object-oriented language that enforces many practices of good software engineering. As one example, it supports constructors and destructors for datatypes. These mechanisms provide a compact way of managing memory within instances of the type, thus avoiding many of the problems associated with memory leaks and pointers in C.
Heap-based allocation
The type of memory allocation provided by the C functions malloc and realloc. Heap-based allocation is often called dynamic storage allocation. This allows a program to request more memory as it needs it rather than allocating a fixed amount at compile time.
Chapter 3. Recursion
Recursion is a powerful principle that allows something to be defined in terms of smaller instances of itself. Perhaps there is no better way to appreciate the significance of recursion than to look at the mysterious ways nature uses it. Think of the fragile leaf of a fern, in which each individual sprig from the leaf's stem is just a smaller copy of the overall leaf. Think of the repeating patterns in a reflection, in which two shiny objects reflect each other. Examples like these convince us that even though nature is a great force, in many ways it has a paradoxical simplicity that is truly elegant. The same can be said for recursive algorithms; in many ways, recursive algorithms are simple and elegant, yet they can be extremely powerful.
In computing, recursion is supported via recursive functions. A recursive function is a function that calls itself. Each successive call works on a more refined set of inputs, bringing us closer and closer to the solution of a problem. Most developers are comfortable with the idea of dividing a larger problem into several smaller ones and writing separate functions to solve them. However, many developers are less comfortable with the idea of solving a larger problem with a single function that calls itself. Admittedly, looking at a problem in this way can take some getting used to. This chapter explores how recursion works and shows how to define some problems in a recursive manner. Some examples of recursive approaches in this book are found in tree traversals (see Chapter 9), breadth-first and depth-first searches with graphs (see Chapter 11), and sorting (see Chapter 12 ).
This chapter covers:
Basic recursion
A powerful principle that allows a problem to be defined in terms of smaller and smaller instances of itself. In computing, we solve problems defined recursively by using recursive functions, which are functions that call themselves.
Tail recursion
A form of recursion for which compilers are able to generate optimized code. Most modern compilers recognize tail recursion. Therefore, we should make use of it whenever we can.
Basic Recursion