班级 学号 姓名 实验组别
实验日期 2010/12/20 室温 报告日期 2010/12/20 成绩 报告内容：(目的和要求，原理，步骤，数据，计算，小结等) 实验名称： 实验二 栈的表示及实现
一、实验目的：
1. 通过实验进一步理解栈的后进先出特性。
2. 掌握栈的逻辑结构，以及顺序存储结构和链式存储结构。 3. 熟练运用C语言实现栈的基本操作。 4. 灵活运用栈解决实际问题。
二、实验内容：
已知学生数据元素的数据类型如下： Struct Student{ Int ID;
Char name[10]; };
1. 设计4个学生数据，学号分别为10,20,30和40,并把这些数据依次
入顺序栈，然后出栈并在屏幕上显示出来
2. 入栈两个学生数据，然后出栈一个学生数据。再次入栈两个学生数
据，然后出栈3个学生数据，并与（1）的结果进行比较 3. 如何操作才能得到“20、40、30、10”的结果。
4. 使用与（1）同样的学生数据，并把这些数据依次入链栈，然后出栈
并在屏幕上显示出来，与（1）的结果进行比较看是否一样。 5. 请设计一个能够测试栈空和栈满的实验。
三、实验学时：2学时
四、实验涉及知识点：
1. 栈是限定在栈顶插入和删除元素的线性表，栈的存储方法也可以是
顺序的和链式的，其数据遵循“先进后出，后进先出”的原则； 2. 栈的抽象数据类型表示了栈中的数据元素，数据元素间的逻辑关系，
以及对栈的操作集合。；
3. 对栈的基本操作包括初始化、求栈长、入栈、出栈、取栈顶元素、
第 页
附 页
判断栈是否为空、清空栈和销毁栈等；
五、程序流程分析
根据实验内容要求和书上对栈的基本操作的算法即可画出本次实验程序的流程图，对顺序栈和链式栈的操作的实验流程图基本相同，如下：
初始化栈及所用数据出栈一个数据并显示将数据入栈入栈其他的数据N依次出栈所有数据并输出显示入栈完成？Y依次出栈所有数据并输出显示判断栈是否为空入栈前两个数据判断栈是否为满 图1.顺序栈操作流程图
而对于链式栈的操作，与顺序栈的操作流程唯一不同的一点是，没有最后一项“判断栈是否为满”，其他都与上述图1所示流程图一致，具体如下所示：
第 页
附 页
初始化栈及所用数据出栈一个数据并显示将数据入栈入栈其他的数据N依次出栈所有数据并输出显示入栈完成？Y依次出栈所有数据并输出显示判断栈是否为空入栈前两个数据 图2.链式栈操作流程图 六、实验源程序：
对顺序栈和单链栈的基本操作都可以直接应用书中所给算法，包括初始化、判断栈空、入栈、出栈；这些基本操作的算法及数据类型可以先编写入一个头文件中，另外，次头文件中还包括两个书中没有的算法，即判断栈满的算法（可以用s.top是否等于stacksize-1来判断栈是否满）以及输出数据的算法，如下所示：
对顺序栈操作的头文件“shunxuzhan.h”为： #include int ID; //学号 第 页 附 页 char name[10]; //姓名 }datatype; typedef struct { datatype items[stacksize]; int top; }sqstack; int initstack(sqstack *s) { s->top=-1; return 1; } int stackempty(sqstack s) { if(s.top==-1) return 1; else return 0; } int stackfull(sqstack s) { if(s.top==stacksize-1) return 1; else return 0; } int push(sqstack *s,datatype e) { if(s->top>=stacksize-1) { printf(\"栈已满，不能完成入栈操作\\n\"); return 0; } s->top++; s->items[s->top]=e; return 1; 第 页 附 页 } int pop(sqstack *s,datatype *e) { if(s->top<=-1) { printf(\"堆栈已空，不能完成出栈操作!\\n\"); return 0; } *e=s->items[s->top]; s->top--; return 1; } void display(datatype s) { printf(\"Number:%d,Name:%s\\n\} 然后再在对顺序栈进行操作的主程序中先包含头文件“shunxuzhan.h” 该顺序栈的主程序为： #include 附 页 /*将N个学生信息依次入栈，入栈时不显示*/ { if(!push(&studata,stu[i])) { printf(\"插入数据错误!\\n\"); return 0; } } printf(\"第一种方式：\\n\"); while(!stackempty(studata)) //将学生信息全部出栈 { if(!pop(&studata,&temp)) { printf(\"出栈操作时错误!\\n\"); return 0; } display(temp); //出栈的同时输出学生信息 } printf(\"\\n第二种方式：\\n\"); push(&studata,stu[0]); push(&studata,stu[1]); //入栈两个学生数据 pop(&studata,&temp); display(temp); //出栈一个学生数据并输出 push(&studata,stu[2]); push(&studata,stu[3]); //再次入栈两个学生数据 pop(&studata,&temp); //出栈三个学生数据并显示 display(temp); pop(&studata,&temp); display(temp); pop(&studata,&temp); display(temp); /*得到20 40 30 10的结果的方法：也就是上面第二种方式*/ printf(\"\\n\"); if(stackempty(studata)) //测试栈是否为空 printf(\"所操作的栈此时为空\\n\"); else 第 页 附 页 printf(\"所操作的栈此时非空\\n\"); if(stackfull(studata)) //测试栈是否为满 printf(\"所操作的栈此时为满\\n\"); else printf(\"所操作的栈此时非满\\n\"); } 对于链式栈程序来说，与顺序栈程序的不同在于所包含的头文件不同，主程序中变量名与顺序表的程序中的变量名不同外，而其他都大致相同，只不过链式栈由于没有判断栈是否满的过程，所以主程序中没有顺序栈程序的最后四行。程序如下： 链式栈程序所包含的头文件： #include int ID; //学号 char name[10]; //姓名 }datatype; typedef struct snode { datatype data; struct snode *next; }snode,*linkstack; //带头结点的链栈 int initstack(linkstack *top) { *top=(linkstack)malloc(sizeof(snode)); if(*top==NULL) { printf(\"初始化链栈错误!\\n\"); return 0; } (*top)->next=NULL; return 1; 第 页 附 页 } int stackempty(linkstack top) { if(top->next==NULL) return 1; else return 0; } int push(linkstack top,datatype e) { snode *p; p=(snode*)malloc(sizeof(snode)); if(!p) { printf(\"入栈操作出错!\\n\"); return 0; } p->data=e; p->next=top->next; top->next=p; return 1; } int pop(linkstack top,datatype *e) { snode *p; if(!top->next) { printf(\"栈已空,不能完成出栈操作!\\n\"); return 0; } p=top->next; top->next=p->next; *e=p->data; free(p); return 1; } 第 页 附 页 void display(datatype s) { printf(\"Number:%d,Name:%s\\n\} 链式栈主程序中先包含头文件lianshizhan.h,主程序为： #include #include\"lianshizhan.h\" #define N 4 int main() { int i; datatype stu[N],temp; linkstack studata; //studata是包含学生信息的链栈的top int ID[N]={10,20,30,40}; char name[N][10]={\"Mary\ for(i=0;i strcpy(stu[i].name,name[i]); } initstack(&studata); for(i=0;i printf(\"插入数据错误!\\n\"); return 0; } } printf(\"第一种方式：\\n\"); while(!stackempty(studata)) //将学生信息全部出栈 第 页 附 页 { if(!pop(studata,&temp)) { printf(\"出栈操作时错误!\\n\"); return 0; } display(temp); //出栈的同时输出学生信息 } printf(\"\\n第二种方式：\\n\"); push(studata,stu[0]); push(studata,stu[1]); //入栈两个学生数据 pop(studata,&temp); display(temp); //出栈一个学生数据并输出 push(studata,stu[2]); push(studata,stu[3]); //再次入栈两个学生数据 pop(studata,&temp); //出栈三个学生数据并显示 display(temp); pop(studata,&temp); display(temp); pop(studata,&temp); display(temp); /*得到20 40 30 10的结果的方法：也就是上面第二种方式*/ printf(\"\\n\"); if(stackempty(studata)) //测试栈是否为空 printf(\"所操作的栈此时为空\\n\"); else printf(\"所操作的栈此时非空\\n\"); } 七、实验步骤 顺序表程序的实验步骤： 1. 进行Visual Studio开发环境； 2. 创建项目： 文件—新建—项目—WIN32项目—输入项目名称test3； 3. 创建头文件和源文件，将预先编制好的程序输入； 4. 保存文件； 第 页 附 页 5. 选择调试—开始调试。 对于链式栈的实验步骤，与上述步骤相同，只是项目名称为test4，头文件和源文件的名称和上述顺序表的不同，输入的程序不同而已。 此次对顺序栈和链式栈的调试过程，只要点击开始调试，无需数据输入，就可以看到屏幕上输出的程序的运行结果，将实际运行结果和实现前分析的预期结果进行对比，就可以验证程序的正确性。 结果如下： 顺序栈的程序的运行结果为： 图1.顺序栈的程序运行结果 链式栈的程序运行结果如下： 图2.链式栈的程序运行结果 第 页 附 页 八、实验小结 通过本题实验，让我再次感觉到了应用数据结构相关知识编写的程序的通用性，比如说对栈的插入，删除的操作，本次实验处理的是结构体类型的学生信息，应用数据结构的知识只需将程序中所处理的datatype定义成包含学生信息的结构体，那么其他的插入、删除等操作的算法就都可以应用了，而在学习数据结构这门课以前，编程时，对于不同类型的数据处理的方法就不太相同，算法也不那么通用，工作的重复性很大，而且需要考虑对不同的数据类型应该怎样去分别实现。是对时间和精力的极大浪费。由此我也看到了学习数据结构的深远意义。 第 页 因篇幅问题不能全部显示，请点此查看更多更全内容