数据结构实验4_C语言_顺序栈的基本操作及应用、栈的应用之进制转换

实验4、顺序栈的基本操作及应用（1）实验目的通过该实验，让学生掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。（2）实验内容用顺序存储结构，实现教材定义的栈的基本操作，提供数制转换功能，将输入的十进制整数转换成二进制、八进制或十六进制。（3）参考界面菜单中包括以下功能：1.初始化栈，2.

scl、

6128人浏览 · 2020-10-25 14:42:28

scl、 · 2020-10-25 14:42:28 发布

实验4、顺序栈的基本操作及应用

（1）实验目的
通过该实验，让学生掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。

栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。

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

（3）参考界面

菜单中包括以下功能：

1.初始化栈，

2.销毁栈，

3.清空栈，

4.栈判空，

5.求栈长度,

6.获取栈顶元素，

7.插入一个元素，

8.删除一个元素，

9输出所有元素，

10进制转换。

要求：自定义的函数中不允许出现提示语和输出语句。

（4）验收/测试用例

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

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

验证性

重点：入栈和出栈
难点：进制转换（十六进制）

环境：Dev C++

一、设计思想

功能函数不出现输出语句，返回结果到主函数，规范函数返回值书写，功能函数按照返回值类型分为
1.1 void返回值类型配合 &参数的,例如像初始化栈、销毁栈、清空栈、入栈、
1.2 SElemType、int、bool返回值类型的，例如像栈判空、求栈长度、获取栈顶元素，出栈、输出所有元素
提高程序健壮性的地方：操作功能函数前判断栈是否初始化、栈是否为空
关于一些功能函数的说明：
3.1 功能9的打印栈内元素函数实现思想：开始先判断是否栈未初始化，若栈已经初始化，调用功能函数4判空函数，判断栈是否为空，然后for循环栈元素个数次，每次就调用打印函数
3.2 打印函数的参数为（MyStack s,int i），注意的是，是没有&符的，方便后面功能函数移动s.top指针而不影响真实的栈，传入i的目的，是每次找到元素位置（s.top – i- 1）,然后在调用获取栈顶元素的函数（这里可以直接获取，但是为了调用写好的函数）获取结果return
对于进制转换的实现，需要注意的是把转化16进制需要单独列出，因为涉及英文字母ABCDEF,所以压栈的时候压字母对应的ascii值（65,66,67,68,69,70），出栈的时候，调用出栈函数Pop(),判断Pop()返回的出栈元素是否在65-70之间，即是否对应为英文字母，是就switch转化为相应字母打印，不是就直接打印即可
需要注意的是，进制转换栈使用完毕后需要销毁（清空就不用了，所有的元素均已出栈）

二、主要源代码


	# include<iostream>
	# include<stdio.h>
	# include<stdlib.h>
	
	
	# define STACK_INIT_SIZE 88
	# define STACKINCRMENT 6
	using namespace std;
	typedef int SElemType;
	
	typedef struct {
		SElemType *base;
		SElemType *top;
		int stacksize;
	}MyStack; 
	
	
	// 一、函数声明
	
	// 1. 初始化栈
	void InitStack(MyStack &s);
	
	// 2. 销毁栈
	void DestoryStack(MyStack &s);
	
	// 3. 清空栈
	void ClearStack(MyStack &s); 
	
	// 4. 栈判空
	bool JudgeEmpty(MyStack s) ;
	
	// 5. 求栈长度
	int GetStackLength(MyStack s); 
	
	// 6. 获取栈顶元素
	SElemType GetTop(MyStack s) ;
	
	// 7. 插入一个元素（入栈） 
	void Push(MyStack &s,SElemType e) ;
	
	// 8. 删除一个元素（出栈） 
	SElemType Pop(MyStack &s);
	
	// 9. 输出所有的元素
	SElemType PrintElem(MyStack s,int i); 
	 
	// 10. 进制转换
	SElemType MetricConversion (int num,int which,MyStack &ms_mc);
	
	 
	
	int main(){
		MyStack ms;
		ms.base = NULL;
		ms.top = NULL;
		
		//进制转化栈 
		MyStack ms_mc;
		ms_mc.base = NULL;
		ms_mc.top = NULL;
		
		int flag = 1;
		
		
		while(flag == 1){
			
			cout<<"☆欢迎使用顺序栈基本操作小程序~☆"<<endl;
			cout<<"==Design by 软6-1925050351-司超龙"<<endl<<endl;
			cout<<"1. 初始化栈"<<endl;
			cout<<"2. 销毁栈"<<endl;
			cout<<"3. 清空栈"<<endl;
			cout<<"4. 栈判空"<<endl;
			cout<<"5. 求栈长度"<<endl;
			cout<<"6. 获取栈顶元素"<<endl;
			cout<<"7. 插入一个元素"<<endl;
			cout<<"8. 删除一个元素"<<endl; 
			cout<<"9. 输出所有的元素"<<endl;
			cout<<"10.进制转换"<<endl;
			cout<<"☆输入一个负数退出程序~☆"<<endl<<endl;
			cout<<"请输入响应指令完成操作~"<<endl;
			 
			int n;
			cin>>n; 
			switch(n){
				case 1:
					system("cls");
					
					InitStack(ms);
					if(ms.base!= NULL){
						cout<<"栈初始化成功！"<<endl<<endl;
					}
					else{
						cout<<"栈初始化失败！ 请重新初始化~"<<endl<<endl; 
					}
					break;
				case 2:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else{
						DestoryStack(ms);
						if(ms.base == NULL){
							cout<<"栈销毁成功！"<<endl<<endl; 
						} 
						else{
							cout<<"栈销毁失败!请重新销毁~"<<endl<<endl; 
						}
					}
					break;
				case 3:
					system("cls");
						if(ms.base == NULL){
							cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
						}
						else if(ms.base == ms.top){
							
							cout<<"栈为空，不必执行清空操作" <<endl<<endl; 
						}
						else{
							ClearStack(ms);
							cout<<"栈清空完成"<<endl<<endl; 
						
						}
					break;
				case 4:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else{
						if(JudgeEmpty(ms)){
							cout<<"栈为空！"<<endl<<endl;
						}
						else{
							cout<<"栈不为空！"<<endl<<endl;
						}
					}
					break;
					
				case 5:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else{
						cout<<"栈的长度为："<<GetStackLength(ms)<<endl<<endl; 
					}
					break;
				case 6:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else if(ms.base == ms.top){
							
						cout<<"栈为空,不存在栈顶元素！" <<endl<<endl; 
					}
					else{
						cout<<"栈顶元素为 "<<GetTop(ms)<<endl<<endl;
						
					} 
					break;
				case 7:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else{
						if(ms.top - ms.base >= ms.stacksize){
							cout<<"栈已满， 重新申请空间中...."<<endl;
							ms.base = (SElemType *) realloc(ms.base,(ms.stacksize + STACKINCRMENT) * sizeof(SElemType));
							if(!ms.base){
								cout<<"重新分配失败！请重新操作~"<<endl;
							}
							else{
								ms.top = ms.base + ms.stacksize;
								ms.stacksize = ms.stacksize + STACKINCRMENT;
								
							}
							 
						}
						SElemType e;
						cout<<"请输入一个入栈的元素：" <<endl;
						cin>>e;
						Push(ms,e);
						cout<<"元素" <<e<<" 入栈成功！"<<endl<<endl;
						
					}
					
					
					break;
				case 8:
					system("cls");
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else if(ms.base == ms.top){
							
						cout<<"栈为空,出栈失败！" <<endl<<endl; 
					}
					else{
						cout<<"元素" <<Pop(ms)<<" 出栈成功！"<<endl<<endl;
					} 
	
					break;
				case 9:
					system("cls");
					
					if(ms.base == NULL){
						cout<<"栈还未初始化！请先初始化~"<<endl<<endl; 
					}
					else{
						//调用判空函数 
						if(JudgeEmpty(ms)){
							cout<<"栈为空！" <<endl<<endl;
						}
						else{
							cout<<"栈内的元素为：(先进栈的在后面) ";
							//i可以从0开始，这里为了保证和个数一致，从1开始 
							for(int i = 1;i<=ms.top - ms.base;i++){
								cout<<PrintElem(ms,i)<<" ";
							}
							cout<<endl<<endl;
						}
					}
					break;
				case 10:
					system("cls");
					int num,which;
					cout<<"请输入你要转化的10进制整数数值(0<num)："<<endl;
					cin>>num;
					if(num > 0){
						
						cout<<"1. 转化为2 进制"<<endl;
						cout<<"2. 转化为8 进制"<<endl;
						cout<<"3. 转化为16进制"<<endl<<endl; 
						cout<<"请输入对应指令："<<endl;
						cin>>which;
						if(which == 1 || which == 2 ){
							MetricConversion(num,which,ms_mc);
							//cout<<GetStackLength(ms_mc)<<endl;
							
							cout<<"转化结果为：";
							
							/*
							这是调用9打印函数打印 
							for(int i = 1;i<= ms_mc.top - ms_mc.base;i++){
								cout<<PrintElem(ms_mc,i);
							
							}
							*/
							//这是直接移动top指针来打印 
							while(ms_mc.base != ms_mc.top){
								cout<< *(--ms_mc.top);
							}
							
						}
						//因为16进制涉及字母打印，单独列出 
						else if(which == 3) {
							
							MetricConversion(num,which,ms_mc);
							//cout<<GetStackLength(ms_mc)<<endl;
							
							cout<<"转化结果为：";
							
							//debug-->cout<<"栈长度为： "<<ms_mc.top - ms_mc.base <<endl;
							
							/*
							这是调用9打印函数打印 
							for(int i = 1;i<= ms_mc.top - ms_mc.base;i++){
								cout<<PrintElem(ms_mc,i);
							
							}
							*/
							//这是直接移动top指针来打印 
							while(ms_mc.base != ms_mc.top){
								 
								 
								int num = Pop(ms_mc);
								
								if(num <= 9){
									cout<<num;
								}
								//A-F的显示
								else{
									switch(num){
										case 65:
											cout<<'A';
											break;
										case 66:
											cout<<'B';
											break;
										case 67:
											cout<<'C';
											break;
										case 68:
											cout<<'D';
											break;
										case 69:
											cout<<'E';
											break;
										case 70:
											cout<<'F';
											break;
										
									}
								}
							}
							cout<<endl<<endl; 	
							
							DestoryStack(ms_mc) ;
							if(ms_mc.base == NULL && ms_mc.top == NULL){
								
								cout<<"栈已经销毁完毕！"<<endl<<endl; 
							} 
						
						}
						else{
							cout<<"输入的指令有误！下次吧下次吧~"<<endl;
						}
				
					}
					else{
						cout<<"请输入要求之内的数值~" <<endl;
					}
					
					cout<<endl; 			
					break;
				default :
					system("cls");
					if(n < 0){
						flag  = 0;
						system("cls");
						cout<<"程序已经退出！欢迎下次使用~"<<endl; 
						break;
					}
					else{
						cout<<"输入的指令有误，下次吧，下次吧~~"<<endl; 
					}
			}
	
		}
		return 0;
	}
	
	// 二、函数实现
	
	//1. 初始化一个栈
	
	void InitStack(MyStack &s){
		s.base = (SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
		s.top = s.base;
		s.stacksize = STACK_INIT_SIZE;
	} 
	
	//2. 销毁栈 
	void DestoryStack(MyStack &s) {
		
		s.stacksize = 0;
		free(s.base);
		s.base = NULL;
		s.top = NULL;
		
	
	}
	
	//3. 清空栈
	
	void ClearStack(MyStack &s){
		s.top = s.base;
		
	} 
	
	//4. 栈判空
	bool JudgeEmpty(MyStack s){
		if(s.base == s.top){
			return true;
		}
		else
			return false;
	} 
	
	
	
	//5. 求栈长度
	int GetStackLength(MyStack s){
		return s.top - s.base;
	}
	
	//6. 获取栈顶元素
	SElemType GetTop(MyStack s) {
		
		//注意优先级，先使用还是先减减 
		return *(--s.top);
	}
	
	// 7. 插入一个元素
	void Push(MyStack &s,SElemType e){
		
		*(s.top++) = e;
	} 
	
	
	
	// 8. 删除一个元素（出栈） 
	SElemType Pop(MyStack &s){
		return *(-- s.top);
	}
	
	// 9. 输出所有的元素
	SElemType PrintElem(MyStack s,int i){
		//获取栈顶的元素
		if(s.base != s.top) {
			i--;
			s.top -= i; 
			return GetTop(s);
			
		}
		
	}
	
	// 10. 进制转换
	SElemType MetricConversion (int num,int which,MyStack &ms_mc){
		InitStack(ms_mc);
		switch(which){
			case 1:
				while(num != 0){
					int YuShu = num % 2;
					Push(ms_mc,YuShu);
					num = num / 2;
				}
				//cout<<GetStackLength(ms_mc)<<endl;debug正常 
				break;
			case 2:
				while(num != 0){
					int YuShu = num % 8;
					Push(ms_mc,YuShu);
					num = num / 8;
				}
				//cout<<GetStackLength(ms_mc)<<endl;debug正常 
				break;
			case 3:
				while(num != 0){
					int YuShu = num % 16;
					if(YuShu <10){
						Push(ms_mc,YuShu);
					}
					else{
						if(YuShu == 10) Push(ms_mc,65);
						if(YuShu == 11) Push(ms_mc,66);
						if(YuShu == 12) Push(ms_mc,67);
						if(YuShu == 13) Push(ms_mc,68);
						if(YuShu == 14) Push(ms_mc,69);
						if(YuShu == 15) Push(ms_mc,70);
						
					}
					
					num = num / 16;
				}
				//cout<<GetStackLength(ms_mc)<<endl;debug正常 
				break;
		}
	}

三、程序截图

在这里插入图片描述

四、实验结果运用

复习了增、删受限的线性表栈的相关操作，规范了函数返回值类型的书写
练习了压栈、出栈、进制转换相应功能
对于进制转化，特别是10进制—》16进制，需要对压栈的元素进行处理，因为顺序栈只能存放数据类型相同的数据，因此把字母直接压进栈是不现实的，只能压进字母对应的ASCII码，当打印的时候，强制类型转换一直不成功，出现乱码等问题(但是在另一语句，char(65)确实能得到A)，因此需要switch（出栈的元素值）,在case语句中完成ASCII码向字母的转换打印
进制转化栈使用完毕需要销毁，防止内存泄露