《数据结构》3.1双栈结构
发布时间:2020-12-15 05:58:12 所属栏目:安全 来源:网络整理
导读:题目描述: /* 题目描述:将编号0和1的两个栈存放于一个空间V[m]的数组空间中,栈底分别处于数组的两端。 当第0号栈的栈顶指针top[0]=-1时该栈为空;当第1号栈的栈顶指针top[1]=m时,该栈为空。 两个栈均从两端向中间增长。试编写双栈初始化,判断栈空,栈满
题目描述: /*
//定义 typedef struct{ int top[2],bot[2]; int *V; int m; }DblStack; 实现如下: #include<stdio.h> #include<malloc.h> //定义 typedef struct{ int top[2],bot[2]; int *V; int m; }DblStack; /* 初始化:为栈空间分配一个大小为m的数组空间。0号栈的栈顶指针和栈底指针的初始值都是-1; 1号栈的栈顶指针和栈底指针的初始值都是m。表示栈空。 */ int InitStack(DblStack &S,int m){ //S.V=new int[m];//写成下面的语句也一样 S.V=(int *)malloc(m*sizeof(int)); if(!S.V){ return 0;//存储分配失败 } S.top[0]=-1; S.bot[0]=-1; S.top[1]=m; S.bot[1]=m; return 1; } /* 判断双栈是否为空:0号栈的栈顶指针和栈底指针的初始值都是-1; 1号栈的栈顶指针和栈底指针的初始值都是m。表示栈空。 */ int IsEmpty(DblStack &S){ if((S.top[0]==S.bot[0]) && (S.top[1]==S.bot[1])){ return 1;//栈空 }else{ return 0;//栈非空 } } /* 判断栈是否满:当S.top[1]-S.top[0]==1时,表示栈满。 */ int IsFull(DblStack &S){ if(S.top[1]-S.top[0]==1){ return 1;//栈满 }else{ return 0;//栈不满 } } /* 进栈:首先判断栈是否满,若满返回0;否则返回1. */ int Push(DblStack &S,int e1,int e2){ //元素e1进入0号栈,元素e2进入1号栈 if(IsFull(S)){ return 0;//栈已满,无法入栈 } // *++S.top[0]=e1; // *++S.top[1]=e2; S.V[++S.top[0]]=e1; //因为栈空间是放在数组中的,所以,进操作类似于向数组中添加元素。 S.V[--S.top[1]]=e2; return 1; } /* 出栈:首先判断栈是否为空,若空返回0;否则返回1。 */ int Pop(DblStack &S,int &e1,int &e2){ //用e1返回0号栈的栈顶元素;用e2返回1号栈的栈顶元素。 if(IsEmpty(S)){ return 0; } // e1=*--S.top[0]; // e2=*--S.top[1]; e1=S.V[S.top[0]--];//出栈操作也类似于数组的操作。 e2=S.V[S.top[1]++]; return 1; } int main(){ DblStack S; int m; printf("请输入双栈的数组空间大小:"); scanf("%d",&m); if(InitStack(S,m)){ printf("双栈初始化成功!n"); }else{ printf("双栈初始化失败!n"); } if(IsEmpty(S)){ printf("双栈S为空!n"); }else{ printf("双栈S非空!n"); } if(IsFull(S)){ printf("双栈已满!n"); }else{ printf("双栈未满!n"); } int n; printf("请输入每个栈入栈的元素个数:"); scanf("%d",&n); for(int i=0;i<n;i++){ int e1,e2; printf("请输入每个栈的第%d个元素:",i+1); scanf("%d%d",&e1,&e2); if(Push(S,e1,e2)){ printf("入栈成功n"); }else{ printf("入栈失败n"); } } int e1,e2; Pop(S,e2); printf("两个栈的栈顶元素出栈:%d %d",e2); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |