C - 单链表倒序遍历

思路：

利用函数栈的 后进先出 的特性

如果链表太深，会爆掉函数栈的

// jave.lin 2020.4.30
#include 
#include 

typedef struct LL LinkedList;
typedef struct stack Stack;

#define GET_LL(address) ((LinkedList*)(((void*)0)+address))
#define GET_PTR(offset) (NULL+offset)
#define GET_TYPE_PTR(offset,type) ((type)(NULL+offset))

typedef struct LL {
    int value;
    LinkedList* next;
} LinkedList;

typedef struct stack {
    size_t size;
    int pos;
    int* address;
} Stack;

size_t GetLLSize(LinkedList* ll) {
    size_t ret = 0;
    while(ll != NULL) {
        ++ret;
        ll = ll->next;
    }
    return ret;
}

Stack* MallocStack(size_t size) {
    Stack* ret = (Stack*)(malloc(sizeof(Stack)));
    if (ret == NULL) return NULL;
    ret->pos = -1;
    ret->size = size;
    ret->address = malloc(sizeof(int) * size);
    if (ret->address == NULL) {
        free(ret);
        return NULL;
    }
    return ret;
}
int IsEmptyStack(Stack* stack) {
    return (stack->pos == -1) ? 1 : 0;
}
int IsFullStack(Stack* stack) {
    return (stack->pos == stack->size - 1) ? 1 : 0;
}
void FreeStack(Stack* stack) {
    free(stack->address);
    free(stack);
}
int PushStack(Stack* stack, void* ptr) {
    if (IsFullStack(stack) == 1) return 0;
    *(stack->address + (++stack->pos)) = (int)ptr;
    return 1;
}
void* PopStack(Stack* stack) {
    if (IsEmptyStack(stack) == 1) return NULL;
    return (void*)(*(stack->address + (stack->pos--)));
}
void StackIterate(Stack* stack, void (* cb)(void*)) {
    while(!IsEmptyStack(stack)) {
        cb(PopStack(stack));
    }
}

// 根据递归来倒序遍历
void ReverseIterate(LinkedList* ll, void (* cb)(LinkedList*)) {
    if (ll == NULL) return;

    if (ll->next != NULL) {
        ReverseIterate(ll->next, cb);
        cb(ll);
    } else {
        cb(ll);
    }
}

// 根据数组来逆序，但是没什么实用性，因为链表是变长与可不连续而设计的
// 但是数组是定长，与连续内存特性的，resize array来变长数组效率不高
// 而且resize后，如果是插入中间数据，则需要将后续数据遍历挪到
// 链表与数组各有优缺点：
// 数组：
//      优点：连续紧凑内存，而减少内存用量
//      缺点：定长，不方便插入、删除数据
// 链表：
//      优点：变长，灵活插入、删除
//      缺点：需要多一份指针地址内存
void ReverseIterate1(LinkedList* ll, void (* cb)(LinkedList*)) {
    
    if (ll == NULL) return;

    size_t size = GetLLSize(ll);
    int arr[size];

    for (size_t i = 0; i next;
    }

    for (size_t i = 0; i address + stack->pos), 
        //     (int)ll,
        //     (stack->address + stack->pos));
        ll = ll->next;
    }

    // StackIterate(stack, ) // 回调不一样的签名没啥用，虽然还可以再套一层callback来处理这里的cb回调，但没必要了
    while(IsEmptyStack(stack) != 1) { // 还是直接遍历吧
        cb((LinkedList*)PopStack(stack));
    }

    FreeStack(stack);
}

void printNode(LinkedList* node) {
    printf("%d,", node->value);
}

void freeNde(LinkedList* node) {
    free(node);
}

int main() {

    LinkedList* header = malloc(sizeof(LinkedList));
    header->value = -1;

    // construct & input value
    LinkedList* p = header;
    printf("initialize : %d,", p->value);
    for (size_t i = 0; i next = malloc(sizeof(LinkedList));
        p->next->value = i;
        printf("%d,", i);
        p = p->next;
    }
    p->next = NULL;
    printf("\n");

    // 倒序遍历：递归
    printf("reverse iterate linked list by [recursion]:\n");
    ReverseIterate(header, printNode);
    printf("\n");
    // 倒序遍历：数组
    printf("reverse iterate linked list by [array]:\n");
    ReverseIterate1(header, printNode);
    printf("\n");
    // 倒序遍历：栈
    printf("reverse iterate linked list by [stack]:\n");
    ReverseIterate2(header, printNode);
    printf("\n");

    // 总结为：可以使用多种多样的方式来倒序遍历
    // 只要某个数据结构可以支持遍历就好了

    printf("positive iterate linked list:\n");
    p = header;
    while(p != NULL) {
        printf("%d,", p->value);
        p = p->next;
    }

    printf("\n");
    // 倒序遍历
    ReverseIterate(header, freeNde);

    printf("done!\n");
    return 0;
}

输出

initialize : -1,0,1,2,3,4,5,6,7,8,9,
reverse iterate linked list by [recursion]:
9,8,7,6,5,4,3,2,1,0,-1,
reverse iterate linked list by [array]:
9,8,7,6,5,4,3,2,1,0,-1,
reverse iterate linked list by [stack]:
9,8,7,6,5,4,3,2,1,0,-1,
positive iterate linked list:
-1,0,1,2,3,4,5,6,7,8,9,
done!

总结

可以使用多种多样的方式来倒序遍历 只要某个数据结构可以支持遍历就好了

References

• 单链表的逆序遍历函数