20##级数据结构实验报告

实验名称：实验二栈和队列

日    期： 2008年11月15日

1．实验要求

实验目的

通过选择下面五个题目之一进行实现，掌握如下内容：

进一步掌握指针、模板类、异常处理的使用

掌握栈的操作的实现方法

掌握队列的操作的实现方法

学习使用栈解决实际问题的能力

学习使用队列解决实际问题的能力

实验内容

2.1题目1

根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

    要求：

1、  实现一个共享栈

2、  实现一个链栈

3、  实现一个循环队列

4、  实现一个链队列

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

存储结构：

特殊线性表：栈，队列

 

2.2 关键算法分析

共享栈的入栈算法伪码（Push）：

1．如果栈满，抛出上溢异常。

2．判断是插在栈1还是栈2：

2.1如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x；

2.2如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x。

共享栈的出栈算法伪码（Pop）：

1. 判断是在栈1删除还是在栈2删除。

2. 若是在栈1删除，则

2.1 若栈1为空栈，抛出下溢异常；

2.2 删除并返回栈1的栈顶元素；

3. 若是在栈2删除，则

3.1 若栈2为空栈，抛出下溢异常；

3.2 删除并返回栈2的栈顶元素。

共享栈的取栈顶元素算法伪码（GetTop）：

1．  判断是在栈1取还是栈2取；

2．  如果在栈1取，则

2.1 若栈1不空，返回栈顶元素的值，不删除；

2.2 若栈1空，返回0；

3．如果在栈2取，则

3.1 若栈2不空，返回栈顶元素的值，不删除；

3.2 若栈2空，返回0。

链栈的入栈算法伪码（Push）：

1．  申请一个新的结点，数据域为x；

2．  将新结点插在栈顶；

3．  栈顶指针重新指向栈顶元素。

链栈的出栈算法伪码（Pop）：

1．  如果栈空，抛出下溢异常；

2．  暂存栈顶元素；

3．  将栈顶结点摘链；

4．  删除该结点，返回该元素的值。

链栈的取栈顶元素算法的伪码（GetTop）：

1．  如果栈非空，返回栈顶元素的值，不删除。

循环队列的入队算法伪码（EnQueue）：

1．  如果队满，抛出上溢异常；

2．  队尾指针在循环意义下加1；

3．  在队尾插入元素。

循环队列的出队算法伪码（DeQueue）：

1．  如果队空，抛出下溢异常；

2．  队头指针在循环意义下加1；

3．  读取并返回出队前的队头元素。

循环队列的取队头元素算法伪码（GetQueue）：

1．  如果队空，抛出下溢异常；

2．  值为队头指针的工作指针i在循环意义下加1，注意不给队头指针赋值；

3．  返回队头指针的队头元素。

链队列的入队算法伪码（EnQueue）：

1．  申请一个数据域为x的新结点；

2．  该结点的next域置空；

3．  将其插到队尾。

链队列的出队算法伪码（DeQueue）：

1．  如果队空，抛出下溢异常；

2．  暂存队头元素；

3．  将队头元素所在结点摘链；

4．  如果被删除的队头元素同时也是队尾元素，则修改队尾指针。

链队列的取队头元素算法伪码（GetQueue）：

1．  如果队非空，返回队头元素的值，不删除。

以上算法的时间复杂度均为O(1)。可比较的是空间性能。初始时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满。但是每个元素都需要一个指针域，所以产生了结构性开销。循环队列和链队列的空间性能的比较与顺序栈和链栈的空间性能比较类似，只是循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队列。

3.  程序运行结果

 

测试条件：主函数都大都采用了使用循环来入栈（队）（链队列除外），问题规模取决于栈本身的大小，而链队列和链栈不受限制（除非内存没了）。每次入栈（队）、出栈（队）、取栈顶（队头）元素前后都执行函数Empty()判断栈（队列）是否为空。

测试结论：程序可以正常且正确运行。

4.        总结   

1、  调试时出现的问题及解决的方法

对循环队列进行测试时，由于之前设定的队列的大小是10，故在入队时设定的k最大为9了即k<10，然而运行时程序出错，于是试着把k<10改为了k<9，重新运行便无问题了。这是因为循环队列实际上是留出了一个空的数组元素空间，以便判断队是否已满，所以实际上最多只能储存9个元素。故k=0;k<9。

但后来添加了异常处理，故而改为可以由用户自行输入元素值。

2、  心得体会

这次选择的题目非常基本，是共享栈、链栈、循环队列、链队列的基本实现，相对也比较容易，但却是很基础的，有些细节部分是值得高度重视的，也是容易出错的地方，例如上所写的测试循环队列时出现的问题。

对这些基本的特殊线性表的测试与实现是编写较复杂程序的基础，应该牢固掌握它们。

这个实验也让我学会了异常处理的方法。

3、  下一步的改进

由于近期处于期中考试阶段，所以没能选择更有难度的题目做，但实际上这道题虽然看似简单但在很多地方也是容易出错的。改进方面，链表由于一般没有上限（除非没有内存），就自己预设了一个数组存放入栈（队）的元素，其实应该也可以设为让用户自己来输入。

循环队列：

共享栈：

链队列：

链栈：

第二篇：数据结构实验报告2-栈和队列

北京物资学院信息学院实验报告

课程名 数据结构(C++)实验

实验名称 栈和队列算法的实现

实验日期 年 月 日 实验报告日期 年 月 日 姓 名 ______ ___ 班 级_____ _______ 学 号___

一、实验目的

1. 掌握栈和队列的顺序存储和链接存储数据结构；

2. 掌握栈和队列顺序存储和链接存储的基本操作；

3. 会初步应用栈和队列；

二、实验内容

栈部分

1. 实现顺序栈的所有操作算法，并自编主函数证实它们的正确性。

2. 利用栈实现数制转换（十进制-八进制或十进制-二进制）算法。

3. 递归:【习题4-4】1, 2, 6 (1);

4. 【习题4-4】8. 注意双栈的顺序存储结构，可设MaxSize为10。按要求实现下列算法：

4.1初始化：栈1和栈2置空；

void InitStack(BothStack& BS) ;

4.2判断栈是否为空：当k=1或k=1时判断对应的栈1或栈2是否为空： bool StackEmpty(BothStack& BS,int k);

4.3进栈：当k=1或k=1时向对应的栈1或栈2的栈顶压入元素：

void Push(BothStack& BS,int k,ElemType item);

4.4退栈：当k=1或k=1时对应的栈1或栈2退栈并返回栈顶元素： ElemType Pop(BothStack& BS,int k);

4.5遍历栈：当k=1或k=1时遍历对应的栈1或栈2：

void OutputBStack(BothStack& BS,int k);

并自编主函数证实它们的正确性。

5. 实现链栈的操作功能(P137-138)

队列部分

1．实现循环队的操作功能(P163-164)

2. 编写一个输出循环队的算法，其功能为：

从队首到队尾依次输出队中所有元素；

输出队首单元号、队尾单元号；

输出队中的元素个数。

3. 建立一个有10个单元的循环队，准备15个待进队的元素，并完成以下操作： 前7个元素进队；3个元素出队；后续5个元素进队；4个元素出队；3个元素 1

进队。

每个操作之后都要：输出队列；输出队首单元号、队尾单元号和队中的元素个数。

4. 实现链队的操作功能(P166-167)(选作)

综合题

键盘输入(或用其他方式提供原始数据)若干字符，用正序和逆序输出它们。(选作)

三、实验地点与环境

3.1 实验地点

(南实验楼 教室)

3.2实验环境

(所用语言环境)

四、实验步骤

1.

2.

3.

?

五、实验结果与分析

5.1 实验结果 (原始数据，预期结果和运行结果)

序号 算法名称(函数名)

与功能

1

2

3

函数名： 功 能：

说明

5.2 分析

（选择部分算法分析，包括函数参数说明、调试中所遇到的问题和解决方法、中间结果等，必要时给出函数和主函数的关键段落。所选算法应是：重要的算法、有编程特点的算法等）

所在头文件名 主函数所在文件名 头文件： CPP文件： 原始数据： 运行结果： 原始数据与 运行结果* * 如果不能按“原始数据”、“运行结果”列出数据则不列，必要时在“分析”部分

六、小结

（收获与心得）

2