一. 实验要求 用顺序存储结构，实现栈的基本操作，提供数制转换功能，将输入的十进制整数转换成二进制。 二. 实验目的 通过该实验，掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。 三. 设计思想
首先声明全局变量checkStatus用于判断栈是否创建，定义栈的顺序存储表示，定义ElemType类型的栈顶指针top，栈底指向base和栈的元素数量stacksize初始化为空栈，先申请存储空间，如果S.base不为空，让S.top=S.base，表示初始化为一个空栈，S.stacksize=STACK_INIT_SIZE表示栈S的空间大小为栈的初始空间大小。销毁栈，清除空间，归零数据，清零长度，则销毁成功。将栈置空，直接令S.top=S.base，表示栈空。判断栈是否为空栈，用if语句判断S.top==S.base是否成立，如果成立，则栈为空；否则，则栈不为空。返回栈的长度，栈的长度length=S.top-S.base。求栈顶元素，先判断栈是否为空：if(S.top==S.base){ cout<<"栈为空，没有栈顶元素！"<<endl; }。S.top指向最后一个元素的下一个位置，所以直接返回e=*(S.top-1)即为栈顶元素的值。插入元素,并使其成为栈顶元素，要先判断栈是否满：if((S.top-S.base)>=S.stacksize)，如果栈满，要追加存储空间。否则，令*(S.top)=e; S.top++;即可。删除栈顶元素,并返回其值，先判断栈是否为空：if(S.top==S.base){ cout<<"栈为空，没有栈顶元素！"<<endl; }。若栈不为空，则执行S.top—即删除了栈顶元素，返回e=*(S.top)即为删除前栈顶元素的值。输出栈内元素，先判断栈是否为空：if(S.top==S.base){ cout<<"栈为空，没有栈顶元素！"<<endl; }。若栈不为空，则申请一个新的栈p，让p=S，对栈p中的元素进行while循环输出：while(p.top!=p.base){ p.top--; cout<<*(p.top)<<endl; }。即输出完毕。创建并输入栈元素，先给栈S申请内存空间，然后让用户在键盘输入要输入栈内的元素个数n，利用for循环循环输入栈元素e：for(int i=1;i<=n;i++)｛cin>>e; *(S.top)=e; S.top++;｝。十进制转换为二进制，先初始化一个栈L，然后在键盘输入一个十进制数n。用while循环将n转换成二进制插入栈L中：令i等于n/2的余数，然后让i入栈L中*(L.top)=i，L.top++，再令n等于n/2的整数部分，直到n为0。然后用while循环输出栈L即可：while(L.top!=L.base)｛L.top--; e=*(L.top); cout<<e;｝，输出的即为n的二进制数。四. 主要源代码
#include "iostream" using namespace std; int checkStatus=0; typedef int ElemType; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { ElemType *top; ElemType *base; int stacksize; }SqStack; static SqStack S; void selectFunc(int _select); void InitStack(SqStack &S); void DestroyStack(SqStack &S); void ClearStack(SqStack &S); void StackEmpty(SqStack &S); void GetLen(SqStack &S); void GetTop(SqStack &S); void Push(SqStack &S); void Pop(SqStack &S); void PrintStack(SqStack &S); void CreateStack(SqStack &S); void Convert(); void main() { cout<<"***************************************************************"<<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<<"**************** 11.退出 ****************"<<endl; cout<<"**************** 12.进制转换 ****************"<<endl; cout<<"***************************************************************"<<endl; int _select; while(1) { cout<<"请输入功能前面的数字代号："; cin>>_select; if(!cin || _select==0 || _select>12) { cout<<"您输入的选项有误，请重新输入！"<<endl; cin.clear(); cin.sync(); continue; } else { if(_select<0) { exit(1); } else { selectFunc(_select); } } cout<<endl; } system("pause"); } void selectFunc(int _select) { switch(_select) { case 1: { InitStack(S); checkStatus=1; break; } case 2: { if(checkStatus==1) { DestroyStack(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 3: { if(checkStatus==1) { ClearStack(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 4: { if(checkStatus==1) { StackEmpty(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 5: { if(checkStatus==1) { GetLen(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 6: { if(checkStatus==1) { GetTop(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 7: { if(checkStatus==1) { Push(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 8: { if(checkStatus==1) { Pop(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 9: { if(checkStatus==1) { PrintStack(S); } else { checkStatus=0; cout<<"尚未初始化栈，请先初始化!"<<endl; } break; } case 10: { CreateStack(S); checkStatus=1; break; } case 11: { ClearStack(S); DestroyStack(S); exit(1); break; } case 12: { Convert(); break; } default: { cout<<"输入不合法，请重新输入！"<<endl; break; } } } void InitStack(SqStack &S) { S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) { cout<<"存储空间分配失败！"<<endl; } else { S.top=S.base; S.stacksize=STACK_INIT_SIZE; cout<<"初始化空栈成功！"<<endl; } } void DestroyStack(SqStack &S) { free(S.base); S.top=NULL; S.base=NULL; S.stacksize=0; cout<<"销毁栈成功！"<<endl; } void ClearStack(SqStack &S) { S.top=S.base; cout<<"栈置空成功！"<<endl; } void StackEmpty(SqStack &S) { if(S.top==S.base) { cout<<"栈为空！"<<endl; } else { cout<<"栈不为空！"<<endl; } } void GetLen(SqStack &S) { int length=0; length=S.top-S.base; cout<<"栈的长度为"<<length<<endl; } void GetTop(SqStack &S) { ElemType e; if(S.top==S.base) { cout<<"栈为空，没有栈顶元素！"<<endl; } else { e=*(S.top-1); cout<<"栈顶元素为"<<e<<endl; } } void Push(SqStack &S) { ElemType e; cout<<"请输入要插入的元素："; cin>>e; if((S.top-S.base)>=S.stacksize) { S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) { cout<<"栈满，且追加存储空间失败！"<<endl; } else { S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } } *(S.top)=e; S.top++; cout<<"插入成功！"<<endl; } void Pop(SqStack &S) { ElemType e; if(S.top==S.base) { cout<<"栈为空，无法删除！"<<endl; } else { S.top--; e=*(S.top); cout<<"删除成功，删除的元素为"<<e<<endl; } } void PrintStack(SqStack &S) { if(S.top==S.base) { cout<<"栈为空！"<<endl; } else { cout<<"栈内元素为："<<endl; SqStack p; p=S; while(p.top!=p.base) { p.top--; cout<<*(p.top)<<endl; } } } void CreateStack(SqStack &S) { int n; ElemType e; S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); S.top=S.base; S.stacksize=STACK_INIT_SIZE; cout<<"请输入栈内元素个数："; cin>>n; cout<<"请输入栈元素："; for(int i=1;i<=n;i++) { cin>>e; *(S.top)=e; S.top++; } cout<<"栈初始化并添加数据成功！"<<endl; } void Convert() { SqStack L; L.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); L.top=L.base; L.stacksize=STACK_INIT_SIZE; int n; cout<<"请输入一个十进制数："; cin>>n; while(n) { int i=n%2; *(L.top)=i; L.top++; n=n/2; } cout<<"其二进制为："; int e; while(L.top!=L.base) { L.top--; e=*(L.top); cout<<e; } cout<<endl; }五. 调试与测试数据
