这两天完成了栈的顺序存储结构的相关算法，包括初始化、压栈、出栈、取栈顶元素、判断栈是否为空、返回栈长度、栈的遍历、清栈、销毁栈。这次的实现过程有两点收获，总结如下：
一、清楚遍历栈的概念
　　栈的遍历指的是从栈底想栈顶方向运行visit()函数，这是之前的学习中所忽略的；栈的遍历解除了栈的输出顺序只能从栈顶像栈底方向的限制。
二、清空栈时要不要将stacksize重置
　　网上看到有的人在实现清空栈这一功能时，将stacksize重置为0，我觉得有点问题，起初的想法是将其重置为初始化时的值，在与同学讨论了后，最后决定不应重置stacksize的值，原因是:
　　重置的目的是针对使用了realloc()重新分配了地址的栈，但是realloc()函数分配的是一段连续的地址，指向栈底的指针指向了这段空间，即使将stacksize重置回初始值，增加的那段空间还是由指向栈底的指针来控制的(参照这句S.base=(Elemtype *)realloc(S.base,(S.stacksize+STACKINCREACE)*sizeof(Elemtype));思考)，因此重置没有意义。类比顺序表的清空：顺序表的清空也是只将当前长度置为0，没有改变它的listsize值。
　　这次使用的编译环境是VC++6.0。
//头文件内容
//--------------------栈的顺序存储结构--------------------
#define STACK_INIT_SIZE 100
#define STACKINCREACE 10
typedef char E//在头文件中说明
typedef int S
typedef struct{
Elemtype *base;
Elemtype *
//----------------------函数声明部分----------------------
Status InitStack(SqStack &S);
Status Push(SqStack &S,Elemtype e);
Status Pop(SqStack &S,Elemtype &e);
Status GetTop(SqStack S,Elemtype &e);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status StackTraverse(SqStack S);
Status ClearStack(SqStack &S);
Status DestroyStack(SqStack &S);
//源文件内容
#include &stdio.h&
#include &stdlib.h&
#include "SqStackHeader.h"
//--------------------主函数入口--------------------
void main(){
char temp='a';
char getElem=NULL;
char popElem=NULL;
InitStack(stack);
Push(stack,temp);
Push(stack,'b');
GetTop(stack,getElem);
printf("栈顶元素是：%c\n",getElem);
char *empty=NULL;
empty=StackEmpty(stack)?"是空栈！":"不是空栈！";
printf("是否为空栈判断结果：%s\n",empty);
ClearStack(stack);
DestroyStack(stack);
StackTraverse(stack);
printf("栈的长度：%d\n",StackLength(stack));
Pop(stack,popElem);
//------------------栈的初始化函数------------------
Status InitStack(SqStack &S){
S.base = (Elemtype *)malloc(STACK_INIT_SIZE*sizeof(Elemtype));
//编译时报错：missing &)&
//错误原因：由于头文件中定义常量时后面加了;导致编译的时候将STACK_INIT_SIZE用100;代替，
//使得该函数提前结束语100处，malloc后的&(&找不到匹配的&)&而报错
//解决方法：去掉常量定义中的;
if(!S.base){
return false;
S.stacksize=STACK_INIT_SIZE;
S.top=S.base;
return true;
//---------------------入栈函数---------------------
Status Push(SqStack &S,Elemtype e){
//判断是否溢出
if(S.top-S.base&=S.stacksize){
S.base=(Elemtype *)realloc(S.base,(S.stacksize+STACKINCREACE)*sizeof(Elemtype));
if(!S.base){
return false;
S.top=S.base+S.//注意因为这里的栈底指针的改变，导致栈顶指针随之改变
S.stacksize+=STACKINCREACE;
//压栈部分
return true;
//---------------------出栈函数---------------------
Status Pop(SqStack &S,Elemtype &e){
//非法判断
if(S.base==S.top){
return false;
//注意这里因为top指向栈中当前元素的上一个空间，所以要先将其位置减一
return true;
//-------------------查看栈顶元素-------------------
Status GetTop(SqStack S,Elemtype &e){
if(S.base==S.top ){
return false;
e=*(S.top-1);
return true;
//------------------判断栈是否为空------------------
Status StackEmpty(SqStack S){
if(S.base==S.top){
return true;
return false;
//------------------返回栈元素个数------------------
int StackLength(SqStack S){
if(S.base==S.top){
return S.top-S.base;
//--------------------遍历栈------------------------
Status StackTraverse(SqStack S){//从栈底到栈顶的方向
if(S.top==S.base){
return false;
while(S.base &S.top ){
printf("%c\t",*(S.base++));
printf("\n");
return true;
//--------------------清空栈------------------------
Status ClearStack(SqStack &S){//清空栈的时候不用将stacksize重新赋值
S.top=S.base;
//因为经过realloc函数重新分配空间后(stacksize大小改变)，
return true;
//S.base指向的是一段stacksize大小的连续存储空间
//即使将他重置，剩余的空间也是闲置的(顺序表里也只是经当前长度置为0)
//--------------------销毁栈------------------------
Status DestroyStack(SqStack &S){
free(S.base);
free(S.top);
S.base=NULL;
return true;
阅读(...) 评论()您所在的位置： &
清华大学出版社
《妙趣横生的算法（C语言实现）》第1章数据结构基础，如果你只想掌握一般层次的知识，或是已经学过数据结构，只是为了深入学习本书后续的内容而进行回顾和复习，那么本章的介绍是足够的。本节为大家介绍栈的定义。
栈是一种重要的线性结构。可以这样讲，栈是前面讲过的线性表的一种具体形式。也就是说，栈必须通过顺序表或者链表来实现。顺序表或者链表既可以像前面介绍的那样独立存在，组织和操作数据，同时它们也是一些特殊的数据结构（栈、队列……）实现的基础，它们的概念更宽泛一些。下面通过具体的介绍来深入理解栈的概念。
1.4.1& 栈的定义
栈（stack）是一个后进先出（last in first out，LIFO）的线性表，它要求只在表尾进行删除和插入等操作。也就是说，所谓栈其实就是一个线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制。首先，栈的元素必须先进后出，这与一般的顺序表不同。其次，栈的操作只能限定在这个顺序表的表尾进行。这就是栈的独特之处。对于栈来说，这个顺序表或者链表的表尾（也就是进行删除和插入等操作的地方）称为栈的栈顶（top），相应的表头称为栈底（bottom）。
栈形如一个子弹膛，最先压进去的子弹一定最后弹出，如图1-9所示。
图1-9& 栈的示意
如图1-9所示，栈的本质就是一个线性表，只不过数据不能像一般的顺序表那样操作自如。数据必须从栈顶进入，还必须从栈顶取出，先进入栈中的数据在后进入栈中的数据的下面。最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。
上面只给出了栈及其操作的形象的描述。下面具体介绍如何定义一个栈，并在随后的小节中介绍栈的操作。
线性表有两种存储形式，即顺序表存储和链表存储。一般的栈都是用顺序表存储形式实现的，因此在这里只介绍顺序栈。
可以用以下的方式定义一个顺序栈。typedef&struct{ &&&&&ElemType&* &&&&&ElemType&* &&&&&int& &}sqS&
这里定义了一个顺序栈sqStack类型，它包含3个数据项：base、top、stacksize。其中，base是指向栈底的指针变量。top是指向栈顶的指针变量，它们指向的数据类型为ElemType，这是压入栈中的数据的类型（可以是int、char等）。stacksize指示栈的当前可使用的最大容量。掌握了这3个数据，就相当于掌握了一个完整的栈。可以通过base和top对栈进行各种操作，通过stacksize判断栈的空间分配情况。
【责任编辑： TEL：（010）】&&&&&&
关于&&&&&&的更多文章
想要理解大数据，使之更贴近大多数人，最重要的手段的之一就是数
本书描述了黑客用默默无闻的行动为数字世界照亮了一条道路的故事。
讲师： 26人学习过讲师： 14人学习过讲师： 34人学习过
PowerShell是微软的新命令行Shell和脚本语言，承诺会
Python 是一门常用的编程语言，它不仅上手容易，而且
《Photoshop CC图像处理》全面介绍了图形图像处理软件
本书详细描述如何在复杂技术项目中使用Scrum，并结合真实的Scrum案例及专家洞识，在简明及高度概括的理论之上更侧重于实践，并不
51CTO旗下网站用C语言写出: 顺序栈（静态定义、动态定义）操作的验证（建栈、入栈、出栈、销毁栈、判空、求栈长度、取栈顶元素、输出栈中元素等）
本回答由提问者推荐
var sogou_ad_id=731547;
var sogou_ad_height=160;
var sogou_ad_width=690;您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
(第三章栈和队列.ppt 39页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：80 &&
(第三章栈和队列
你可能关注的文档：
··········
··········
日北京理工大学http://www.bit9.dhs.org/回顾：1.了解线性结构的特点，线性表是线性结构上一种典型的ADT，采用顺序存储结构表示的线性表简称为顺序表，采用链式存储结构表示的线性表简称为链表。能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。2.熟练掌握这两类存储结构的定义以及各基本操作与作业问题的实现算法，会分析操作的算法时间复杂度。最好能全部实现以备后用，将来还有课程设计3.会应用顺序表和链表解决实际问题，如一元多项式的表示、相加、求导（假设用普通单链表或单循环链表存储）4.循环链表、双向链表、双向循环链表的特点和基本操作5.习题:作业+2.1—2.102.152.162.192.212.226.课程设计：配套题集P79-170实习1、实习2、实习5，任选两章，从各章实习题中任选1题，不可与示例雷同。期末交课程设计手册及光盘第二章作业说明-多项式求导第三章栈和队列3.1栈的抽象数据类型定义与实现3.2栈的应用举例3.3栈的应用---栈与递归3.4队列的抽象数据类型定义和实现3.5队列应用---离散事件模拟3、顺序栈的定义顺序栈基本操作的实现—初始化/销毁/置空StatusInitStack(SqStack&S){//构造空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.//空栈S.stacksize=STACK_INIT_SIZE;return(OK);}//InitStack入栈与出栈StatusPush(SqStack&S,SElemTypee){//插入e为栈顶元素if(S.top-S.base==S.stacksize){//栈满则应重新分配空间S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=(S.base+S.stacksize);//使得S.top重新指向栈顶,因reallocS.stacksize+=STACKINCREMENT;}*S.top++=e;//top指向待插入位置return(OK);}//Push引用型操作StatusStackEmpty(SqStackS)
{if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){return(S.top-S.base);}StatusGetTop(SqStackS,SElemType&e){{if(S.top==S.base)returnERROR;e=*(S.top-1);//注意top指向待插入位置returnOK;}StatusStackTraverse(SqStackS,Status(*visit)(ElemType)){ //从栈底元素到栈顶元素依次执行visit函数,常用于输出栈中元素 ElemType*p=S.
if(S.base==S.top)printf(&空栈\n&); else while(p&S.top){(*visit)(*p);++p;} returnOK;}//除遍历操作外时间复杂度均O(1)4、链栈的定义与实现【补充】基本操作实现回顾：3.2栈的应用1、十进制整数转换为八进制2、括号匹配检验正确：([]{})错误：[(])([])})(([])3、行编辑程序whli##ilr#e(s#*s)//while(*s)(*s=#++)
//putchar(*s++);回顾:栈的概念:栈栈底指针栈顶指针栈顶元素栈的两种存储结构定义及各自适用场合，及栈的操作在两种结构下的实现栈的应用--LastInFirstOut后进先出//总是访问最近插入的一个//按插入顺序倒着访问作业:3.3栈与递归专题课件2、链队列的定义和基本操作实现基本操作实现—初始化基本操作实现—销毁与清空基本操作实现—入队基本操作实现—出队3、顺序队列的定义和操作实现循环队列类型定义：a1∧anQ.frontQ.rearStatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其“值”if(Q.front==Q.rear)returnERROR;//空队列QueuePtrp=Q.front-&next
正在加载中，请稍后...