数据结构-实验三-栈和队列及其应用.doc

资源ID：92328881 资源大小：364.04KB 全文页数：32页
资源格式： DOC 下载积分：10金币

快捷下载

会员登录下载

微信登录下载

三方登录下载：

微信扫一扫登录

下载资源需要10金币

邮箱/手机：
温馨提示：	快捷下载时，用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）。如填写123，账号就是123，密码也是123。
支付方式：
验证码：	换一换

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

友情提示

1、下载资料失败解决办法

2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。

3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。

4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。

5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。

网站客服

侵权投诉

数据结构-实验三-栈和队列及其应用.doc

实验编号：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; elsecout<<"blank"<<endl;break;case 3:if (StackEmpty(S)cout << "栈空 " << endl;elsecout << "栈未空 " << 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"<<endl;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 "<<S、top-S、base << endl;return OK;/SStack、h:#include<iostream>#include<stdlib、h>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"<<endl;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<<""<<endl;cout<<"请选择功能"<<endl;cout<<"1、入栈"<<endl;cout<<"2、出栈"<<endl;cout<<"3、得到顶部数据"<<endl;cout<<"4、判断栈就是否为空"<<endl;cout<<"5、输出栈得长度"<<endl;cout<<"0、退出程序"<<endl;cout<<"您得选择就是："cin>>select;switch (select)case 0:break;case 1:cout<<"push data:"cin>>e;if(push(L,e)cout<<"push succeed"<<endl;else cout<<"push failed"<<endl;break;case 2:if(pop(L,e)cout<<"data "<<e<<" is pop"<<endl;else cout<<"pop failed"<<endl;break;case 3:if(GetTop(L,e)cout<<"head data "<<e<<" is pop"<<endl;else cout<<"Get failed"<<endl;break;case 4:if(StackEmpty(L)cout<<"stack is not NULL"<<endl;else cout<<"stack is NULL"<<endl;break;case 5:cout<<"this stack length is "<<StackLength(L)<<endl;break;/Lstack、h#include<iostream>#include<stdlib、h>using namespace std;const int OK=1;const int ERROR=0;typedef int SElemType;typedef int Status;typedef struct LqStackSElemType 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<<"栈创建成功"<<endl;cout<<"输入待转换得数："cin>>N;while(N)push(S,N%number);N=N/number;while(StackEmpty(S)pop(S,e);cout<<e;cout<<endl;/SStack、h#ifndef SSTACK_H#define SSTACK_H#include<iostream>#include<stdlib、h>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)/销毁队列Qwhile(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<<"-"<<endl;cout<<"请选择以下功能："<<endl;cout<<"-1,入队"<<endl;cout<<"-2,出队"<<endl;cout<<"-3,判断队空"<<endl;cout<<"-0,退出程序"<<endl;cout<<"请输入您得选择"cin>>select;switch (select)case 0:break;case 1:cout<<"输入入队数据"<<endl;cin>>e;if(EnQueue(Q,e)cout<<"入队成功"<<endl;break;case 2:if(DeQueue(Q,e)cout<<e<<"出队"<<endl;break;case 3:if(QueueEmpty(Q) cout<<"此队不为空"<<endl;else cout<<"此队为空"<<endl;break;/QNode、h#ifndef QNODE_H#define QNODE_H#include<iostream>#include<stdlib、h>using namespace std;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode * next;QNode,*QueuePrt;typedef struct QueuePrt front;QueuePrt rear;LinkQueue;Status InitQueue(LinkQueue &Q);/构造空队列Status DestroyQueue(LinkQueue &Q);/销毁队列QStatus 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<<"创建队成功"<<endl; 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、baseQ、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、baseQ、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);return OK;void Menu(SqQueue &Q)/输出选择菜单int select=1;QElemType e;while (select)cout<<"-"<<endl;cout<<"请选择一下功能:"<<endl;cout<<" 1，入队"<<endl;cout<<" 2，出队"<<endl;cout<<" 3，判断就是否为空"<<endl;cout<<" 0，退出程序"<<endl;cout<<"您得选择就是："cin>>select;switch (select)case 0:break;case 1:cout<<"输入插入得数据:"cin>>e;if(EnQueue(Q,e)cout<<"入队成功"<<endl;else cout<<"队满"<<endl;break;case 2:if(DeQueue(Q,e)cout<<e<<"出队"<<endl;else cout<<"队空"<<endl;break;case 3:if(SqQueueEmpty(Q)cout<<"队未空"<<endl;else cout<<"队空"<<endl;break;/SqQueue、h:#ifndef SQQUEUE_H#define SQQUEUE_H#include<iostream>#include<stdlib、h>using namespace std;const int MAXSIZE=100;const int MORE=100;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef structQElemType *base;int front ;int rear;SqQueue;Status InitQueue(SqQueue &Q);/创建空队列Status EnQueue(SqQueue &Q,QElemType e);/插入元素e为Q得新队尾元素Status DeQueue(SqQueue &Q,QElemType &e);/删除Q得对头元素，用e返回其值。Status SqQueueEmpty(SqQueue Q);/判断Q就是否为空Status DestroyQueue(SqQueue &Q);/销毁栈void Menu(SqQueue &Q);/输出选择菜单#endifØ 运行结果：（4）利用栈实现任一个表达式中得语法检查（括号得匹配）。Ø 代码部分：/SqStack、h#include<iostream>#include<stdlib、h>using namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int ERROR=0;const int OK=0;typedef char SElemType;typedef int Status;typedef structSElemType *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);/出栈/SqStack、cpp#include"SqStack、h"/创建栈 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;return OK;/main、cpp#include"SqStack、h"int main()char c; SElemType e;SqStack S;InitStack(S);while(c=getchar()!='#')switch(c)case '(':case '':case '':Push (S,c); break;case ')': if (S、top=S、base) break;GetTop(S,e);if (e='(')Pop(S,e);break;case '':if (S、top=S、base) break;GetTop(S,e);if (e='')Pop(S,e); break;case '':if (S、top=S、base) break;GetTop(S,e);if (e='')Pop(S,e); break;if (S、base=S、top)cout<<"括号完全匹配"<<endl; elsecout<<"括号不完全匹配"<<endl; return OK; Ø 运行结果：（5）利用栈实现表达式得求值。Ø 代码部分：/SqStack、h#include<iostream>#include<stdlib、h>using namespace std;typedef int Status;typedef char SElemType;typedef struct SqStackSElemType data;struct SqStack * next;SqStack,*LinkStack;const int OK=1;const int ERROR=0;Status

注意事项

本文（数据结构-实验三-栈和队列及其应用.doc）为本站会员（教****）主动上传，淘文阁 - 分享文档赚钱的网站仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知淘文阁 - 分享文档赚钱的网站（点击联系客服），我们立即给予删除！

温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载不扣分。