递归实现括号匹配问题C语言,数据结构与算法：栈的原理及操作实例–进制转换、括号匹配、递归的消除… 顺序栈 顺序栈的类型描述： 利用顺序存储方式实现的栈称为顺序栈。 继承顺序表的特点，仍然用动态分配的一维数组来描述其顺序存储结构。 #define STACK_INIT_SIZE 100 //存储空间的初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 typedef int ElemType; //简化操作，让类型在此定义为int型 typedef struct{ ElemType *date; int top; //栈顶指针 int stacksize; }SqStack; 通常将数组的0下标作为栈底，这样空栈时栈顶指针指向数组第一个素。 ——>为什么只设一个指针？ ——指针是单方向操作结构，只需定义“栈顶指针”即可。 栈的初始化： int InitStack(SqStack &s){ //这里为什么要加“&”(取地址符)——>这里实际上操作的是栈地址，或者说栈空间，又或说：栈(顶)素 s.date=new ElemType[STACK_INIT_SIZE]; if(!s.date) exit(overflow); //存储分配失败 s.top=-1; //栈空 s.stacksize=STACK_INIT_SIZE; return OK; } ——>栈中，好像挺喜欢用“s.top=-1”来表示栈(s)为空。 进栈操作： int Push(SqStack &s,ElemType e){ //将e插入栈顶 ElemType *p; if(s.top>=s.stacksize-1){ p=(ElemType *)realloc(s.date,(s.stacksize+STACKINCREMENT)*sizeof(ElemType)); //此时，应开辟空间，开辟一个符合栈类型(ElemType)的空间 if(!p) exit(overflow); //存储分配失败 s.date=p; s.stacksize=s.stacksize+STACKINCREMENT; } s.date[++s.top]=e; return OK; } “s.top”:“头”处插入数据。前面说过，栈只能单方向操作!我们称被操作的方向为：栈顶。 出栈操作: int Pop(SqStack &s,ElemType &e){ //若栈不空，则删除s的栈顶素，用e返回其值，并返回OK；否则返回error if(s.top==-1) return error; e=s.date[s.top–]; return OK; } 判断栈是否为空栈： int StackEmpty(SqStack s){ if(s.top==-1) return OK; return error; } ——>需注意的是：对于顺序栈，入栈时首先应判断栈是否满了(条件：S.top>=S.stacksize-1)，防止空间溢出 这就好比链式操作·出栈时要先判断栈是否为空一样。 链栈 typedef struct node{ ElemType data; struct node *next; }StackNode,*LinkStack; //*LinkStack是什么？学过c/c++的都知道，这不过是栈指针罢了，有了它，下面设置关于栈的指针时就会轻松许多 LinkStack top; //明目张胆的设置栈顶指针top 基本操作： 其主要运算仍是对于栈顶执行插入、删除之类的操作。 void InitStack(LinkStack &top){ //置空栈 top=NULL; //构建一个空栈，栈顶指针为top } int StackEmpty(LinkStack top){ //判断栈是否为空 if(top==NULL) return OK; else return error; } int Push(LinkStack &top,ElemType x){ //入栈 StackNode *s; s=new StackNode; //new一个新空间，并让指针指向它。同顺序栈中的这一步：p=(ElemType *)realloc(s.date //(s.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!s) exit(overflow); s->data=x; s->next=top; top=s; return OK; } int Pop(LinkStack &top,ElemType &x){ //出栈 StackNode *p; if(top==NULL) return error; else{ x=top->data; p=top; top=top->next; delete p; return OK; } } 应用实例-操作 1.进制转换(十->?) 原理：由十进制转换为其它进制时，其打印输出(从高位->低位)与计算过程恰好相反。 实现：将计算得到的八进制数的各位按顺序入栈，然后按出栈顺序打印即可(最简单、从输出过程控制)。 (算法思想：(结合上面两种之任一)) void conversion(){ SqStack s; int N,e; InitStack(s); scanf(“%d”,&N); //输入十进制数 while(N){ Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ //调用函数判断栈空与否 Pop(s,e); //条件都满足下 出栈 printf(“%d”,e); } } 2.汉诺塔的递归实现 曾经看过汉诺塔的实现过程，我去，真是。。。看了都不想学了那种感觉。今天既然说栈，咱就好好唠唠这个“栈”。 
在高级语言编写的程序中，为了追求效率，调用函数与被调用函数之间的联结和信息交换(如：参数传递)都是通过栈来进行的。 下面，探究下“递归”世界下的“汉诺塔”： void hannuo(int n,char x,char y,char z){ //将x塔上按直径大小从上到下编号为1-n的圆盘从x移到z，y可做辅助塔 if(n==1) move(x,1,z); //将编号为1的圆盘从x移到z else{ hannuo(n-1,x,z,y); //将x编号上为1至n-1的圆盘移到y，z做辅助塔 move(x,n,z); //将编号为n的圆盘从x移到z hannuo(n-1,y,x,z); //将y编号上为1至n-1的圆盘移到z，x做辅助塔 } } void move(char x,int n,char z){ printf(“%d号圆盘：%c– –>%c ”,n,x,z); } (留意下5、6、7三行) but，递归真的好吗？ 递归的消除 原因：递归虽然代码量小，重构性大，但其在时空上的性能未必是最好的。递归的消除有两种：1.简单递归消除(尾递归和单向递归消除) 2.基于栈。 典型：斐波那契的非递归实现(单向递归消除) (核心代码) if(n==1||n==0) return n; else{ int x=0,y=1,m; for(int i=2;i<=n;i++){ m=y; y=x+y; x=m; } } 这段代码的思想非常重要！非常重要！非常重要！！！ 建议手动画图将过程“画”出来，以便更好的理解。 本文同步分享在 博客“行舟客”(CSDN)。 如有侵权，请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/30311.html
