六盘水市住房和城乡建设局网站,wordpress怎么做相册,步骤记录器,网络公关名词解释一、栈的定义
相信大家对于栈或多或少有一些了解#xff0c;可能大多数人会告诉你栈是一种先进后出的数据结构。这其实说了跟没说一样(❁◡❁)#xff01;当然#xff08;last in#xff0c;first out#xff09;是栈最有特色的性质。
这里可以给大家一些比较好理解的例…一、栈的定义
相信大家对于栈或多或少有一些了解可能大多数人会告诉你栈是一种先进后出的数据结构。这其实说了跟没说一样(❁´◡❁)当然last infirst out是栈最有特色的性质。
这里可以给大家一些比较好理解的例子像男生对枪械感兴趣的不难发现弹夹其实就是一个先进后出的容器压入子弹后先打出去的一定是最后压入的。同理第一枚压入的子弹一定是最后打出的。 再比如我们在浏览网页时经常会有回退即回到上一个浏览的网页这一操作那么同样不难想象第一次回退操作的结果肯定是回到除当前页面最后浏览的而并不是第一个浏览的网页这同样是先进后出的典型代表。 接下来我们展开讲一讲怎么将后进先出抽象出来。这里我们先回顾一下线性表的插入和删除操作先找到插入位置的前驱结点然后做指针或数组下标的相关操作。那么栈只不过是将操作对象局限为最后一个结点罢了。
那么其实总结起来说栈还就只是一种后进先出的容器罢了更简单明了地说栈的本质还是一种顺序表不过是只能在其一端进行插入和删除操作的特殊线性表。
那么就会有很多人问既然栈的本质还是一种线性表那我们为什么还要去重新定义这样一种数据结构呢直接在线性表的基础上进行数组下标或者是链表指针的操作不就行了。首先我想说这是一个好问题因为我也有这样的疑问。但是大家想一下我们既然有了数组为什么还要有顺序表呢因为大家清楚顺序表本质就是一个数组。其实这就涉及到程序设计的问题我们当然希望在编写程序的时候关注的问题越少越好所以栈这个数据结构的创建就使得程序设计时的思考范围变小了可以不需要去花精力考虑类似于数组下标等问题。
二、理解并手撕栈
头文件及宏定义
#include stdio.h
#include stdlib.h#define elemtype int
#define initcapacity 10
#define increment 10
initcapacity初始化栈时的最大容量。
increment在后面栈满后对空间进行再分配时栈的最大空间的增量。
栈的定义
这里以顺序栈为例后期会更新其他实现链栈、队列栈
typedef struct Stack{elemtype *base;elemtype *top;int stacksize;
} Stack;
结构体中定义了两个elemtype类型的指针*top、*base然后是栈的最大容量stacksize。其中*top指向栈顶*base指向栈底所以由栈的LIFO特性可以知道所有的操作都是在top一端进行的。
初始化栈initStack
Stack* initStack(){Stack *s(Stack*)malloc(sizeof(Stack));s-base(elemtype*)malloc(sizeof(elemtype)*initcapacity);s-tops-base;s-stacksizeinitcapacity;return s;
}
初始化时当然是先要定义结构体Stack *s然后将结构体中的元素*top、*base分配空间而空间的长度就是宏定义的initcapacity。最后还要更新一下s-stacksize。
ps此处可以给s-base分配再将其赋给s-top也可以反过来没有区别
ps函数返回值是*Stack,当然也可以传入*Stack指针然后再进行初始化。
销毁栈destroyStack
void destroyStack(Stack *s){ free(s-base); s-baseNULL; s-topNULL;s-stacksize0;
}
这里进行的操作是先对结构体中的s-base进行free操作然后将其指针指置空。最后更新s-stacksize0。
这里大家可能也会有问题为什么只free(s-base),不用free(s-top)
这里要简单解释一下free()函数的机制我们输入由动态分配的内存的首地址然后函数会将自定计算这块内存的长度然后将其设置为可分配状态最后由操作系统释放掉。而我们这里的首地址是s-base,s-top并不是首地址所以应该释放掉s-base。
这里可能大家还会有疑惑既然是将栈销毁为什么不直接free(s),也就是直接将结构体释放掉这样难道不是更方便吗
首先我们要明确销毁栈的目的是什么应该是在我不需要这个栈时我希望这一块空间被释放掉也就是可被再分配。
那么如果直接将释放结构体那么在结构体中动态分配的内存也就是s-base是无法释放的这也就会导致内存泄漏与我们的目的就不符了。
清空栈clearStack
void clearStack(Stack *s){s-tops-base;s-stacksize0;
}
清空栈比较简单我只需要将将top指针重置为base就可以了。
ps这种方式的清空并不是真正意义上的将栈中元素删除了它其实是一种清空的假象栈的物理结构并没有改变只不过那些没有删去的元素不用再去访问它了在我要入栈时就会覆盖掉那些元素
如果有强迫症的话可以将每一个元素删除 (^///^)。
压栈pushStack
void pushStack(Stack *s,elemtype e){if(s-top - s-base s-stacksize){s-base(elemtype*)realloc(s-base,sizeof(elemtype)*(initcapacityincrement));if(!s-base){printf(fail realloc\n);exit(0);}s-tops-bases-stacksize;s-stacksizeincrement;}*s-tope;s-top;
}
其实压栈的核心操作就是两行代码 *s-tope; s-top; 另一大坨主要是考虑扩容和代码健壮性的校验代码 s-base(elemtype*)realloc(s-base,sizeof(elemtype)*(initcapacityincrement)); 值得注意的是如果不熟悉realloc()函数要注意一下该函数的输入两个参数(原内存首地址再分配后的内存空间总数) 然后进行强制类型转换。
弹栈popStack
void popStack(Stack *s){if(s-tops-base){printf(stack is empty\n);exit(0);}printf(pop-%d\n,*(--s-top));
}
弹栈的操作比较简单先判断是否为空栈然后将顶部元素弹出。这里需要注意的是s-top并不是头部元素一般情况下它是空的等待着要入栈的元素。所以弹出的元素应该是--s-top指向的元素。
ps:s-top是一个指针要输出值的话是*s-top
栈长度、顶部元素获取
int lengthStack(Stack *s){return s-top - s-base;
}elemtype GetTop(Stack *s){return *(s-top-1); //时刻记住s-top,是一个指针要取值的话加*
}
这里涉及到的知识带是指针可以相减获得两指针的距离 s-top - s-base; 同样这里需要注意栈顶元素是*(s-top-1)。
遍历栈traverseStack
void traveraeStack(Stack *s){if(s-bases-top){printf(Stack is empty\n);exit(0);}int lenlengthStack(s);for(int i1;ilen;i){printf(%d-,*(s-top-i)); } printf(end\n);
}
这里在遍历的时候也有一个小细节不能直接写 *--(s-top)因为*s是作为指针传入的这样会修改结构体中s-top的值那么遍历结束后s-top就会与s-base重合了此时再进行遍历就会是空栈
运行结果 没有bug
三、写在最后
其实栈的实现逻辑是很简单的就抓住栈的LIFO特性就可以了后面的学的队列也是这样。
今天是以顺序栈为例分析的其实还有链表实现栈队列实现栈以及以栈为基础的双端栈这些数据结构都会之后的博客中我都会写到。然后文章有什么问题的话希望大家能够帮忙指正
然后源代码已经上传到下面了有需要的可以自取。
顺序栈源码 文章转载自： http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.zkpwk.cn.gov.cn.zkpwk.cn http://www.morning.qnzk.cn.gov.cn.qnzk.cn http://www.morning.zpyh.cn.gov.cn.zpyh.cn http://www.morning.gnfkl.cn.gov.cn.gnfkl.cn http://www.morning.kaweilu.com.gov.cn.kaweilu.com http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.mnwsy.cn.gov.cn.mnwsy.cn http://www.morning.lqzhj.cn.gov.cn.lqzhj.cn http://www.morning.xfwnk.cn.gov.cn.xfwnk.cn http://www.morning.tbqbd.cn.gov.cn.tbqbd.cn http://www.morning.srbsr.cn.gov.cn.srbsr.cn http://www.morning.qsbcg.cn.gov.cn.qsbcg.cn http://www.morning.rfpq.cn.gov.cn.rfpq.cn http://www.morning.dgckn.cn.gov.cn.dgckn.cn http://www.morning.tgczj.cn.gov.cn.tgczj.cn http://www.morning.ygmw.cn.gov.cn.ygmw.cn http://www.morning.ymyhg.cn.gov.cn.ymyhg.cn http://www.morning.crqpl.cn.gov.cn.crqpl.cn http://www.morning.pbtdr.cn.gov.cn.pbtdr.cn http://www.morning.jkdtz.cn.gov.cn.jkdtz.cn http://www.morning.frnjm.cn.gov.cn.frnjm.cn http://www.morning.nwmwp.cn.gov.cn.nwmwp.cn http://www.morning.qjzgj.cn.gov.cn.qjzgj.cn http://www.morning.tqsnd.cn.gov.cn.tqsnd.cn http://www.morning.rjhts.cn.gov.cn.rjhts.cn http://www.morning.smry.cn.gov.cn.smry.cn http://www.morning.tnhqr.cn.gov.cn.tnhqr.cn http://www.morning.rcwzf.cn.gov.cn.rcwzf.cn http://www.morning.jbxd.cn.gov.cn.jbxd.cn http://www.morning.dtzxf.cn.gov.cn.dtzxf.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.phgz.cn.gov.cn.phgz.cn http://www.morning.kwqcy.cn.gov.cn.kwqcy.cn http://www.morning.lmpfk.cn.gov.cn.lmpfk.cn http://www.morning.lhytw.cn.gov.cn.lhytw.cn http://www.morning.wrlxt.cn.gov.cn.wrlxt.cn http://www.morning.xkhxl.cn.gov.cn.xkhxl.cn http://www.morning.jpwmk.cn.gov.cn.jpwmk.cn http://www.morning.ttcmdsg.cn.gov.cn.ttcmdsg.cn http://www.morning.gryzk.cn.gov.cn.gryzk.cn http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.pshtf.cn.gov.cn.pshtf.cn http://www.morning.qqbw.cn.gov.cn.qqbw.cn http://www.morning.fyglr.cn.gov.cn.fyglr.cn http://www.morning.bgpb.cn.gov.cn.bgpb.cn http://www.morning.grtwn.cn.gov.cn.grtwn.cn http://www.morning.nrddx.com.gov.cn.nrddx.com http://www.morning.jcpq.cn.gov.cn.jcpq.cn http://www.morning.tdmr.cn.gov.cn.tdmr.cn http://www.morning.rbnj.cn.gov.cn.rbnj.cn http://www.morning.bwmq.cn.gov.cn.bwmq.cn http://www.morning.nsrtvu.com.gov.cn.nsrtvu.com http://www.morning.tkgjl.cn.gov.cn.tkgjl.cn http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.nyhtf.cn.gov.cn.nyhtf.cn http://www.morning.rwtlj.cn.gov.cn.rwtlj.cn http://www.morning.alive-8.com.gov.cn.alive-8.com http://www.morning.pngph.cn.gov.cn.pngph.cn http://www.morning.lnbcx.cn.gov.cn.lnbcx.cn http://www.morning.cmldr.cn.gov.cn.cmldr.cn http://www.morning.ysskn.cn.gov.cn.ysskn.cn http://www.morning.xnyfn.cn.gov.cn.xnyfn.cn http://www.morning.jqsyp.cn.gov.cn.jqsyp.cn http://www.morning.sryyt.cn.gov.cn.sryyt.cn http://www.morning.jtmrx.cn.gov.cn.jtmrx.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.pyncx.cn.gov.cn.pyncx.cn http://www.morning.gjlst.cn.gov.cn.gjlst.cn http://www.morning.gjqwt.cn.gov.cn.gjqwt.cn http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn http://www.morning.rpljf.cn.gov.cn.rpljf.cn http://www.morning.fjshyc.com.gov.cn.fjshyc.com http://www.morning.fqnql.cn.gov.cn.fqnql.cn http://www.morning.lbrwm.cn.gov.cn.lbrwm.cn http://www.morning.rqqct.cn.gov.cn.rqqct.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.dbfwq.cn.gov.cn.dbfwq.cn http://www.morning.rzcmn.cn.gov.cn.rzcmn.cn http://www.morning.pqhgn.cn.gov.cn.pqhgn.cn
