数据结构实验三栈和队列及其应用
实验编号：3四川师大《数据结构》实验报告2016年10月29日
实验三栈和队列及其应用_
一．实验目的及要求
（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；
（2）本实验训练的要点是“栈”的观点及其典型用法；
（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。
二．实验内容
（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；
（2）应用栈的基本操作，实现数制转换（任意进制）；
（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；
（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。
（5）利用栈实现表达式的求值。
注：（1）～（3）必做，（4）～（5）选做。
三．主要仪器设备及软件
（1）PC机
（2）Dev C++ ,Visual C++, VS2010等
四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；
A.顺序储存：
?代码部分：
//Main.cpp:
#include"SStack.h"
int main()
{
SqStack S;
SElemType e;
int elect=1;
InitStack(S);
cout << "已经创建一个存放字符型的栈" << endl;
while (elect)
{
Muse();
cin >> elect;
cout << endl;
switch (elect)
{
case 1:
cout << "input data:";
cin >> e;
Push(S, e);
break;
case 2:
if(Pop(S, e))
{cout << e <<" is pop"<< endl; }
else{cout<<"blank"< break; case 3: if (StackEmpty(S)) { cout << "栈空" << endl; } else { cout << "栈未空" << endl; } break; case 4: GetTop(S, e); cout << "e is " << e << endl; break; case 5: StackLength(S); break; case 0:break; } } DestroyStack(S); return OK; } //SStack.cpp: #include"SStack.h" //输出菜单 void Muse() { cout << "请选择功能：" << endl; cout << " 1.入栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } //创建栈 Status InitStack(SqStack &S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(ERROR); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } //得到顶部数据 Status GetTop(SqStack S, SElemType &e) { if (S.base == S.top) return ERROR; e = *(S.top - 1); return OK; } //入栈 Status Push(SqStack &S, SElemType &e) { if (S.top - S.base >= STACK_INIT_SIZE) { S.base = (SElemType *)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(ERROR); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } //出栈 Status Pop(SqStack &S, SElemType &e) { if (S.base == S.top) { return ERROR; } e = *--S.top; cout<<"pop succeed"< return OK; } //判栈空 Status StackEmpty(SqStack S) { if (S.top == S.base) { return ERROR; } return OK; } //销毁栈 Status DestroyStack(SqStack &S) { free(S.base); S.top=NULL; S.stacksize = 0; cout << "栈已销毁" << endl; return OK; } int StackLength(SqStack S) { cout << "StackLength is "< return OK; } //SStack.h: #include #include using namespace std; const int STACK_INIT_SIZE = 100; const int STACKINCREMENT = 10; const int ERROR = 0; const int OK = 1; typedef char SElemType; typedef int Status; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack &S);//创建顺序存储的栈 Status GetTop(SqStack S, SElemType &e);//得到栈顶数据Status Push(SqStack &S, SElemType &e);//入栈 Status Pop(SqStack &S, SElemType &e);//出栈 void Muse();//输出菜单界面 Status StackEmpty(SqStack S);//判断栈是否为空 Status DestroyStack(SqStack &S);//销毁栈 int StackLength(SqStack S);//计算栈的长度 ?运行结果： B. 链式储存： ?代码部分： //Main.cpp #include"Lstack.h" int main(){ Lq_Stack L; if(InintStack (L)){ cout<<"build stack succeed"< } else exit (ERROR); int e=0; Menu(L,e); DestroyStack(L); return 0; } //Lstack.cpp #include"Lstack.h" Status InintStack(Lq_Stack &L){ //创建栈 L=(LqStack *)malloc(sizeof(LqStack)); if(!L) exit(ERROR); L->data=0; L->next=NULL; return OK; } Status push (Lq_Stack &L,SElemType e){ //入栈 LqStack *p; p=(LqStack *)malloc(sizeof(LqStack)); if(!p) exit(ERROR); p->data=e; L->data++; p->next=L->next; L->next=p; return OK; Status pop (Lq_Stack &L,SElemType &e){ //出栈 LqStack *p; if(L->next==NULL) return ERROR; p=L->next; e=p->data; L->next=p->next; L->data--; free(p); return OK; } Status GetTop(Lq_Stack L, SElemType &e){ //得到栈顶数据 if(L->next==NULL) return ERROR; e=L->next->data; return OK; } Status StackEmpty(Lq_Stack L){ //判断栈是否为空 if(L->next==NULL){return ERROR;} else return OK; int StackLength(Lq_Stack L){ //计算栈的长度 return L->data; } Status DestroyStack(Lq_Stack &L){ //销毁栈 LqStack *p; while(!L) { L=p; L=L->next; free(p); } return OK; } void Menu(Lq_Stack &L,SElemType e){ //输出菜单选择执行的功能 int select=1; while(select) { cout<<"————————————"< cout<<"请选择功能"< cout<<"——————1.入栈"< cout<<"——————2.出栈"< cout<<"——————3.得到顶部数据"< cout<<"你的选择是："; cin>>select; switch (select){ case 0:break; case 1: cout<<"push data:"; cin>>e; if(push(L,e)){ cout<<"push succeed"< } else cout<<"push failed"< break; case 2: if(pop(L,e)){ cout<<"data "< else cout<<"pop failed"< break; case 3: if(GetTop(L,e)){ cout<<"head data "< else cout<<"Get failed"< break; case 4: if(StackEmpty(L)){ cout<<"stack is not NULL"< else cout<<"stack is NULL"< break; case 5: cout<<"this stack length is "< break; } } } //Lstack.h #include #include using namespace std; const int OK=1; const int ERROR=0; typedef int SElemType; typedef int Status; typedef struct LqStack{ SElemType data; struct LqStack *next; }LqStack,*Lq_Stack; Status InintStack (Lq_Stack &L);//创建栈 Status push (Lq_Stack &L,SElemType e);//入栈 Status pop (Lq_Stack &L,SElemType &e);//出栈 Status GetTop(Lq_Stack L, SElemType &e);//得到栈顶数据 Status StackEmpty(Lq_Stack L);//判断栈是否为空 int StackLength(Lq_Stack L);//计算栈的长度 Status DestroyStack(Lq_Stack &L);//销毁栈 void Menu(Lq_Stack &L,SElemType e);//输出菜单选择执行的功能?运行结果： （2）应用栈的基本操作，实现数制转换（任意进制）；；?代码部分： //Main.cpp #include"SStack.h" int main(){ int number; cout<<"要将数值转换为多少进制"; cin>>number; conversion(number); return 0; } SStack.cpp #include"SStack.h" Status InitStack(SStack &S){ //创建栈 S.dase=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.dase) exit(ERROR); S.top=S.dase; S.stacksize=STACK_INIT_SIZE; return OK; } Status push(SStack &S,ElemType e){ //入栈 if(S.top-S.dase >= S.stacksize){//栈满追加空间 S.dase=(ElemType *)realloc(S.dase, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(ElemType)); if(!S.dase) exit(ERROR); S.top=S.dase+STACK_INIT_SIZE; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status pop(SStack &S,ElemType &e){ //出栈 if(S.top== S.dase) return ERROR; e=*--S.top; return OK; } Status StackEmpty(SStack &S){ //判断栈是否为空 if(S.dase==S.top) return ERROR; return OK; } void conversion(int number){ //转换为e进制并输出 SStack S; int N,e; if(InitStack(S)){ cout<<"栈创建成功"< } cout<<"输入待转换的数："; cin>>N; while(N){ push(S,N%number); N=N/number; } while(StackEmpty(S)){ pop(S,e); cout< } cout< } //SStack.h #ifndef SSTACK_H #define SSTACK_H #include #include using namespace std; const int STACK_INIT_SIZE=100; const int STACKINCREMENT=10; const int OK=1; const int ERROR=0; typedef int Status; typedef int ElemType; typedef struct { ElemType *dase; ElemType *top; int stacksize; }SStack; Status InitStack(SStack &S);//创建栈 Status push(SStack &S,ElemType e);//入栈 Status push(SStack &S,ElemType &e);//出栈 Status StackEmpty(SStack &S);//判断栈是否为空 void conversion(int number);//转换为number进制并输出 #endif ?运行结果： （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）。 ?代码部分： A:链式储存： //Main.cpp: #include"QNode.h" int main(){ LinkQueue Q; 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 实验三栈和队列的应用 1、实验目的 （1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。 （2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； （3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现 （1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。 （2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用 （1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。 提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为0重复做下列动作 将x%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。 (3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。 （4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤 （1）理解栈的基本工作原理； （2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法； （4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。 4、实验帮助 算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X % R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 5、算法描述 （1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */ 实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________ 一、实验内容： 本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用，其中包含优先级的判断。 二、设计思想 1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先 级 2.优先级关系用“>”“<”“=”来表示三种关系 3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作 符栈 4.运用入栈出栈优先级比较等方式完成运算 三、主要算法框架 1.建立两个栈InitStack(&OPTR); InitStack(&OPND); 2.Push“#”到 OPTR 3.判断优先级做入栈出栈操作 If“<” Push(&OPTR, c); If“=” Pop(&OPTR, &x) If“>” Pop(&OPTR, &theta); Pop(&OPND, &b); Pop(&OPND, &a); Push(&OPND, Operate(a, theta, b)); 四、调试报告 遇到的问题与解决 1.C语言不支持取地址符，用*S代替&S来编写代码 2.一开始没有计算多位数的功能只能计算一位数，在几个中间 不含运算符的数字中间做p = p*10+c运算。代码如下：p = p * 10 + c - '0'; c = getchar(); if (In(c)) { Push(&OPND, p); p = 0; } 主要算法改进设想： 1.可以用数组储存优先级 2.可以用C++编写，C++支持取地址符&。 五、实验总结 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 1、顺序栈： 2、链栈： 3、循环队列： 4、链队 三、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include }SqStack; int InitStack(SqStack *S); /*构造空栈*/ int push(SqStack *S,ElemType e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/ void PrintStack(SqStack *S); /*出栈并输出栈中元素*/ int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int Push(SqStack *S,ElemType e){ }/*Push*/ int Pop(SqStack *S,ElemType *e){ }/*Pop*/ } /*CreateStack*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\n"); else { printf("Init Fail!\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e)) Push(S,e); 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 内容： 把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。 【思考问题】 1.栈的顺序存储和链表存储的差异？ 2.还会有数据移动吗？为什么？ 3.栈的主要特点是什么？队列呢？ 4.栈的主要功能是什么？队列呢？ 5.为什么会有环状队列？ 【参考代码】 （一）利用顺序栈实现十进制整数转换转换成r进制 1、算法思想 将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下： N N / 8 （整除）N % 8（求余） 3456 432 0 低 432 54 0 54 6 6 6 0 6 高 所以：（3456）10 =（6600）8 我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 算法思想如下：当N>0时重复1，2 ①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替N 2、转换子程序 第三章栈和队列的应用 【实验目的】 1．熟练掌握栈和队列的结构，以及这两种数据结构的特点； 2．能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； 3．熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； 第一节知识准备 一、栈： 1. 基本概念 栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。 由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出 （Last In First Out）的线性表，简称LIFO表。 栈示意图见图3-1 2. 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作： InitStack(&S) 构造一个空栈S StackEmpty(S) 判断栈S是否为空 StackLength(S) 返回栈S的元素个数,即栈的长度 GetTop(S,&e) 取栈S的栈顶元素 Push(&S,e) 将元素e入栈 Pop(&S,&e) 删除S的栈顶元素并用e返回其值（即出栈） }ADT Stack 3. 栈的表示： 栈有两种存储表示方法：顺序存储结构和链式存储结构。 (1)顺序存储结构： #define STACK_INIT_SIZE 100； //存储空间初始分配量 #define STACKINCREMENT 10； //存储空间分配增量 typedef struct{ SElemType *base； //栈底指针 SElemType *top； //栈顶指针 int StackSize； //栈的当前容量 }SqStack； (2)链式存储结构： Typedef struct Lnode{ ElemType data; struct Lnode *next; }Lnode, *LinkList; 二、队列： 1. 与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2：────────────── 出队←a1 a2 …… an-1 ←an进队 ────────────── 队头队尾 图3-2 队列 2. 队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作： InitQueue(&Q) 构造一个空队列Q 实验二栈与队列操作 实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。 本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立顺序栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）将栈顶元素出栈。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立带头结点的链栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）完成出栈操作。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 （7）输出链栈的长度。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。 （2）从键盘输入1个元素，执行入队操作，并显示结果。 （3）将队头元素出队，并显示结果。 （4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。 （2）编写带头结点的循环链表的初始化函数，只用尾指针表示。 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。 （2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题 实验三栈和队列的操作 一.实验目的和要求 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用栈和队列的各种操作来进行具体的实际应用。 3、加强综合程序的分析、设计能力。 二.实验内容 课后习题4-7 三.实验步骤 1、定义一个函数void QInsert(LNode*&Rear,const ElemType& item)，新建一个结点，如果尾指针为空，则指向新建的结点；否则新结点指向尾指针当前指向的结点，然后尾指针指向新结点，最后新结点成为尾指针。 2、定义一个函数ElemType QDelete(LNode*&Rear)，若删除的是最后一个结点，则删除后尾指针为NULL，尾指针指向被删除结点的后继。 3、定义函数void Print(LNode*&Rear)输出队列，从第一个结点开始依次输出，第一个结点就是尾指针指向的结点。 注意：定义文件后缀为.cpp，头文件为 实验三：栈和队列 程序代码： （1）：栈 #include if(p==NULL) { printf("There is no bumber\n"); return; } printf("The remaining numbers are:\n"); while(p!=NULL) { printf("%4d",p->data); p=p->next; } } int pops(node_type **top) { node_type *p; int x; if((*top)==NULL) { printf("error\n"); return 0; } else { x=(*top)->data; printf("\n%d\n",x); p=(*top); (*top)=(*top)->next; return(x); free(p); } } void main() { node_type *h=NULL; pushs(&h); printlst(&h); printf("\nPop a number\n"); pops(&h); printlst(&h); printf("\nPop a number\n"); pops(&h); printlst(&h); } （2）：队列 《数据结构》课程实验实验报告三 第三章栈和队列的操作 实验题目：实验三栈和队列的操作 学号：11416106 班级：计算机111 姓名：张婷指导教师：游静 实验完成时间：2013.4.22 实验成绩： 实验三栈和队列的操作 一、实验学时 2学时 二、背景知识 1.栈: (1).入栈和进栈操作只能从栈顶一端进行; (2).LIFO(后进先出); (3).栈的两种存储定义:顺序栈和链式栈。 2.队列: (1).入队操作从队尾进行,出队操作从对头进行; (2).FIFO(先进先出); (3).队列的两种存储定义:顺序队和链队。 三、目的要求 1．掌握栈的顺序表示和实现。 Typedef struct{ SelemType *base; SelemType *base; Int stacksize; }sqstack; 2．掌握队列的链式表示和实现以及顺序表示和实现。 链队列： Typedef struct Qnode{ QelemType data; struct Qnode *next; } Qnode,*Queueptr; Typedef struct{ Queueptr front; Queueptr rear; }linkQueue; 顺序队列: #define MAXQSIZE 100 Typedef struct{ Qelemtype *base; int front; int rear; }sqQueue; 四、实验内容 1．顺序栈和循环队列的创建、入栈（队）、出栈（队）等基本操作。 2．数制转换问题 【问题描述】 十进制数N和其它d进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 【基本要求】 首先初始化一个顺序栈，通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例：顺序队列的入队和出队操作。 栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11 01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++; k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。 实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：2011-4-13，星期三，3，4节10：10—11：50； 地点：信息学院实验中心，弘毅楼D406、407。 班级：信息091-3第一和第二小组； 二、实验内容 【实验目的】 深入理解栈和队列的特性，领会它的应用背景。熟练掌握在不同存储结构、不同的约定中，其基本操作的实现方法与差异。并体会以下几点（注意你所做的约定）： 1、顺序栈（初始化、栈空/栈满条件，入栈/出栈）； 2、链栈（初始化、栈空条件，入栈/出栈）； 3、顺序队列 4、链队列 【实验选题】 选题一、栈的基本操作的实现（1人/组） 实验1要求 1．会定义顺序栈和链栈的结点类型。 2．掌握栈的插入和删除结点在操作上的特点。 3．熟悉对栈的一些基本操作和具体的函数定义。 具体内容 程序1 该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。 选题二、队列基本操作的实现（1人/组） 实验2要求 4．会定义顺序队列和链队的结点类型。 5．掌握队列的插入和删除结点在操作上的特点。 6．熟悉对队列的一些基本操作和具体的函数定义。 具体内容 程序1：链队列表示和实现 程序2：队列运算在顺序存储结构上的实现 假定采用Queue记录类型的对象Q来表示顺序存储的队列，则在Q上进行各种队列运算 三、实验过程要求 1、分组形式：学生自行分组，每组3人，汇总到课代表处，课代表在本周末前mail告 诉我； 2、组内分工与协作： 1）同一小组的同学在上机前讨论确定问题可以采用的数据结构、流程的安排、模块的划分等，共同完成上机前的准备工作，并对要编制的代码进行分工； 实验报告三栈和队列 一、实验目的： （1）掌握栈的基本操作的实现方法。 （2）利用栈先进后出的特点，解决一些实际问题。 （3）掌握链式队列及循环队列的基本操作算法。 （4）应用队列先进先出的特点，解决一些实际问题。 二、实验内容： 1、使用一个栈，将一个十进制转换成二进制。 粘贴源程序： package Q1; public class SeqStack { public int element[]; public int top; public static SeqStack p; public SeqStack(int size){ this.element=new int[size]; this.top=-1; } public void push(int x){ this.top++; this.element[this.top]=x; } public int pop(){ return this.top==-1 ? -1: (int)this.element[this.top--]; } public int get(){ return this.top==-1 ? -1: (int)this.element[this.top]; } public static void disp(SeqStack p){ int t = -2; while(t!=-1){ t=p.pop(); if(t!=-1) System.out.printf("%d",t); } } public static void fun(int x){ int t; while(x!=1){ t=x%2; x=x/2; p.push(t); } if(x==1) 数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的 1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include 《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验二栈和队列的基本操作。 实验目的 1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。 2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。 实验内容 题目1： 进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数 算法提示： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X%R入栈X=X/R 只要栈不为空重复做下列动作 栈顶出栈输出栈顶元素 题目2： 利用队列的方式实现杨辉三角的输出。 算法设计分析 （一）数据结构的定义 1、栈的应用 实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。 栈抽象数据结构描述 typedef struct SqStack /*定义顺序栈*/ { int *base; /*栈底指针*/ int *top; /*栈顶指针*/ int stacksize; /*当前已分配存储空间*/ } SqStack; 2、队列的应用 由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成杨辉三角的递归性。即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造杨辉三角的第N+1行，从而实现打印杨辉三角的目的。 队列抽象数据结构描述 typedef struct SeqQueue { int data[MAXSIZE]; int front; /*队头指针*/ int rear; /*队尾指针*/ }SeqQueue; （二）总体设计 1、栈 （1）主函数：统筹调用各个函数以实现相应功能 int main() （2）空栈建立函数：对栈进行初始化。 int StackInit(SqStack *s) （3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出杨辉三角函数：按一定格式输出杨辉三角。 void YangHui(int n) （三）各函数的详细设计： 1、栈 （1）int main()主函数 定义s为栈类型 调用函数建立空栈 栈和队列基本操作实验报告 实验二堆栈和队列基本操作的编程实现【实验目的】 堆栈和队列基本操作的编程实现 要求: 堆栈和队列基本操作的编程实现(2学时，验证型)，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验(学时数:2H) 【实验内容】 内容: 把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。【实验分析、说明过程】 分析: 进栈操作 先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下: 将新结点p的指针域指向原栈顶S(执行语句p->next=S)。 将栈顶S指向新结点p(执行语句S=p)。 注:进栈操作的?与?语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。 出栈操作 先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下: 结点p 指针域指向原栈顶S(执行语句p=S)。 栈顶S指向其的下一个结点(执行语句S=S->next) 释放p结点空间(执行语句free(p))。 队列分析:用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。 【思考问题】 1. 栈的顺序存储和链表存储的差异, 答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。数据结构_实验三_栈和队列及其应用
实验三 栈和队列的应用
数据结构实验二-栈和队列的基本操作与应用
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
实验二 栈和队列
实验二栈队列的实现及应用
实验二 堆栈和队列基本操作的编程实现
数据结构实验三栈和队列的应用
实验二 栈与队列操作实验题目
实验三 栈和队列的操作
栈和队列实验报告
实验三 栈和队列
栈和队列综合实验报告
实验二栈和队列基本操作与应用
实验三 栈和队列
栈和队列及其应用实验报告
栈和队列的基本操作讲解
栈和队列基本操作实验报告
- 数据结构实验 栈和队列
- 数据结构实验报告栈和队列迷宫图最短路径
- 实验二栈队列的实现及应用
- 数据结构实验三栈和队列及其应用
- 数据结构实验三栈和队列
- 栈的操作(实验报告)
- 大数据结构_实验三_栈和队列及其应用
- 数据结构栈和队列实验报告
- 实验报告(栈和队列)
- 实验三栈和队列及其应用(I)讲解
- 2数据结构实验报告二(栈和队列及其应用)
- 数据结构堆栈与队列实验报告
- 实验三 栈和队列
- 数据结构_实验三_栈和队列及其应用
- 数据结构实验3栈和队列
- 实验三 栈和队列的定义及基本操作1
- 实验二 堆栈和队列基本操作的编程实现
- 栈和队列基本操作实验报告
- 实验二 栈和队列(基本操作)
- 2数据结构实验报告二(栈和队列及其应用)