版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、一、实验目的和要求(1)理解栈和队列的特征以及它们之间的差异,知道在何时使用那种数据结构。(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队队列满和队空的 条件。(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验环境和方法实验方法:(一)综合运用课本所学的知识,用不同的算法实现在不同的程序功能。(二)结合指导老师的指导,解决程序中的问题,正确解决实际中存在的异常情况,逐步 改善功能。(三)根据实验内容,编译程序。实验环境:Windows xp Visual C+6.0三、实验内容及过程描述实验
2、步骤: 进入Visual C+ 6.0集成环境。 输入自己编好的程序。 检查一遍已输入的程序是否有错(包括输入时输错的和编程中的错误),如发现有错,及时改正。 进行编译和连接。如果在编译和连接过程中发现错误,频幕上会出现“报错信息” 根据提示找到出错位置和原因,加以改正。再进行编译,如此反复直到不出错为止。 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确,应运行多次,分别检查在不同情况下结果是否正确实验内容:编译以下题目的程序并调试运行。Workspace Proj3_1 : 1 project(s) -:Proj31Jiles -_j Sourceiles
3、肉 algo3-1xpp 圍 exp3-1 .cpp i Header Files_| Resource FilesTCIassVicwl il FilcView 序栈个主1)、编写一个程序 algo3-1.cpp,实现顺 的各种基本运算,并在此基础上设计一 程序并完成如下功能:(1)初始化栈s;(2)判断栈s是否非空;(3) 依次进栈元素a,b,c,d,e;(4) 判断栈s是否非空;(5) 输出出栈序列;(6) 判断栈s是否非空;(7) 释放栈。图3.1 Proj3_1工程组成本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数,方框中指出函数名,箭
4、头方向表示函数间的调用关系。初始化栈S销毁栈s/判断栈空/进栈出栈/取栈顶元素In itStack(SqStack *&s)DestroyStack(SqStack *&s)StackEmpty(SqStack *s)Push(SqStack *&s,ElemType e) Pop(SqStack *& s,ElemType &e) GetTop(SqStack *s,ElemType &e) 对应的程序如下:文件名:algo3-1.cpp #in clude #include #defi ne MaxSize 100 typedef char ElemType; typedef struct
5、 ElemType dataMaxSize;int top;栈顶指针 SqStack;void InitStack(SqStack *&s)/初始化栈 S s=(SqStack *)malloc(sizeof(SqStack);s-top=-1;/栈顶指针置为-1void DestroyStack(SqStack *&s)/销毁栈 sfree(s);bool StackEmpty(SqStack *s)/ 判断栈空return(s-top=-1);bool Push(SqStack *&s,ElemType e)进栈 if (s-top=MaxSize-1) II栈满的情况,即栈上溢出 ret
6、urn false;s-top+;II栈顶指针增1s-datas-top=e;II元素e放在栈顶指针处return true;bool Pop(SqStack *& s,ElemType &e)II 出栈 if (s-top=-1)II栈为空的情况,即栈下溢出return false;e=s-datas-top; II取栈顶指针元素的元素 s-top-;II栈顶指针减1return true;bool GetTop(SqStack *s,ElemType &e)II 取栈顶元素 if (s-top=-1)II栈为空的情况,即栈下溢出return false;e=s-datas-top; II取
7、栈顶指针元素的元素 return true;设计exp3-1.cpp程序如下II文件名:exp3-1.cpp#in clude #include #defi ne MaxSize 100typedef char ElemType;typedef structElemType dataMaxSize;int top;栈顶指针 SqStack;extern void In itStack(SqStack *&;s);extern void DestroyStack(SqStack *& s);extern bool StackEmpty(SqStack *s);exter n bool Push(
8、SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType & e);extern bool GetTop(SqStack *s,ElemType & e);void mai n()ElemType e;SqStack *s;printf(栈s的基本运算如下:n”);printf(1)初始化栈 sn);In itStack(s);printf( (2)栈为 %sn,(StackEmpty(s)?空:非空);printf( (3)依次进栈元素 a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push
9、(s,d);Push(s,e);printf( 栈为 %sn,(StackEmpty(s)?空:非空); printf(5)出栈序列:);while (!StackEmpty(s)Pop(s,e);prin tf(%c ,e);prin tf(n);printf( (6)栈为 %sn,(StackEmpty(s)?空:非空);printf( (7)释放栈 n);DestroyStack(s);运行结果如下:2)、编写一个程序algo3-2.cpp,实现链栈的各种基本运算,并在此基础上设计一个主程序并完成如下功能:(1)初始化链栈s;(2)判断链栈s是否非空;(3)依次进栈 a,b,c,d, e
10、;(4)判断链栈s是否非空;(5 )输出链栈长度;(6)输出从栈底到栈顶元素;(7)输出出队序列;(8)判断链栈s是否非空;(9)释放队列。本工程Proj3_2的组成结构如图11 Workspace Proj3_2: 1 project(s) -1 Proj3_Z files s Source Files 5 ClassViewHFileView宙 algo3-2.cpp 圍 exp3-2.cpp _l Header Files _J Resource Files图3.3 Proj3_2工程组成3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数,方框中指出函数名,箭头方向表示函数间的
11、调用关系图3.4 Proj3_2工程的程序结构图其中包含如下函数:InitStack(LiStack *&s)/初始化栈 sDestroyStack(LiStack *&s)/ 销毁栈StackEmpty(LiStack *s) 判断栈是否为空 Push(LiStack *&s,ElemType e)进栈Pop(LiStack *&s,ElemType &e)/ 出栈GetTop(LiStack *s,ElemType &e) /取栈顶元素对应的程序如下:/文件名:algo3-2.cpp#in elude 数据域#include typedef char ElemType; typedef s
12、truct li nknode ElemType data;ElemType data;数据域struct linknode *n ext;指针域 LiStack;void InitStack(LiStack *&s)/初始化栈 s s=(LiStack *)malloc(sizeof(LiStack);s- next=NULL;void DestroyStack(LiStack *&s)/ 销毁栈LiStack *p=s,*q=s-n ext;while (q!=NULL) free(p);p=q;q=p-n ext;free(p); II此时p指向尾节点,释放其空间bool StackEm
13、pty(LiStack *s) II 判断栈是否为空retur n(s-n ext=NULL);void Push(LiStack *& s,ElemType e)进栈 LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;II新建元素e对应的节点*pp-next=s-next;II插入*p节点作为开始节点s_n ext=p;bool Pop(LiStack *&s,ElemType &e)II 出栈LiStack *p;if (s- next=NULL)II栈空的情况return false;p=s-n ext;IIp指向开始节点e=
14、p-data;s-n ext=p-n ext;II删除*p节点free(p);II释放*p节点return true;bool GetTop(LiStack *s,ElemType &e) II 取栈顶元素 if (s- next=NULL)栈空的情况return false;e=s-n ext-data; return true;设计exp3-2.cpp主程序/ 文件名:exp3-2.cpp#in elude #include typedef char ElemType;typedef struct li nknodeElemType data;数据域struct linknode *n e
15、xt;指针域 LiStack;extern void In itStack(LiStack *&;s);extern void DestroyStack(LiStack *&s);exter n bool StackEmpty(LiStack *s);extern void Push(LiStack *& s,ElemType e);exter n bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType & e);void mai n()ElemType e;LiStack *s;printf(栈s的基本
16、运算如下:n”);printf( (1)初始化栈 sn);In itStack(s);printf(2)栈为 %sn,(StackEmpty(s)?空:非空);printf(3)依次进栈元素 a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf(栈为 %sn,(StackEmpty(s)?空:非空);printf( (5)出栈序列:);while (!StackEmpty(s)Pop(s,e);prin tf(%c ,e);prin tf(n);printf(6)栈为 %sn,(StackEmpty(s)?空:
17、非空);printf( (7)释放栈 n);DestroyStack(s);程序运行结果如下:下nu8运化空进非序宀工桟k 本勢次翼毂ny S 吾 1234567 s耳b a 匚 4&c b acontinue.3)、编写一个程序 algo3-3.cpp,实现顺序环形队列的各种基本运算,并在此基础上设计一个主程序并完成如下功能:(1) 初始化队列q;(2) 判断队列q是否非空;(3) 依次进队列a,b,c;(4) 出队一个元素,输出该元素;(5) 输出队列q的元素个数;(6 )依次进队列元素 d,e,f;(7) 输出队列q的元素个数;11 Workspace Poj3_3: 1 project
18、(s) -Bl Proj3 _3 files -Source FilesC Header FilesI Resource Files: Cl酣凶沱钏圍Fil肆怔评图3-5 Proj3_3的工程组成(8) 输出出队序列;(9) 释放队列。本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图 3.6所示。图中方框表示函数,方框中指出函数名,箭头方向表示函数间的调用关系图3.6 Proj3_3工程的程序结构图其中包含如下函数:Ini tQueue(SqQueue *& q) 初始化队列DestroyQueue(SqQueue *&q)/ 销毁队列QueueEmpty(SqQueue *
19、q)判断队列空en Queue(SqQueue *&q,ElemType e) 进队 deQueue(SqQueue *&q,ElemType &e) / 出队对应的程序如下:/文件名:algo3-3.cpp#in elude #include #defi ne MaxSize 5typedef char ElemType;typedef structElemType dataMaxSize;int fron t,rear;/队首和队尾指针 SqQueue;void Ini tQueue(SqQueue *&q)/ 初始化队列 q=(SqQueue *)malloc (sizeof(SqQue
20、ue);q_fron t=q-rear=0;void DestroyQueue(SqQueue *&q)/ 销毁队列free(q);bool QueueEmpty(SqQueue *q)/ 判断队列空return(q-fr on t=q-rear);bool en Queue(SqQueue *&q,ElemType e)/ 进队if (q-rear+1)%MaxSize=q-fro nt)/ 队满上溢出return false;q-rear=(q-rear+1)%MaxSize;q_dataq_rear=e;return true;bool deQueue(SqQueue *&q,ElemT
21、ype &e) / 出队if (q-fro nt=q-rear)/ 队空下溢出return false;q-fro nt=(q-fro nt+1)%MaxSize;e=q-dataq-fr on t;return true;设计exp3-3.cpp主程序#in clude #include #defi ne MaxSize 5typedef char ElemType;typedef structElemType elemMaxSize;int fron t,rear;/队首和队尾指针 SqQueue;exter n void In itQueue(SqQueue *&q);exter n void DestroyQueue(SqQueue *&q);exter n bool QueueEmpty(SqQueue *q);extern bool en Queue(SqQueue *& q,ElemType e); extern bool deQueue(SqQueue *& q,ElemType & e); void mai n()ElemType e;SqQueue *q;printf(环形队列基本运算如下:n);
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 自我成长记主题班会
- 科技创新实践主题班会
- 诚信故事启迪心灵主题班会
- 绿色工厂评定标准
- 民营企业免责协议书模板
- 电焊工培训协议书模板
- 军人驿站合作协议书模板
- 2.2-合理利用网络教案-2021-2022学年道德与法治八年级上册同步教学课件教案部编版
- 甜品消费习惯调查
- 关于喝汤习惯的问卷调查
- FZ∕T 61002-2019 化纤仿毛毛毯
- 2024年高考语文阅读之李娟散文专练全国解析版
- 国开2024《人文英语4》边学边练参考答案
- 中医药数字化赋能产业发展
- 【课题申报】探索初中生物课程的跨学科教学
- 城市规划专业介绍
- 2024年三级劳动关系协调员技能理论考试题库(浓缩500题)
- DB34 3468-2019 民用建筑楼面保温隔声工程技术规程
- YY 1001-2024全玻璃注射器
- 教育机构运营推广方案
- 2024年高考语文复习:文言文断句专项练习题汇编(含答案解析)
评论
0/150
提交评论