老板合作网站开发,wordpress 百度统计,朝阳区手机网站制作服务,襄阳优化公司目录 一#xff0c;栈的定义
二#xff0c;栈的基本操作
1#xff0c;顺序栈
1.1顺序栈的基本概念
1.2顺序栈的基本操作
2#xff0c;链栈
2.1链栈的基本概念
2.2链栈的种类
2.3链栈的基本操作
三#xff0c;栈的应用
1#xff0c;函数递归调用
2#xff0c;…目录 一栈的定义
二栈的基本操作
1顺序栈
1.1顺序栈的基本概念
1.2顺序栈的基本操作
2链栈
2.1链栈的基本概念
2.2链栈的种类
2.3链栈的基本操作
三栈的应用
1函数递归调用
2表达式求值
3数制转换
4迷宫求解
参考资料 一栈的定义 栈Stack是一种常见的数据结构它是一种“后进先出”Last In First OutLIFO的数据结构。栈可以看做是一种特殊的线性表只能在栈顶进行插入和删除操作。栈顶是允许操作的而栈底是固定的。 二栈的基本操作
栈的基本操作包括入栈Push、出栈Pop、取栈顶元素Top和判空IsEmpty等。
1顺序栈 1.1顺序栈的基本概念 顺序栈是一种使用数组实现的栈也称为数组栈。其基本思路是通过数组来存储栈中的元素并通过栈顶指针指示栈顶元素在数组中的位置。顺序栈具有以下特点 存储结构使用数组作为底层存储结构数组的每个元素存储栈中的一个元素操作受限栈只能从栈顶插入和删除元素不支持在栈中间插入和删除元素先进后出栈的元素遵循“先进后出”Last In First Out, LIFO的原则即后插入的元素先被删除顺序访问只能从栈顶开始访问栈中的元素不能从栈底或中间位置访问元素。 顺序栈的实现非常简单可以使用数组和栈顶指针两个变量来实现。顺序栈的主要操作包括初始化、入栈、出栈、获取栈顶元素、判断栈是否为空以及获取栈中元素的数量等。由于顺序栈的存储结构是数组因此在使用过程中需要考虑数组大小的限制当栈中元素数量超过数组大小时需要对数组进行扩容。 注意除了遍历栈中的元素的操作时间复杂度为O(n)外其余入栈、出栈、取栈顶元素、判断栈是否为空操作的时间复杂度均为O(1)。 1.2顺序栈的基本操作 相关的头文件 #includemath.h
#include iostream
typedef int SElemType;
#define STACK_INIT_SIZE 10 //存储空间初始分配量
#define STACK_INCREMENT 2 //存储空间分配增量定义顺序栈结构体 struct SqStack{ //定义顺序栈结构体SElemType *base; //栈底指针SElemType *top; //栈顶指针int stacksize; //栈可用的最大容量
}; 初始化栈 void InitStack(SqStack S){ //初始化栈SS.base (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //给栈分配空间if(!S.base) //如果分配失败exit(OVERFLOW); //则退出程序S.top S.base; //栈顶指针和栈底指针指向同一个位置S.stacksize STACK_INIT_SIZE; //初始化栈的最大容量
} 销毁栈 void DestoryStack(SqStack S){ //销毁栈Sfree(S.base); //释放栈S占用的空间S.top S.base NULL; //将栈底指针和栈顶指针都置为空S.stacksize 0; //将栈的最大容量清零
} 清空栈 void ClearStack(SqStack S){ //清空栈SS.top S.base; //将栈顶指针指向栈底指针实现清空栈的效果
} 判断栈是否为空 int StackEmpty(SqStack S){ //判断栈S是否为空if(S.top S.base) //如果栈顶指针和栈底指针指向同一个位置说明栈为空return true;elsereturn false;
} 返回栈长度 int StackLength(SqStack S){ //求栈S的长度return S.top - S.base; //栈顶指针减去栈底指针的差即为栈的长度
} 获取栈顶元素值 int GetTop(SqStack S,SElemType e){ //获取栈顶元素并将其存储到e中if (S.top S.base){ //如果栈不为空e *(S.top-1); //将栈顶元素存储到e中return true;}elsereturn false;
} 入栈 void Push(SqStack S,SElemType e){ //在栈顶插入元素eif(S.top - S.base S.stacksize){ //如果栈满S.base (SElemType*)realloc(S.base, (S.stacksizeSTACK_INCREMENT)*sizeof(SElemType)); //给栈扩容if(!S.base) //如果扩容失败exit(OVERFLOW); //则退出程序S.top S.base S.stacksize; //将栈顶指针指向扩容后的栈顶S.stacksize STACK_INCREMENT; //更新栈的最大容量}*(S.top) e; //将元素e插入栈顶并将栈顶指针上移一位
} 出栈 // 如果栈为空返回false否则返回true
int Pop(SqStack S,SElemType e){if(S.top S.base) //栈空return false;e *(--S.top); //将栈顶元素赋给e栈顶指针下移一个存储单元return true;
} 遍历打印栈内元素 // 定义一个函数visit用于打印元素
void visit(SElemType e)
{std::cout e ;
}// 定义一个函数用于遍历栈中的元素并对每个元素执行visit函数
void StackTraverse(SqStack S,void(*visit)(SElemType)){SElemType *p S.base;while(S.top p) //p指向栈元素visit(*p); //对该栈调用visit()p指针上移一个存储单元printf(\n);
} 主函数 int main() {int j;SqStack s;SElemType e;InitStack(s);for(j 1; j 12; j)Push(s, j);printf(栈中元素依次为\n);StackTraverse(s, visit);Pop(s,e);printf(弹出的栈顶元素e %d\n,e);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));DestoryStack(s);printf(销毁栈后s.top %u,s.base %u,s.stacksize %d\n,s.top,s.base,s.stacksize);
}
2链栈 2.1链栈的基本概念 链栈是一种基于链表实现的栈其特点是无需事先分配固定长度的存储空间栈的长度可以动态增长或缩小避免了顺序栈可能存在的空间浪费和存储溢出问题。 链栈中的每个元素称为“节点”每个节点包括两个部分数据域和指针域。数据域用来存储栈中的元素值指针域用来指向栈顶元素所在的节点。 链栈的基本操作包括入栈、出栈、获取栈顶元素和遍历等相比顺序栈而言链栈的实现难度稍高但其在某些情况下有着更好的灵活性和效率特别适用于在动态存储空间较为紧缺的场合。 链栈的进栈push和出栈pop操作都很简单时间复杂度均为O(1) 注意如果栈的使用过程中元素变化不可预料,那么最好使用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈。 2.2链栈的种类 链栈按照链表的实现方式可分为单链栈和双链栈。实际应用通常采用单链栈。 单链栈使用单链表实现每个节点只含有一个指向下一个节点的指针。因此单链栈只能从栈顶进行插入和删除操作。 双链栈使用双向链表实现每个节点同时包含指向前一个节点和后一个节点的指针。因此双链栈既可以从栈顶进行插入和删除操作也可以从栈底进行插入和删除操作使得操作更加灵活。 2.3链栈的基本操作 单链栈的类型定义 // 定义链栈的结构体
typedef struct StackNode{SElemType data;StackNode *next;
}StackNode,*LinkStack;单链栈初始化 // 初始化链栈
int InitStack(LinkStack S){S NULL;return true;
}判断单链栈是否为空 // 判断链栈是否为空
bool StackEmpty(LinkStack S){return S NULL;
} 单链栈入栈 // 入栈
bool Push(LinkStack S, SElemType e){StackNode *p (StackNode*)malloc(sizeof(StackNode));if(!p){return false; // 分配内存失败}p-data e;p-next S;S p;return true;
} 单链栈出栈 // 出栈
bool Pop(LinkStack S, SElemType e){if(StackEmpty(S)){return false; // 栈为空}StackNode *p S;e p-data;S S-next;free(p);return true;
} 获取单链栈栈顶元素 // 获取栈顶元素
bool GetTop(LinkStack S, SElemType e){if(StackEmpty(S)){return false; // 栈为空}e S-data;return true;
} 清空单链栈 // 清空栈
void ClearStack(LinkStack S){StackNode *p;while(S){p S;S S-next;free(p);}
} 销毁单链栈 // 销毁栈
void DestroyStack(LinkStack S){ClearStack(S);S NULL;
} 遍历单链栈 // 遍历栈并打印
void StackTraverse(LinkStack S){StackNode *p S;while(p){printf(%d , p-data);p p-next;}printf(\n);
} 测试代码 #include iostreamint main() {LinkStack S;InitStack(S);int e;Push(S, 1);Push(S, 2);Push(S, 3);printf(现在栈内元素为(后进先出));StackTraverse(S);printf(栈顶元素为%d\n, GetTop(S,e));Pop(S,e);printf(现在栈内元素为(后进先出));StackTraverse(S);printf(弹出一个元素后栈顶元素为%d\n, GetTop(S,e));ClearStack(S);if (StackEmpty(S)) {printf(栈为空\n);} else {printf(栈不为空\n);}DestroyStack(S);return 0;
}
三栈的应用
1函数递归调用 函数递归调用时计算机会把函数调用时需要的参数和返回地址等信息放入栈中函数执行完毕后再从栈中取回这些信息。 //以汉诺塔问题为例展示栈的递归调用
#include iostreamint c 0;
void move(char x,int n,char z){printf(第%i步:将%i号盘从%c移到%c\n, c, n, x, z);
}void hanoi(int n, char x, char y, char z){if(n1){move(x, 1, z);}else{hanoi(n-1, x, z, y);move(x, n, z);hanoi(n-1, y, x, z);}
}int main() {int n;printf(三个塔座为a,b,c,圆盘最初在a座借助b座移到c座请输入圆盘数量);scanf(%d,n);hanoi(n, a, b, c);
} 2表达式求值 在编译器中中缀表达式转为后缀表达式后可以使用栈来实现后缀表达式的求值。 char Precede(SElemType t1, SElemType t2)
{ char f;switch(t2){ case :case -: if(t1( || t1\n)f; elsef; break;case *:case /: if(t1* || t1/ || t1))f; elsef; break;case (: if(t1)){ printf(括号不匹配\n);exit(OVERFLOW);}elsef; break;case ): switch(t1){ case (: f; break;case\n: printf(缺乏左括号\n);exit(OVERFLOW);default : f; }break;case\n: switch(t1){ case\n: f; break;case (: printf(缺乏右括号\n);exit(OVERFLOW);default : f; }}return f;
}
Status In(SElemType c)
{ switch(c){ case :case -:case *:case /:case (:case ):case\n: return TRUE;default : return FALSE;}
}
SElemType Operate(SElemType a, SElemType theta, SElemType b)
{ switch(theta){ case : return ab;case -: return a-b;case *: return a*b;}return a/b;
}// 表达式求值范围为int类型输入负数要用0-正数表示
typedef int SElemType;
SElemType EvaluateExpression()
{ SqStack OPTR, OPND;SElemType a, b, d, x; char c; cgetchar(); InitStack(OPTR); InitStack(OPND);Push(OPTR, \n); GetTop(OPTR, x); while(c!\n || x!\n) { if(In(c)) switch(Precede(x, c)) { case: Push(OPTR, c); cgetchar(); break;case: Pop(OPTR, x); cgetchar(); break;case: Pop(OPTR, x); Pop(OPND, b); Pop(OPND, a);Push(OPND, Operate(a, x, b)); }else if(c0 c9) { d0;while(c0 c9) { dd*10c-0;cgetchar();}Push(OPND, d); }else { printf(出现非法字符\n);DestroyStack(OPTR);DestroyStack(OPND);exit(OVERFLOW);}GetTop(OPTR, x); }Pop(OPND, x); if(!StackEmpty(OPND)) { printf(表达式不正确\n);DestroyStack(OPTR);DestroyStack(OPND);exit(OVERFLOW);}DestroyStack(OPTR);DestroyStack(OPND);return x;
}
void main()
{printf(请输入算术表达式负数要用0-正数表示\n);printf(%d\n, EvaluateExpression());
}3数制转换 可以使用栈来进行二进制和十进制等进制之间的转换 #define N 8
typedef int SElemType; void conversion()
{ SqStack s;unsigned n; SElemType e;InitStack(s); printf(将十进制整数n转换为%d进制数请输入n≥0, N);scanf(%u, n); while(n) { Push(s, n%N); nn/N;}while(!StackEmpty(s)) { Pop(s, e); printf(%d, e); }printf(\n);
}
void main()
{conversion();
}4迷宫求解 在迷宫求解中可以使用栈来实现深度优先搜索算法。 // 利用栈求解迷宫问题只输出一个解
struct PosType
{ int x; int y;
};
// 全局变量
PosType begin, end;
PosType direc[4]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// {行增量, 列增量}移动方向依次为东南西北
#define MAXLENGTH 25
typedef int MazeType[MAXLENGTH][MAXLENGTH];
MazeType m;
int x, y;
void Print()
{ int i, j;for(i0; ix; i){ for(j0; jy; j)printf(%3d, m[i][j]);printf(\n);}
}
void Init()
{ int i, j, x1, y1;printf(请输入迷宫的行数,列数包括外墙);scanf(%d,%d, x, y);for(i0; iy; i) { m[0][i]0; m[x-1][i]0; }for(i1; ix-1; i){ m[i][0]0; m[i][y-1]0; }for(i1; ix-1; i)for(j1; jy-1; j)m[i][j]1; printf(请输入迷宫内墙单元数);scanf(%d, j);printf(请依次输入迷宫内墙每个单元的行数,列数\n);for(i1; ij; i){ scanf(%d,%d, x1, y1);m[x1][y1]0; }printf(迷宫结构如下\n);Print();printf(请输入入口的行数,列数);scanf(%d,%d, begin.x, begin.y);printf(请输入出口的行数,列数);scanf(%d,%d, end.x, end.y);
}
int curstep1;
struct SElemType
{ int ord; PosType seat; int di;
};// 定义墙元素值为0可通过路径为1经试探不可通过路径为-1通过路径为足迹
Status Pass(PosType b)
{ if(m[b.x][b.y]1)return OK;elsereturn ERROR;
}
void FootPrint(PosType b)
{ m[b.x][b.y]curstep;
}
void NextPos(PosType b, int di)
{ b.xdirec[di].x;b.ydirec[di].y;
}
void MarkPrint(PosType b)
{ m[b.x][b.y]-1;
}
Status MazePath(PosType start, PosType end)
{ PosType curposstart; SqStack S; SElemType e; InitStack(S); do{ if(Pass(curpos)) { FootPrint(curpos); e.ordcurstep; e.seatcurpos; e.di0; Push(S, e); curstep; if(curpos.xend.x curpos.yend.y) return TRUE;NextPos(curpos, e.di); }else { if(!StackEmpty(S)) { Pop(S, e); curstep--; while(e.di3 !StackEmpty(S)) { MarkPrint(e.seat); Pop(S, e); curstep--; }if(e.di3) { e.di; Push(S, e); curstep; curpose.seat; NextPos(curpos,e.di);}}}}while(!StackEmpty(S));return FALSE;
}
void main()
{Init(); if(MazePath(begin, end)) { printf(此迷宫从入口到出口的一条路径如下\n);Print(); }elseprintf(此迷宫没有从入口到出口的路径\n);
}参考资料
严蔚敏、吴伟民《数据结构C语言版》高一凡《数据结构算法解析》程杰《大话数据结构》王道论坛《数据结构考研复习指导》
