1.栈：限定仅在表尾进行插入\删除操作，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈，是后进先出的线性表;
a.顺序栈
#define MAXSIZE 100 typedef struct { SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈可用最大容量 }SqStack;
i.初始化
Status InitStack(SqStack &S) { S.base = new SElemType(MAXSIZE); if(!S.base) exit(OVERFLOW); S.top = S.base; //top初始化为base //空栈 S.stacksize = MAXSIZE; return OK; }
ii.入栈
Status Push(Sqstack &S, SElemType e) { if(S.top - S.base == S.stacksize) //栈满 return ERROR; *S.top++ *S.top = e; return OK; }
iii.出栈
Status Pop(Sqstack &S, SElemType e) { if(S.top == S.base) //栈空 return ERROR; *S.top--; e = *S.top; return OK; }
iv.取栈顶元素
Status GetTop(Sqstack S) { if(S.top != S.base) //栈非空 return ERROR; return *(S.top - 1); }
b.链栈
i.初始化
Status InitStack(LinkStack &S) { S = NULL; return OK; }
ii.入栈
Status Push(LinkStack &S, SElemType e) { p = new StackNode; p->data = e; p->next = S; S = p; return OK; }
iii.出栈
Status Pop(LinkStack &S, SElemType &e) { if(S == NULL) return ERROR; e = S->date; p = S; S = S->next; delete p; return OK; }
c.递归：
i.在一个函数、过程或是数据结构定义的内部出现定义本身的应用
1.定义是递归的：复杂问题能够分解成几个相对简单且解法相同的问题来求解，称作递归求解，分解-求解的策略叫做“分治法”,采用分治法进行递归求解需满足三点：能将一个问题转变为新问题并且与原问题解法类同，并且处理对象更小且变化有规律；可以转化使问题简化；必须有一个明确的递归出口（递归边界）；
一般形式：
void p(参数表) { if(递归结束条件成立) 可直接求解； else p(较小的参数); }
a.阶乘函数
long Fact(long n) { if(n == 0) return 1; //递归终止条件 else return n * Fact(n - 1); //递归步骤 }
b.Fibonacci数列
long Fib(long n) { if(n == 1 || n == 2) return 1; //递归终止条件 else return Fib(n - 1) + Fib(n - 2); //递归步骤 }
2.数据结构本身具有递归的特性
a,遍历输出链表中各个结点
void TraverseList(LinkList p) { if(p) { cout << p->data << endl; //输出当前结点的数据域 TraversrList(p->next); //p指向后继结点继续递归 } }
3.问题本身没有明显的递归结构，但是递归求解比迭代求解更简单
a.Hanoi塔问题
int count = 0; void move(char A, int n, char C) { cout << ++count << "," << A << "," << C << endl; } void Hanoi(int n, char A, char B, char C) //将 A 上圆盘搬移到 C 上， B 做辅助 { if(n == 1) move(A, 1, C); //将编号为 1 的圆盘从 A 移动到 C else { Hanoi(n-1, A, C, B) //将A上编号1至n-1的圆盘移到B C做辅助塔 move(A, n, C) //将编号为n的圆盘从A移到C Hanoi(n-1, B, A, C) //将B上编号为1至n-1的圆盘移到C A做辅助塔 } }
ii.函数调用
1.在一个函数调用另一个函数时，系统需要先完成：
a.将所有的实参、返回地址等信息传递给被调函数
b.为被调函数的 局部变量 分配存储区
c,将控制转移到被调函数的入口
2,在被调用函数返回之前，系统需要先完成
a.保存被调函数的计算结果
b.释放被调函数的数据区
c.按照被调函数保存的返回地址将控制转移到调用函数
系统将整个程序运行时所需的数据安排在一个栈中，调用函数时 会在栈顶分配一个存储区，函数退出时就会释放该函数的存储区，当前运行的函数必须在栈顶；
递归函数调用时，系统设立“递归工作栈”作为整个函数运行是的存储区，每层递归所需的信息构成一个“工作记录”（包括所有的实参、局部变量以及上一层的返回地址等），每进入一层递归就会产生一个新的“工作记录”压入栈顶，反之弹出，当前工作记录必然是位于栈顶，称为“活动记录”;
