实验报告示例： 利用栈排序问题
实验报告 利用栈排序问题
1. 实验目的
实现栈的操作;
利用栈的入栈、出栈动作对数据进行排序。
2. 实验内容
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个栈，另外设计一个线性表。给定n个数据，首先将其入栈，然后将数据出栈，并按从小到大的顺序依次入线性表。(小的数先写入线性表，大的数后写入线性表。)
3. 解题方法
3.1 求解方法
利用栈来存放给定的n个数据，为保证最终能从小到大的顺序依次出战，
应当将大的数先入栈，小的数后入栈。为此引入辅助栈，在数据ai入栈
时，若ai 比当前栈顶的元素小，则必须将当前栈顶的元素弹出，保存在
辅助栈中，重复这一出栈入栈动作，直至ai 不小于当前栈顶的元素，这
将ai入栈，并将辅助栈中的所有元素弹回原栈中。 时
3.2 数据结构
TYPE stack = RECORD [栈类型定义]
s: ARRAY[1..N] of integer;
top: 0..N
END;
VAR st1, st2 : stack;
a : array [1..N] of integer; [向量，存放给定的n个数据]
L : array [1..N] of integer; [线性表，用于存放结果]
3.3 算法描述
1. [初始化]
初始化st1，st2
2. a[1]入栈st1
3. 循环 i从2 到 n ，反复执行
若 a[i] , top(st1)
则 push(st1, a[i])
否则:
(1)将st1中从栈顶开始所有小于ai的元素依次出栈、入栈st2;
(2) push(st1, a[i])
(3)将st2中所有元素依次出栈，并入栈st1;
4. 将st1中所有元素依次出栈、入线性表L
5. 算法结束。
3.4 算法复杂性分析
最坏情况下:给定n个数据是从大到小的，则需要进行
n次入st1和n次出st1操作
2 * ( 0+1+…+(n-1)) = n(n-1)次出st1和入st2操作
2 * ( 0+1+…+(n-1)) = n(n-1)次出st2和入st1操作
2出入栈总次数 N = 2*n+2*n*(n-1) = O (n)
好情况下:给定n个数据是从小到大的，则只需要进行n次入st1 最
和出st1操作，出入栈总次数 N = 2*n = O (2n)
比较次数不受数据原始大小顺序的影响，为 O(n)。
2算法复杂性为:O(n) ~ O(n)
4. 程序设计
4.1 数据结构
) 4.2 源程序(略
5. 上机实验
5.1 实验环境: Borland C++ V3.1
[给出若干组数据，注意边界情况] 5.2 输入数据:
5.3 实验结果
6.
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
本算法利用向量实现栈，并通过了上机调试，得到了正确的排序结果，达到
实验目的。
浙公网安备 33021202002483