数据结构：顺序栈的基本操作及应用

我就是我 2022-12-18 02:53 156阅读 0赞

## 数据结构：顺序栈的基本操作及应用 ##

## 实验目的 ##

通过该实验，让学生掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。

## 实验内容 ##

用顺序存储结构，实现教材定义的栈的基本操作，提供数制转换功能，将输入的十进制整数转换成二进制、八进制或十六进制。

## 参考界面 ##

菜单中包括以下功能：  
1.初始化栈，2.销毁栈，3.清空栈，4.栈判空，5.求栈长度，6.获取栈顶元素，7.插入一个 元素，8.删除一个元素，9输出所有元素，10进制转换。  
要求：自定义的函数中不允许出现提示语和输出语句。

## 验收 ##

通过菜单调用各个操作，测试点：

*  没有初始化前进行其他操作，程序是否能控制住；
 *  初始化一个栈；
 *  判栈空，屏幕显示栈为空；
 *  3个数入栈， 2、4、6；
 *  栈长度，屏幕输出3；
 *  取栈顶元素，再判栈空，然后再判栈长度。让学生知道取栈顶元素不改变栈中的内容，栈顶指针不发生改变；
 *  出栈，再判栈长度和输出栈中内容；（多次出栈，直到栈为空；再出栈，是否提示栈为空）
 *  销毁栈，再做其他操作，判断程序是否能控制；
 *  数制转换，（允许用户输入想把十进制转换成几进制），然后灵活的转换成对应的进制。

## 具体代码如下 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    //--------------栈的顺序存储表示------------------- 
    #define INIT_SIZE 100 //初始分配量 
    #define CREMENT 10 //分配增量
     
    typedef int status;     //status是函数的类型，其值是函数结果状态代码。
    typedef int SElem;     //自定义
    
    /* base：在栈构造之前和销毁之后，base 的值为NULL top:栈顶指针 stacksize：目前已经分配的存储空间，以元素为单位 */
    typedef struct { 
    	SElem * base;  
    	SElem * top;
    	int stacksize;     
    }SqStack; 
    
    //---------------基本操作的函数原型说明------------ 
    status InitStack(SqStack *S);
          //构造一个空栈S
    status DestroyStack (SqStack *S);
          //销毁栈S
    status ClearStack (SqStack *S);
          //清空栈S 
    static StackEmpty(SqStack *S);
          //判空栈S 
    int StackLength(SqStack S);
          //求栈S的长度 
    status GetTop(SqStack S,SElem *e);
          //获取栈顶元素 
    status Push(SqStack *S,SElem e);
          //插入一个元素（压入） 
    status Pop(SqStack *S,SElem *b);
          //删除一个元素（弹出） 
    
    //---------------主函数---------------------------- 
    int main (){ 
    	int i;
    	SqStack L = { NULL,NULL,0};	
    	SElem num;
    	int choice;
    	while (1){ 
    		//菜单
    		printf("\t\t\t 1---初始化一个栈\n");
    		printf("\t\t\t 2---销毁栈\n");
    		printf("\t\t\t 3---清空栈\n");
    		printf("\t\t\t 4---判断栈是否为空\n");
    		printf("\t\t\t 5---求栈长度\n");
    		printf("\t\t\t 6---获取栈顶元素\n");
    		printf("\t\t\t 7---插入一个元素\n");
    		printf("\t\t\t 8---删除一个元素\n");
    		printf("\t\t\t 9---输出所有元素\n");
    		printf("\t\t\t 10--进制转换\n");	
    		printf("\t\t\t 退出，输入一个负数！");
    		printf("\n");
    		printf("\t\t----------------------------------------------\n");
    		printf("\n");
    		printf("请输入你需要的操作：\n");
    		//退出
    		scanf("%d",&choice);
    		if(choice<=0){ 
    			printf("已退出\n");
    			return 0;
    		} 
    		switch (choice){ 
    			case 1:
    				if(L.base){ 
    					printf("栈已存在，不可重复初始化！\n");
    				}else{ 
    					//初始化 
    					i=InitStack (&L);
    					if(i==1){ 
    						printf("初始化栈成功\n");
    					}else if(i==-2){ 
    						printf("分配空间失败\n");
    					} 
    // printf("%d",L.stacksize);
    				}
    				break;
    			case 2:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//销毁
    					i = DestroyStack(&L); 
    					if(i==1){ 
    						printf("销毁栈成功\n");
    					}
    				}
    				break;
    
    			case 3:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//清空
    					i = ClearStack(&L);
    					if(i == 1){ 
    						printf("清空栈成功\n");
    					} 
    				}				
    			 	break;
    			case 4:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//判空
    					i = StackEmpty(&L);
    					if(i == 1){ 
    						printf("该栈为空栈\n");
    					} else{ 
    						printf("该栈为非空栈\n");
    					}
    				}				
    			 	break;
    			case 5:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//求长度
    					i = StackLength(L);
    					 printf("当前栈的长度为%d\n",i);
    				}
    			 	break;
    			case 6:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//获取栈顶元素
    					i = GetTop(L,&num); 
    					if(i == 1){ 
    						printf("该栈顶元素为：%d\n",num);
    					}else{ 
    						printf("该栈为空栈！\n");
    					}
    				}
    			 	break;
    			case 7:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//插入
    					printf("请输入你想插入的元素:");
    					scanf("%d",&num);
    					i = Push(&L,num);
    					if(i == 1){ 
    						printf("插入成功\n");
    					}else { 
    						printf("分配空间失败\n");
    					}
    				}
    			 	break;
    			case 8:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					i = Pop(&L,num);
    					printf("%d\n",&num); 
    					if(i == 1){ 
    						printf("栈顶元素%d删除成功\n",num);
    					}else { 
    						printf("该栈为空栈\n");
    					}
    				}
    			 	break;
    			case 9:
    				if(!L.base){ 
    					printf("栈未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//打印 
    					SElem *q;
    					q = L.base;
    					printf("栈内元素如下:【栈底】->");
    					if(L.base==L.top)
    						printf("空栈！！！\n");
    					while(L.top>q){ 
    						printf("【%d】-> ",*q);
    						q++;
    					}
    					printf("【栈顶】\n");
    				}
    			 	break;
    			case 10:
    				//进制转换
    				printf("请输入你想转换到什么进制：");
    				scanf("%d",&syst);
    				printf("请输入你想转换的数:");
    				scanf("%d",&numb);
    				while(numb!=0){ 
    					i = Push(&N,numb%syst);
    					numb = numb / syst;
    				}
    				printf("转换后为：");
    				SElem *p;
    				p = N.top;
    				while(N.base<p){ 
    					printf("%d",*(p-1));
    					p--;
    				}
    				i = ClearStack(&N);
    			 	break;
    			default:
    				printf("选择失败！请重新选择！\n");
    				break; 	 	 	 			
    		}
    		system("pause");   //请按任意键结束 
    		system("cls");     //清屏 
    	}
    	return 0;
    } 
    
    //---------------基本操作的算法描述----------------
    status InitStack(SqStack *S){ 
    	/*构造一个空的栈S *S:可以影响到 函数以外的栈 */
    	 S->base = (SElem *)malloc (INIT_SIZE *sizeof(SElem));
    	 if (!S->base)  return OVERFLOW;    //分配失败 
    	 S->top = S->base;                  //空栈 
    	 S->stacksize = INIT_SIZE;         //分配100个元素
    // printf("%d",S->stacksize); 
    	 return OK; 
    }
    
    status DestroyStack (SqStack *S){ 
    	/*销毁栈 *S:可以影响到 函数以外的栈 free函数施放栈空间 然后重置其三项属性 */   
    	free (S->base);
    	S->base = NULL;
    	S->top = NULL;
    	S->stacksize = 0; 
    	return OK; 
    }
    
    status ClearStack (SqStack *S){ 
    	/*清空栈 *S 即将栈顶top回退至base 清空后这个栈还能用 */
    	S->top = S->base;
    /* if (S->top) { printf("!%d,%d",S->top,S->base); } */	
    	return OK;
    }
    
    status StackEmpty (SqStack *S){ 
    	/*判空 *S 为空返回OK，否则返回ERROR */ 
    	if (S->top==S->base){ 
    		return OK;
    	}else{ 
    		return ERROR;
    	}
    }
    
    int StackLength (SqStack S){ 
    	/*求长度 S:不需要对原栈进行修改，故不需要影响到原栈 即求从top到base间元素的个数 */
    	int i;
    	while (S.top != S.base){ 
    		//这个算法中S.base并不存放元素。 
    		i++;
    		S.top--;
    	}
    	return i; 
    } 
    
    status GetTop (SqStack S,SElem *e){ 
    	/*获取栈顶元素 不为空用e返回栈顶元素 */
    	if(S.top == S.base){ 
    		return ERROR;
    	}else{ 
    		e = S.top-1;
    		return OK;
    	}
    }
    
    status Push(SqStack *S,SElem e){ 
    	/*插入 *S 先判断是否栈满，栈满则追加存储空间 然后插入元素e */ 
    	if(S->top - S->base >= S->stacksize){ 
    		//栈满
    		 S->base = (SElem*)realloc(S->base,(S->stacksize + CREMENT)*sizeof(SElem));  //追加 
    		 if (!S->base){ 
    		 	return OVERFLOW;  //分配失败 
    		 }
    		 S->top = S->base+S->stacksize;
    		 S->stacksize += CREMENT;
    	}
    	*S->top = e;   //S->top可是指针类型，而e为数据，故赋值的时候需要加* 
    	S->top ++;
    	return OK;
    }
    
    status Pop(SqStack *S,SElem *b){ 
    	/*删除 *S，*e 若栈不为空，删除栈顶元素，并用e返回其值 */ 
    	if (S->top == S->base){ 
    		return ERROR;
    	}
    	S->top =S->top-1;
    	b = S->top;
    	return OK;
    }