数据结构_实验三_栈和队列及其应用
实验编号：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 "< break; case 3: if(GetTop(L,e)){ cout<<"head data "< 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; InitQueue(Q); Menu(Q); DestroyQueue(Q); return 0; } //QNode、cpp: #include"QNode、h" Status InitQueue(LinkQueue &Q){ //构造空队列 Q、front=Q、rear=(QueuePrt)malloc(sizeof(QNode)); if(!Q、front) exit (ERROR); Q、front->next=NULL; return OK; } Status DestroyQueue(LinkQueue &Q){ //销毁队列Q while(Q、front){ Q、rear=Q、front->next; free(Q、front); Q、front=Q、rear; } return OK; } Status EnQueue (LinkQueue &Q,QElemType e){ //插入元素a为Q得新得队尾元素 QNode *p; p=(QueuePrt)malloc(sizeof(QNode)); if(!p) exit(ERROR); p->data=e;p->next=NULL; Q、rear->next=p; Q、rear=p; return OK; } Status DeQueue (LinkQueue &Q,QElemType &e){ //删除Q得队头元素，用e返回其值 QNode *p; if(Q、front==Q、rear) return ERROR; p = Q、front->next; e=p->data; Q、front->next=p->next; if (Q、rear==p) Q、rear=Q、front; free(p); return OK; } Status QueueEmpty(LinkQueue Q){ //判断对就是否为空 if(Q、front==Q、rear)return ERROR; return OK; } void Menu(LinkQueue &Q){ //输出选择界面 int select=1; QElemType e; while(select){ cout<<"--------------------"< cout<<"请选择以下功能："< cout<<"--------------1,入队"< cout<<"--------------2,出队"< cout<<"--------------3,判断队空"< cout<<"--------------0,退出程序"< cout<<"请输入您得选择"; cin>>select; switch (select){ case 0:break; case 1: cout<<"输入入队数据"< cin>>e; if(EnQueue(Q,e)){ cout<<"入队成功"< } break; case 2: if(DeQueue(Q,e)){ cout< } break; case 3: if(QueueEmpty(Q)) cout<<"此队不为空"< else cout<<"此队为空"< break; } } } //QNode、h #ifndef QNODE_H #define QNODE_H #include #include using namespace std; const int OK=1; const int ERROR=0; typedef int QElemType; typedef int Status; typedef struct QNode{ QElemType data; struct QNode * next; }QNode,*QueuePrt; typedef struct { QueuePrt front; QueuePrt rear; }LinkQueue; Status InitQueue(LinkQueue &Q);//构造空队列 Status DestroyQueue(LinkQueue &Q);//销毁队列Q Status EnQueue (LinkQueue &Q,QElemType e);//插入元素a为Q得新得队尾元素 Status DeQueue (LinkQueue &Q,QElemType &e);//删除Q得队头元素，用e返回其值Status QueueEmpty(LinkQueue Q);//判断对就是否为空 void Menu(LinkQueue &Q);//输出选择界面 #endif ?运行结果： B顺序存储: ?代码部分： //main、cpp: #include"SqQueue、h" int main(){ SqQueue Q; if(InitQueue(Q)){ cout<<"创建队成功"< Menu(Q); DestroyQueue(Q); } return 0; } //SqQueue、cpp: #include"SqQueue、h" Status InitQueue(SqQueue &Q){ //创建空队列 Q、base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType)); if (!Q、base) exit(ERROR); Q、front=Q、rear=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e){ //插入元素e为Q得新队尾元素 if(((Q、rear+1)% MAXSIZE) == Q、front) return ERROR; Q、base[Q、rear]=e; Q、rear=(Q、rear+1)%MAXSIZE; return OK; } Status DeQueue(SqQueue &Q,QElemType &e){ //删除Q得对头元素，用e返回其值。 if(Q、front == Q、rear) return ERROR; e=Q、base[Q、front]; Q、front=(Q、front+1)%MAXSIZE; return OK; } Status SqQueueEmpty(SqQueue Q){ //判断Q就是否为空 if(Q、front==Q、rear) return ERROR; return OK; } Status DestroyQueue(SqQueue &Q){ //销毁栈 Q、front=Q、rear=0; free(Q、base); 实验编号：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、转换子程序 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 第三章栈和队列的应用 【实验目的】 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)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 实验三：栈和队列 程序代码： （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进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 【基本要求】 首先初始化一个顺序栈，通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例：顺序队列的入队和出队操作。 实验二 第三章栈和队列上机实验 一、实验时间与地点 第一组和第二组 时间：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) 《数据结构》实验指导及报告书 2014 / 2015 学年第 1学期 姓名： 学号： 班级： 指导教师：徐江 计算机科学与工程学院 2014 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include 数据结构实验报告 实验名称：实验2——栈和队列 学生姓名： 班级： 班内序号： 学号： 日期： 一、实验要求 1、实验目的：进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 2、实验内容： 根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求： 实现一个共享栈 实现一个链栈 实现一个循环队列 实现一个链队列 编写测试main()函数测试线性表的正确性 二、程序分析 2.1 存储结构 顺序栈、链栈和顺序队列 顺序栈链栈顺序队列 2.2 关键算法分析 A、实现一个共享栈： a、伪代码实现 入栈操作：如果栈满，则抛出上溢异常； 判断是插在栈1还是栈2，如果在栈1插入，则栈顶指针top1加1，在top1处 填入x，如果在栈2插入，则栈顶指针top2加1，在top2处填入x。 出栈操作：如果栈空，则抛出下溢异常； 判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，并且top1减1， 如果是栈2，则输出栈2栈顶元素，并且top2加1。 得到栈顶元素操作：如果栈空，则抛出下溢异常； 判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，如果是栈2，则 输出栈2栈顶元素。 b、算法实现： void shareseqstack::push(int x,int pushnumber)//进栈操作 {if(top1+1==top2)//异常处理 throw "上溢"; if(pushnumber==1)//判断栈1还是栈2 data[++top1]=x; if(pushnumber==2) data[--top2]=x; } void shareseqstack::pop(int popnumber)//出栈操作 {if(popnumber==1) //异常处理 { if(top1==-1) throw "下溢";数据结构_实验三_栈和队列及其应用
实验三 栈和队列的应用
数据结构实验二-栈和队列的基本操作与应用
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
实验二 栈和队列
实验二栈队列的实现及应用
实验二 堆栈和队列基本操作的编程实现
数据结构栈和队列实验报告.doc
数据结构实验三栈和队列的应用
实验二 栈与队列操作实验题目
实验三 栈和队列的操作
数据结构栈和队列实验报告
栈和队列实验报告
实验三 栈和队列
实验二栈和队列基本操作与应用
实验三 栈和队列
《数据结构》实验二 栈和队列
数据结构实验二题目一栈和队列实验报告
- 数据结构栈和队列实验报告
- 数据结构课程实验实训报告--堆栈和队列的基本操作。
- 数据结构实验-栈和队列
- 数据结构堆栈与队列实验报告
- 数据结构实验三栈和队列及其应用
- 数据结构_实验三_栈和队列及其应用
- 《数据结构》栈和队列实验报告
- 2数据结构实验报告二(栈和队列及其应用)
- 数据结构栈和队列实验报告
- 栈和队列实验报告
- 数据结构栈和队列实验报告
- 数据结构(栈及队列)实验报告 C语言版
- 栈和队列的基本操作及其应用数据结构实验报告书
- 数据结构_实验三_栈和队列及其应用
- 数据结构课程设计实验报告-栈和队列的用
- 数据结构栈和队列C语言实现
- 数据结构栈与队列的实验报告
- 数据结构试验栈和队列
- 数据结构栈和队列实验报告
- 数据结构栈和队列实验报告.doc