Recently, Professor Zhou Ligong has published his meticulous work "Programming and Data Structure" after years of effort. The electronic version is now available for free download by electronic engineers and college students. With the authorization from Professor Zhou Ligong, this book's content is being serialized.
> > >> 1.1.1 Algorithm Interface
Since an iterator can easily move forward or backward, it can be used to implement the bubble sort algorithm. Its function prototype is:
`void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap);`
Here, `p_if` represents the iterator interface used by the algorithm. `begin` and `end` are a pair of iterators that define the range of data the algorithm processes. This allows the algorithm to handle any data range, not just the entire container. To ensure the validity of the range, a front-closed interval representation is typically used, meaning the range [begin, end) includes all elements between `begin` and `end`, excluding `end`. When `begin == end`, the range is empty.
The `compare` function is also a comparison function, but it compares the values of two iterators. Its type `compare_t` is defined as:
`typedef int (*compare_t)(iterator_t it1, iterator_t it2);`
The `swap` function exchanges the data corresponding to two iterators. Its type `swap_t` is defined as:
`typedef void (*swap_t)(iterator_t it1, iterator_t it2);`
As you can see, the interface only contains an iterator, with no trace of the container itself. This completely separates the container from the bubble sorting algorithm. The iterator-based bubble sorting algorithm is shown in Listing 3.56.
Listing 3.56: Bubble Sort Algorithm Function
```c
void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap)
{
int flag = 1; // flag = 1 indicates no exchange occurred
iterator_t it1 = begin; // it1 points to the first element
iterator_t it2 = end;
iterator_t it_next; // it_next points to the next element of it1
if (begin == end) { // No elements to process
return;
}
iterator_prev(p_if, &it2); // it2 points to the last element to sort
while (it2 != begin) {
it1 = begin;
flag = 1;
while (it1 != it2) {
it_next = it1; // Copy current iterator
iterator_next(p_if, &it_next); // it_next becomes the next element
if (compare(it1, it_next) > 0) {
swap(it1, it_next); // Swap contents
flag = 0; // flag = 0 indicates an exchange occurred
}
it1 = it_next; // Move to the next element
}
if (flag) return; // No exchange, already sorted
iterator_prev(p_if, &it2); // Move it2 forward
}
}
```
Let’s test the iterator-based bubble sorting algorithm with a simple example. See Listing 3.57 for details. We will insert integers into a doubly linked list, add 5, 4, 3, 2, 1, then call `dlist_foreach()` to traverse the list and check if it meets expectations. After that, we will call the `iter_sort()` function from the algorithm library. Once the sorting is complete, the elements should be arranged in ascending order. We will call `dlist_foreach()` again to verify the result.
Listing 3.57: Use Doubly Linked Lists, Algorithms, and Iterators
```c
#include
#include "iterator.h"
typedef struct _dlist_int {
dlist_node_t node; // Include linked list nodes
int data; // Integer type data
} dlist_int_t;
int list_node_process(void *p_arg, dlist_node_t *p_node) {
printf("%d ", ((dlist_int_t *)p_node)->data);
return 0;
}
static int __compare(iterator_t it1, iterator_t it2) {
return ((dlist_int_t *)it1)->data - ((dlist_int_t *)it2)->data;
}
static void __swap(iterator_t it1, iterator_t it2) {
int data = ((dlist_int_t *)it2)->data;
((dlist_int_t *)it2)->data = ((dlist_int_t *)it1)->data;
((dlist_int_t *)it1)->data = data;
}
int main(int argc, char *argv[]) {
iterator_if_t iterator_if;
dlist_head_t head; // Define the header node
dlist_int_t node[5]; // Define 5 node spaces
int i;
dlist_init(&head);
for (i = 0; i < 5; i++) {
node[i].data = 5 - i; // Values are 5 ~ 1
dlist_add_tail(&head, &(node[i].node));
}
dlist_iterator_if_get(&iterator_if);
printf("Before bubble sort:");
dlist_foreach(&head, list_node_process, NULL); // Print before sorting
iter_sort(&iterator_if, dlist_begin_get(&head), dlist_end_get(&head), __compare, __swap);
printf("\nAfter bubble sort:");
dlist_foreach(&head, list_node_process, NULL); // Print after sorting
return 0;
}
```
In this example, the `dlist_foreach()` traversal function is used. Since the iterator can implement bubble sorting, a simple traversal algorithm can be implemented using the iterator, which is independent of the specific container. The prototype of the traversal function is:
`void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg);`
Where `p_if` represents the iterator interface used by the algorithm, `begin` and `end` represent the range of iterators the algorithm needs to process, and `visit` is a user-defined function to traverse the iterator. Its type `visit_t` is defined as:
`typedef int (*visit_t)(void *p_arg, iterator_t it);`
Each time a node is traversed, the function pointed to by `visit` is called. The value passed to `p_arg` is the user parameter, which is the same as the `p_arg` parameter of the `iter_foreach()` function. The value of `p_arg` is entirely determined by the user and passed to the iterator. The current value is the point of traversal.
The `iter_foreach()` function is shown in Listing 3.58.
Listing 3.58: Traversal Algorithm Function
```c
void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg) {
iterator_t it = begin;
while (it != end) {
if (visit(p_arg, it) < 0) { // If the return value is negative
return; // User terminates the traversal
}
iterator_next(p_if, &it); // Move the iterator forward
}
}
```
Now, in Listing 3.57, lines 43 and 48 use the `dlist_foreach()` function. Can they be modified to use `iter_foreach()` instead and achieve the same effect?
If the data is stored in an array, how would you use the existing bubble sorting algorithm? Since arrays are also containers, you only need to implement array-based iterators, as shown in Listing 3.59.
Listing 3.59: Using Arrays to Implement Iterator Interface
```c
typedef int element_type_t;
static void __array_iterator_next(iterator_t *p_iter) {
(*(element_type_t **)(p_iter))++; // Move the iterator to the next data
}
static void __array_iterator_prev(iterator_t *p_iter) {
(*(element_type_t **)(p_iter))--; // Move the iterator to the previous data
}
void array_iterator_if_get(iterator_if_t *p_if) {
iterator_if_init(p_if, __array_iterator_next, __array_iterator_prev);
}
```
Based on the new iterator, the bubble sort algorithm can also be used directly. See Listing 3.60.
Listing 3.60: Use Arrays, Algorithms, and Iterators
```c
#include
#include "iterator.h"
static int __visit(void *p_arg, iterator_t it) {
printf("%d ", *(int *)it);
return 0;
}
static int __compare(iterator_t it1, iterator_t it2) {
return *(int *)it1 - *(int *)it2;
}
static void __swap(iterator_t it1, iterator_t it2) {
int data = *(int *)it2;
*(int *)it2 = *(int *)it1;
*(int *)it1 = data;
}
int main(int argc, char *argv[]) {
iterator_if_t iterator_if;
int a[] = {5, 3, 2, 4, 1};
array_iterator_if_get(&iterator_if);
printf("Before bubble sort:");
iter_foreach(&iterator_if, a, a + 5, __visit, NULL);
iter_sort(&iterator_if, a, a + 5, __compare, __swap);
printf("\nAfter bubble sort:");
iter_foreach(&iterator_if, a, a + 5, __visit, NULL);
return 0;
}
```
It can be seen that the iterative bubble sorting algorithm is also reused. If there are hundreds of functions in the algorithm library, implementing just two functions of the iterator interface can allow the code to be reused multiple times. Clearly, an iterator provides more flexible traversal behavior, allowing access to elements in a container in any order without exposing the internal structure of the container.
The portable WiFi mini Home Projector has reduced the size and weight on the basis of the traditional projector, which is convenient to carry out and is no longer limited to one location. The connection is simple, the projector can be started with only a power cord, and the playback resources can be obtained by connecting WiFi and USB
led mini projector,best mini projector,devanti mini video projector,mini projector with wifi,mini projector wifi bluetooth
Shenzhen Happybate Trading Co.,LTD , https://www.happybateprojector.com