中国石油大学数据结构上机实验3

《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.4.3一、实验题目实验3顺序栈基本操作二、实验目的1.熟练掌握顺序栈的实现和基本操作2.理解栈后进先出的特点3.熟练应用顺序栈解决实际问题三、算法设计分析（一）数据结构的定义数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：①初始化并建立一个新栈表函数②栈清空函数③栈判断是否为空函数④进栈函数⑤出栈函数⑥取栈顶元素函数⑦输出栈元素函数⑧计算栈中元素个数函数⑨销毁栈函数（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）①初始化并建立一个新栈表SqStack*InitStack(SqStack*s){inti;s=(SqStack*)malloc(sizeof(SqStack));s-top=-1;printf(输入顺序栈元素（以0结束）：\n);scanf(%d,&i);do{s-top++;//栈顶指针增加一s-data[s-top]=i;//将新插入元素赋值给栈顶空间scanf(%d,&i);while(i!=0);printf(成功\n);returns;}②栈清空函数voidSetNULL(SqStack*s){//清空栈s-top=-1;//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1}③栈判断是否为空函数intEMPTY(SqStack*s){//判断栈空if(s-top=0)return0;elsereturn1;}④进栈函数SqStack*Push(SqStack*s){//进栈inta;printf(插入数字：);scanf(%d,&a);if(s-top==maxsize-1)//判断是否栈满{printf(overflow);//溢出returnNULL;}else{s-top++;//栈顶指针增加1s-data[s-top]=a;//将新插入元素赋值给栈顶空间}returns;}⑤出栈函数SqStack*Pop(SqStack*s){//出栈if(s-top==-1)//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1{printf(underlow);returns;}else{s-top--;//栈顶指针减一printf(删除的栈顶元素：);printf(%d\n,(s-data[s-top+1]));//若栈不为空，则删除s的栈顶元素}returns;}⑥取栈顶元素函数voidGetTop(SqStack*s){//取栈顶if(s-top==-1){printf(SqStackisempty);//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1}else{printf(当前栈顶元素是：);printf(%d\n,(s-data[s-top]));//取栈顶元素地址}}⑦输出栈元素函数voidprint(SqStack*s){//输出栈inti=0;if(s-top==-1){printf(成功！);}while(i=s-top){//遍历栈中所有元素printf(%d,s-data[i]);i++;}}⑧计算栈中元素个数函数voidCount(SqStack*s){//计算栈中元素inti=0;while(i=s-top){i++;}printf(个数为%d,i);}⑨销毁栈函数intDestroyStack_Sq(SqStack*s){//销毁一个顺序栈Sfree(s);s=NULL;return1;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目所要求的插入，删除，查找等基本操作。五、实验总结附录实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#includestring.h#definemaxsize64typedefintdatatype;typedefstruct{//定义结构体datatypedata[maxsize];inttop;//栈顶指针intbase;//在构造之前和销毁之后，base的值为NULL}SqStack;SqStack*InitStack(SqStack*s){//初始化并建立一个新栈表inti;s=(SqStack*)malloc(sizeof(SqStack));s-top=-1;printf(输入顺序栈元素（以0结束）：\n);scanf(%d,&i);do{s-top++;//栈顶指针增加一s-data[s-top]=i;//将新插入元素赋值给栈顶空间scanf(%d,&i);while(i!=0);printf(成功\n);returns;}voidSetNULL(SqStack*s){//清空栈s-top=-1;//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1}intEMPTY(SqStack*s){//判断栈空if(s-top=0)return0;elsereturn1;}SqStack*Push(SqStack*s){//进栈inta;printf(插入数字：);scanf(%d,&a);if(s-top==maxsize-1)//判断是否栈满{printf(overflow);//溢出returnNULL;}else{s-top++;//栈顶指针增加1s-data[s-top]=a;//将新插入元素赋值给栈顶空间}returns;}SqStack*Pop(SqStack*s){//出栈if(s-top==-1)//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1{printf(underlow);returns;}else{s-top--;//栈顶指针减一printf(删除的栈顶元素：);printf(%d\n,(s-data[s-top+1]));//若栈不为空，则删除s的栈顶元素}returns;}voidGetTop(SqStack*s){//取栈顶if(s-top==-1){printf(SqStackisempty);//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1}else{printf(当前栈顶元素是：);printf(%d\n,(s-data[s-top]));//取栈顶元素地址}}voidprint(SqStack*s){//输出栈inti=0;if(s-top==-1){printf(成功！);}while(i=s-top){//遍历栈中所有元素printf(%d,s-data[i]);i++;}}voidCount(SqStack*s){//计算栈中元素inti=0;while(i=s-top){i++;}printf(个数为%d,i);}intDestroyStack_Sq(SqStack*s){//销毁一个顺序栈Sfree(s);s=NULL;return1;}intmain(){SqStack*s;inti;printf(1.建立一个顺序栈\n);printf(2.输出栈\n);printf(3.进栈\n);printf(4.退栈\n);printf(5.取栈顶元素\n);printf(6.清空栈\n);printf(7.栈元素个数\n);printf(8.销毁栈\n);printf(9.退出\n);do{printf(\n\n选择功能：);scanf(%d,&i);switch(i){case1:s=InitStack(s);//建立一个顺序栈break;case2:print(s);//输出栈printf(\n);break;case3:s=Push(s);//进栈print(s);printf(\n);break;case4:s=Pop(s);//退栈print(s);printf(\n);break;case5:GetTop(s);//取栈顶元素break;case6:SetNULL(s);//清空栈print(s);printf(\n);break;case7:Count(s);//输出栈个数break;case8:DestroyStack_Sq(s);//销毁栈，并退出break;case9:exit(0);break;}}while(1);return0;}