数据结构算法之递归和栈结构

递归

程序调用自身的编程技巧称为递归
简单案例：n的阶乘

//n的阶乘
int sum(int n) {
    if (n == 1) {
        return n;
    }

    return n * sum(n - 1);
}

汉诺塔

汉诺塔问题描述：3个柱为a、b、c，圆盘最初在a柱，借助b柱移到c柱
规则;每次只能挪动一个 大的必须在下面
动画演示：（图片是网上的）

汉诺塔三个圆盘的过程.gif 汉诺塔四个圆盘的过程.gif

对3个圆盘进行详细分析(假设最上面的是第1个盘子，中间是第2个盘子，最下面最大的第3个盘子)

把1个盘子从A挪到C
把2个盘子从A挪到B
把1个盘子从C挪到B
把2个盘子从A挪到B
把3个盘子从A挪到C
把1个盘子从B挪到A
把2个盘子从B挪到C
把1个盘子从A挪到C
把2个盘子从B挪到C
把3个盘子从A挪到C

简单分析就是，当就1个盘子的时候直接将盘子从A移动到C，若不是，则将n-1个盘子A借助C移动B，然后B中盘子借助A移动到C

void hannuota(int n,char start,char help,char end){
     if(n==1){
         LOGE("把%d个盘子从%c挪到%c",n,start,end);
     }else{
         //把A挪动B
         hannuota(n-1,start,end,help);
         LOGE("把%d个盘子从%c挪到%c",n,start,end);
         hannuota(n-1,help,start,end);
         LOGE("把%d个盘子从%c挪到%c",n,start,end);
     }

}

数组实现栈

代码有详细介绍，不阐述

#ifndef NDK_ARRAYSTACK_H
#define  NDK_ARRAYSTACK_H

#include "malloc.h"
#include <assert.h>
template<class E>
class ArrayStack {
    //栈是先进后出
private:
    //栈顶元素的角标
    int top = -1;
    E *array = NULL;
    //栈的初始长度
    int size = 10;
public:
    ArrayStack();

    ~ArrayStack();

public:
    //栈是否是空的
    bool isEmpty();

    /**
     * 弹出栈顶的元素
     */
    E pop();

    /**
     * 获取栈顶的元素但是不弹出
     */
    E peek();

    /**
     * 将元素入栈
     * @param e
     */
    void push(E e);

    void growArray();
};

template<class E>
ArrayStack<E>::ArrayStack() {
    array = (E*)malloc(sizeof(E) * size);
}
/**
 * 析构函数 释放内存
 */
template<class E>
ArrayStack<E>::~ArrayStack() {
    delete[]array;
}
/**
 * 判断是否为空
 */
template<class E>
bool ArrayStack<E>::isEmpty() {
    return top == -1;
}
/**
 * 弹出栈顶的元素
 */
template<class E>
E ArrayStack<E>::pop() {
    assert(top>=0);
    return array[top--];
};
/**
 * 获取栈顶的元素但是不弹出
 */
template<class E>
E ArrayStack<E>::peek() {
    return array[top];
}
/**
 * 添加数据
 */
template<class E>
void ArrayStack<E>::push(E e) {
    //判断是否有足够的空间
    if (top + 1 == size) {
        //扩容
        growArray();
    }
    array[++top] = e;
}
/**
 * 扩容
 */
template<class E>
void ArrayStack<E>::growArray() {
    size += size >> 1;
    //重新开辟内存空间
    array = (E*)realloc(array, sizeof(E) * size);
}

#endif