1 栈的特点
栈具有先进后出(FILO)的特点，既先进后出，后进先出。
2 栈的顺序储存结构实现
2.1 数据定义
顺序储存是使用数组来储存栈中的数据。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define SIZE 10
typedef int Status;
typedef int Element;
typedef struct {
Element* data; // 数组
int top; // 栈顶索引
int maxSize; // 当前栈的最大容量
}SqStack, *SqStackP;
2.2 顺序栈的实现
初始化顺序栈，主要是初始化栈中的数组，将栈顶索引设置为-1，当栈为空时，我是使用栈顶索引为-1。使用SIZE作为数组初始的长度。maxSize记录了栈的最大容量，用于扩容时使用的。
入栈时当需要判断栈空间是否已满，如果栈空间已满，需要对占空间进行扩容。
/// 顺序表的初始化
Status initStack(SqStackP s) {
s->data = (Element *)malloc(sizeof(Element)*SIZE);
if (s->data == NULL) return ERROR;
// 初始栈顶索引
s->top = -1;
// 栈的最大容量, 用于扩容.
s->maxSize = SIZE;
return OK;
}
/// 清空栈
Status clearStack(SqStackP s) {
// 将栈顶索引置为-1
s->top = -1;
return OK;
}
/// 判断栈是否为空
Status stackIsEmpty(SqStack s) {
if (s.top == -1) {
return TRUE;
} else {
return FALSE;
}
}
/// 获取栈的长度
int stackLength(SqStack s) {
return s.top + 1;
}
/// 获取栈顶元素
Status getStackTop(SqStack s, Element *e) {
// 如果是空栈 return
if (s.top == -1) return ERROR;
*e = s.data[s.top];
return OK;
}
/// 入栈
Status push(SqStackP s, Element e) {
// 如果顺序栈容量达到最大值
if (s->top == (s->maxSize - 1)) {
// 扩容
s->data = realloc(s->data, (s->maxSize + SIZE));
if (s->data == NULL) return ERROR;
s->maxSize += SIZE;
}
s->data[s->top + 1] = e;
s->top++;
return OK;
}
/// 出栈
Status pop(SqStackP s, Element *e) {
if (s->top == -1) return ERROR;
*e = s->data[s->top];
s->top--;
return OK;
}
/// 销毁栈
Status destoryStack(SqStackP s) {
// 释放数组的空间
free(s->data);
s->top = -1;
s->maxSize = 0;
return OK;
}
/// 从栈低到栈顶遍历
void stackTraverse(SqStack s) {
if (stackIsEmpty(s)) return;
for (int i = 0; i <= s.top; i++) {
printf("%d ", s.data[i]);
}
printf("\n");
}
执行下面测试代码
SqStack stack;
int e;
if (initStack(&stack)) {
printf("顺序栈初始化成功\n");
} else {
printf("顺序栈初始化失败\n");
}
for (int i = 0; i < 20; i++) {
push(&stack, i);
}
printf("顺序栈中元素为:\n");
stackTraverse(stack);
pop(&stack, &e);
printf("栈顶弹出元素为:%d\n", e);
stackTraverse(stack);
getStackTop(stack, &e);
printf("栈顶元素为:%d\n", e);
stackTraverse(stack);
printf("是否为空栈:%d\n",stackIsEmpty(stack));
printf("栈的长度为:%d\n", stackLength(stack));
printf("清空栈\n");
clearStack(&stack);
printf("是否已经清空栈 %d, 栈长度为:%d\n",stackIsEmpty(stack), stackLength(stack));
if (destoryStack(&stack)) {
printf("栈销毁成功\n");
}
输出结果
顺序栈初始化成功
顺序栈中元素为:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
栈顶弹出元素为:19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
栈顶元素为:18
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
是否为空栈:0
栈的长度为:19
清空栈
是否已经清空栈 1, 栈长度为:0
栈销毁成功
3 栈的链式结构实现
3.1 数据结构定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Element;
// 栈结点
typedef struct StackNode {
Element data;
struct StackNode *next;
}StackNode, *StackNodeP;
typedef struct LinkStack {
StackNodeP top; // 栈顶指针
int length; // 栈的长度
}LinkStack;
3.2 链表栈的实现
/// 初始化
Status initStack(LinkStack *s) {
s->top = NULL;
s->length = 0;
return OK;
}
/// 清空栈
Status clearStack(LinkStack *s) {
StackNodeP p, temp;
p = s->top;
// 释放所有结点
while (p) {
temp = p;
p = p->next;
free(temp);
}
s->length = 0;
return OK;
}
/// 判断栈是否为空
Status stackIsEmpty(LinkStack s) {
if (s.length == 0) {
return TRUE;
} else {
return FALSE;
}
}
/// 获取栈的长度
Status stackLength(LinkStack s) {
return s.length;
}
/// 获取栈顶元素
Status getStackTop(LinkStack s, Element *e) {
if (s.top == NULL) return ERROR;
*e = s.top->data;
return OK;
}
/// 入栈
Status push(LinkStack *s, Element e) {
StackNodeP n = malloc(sizeof(StackNode));
if (n == NULL) return ERROR;
n->data = e;
n->next = s->top;
s->top = n;
s->length++;
return OK;
}
/// 出栈
Status pop(LinkStack *s, Element *e) {
if (s->top == NULL) return ERROR;
StackNodeP n = s->top;
s->top = s->top->next;
*e = n->data;
free(n);
s->length--;
return OK;
}
/// 遍历
void stackTraverse(LinkStack s) {
StackNodeP p = s.top;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
执行下面测试代码
LinkStack stack;
int e;
if (initStack(&stack)) {
printf("链表栈初始化成功");
}
for (int i = 0; i < 10; i++) {
push(&stack, i);
}
printf("链表栈中元素为:\n");
stackTraverse(stack);
pop(&stack, &e);
printf("栈顶弹出元素为:%d\n", e);
stackTraverse(stack);
getStackTop(stack, &e);
printf("栈顶元素为:%d\n", e);
stackTraverse(stack);
printf("是否为空栈:%d\n",stackIsEmpty(stack));
printf("栈的长度为:%d\n", stackLength(stack));
clearStack(&stack);
printf("是否已经清空栈 %d, 栈长度为:%d\n",stackIsEmpty(stack), stackLength(stack));
运行结果：
链表栈初始化成功
链表栈中元素为:
9 8 7 6 5 4 3 2 1 0
栈顶弹出元素为:9
8 7 6 5 4 3 2 1 0
栈顶元素为:8
8 7 6 5 4 3 2 1 0
是否为空栈:0
栈的长度为:9
是否已经清空栈 1, 栈长度为:0
4 递归
4.1 定义
若在一个函数中，过程或数据结构定义内部又直接（或间接）出现定义本身的应用，则称他们是递归的。
4.2 使用场景
- 定义是递归的
- 数据结构是递归的
- 问题的解法是递归的
4.3 斐波那契数列
斐波那契数列指的是这样一个数列：
1、1、2、3、5、8、13、21、34、
这个数列从第3项开始，每一项都等于前两项之和。
我们可以使用递归法解决上面的问题，我们可以从一个简单的例子来推导，假设我们求5项为多少时，我们可以将上述问题分解成，求第三项和第四项的和，依次类推，将复杂的问题拆解成一个个简单的问题。
代码实现
int fbi(int n) {
if (n < 2)
return 1;
else
return fbi(n - 1) + fib(n - 2);
}
int main(int argc, const char * argv[]) {
// insert code here...
for (int i = 0; i < 10; i++) {
printf("%d ", fbi(i));
}
return 0;
}
输出： 1 1 2 3 5 8 13 21 34 55
4.4 汉诺塔
问题描述：
假如有3个分别命名为A,B,C的塔座,在塔座A上插有n个直接⼤大⼩小各不不相同的,从⼩小到⼤大的 编号为1,2,3...n的圆盘. 现在要求将塔座A上的n个圆盘移动到塔座C上. 并仍然按照同样的顺序叠 排. 圆盘移动时必须按照以下的规则:1. 每次只能移动⼀一个圆盘;2. 圆盘可以插在A,B,C的任⼀一塔座 上;3. 任何时刻都不不能将⼀一个较⼤大的圆盘压在⼩小的圆盘之上.
上述算法可以简单的分为3步：
- 将A塔的n-1个盘子从A移动到B
- 将A塔的第n个盘子移动到C
- 将B塔上的盘子移动到C
上面的第一步和第三步，又可以当做一个单独的汉诺塔游戏来求解
代码实现
int step = 0;
void moves(int num, char source, char target) {
step++;
printf("将%c盘上编号为:%d的盘子移动到%c盘\n", source, num, target);
}
// 将数量为n个盘子从a塔移动到c塔, b作为辅助塔.
// a: 表示目标塔
// b: 移动时需要借助的辅助塔
// c: 移动的目标塔
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
moves(1 ,a, c);
} else {
hanoi(n - 1, a, c, b);
moves(n ,a, c);
hanoi(n - 1, b, a, c);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
hanoi(3, 'A', 'B', 'C');
printf("实现所需步骤: %d\n", step);
return 0;
}
输出：
将A盘上编号为:1的盘子移动到C盘
将A盘上编号为:2的盘子移动到B盘
将C盘上编号为:1的盘子移动到B盘
将A盘上编号为:3的盘子移动到C盘
将B盘上编号为:1的盘子移动到A盘
将B盘上编号为:2的盘子移动到C盘
将A盘上编号为:1的盘子移动到C盘
实现所需步骤: 7
