栈(c语言实现)

《栈(c语言实现)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西北师范大学地环学院地理信息系数据结构实验讲义二栈C语言实现张长城2011-2-8[顺序表构造栈]页脚一栈的基本原理分析作为栈这种数据结构，数据是进行所谓的先进后出操作，但栈在操作中，并不需要在中间插入删除操作、一般也不需要在进栈数据中查找什么，这种情况下，恰恰是顺序表可以完成的非常好的场合，所以栈经常是用一个简单的数组即可完成。123456789101112131415161718192021#includeints[100];inttop=0;voidpush(inte){s[top]=e;top++;}intpop(){top--;returns[top];}

2、main(){inti;for(i=0;i<10;i++)push(i);for(i=0;i<10;i++)printf("%d",pop());}最简单的栈程序，见s0.c这个程序就能完成最简单的栈的程序，原理也很简单。对栈的应用，比如把10进制数1348转换成8进制，则过程是：商余1348/81684168/821021/8252/802这个结果就是2504，但从计算步骤上看：它的结果次序是反的，是4、0、5、2，如果把余数的结果先保存进栈，则出栈恰好是正确的结果。略微修改s0.c就可完成这个工作。这个算法适合任何进制数据转换。页脚123456789101112main(){

3、intN=1348;while(N){push(N%8);N=N/8;}while(top>0)printf("%d",pop());printf("");}最简单的栈应用程序，见s0.c但这个程序有很大的问题：1仅仅有一个栈空间，程序如果要用多个栈、则要说明很多s[]、top之类的变量；2这个栈也仅仅能进出int类型的数据，如果是多种类型数据组成的表格，则不能处理；所以上述程序仅是个原理示范性的程序，在更加广泛的情况下不能用，它太简单了。要对任意类型的表进行栈操作，那就找C#的泛型或者JavaScript吧，在C这里，我们依然最一个简单的特定的表格进行栈处理，这个表就是：str

4、uctElemType{charc;intiData;longlData;charsData[20];};这是个包含字符、整数、长整数、字符串的表，表本身或许没什么现实意义。根据栈的原理，我们知道设计栈不需要链表、顺序表已经足够好了。所以设计一个表示栈的表就是：structsqStack{structElemType*base,*top;intCount,Size;};这个表中*base指针代表栈空间的首地址；*top代表栈空间的栈顶地址；Count代表进栈数据元素的个数，也就是说进栈数据有多少行；Size代表栈的最大空间，也就是说栈最大能容纳多少行数据。这个表实际相当于顺序表的目录

5、表，它能使访问栈更加容易。所以编程的整体路线也将同顺序表、链表中做的那样：不断补充函数。页脚1栈的初试化所谓栈的初始化，就是构造一个指定空间的存储单元，并且给出这片空间的首地址，这个手段在顺序表、链表的编程中已经很熟悉了。如果指定栈的空间是Size，那么就意味着为ElemType这样的表申请Size行的存储空间，写成C语言就是：structElemType*p;p=(structElemType*)malloc(sizeof(structElemType)*Size);当然，要把这个结果存储到栈目录表seqStack中，所以：structseqStack*s;s=(structseq

6、Stack*)malloc(sizeof(structseqStack));s->base=p;s->top=p;s->Count=0;s->Size=Size;注意编程要点：这里的表s保存的最重要数据就是：当前栈中数据的行数Count、以及栈的最大容量。当然，在空栈的情况下，栈顶指针和栈的存储空间首地址是一致的。整个函数就是：123456789structseqStack*StackInit(intSize){structElemType*p;structseqStack*s;p=(structElemType*)malloc(sizeof(structElemType)*Size

7、);s=(structseqStack*)malloc(sizeof(structseqStack));s->base=p;s->top=p;s->Count=0;s->Size=Size;returns;}构造一个有Size存储空间的栈，见s1.c用这样的方式设置了一个栈、并获得栈空间的地址，从而完成了栈的初始化。2进栈操作如有ElemType类型的数据行e，试图进栈s就是：首先把e的内容复制到s->top:s->topçe;然后s->count++，这