前言：
栈和队列的特点： 都是线性结构，同样也是线性表，特殊性在于读取的基本操作上不一样， 线性表是可以读取任何一个元素，而栈和队列则不同。
栈结构特点：
出栈和进栈、插入和删除都在栈顶
栈结构
队列结构特点：
遵循先进先出，读取元素只能有一个方向——队列头a1。插入元素只能从队尾插入
队列结构
栈
如何实现一个栈
我们知道逻辑结构分：线性结合，集合结构，树形结构，图像结构；物理结构分：顺序储存结构/链式储存结构，链表属于物理结构，栈属于物理结构。
- 栈的顺序存储
//栈定义
typedef struct{
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}SqStack;
//构建一个空栈
Status InitStack(sqStack *S){
S->top = -1;//-1表示一个空栈
return OK;
}
//置空栈
Status ClearStack(SqStack *S){
//将栈置空,只需要修改top标签就可以了，不必要将顺序栈的元素都清空
S->top = -1;
return OK;
}
//判断一个栈是否为空
Status StackEmpty(SqStack S){
if (S.top == -1)
return TRUE;
else
return FALSE;
}
//栈的长度
int StackLength(SqStack S){
return S.top + 1;
}
//获取栈顶
Status GetTop(SqStack S,SElemType *e){
if (S.top == -1)
return ERROR;
else
*e = S.data[S.top];
return OK;
}
// 压栈（入栈）
Status PushData(SqStack *S,SElemType *e){
if (S->data == MAXSIZE - 1) return ERROR;//MAXSIZE - 1：-1是因为从0开始
S->top ++;
S->data[S->top] = e;
return OK;
}
//出栈
Status Pop(SqStack *S,SElemType *e){
if (S->top == -1) return ERROR;
*e = S->data[S->top];
S->top --;
return OK;
}
//遍历栈
Status StackTraverse(SqStack S){
int i = 0;
if (S.top == - 1) {
return ERROR;
}
printf("此栈所有元素：");
while (i <= S.top) {
printf("%d",S.data[i++]);
}
printf("\n");
return OK;
}
链式栈结构
栈顶top永远指向栈顶元素，结点与结点之间的链接由next指针
链式栈结构
/* 栈里结点 */
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
/* 链栈结构 */
typedef struct{
LinkStackPtr top;
int count;
}LinkStack;
//构造一个空栈S
Status InitStack(LinkStack *S){
S->top=NULL;
S->count=0;
return OK;
}
//把链栈S置为空栈
Status ClearStack(LinkStack *S){
LinkStackPtr p,q;
p = S->top;
while (p) {
q = p;
p = p->next;
free(q);
}
S->count = 0;
return OK;
}
/*若栈S为空栈,则返回TRUE, 否则返回FALSE*/
Status StackEmpty(LinkStack S){
if (S.count == 0)
return TRUE;
else
return FALSE;
}
//插入元素e到链栈S (成为栈顶新元素)
Status Push(LinkStack *S, SElemType e){
//创建新结点temp
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
//赋值
temp->data = e; //把当前的栈顶元素赋值给新结点的直接后继, 参考图例第①步骤;
temp->next = S->top; //将新结点temp 赋值给栈顶指针,参考图例第②步骤;
S->top = temp;
S->count++;
return OK;
}
//若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR*/
Status Pop(LinkStack *S,SElemType *e){
//if (S.count == 0) return ERROR;
if (StackEmpty(*S)) {
return ERROR;
}
LinkStackPtr p;
//将栈顶元素赋值给*e
*e = S->top->data;
//将栈顶结点赋值给p,参考图例①
p = S->top;
//使得栈顶指针下移一位, 指向后一结点. 参考图例②
S->top= S->top->next;
//释放p
free(p);
//个数--
S->count--;
return OK;
}
//遍历链栈
Status StackTraverse(LinkStack S){
LinkStackPtr p;
p = S.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
main函数：
int main {
int j;
LinkStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;j<=10;j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
StackTraverse(s);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
}
- 递归思想
定义是递归：数学定义是递归 阶乘 /斐波拉契数列
数据结构是递归，链表的结构设计也是递归
问题是递归可以用递归
分治法：将大问题分解成小问题；大问题和小问题的解法是高度相同的；递归出口，边界。
兔子繁衍问题
如果兔子2个⽉之后就会有繁衍能力,那么一对兔子每个月能⽣生出一对兔子; 假设所有的兔子都不死,那么n个月后能生成多少只兔子?
数据分析
调用函数分析
调用分析
此问题是一个斐波拉契数列
int Fbi(int i){
if(i < 2)
return i == 0 ? 0 : 1;
return Fbi(i - 1) + Fbi(i - 2);
}
int main(int argc, const char * argv[]) {
// 1 1 2 3 5 8 13 21 34 55 89 144
for (int i =0; i < 10; i++) {
printf("%d ",Fbi(i));
}
printf("\n");
return 0;
}
Hanoi塔问题：
问题描述: 假如有3个分别命名为A,B,C的塔座,在塔座A上插有n个直接大小各不不相同的,从小到大的 编号为1,2,3...n的圆盘. 现在要求将塔座A上的n个圆盘移动到塔座C上. 并仍然按照同样的顺序叠 排. 圆盘移动时必须按照以下的规则:1. 每次只能移动⼀个圆盘;2. 圆盘可以插在A,B,C的任⼀塔座 上;3. 任何时刻都不能将⼀个较大的圆盘压在小的圆盘之上.
代码实现
int m = 0;
void moves(char X,int n,char Y){
m++;
printf("%d: from %c ——> %c \n",n,X,Y);
}
//n为当前盘子编号. ABC为塔盘
void Hanoi(int n ,char A,char B,char C){
//目标: 将塔盘A上的圆盘按规则移动到塔盘C上,B作为辅助塔盘;
//将编号为1的圆盘从A移动到C上
if(n==1) moves(A, 1, C);
else
{
//将塔盘A上的编号为1至n-1的圆盘移动到塔盘B上,C作为辅助塔;
Hanoi(n-1, A, C, B); //将编号为n的圆盘从A移动到C上;
moves(A, n, C); //将塔盘B上的编号为1至n-1的圆盘移动到塔盘C上,A作为辅助塔;
Hanoi(n-1, B, A, C);
}
}
int main(int argc, const char * argv[]) {
printf("Hanoi 塔问题\n");
Hanoi(3, 'A', 'B', 'C');
printf("盘子数量为3:一共实现搬到次数:%d\n",m);
Hanoi(4, 'A', 'B', 'C');
printf("盘子数量为3:一共实现搬到次数:%d\n",m);
return 0;
}
网友评论