＜数据结构＞顺序栈的实现方式一

顺序栈的实现方式(一)

这是第二次学习数据结构，第一次学习数据结构的时候用的语言是cpp，因为不是主要专业课，所以没有静下来踏踏实实练习，导致经过一段时间之后对于概念还能理解，但是一碰上代码就麻爪。(当时还是年轻啊，现在想起来一把辛酸泪…
这学期有机会再一次接触数据结构，尝试以C语言完成代码实现。

关于顺序栈，似乎主要有两种实现方式，一种仅用一个指针，即top，另一种涉及两个指针，即base和top。个人的理解是，前者用的是静态数组的实现方式，后者则是动态数组(也就是涉及C中的malloc)。因为对指针的使用还没有彻底弄懂，对第二种实现方式也有很多疑问，目前还在钻研，所以先把第一种方式的笔记放上来以做记录。

/*本文档用来总结栈的基本操作*/
/*顺序栈*/
#include
#include#define MAXSIZE 100#define ElemType int#define Status int
#define ok 1
#define error 0/*顺序栈的实现方式1*/
typedef struct{ElemType data[MAXSIZE];int top;
}stack;void InitStack(stack *S){S->top = -1;
}Status Push(stack *S, ElemType e){if(S->top==MAXSIZE-1) return error;//栈满 无法进栈//此处也可以再定义一个判断栈满的函数，调用它并用其返回值判断也可，但好像不太常用（还是看具体需求S->data[++S->top] = e;//指针先上移 再赋值return ok;
}int EmptyStack(stack *S){if(S->top==-1) return 1;//栈空else return 0;//栈不空
}
/*关于函数形参要用指针传递还是值传递的问题*/
/*
值传递 传递的是主函数中值的副本 在定义的函数中对此副本进行的操作并不能影响主函数的该元素的值
即：int x = 10;f(x);printf("...",x); x结果为10,f(x)中的操作无法体现
一种方式是利用函数的返回值int x = 10,y;y = f(x);printf("...",y); y的结果为f(x)中的操作后x的值这种方式仅限于返回值为数值型且返回值为1个，2个则不成立（因为函数的返回值只能一个）
另一种方式则是 利用指针，即指针传递指针传递 传递的是元素的地址，函数黑匣子中对该元素进行的操作能够影响到主函数中的值
限制对指针的操作，即保护数据要用的const，这是另外的问题（也是C里最重要的问题之一）再另外一种方式则是用cpp中的引用运算符&，不过c中无此操作
*/
Status GetTopStack(stack *S, ElemType *x){//指针传递if(EmptyStack(S)==1) return error;//栈空，无法获取栈顶元素//if(S->top==-1) return error;//两种方式均可，若是整个程序中只有此处涉及判断栈空，用第二种方式也未尝不可*x  = S->data[S->top];return ok;
}Status Pop(stack *S,ElemType *x){if(EmptyStack(S)==1) return error;*x = S->data[S->top];S->top--;return ok;
}Status DestroyStack(stack *S);
//个人理解 有待考证 可能等我研究完malloc就能回答了(?
/*结构体中定义的是数组，属于静态存储分配，由编译器/系统完成它的分配与释放，销毁栈的函数可以不定义
但是运用base，top指针这种方式，动态申请内存的顺序栈需要销毁*/Status ClearStack(stack *S){//直接重置栈顶指针即可，后续进栈的元素会完成对之前元素的覆盖，因为有栈顶指针作为标记，重置之前栈中的元素并没有什么影响S->top = -1;return ok;
}int StackLength(stack *S){if(S->top==-1) return 0;return S->top+1;
}void Display(stack *S){if(EmptyStack(S)==1){printf("stack is null\n");}//最好不要用和MAXSIZE扯上关系，因为不确定是否是满栈(即不要采用for循环然后以MAXSIZE为边界的方式while(S->top!=-1){printf("%d ",S->data[S->top]);S->top--;}
}//另外一种方式是定义visit函数，然后Display中调用visit来printf数据，visit失败则返回error（Display为 Status型）int main(void){stack S;//stack型结点，不是地址InitStack(&S);//&不是引用，是取地址int i=5,n,m=0;printf("请输入5个元素:\n");while(i--){scanf("%d",&n);Push(&S,n);}printf("此时栈顶元素为：");GetTopStack(&S,&m);printf("%d\n",m);printf("弹出栈顶元素为：");Pop(&S,&m);printf("%d\n",m);printf("栈中还有元素个数/栈的长度为：");printf("%d\n",StackLength(&S));printf("栈中元素为：");Display(&S);return 0;
}

如有错误，还请多多指教~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！