为啥数据结构的书籍，先要从数据结构概念讲起，再到物理结构，然后是线性表？因为在数据存储的时候，只有两种结构，任何时候都不会脱离这个范畴，即顺序存储和链式存储
Stack的概念及特性
1.栈是一种受限的线性表，只允许在一端进行删除和插入。
2.可以操作的这一端被称之为栈顶，相对的一端叫栈底。
3.插入元素被叫作入栈或压栈，删除元素叫作出栈或退栈。
4.在内存中，栈是从高地址向低地址生长
总结：
栈是线性结构，特点是先进后出
栈的顺序实现
顺序栈的结构
typedef struct{
ElementType stack[MAXSIZE];
int top;//用于指向栈顶，初始值为-1
} SqStack;
顺序栈的初始化
Status initStack(SqStack *stack){
stack->top = -1;
return OK;
}
顺序栈的是否为空
Status stackEmpty(SqStack st){
if (st.top == -1) {
return TRUE;
}
return FALSE;
}
获取栈顶元素
Status getTop(SqStack st, ElementType *e){
if (st.top == -1)
return ERROR;
*e = st.stack[st.top];
return OK;
}
顺序栈的插入
Status pushStack(SqStack *st, ElementType e){
if (st->top == MAXSIZE - 1)
return ERROR;
st->stack[++st->top] = e;
return OK;
}
顺序栈的删除
Status popStack(SqStack *st, ElementType *e){
if (st->top == -1)
return ERROR;
*e = st->stack[st->top--];
return OK;
}
顺序栈的长度
Status stackLength(SqStack st){
return st.top+1;
}
顺序栈的清空
Status clearStack(SqStack *stack){
stack->top = -1;
return OK;
}
栈的链式实现
链式栈的结构
//栈节点，其实就是链表结构
typedef struct StackNode{
ElementType data;
struct StackNode *next;
int top;
} StackNode,*LinkStackNode;
//栈
typedef struct {
LinkStackNode top;//指向栈顶的指针
int count;//记录个数
} LinkStack;
链式栈的初始化
Status initLinkStack(LinkStack *st){
//初始化栈顶元素，指向NULL
// st->top = (LinkStackNode)malloc(sizeof(StackNode));
// if (st->top == NULL)
// return ERROR;
//以上是按照链表思路写的，可以不要，只保留st->top = NULL;
st->top = NULL;
st->count = 0;
return OK;
}
链式栈的插入
栈的链式插入，你可以理解为没有头节点的元素进行头插
Status pushLinkStack(LinkStack *st,ElementType e){
if (st == NULL)
return ERROR;
LinkStackNode p = malloc(sizeof(StackNode));
if (!p)
return ERROR;
p->data = e;
//插入的元素放的后继指向栈顶
p->next = st->top;
//更新栈顶指针，栈顶指针为新插入元素，
st->top = p;
st->count++;
return OK;
}
链式栈的删除
Status popLinkStack(LinkStack *st,ElementType *e){
//不存在栈或者栈是空，直接返回错误
if (st == NULL || st->count == 0)
return ERROR;
LinkStackNode p = st->top;
//删除栈顶元素
free(p);
//更新栈顶指针
st->top = st->top->next;
//元素个数减一
st->count--;
return OK;
}
获取链式栈的栈顶元素
Status getTopLinkStack(LinkStack st,ElementType *e){
if (!st.top || st.count == 0) {
return ERROR;
}
*e = st.top->data;
return OK;
}
链式栈的清空
Status clearLinkStack(LinkStack *st){
if (!st)
return OK;
//清空栈，要把栈中的元素删除
LinkStackNode p,q;
p = st->top;
while (p) {
q = p;
p = p->next;
free(q);
}
st->count = 0;
return OK;
}
栈与递归
什么是递归呢？
递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。
什么情况下使用递归
1.定义是递归的
例如，求和、阶乘、斐波那契数列
2.数据结构是递归的
例如，链表
3.问题解法是递归的
汉诺塔、把皇宫问题、迷宫问题
递归的三要素
1.明确递归终止条件；
2.给出递归终止时的处理办法；
3.提取重复的逻辑，缩小问题规模
递归的优缺点
| 优点 | 缺点 |
|---|---|
| 实现简单 | 递归调用占用空间大，容易栈溢出 |
| 可读性好 | 可能存在重复计算 |
递归的优化方法
1.考虑是否重复计算
使用递归的时候，必要须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来
2.考虑尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾，就是尾递归
不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。而使用尾递归，只保留后一个函数堆栈即可
递归与循环
递归与循环相同特性是重复任务，不同的地方是：
1.递归是一个问题求解的过程
2.递归有函数调用的开销，而循环没有
递归修改成循环
1.自己建立“堆栈”来保存这些内容一边替代系统堆栈，例如树的非递归方式
2.把对递归的调用变为对循环处理
栈与递归的关系
在高级语言中，调用函数和被调用函数之间的连接及信息交换都是通过栈来进行的，具体过程如下：
在运行被调用函数之前：
1.将所有实参、返回地址等信息信息调用传递给被调用函数保存
2.为被调用函数的变量分配存储空间
3.将控制转移到被调用函数入口
被调用函数将要完成时：
1.保存被调用函数的返回结果
2.释放被调用函数的存储空间
3.按照它保存的返回地址将控制移动到调用函数
注意：多个函数嵌套，按照“先调用后返回”的原则，函数之间的信息传递和控制转移要通过栈来实现
网友评论