C语言中迭代器在数据结构中的应用

C语言中，为给定数据结构设计迭代器的思路。

迭代器

在C语言中的迭代器中，迭代器的实现是这样

typedef struct listIter {
    Node * next;
} listIter;

listIter * makeIterator(list * list) {
    listIter * iter;
    iter = malloc(sizeof(* iter));
    iter->next = list->head;
    return iter;
}

Node * next(listIter * iter) {
    Node * current = iter->next;
    if (current != NULL) {
        iter->next = current->next;
    }
    return current;
}

以链表为例

假定我们设计如下链表数据结构，

typedef struct Node {
    struct Node * prev;
    struct Node * next;
    void * value;
} Node;

typedef struct list {
    Node * head;
    Node * tail;
    unsigned long len;
} list;

list * listCreate(void) {
    struct list * list;
    list = malloc(sizeof(* list));
    list->head = list->tail = NULL;
    list->len = 0;
    return list;
}

void listDelete(list * list) {
    unsigned long len;
    Node * current, * next;
    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
    free(list);
}

list * addToHead(list * list, void * value) {
    Node * node;
    node = malloc(sizeof(* node));
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}

list * addToTail(list * list, void * value) {
    Node * node;
    node = malloc(sizeof(* node));
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

list * insertIntoList(list * list, Node * old, void * value) {
    Node * node;
    node = malloc(sizeof(* node));
    node->value = value;

    node->prev = old;
    node->next = old->next;
    if (list->tail == old) {
        list->tail = node;
    }

    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}
void deleteNode(list * list, Node * node) {
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    free(node);
    list->len--;
}

容易理解，不同数据结构需要不同的迭代器，不存在通用的适合任何数据结构的迭代器。因为每个迭代器都需要知道给定数据结构的构造从而定制遍历方式。

使用迭代器

int main(int argc, char ** argv) {
    list * list = listCreate();
    int e1 = 1;
    int e2 = 2;
    int e3 = 3;
    int e4 = 0;
    int e5 = -1;
    addToTail(list, &e1);
    addToTail(list, &e2);
    addToTail(list, &e3);
    addToHead(list, &e4);
    addToHead(list, &e5);

    Node * node;

    listIter * iter = makeIterator(list);
    while ((node = next(iter)) != NULL) {
        printf("%d\n", * (int* )(node->value));
    }

    listDelete(list);
    free(iter);

    return 0;
}

运行如下

$ gcc list.c ;./a.out
-1
0
1
2
3

转载请包括本文地址：https://allenwind.github.io/blog/4411
更多文章请参考：https://allenwind.github.io/blog/archives/