3) 实现提示：以两个多项式相加为例
? 结果多项式另存
? 扫描两个相加多项式，若都未检测完：
? 若当前被检测项指数相等，系数相加，若结果未
变成0，则将结果插入到结果多项式。 ? 若当前被检测项指数不等，则将指数较小者插入
到结果多项式。
? 若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。
5． 长整数（任意长度）四则运算演示程序（实验类型：综合型）
1）问题描述：设计一个实现任意长的整数进行加法运算的演示程序
2）实验要求:
? 利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的范围是 -（215-1）~（215-1）。
? 输入和输出形式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。 3) 实现提示：
? 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。
9
? 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。 4）注意问题:
? 不能给常整数位数规定上限。
实验二 栈与队列应用
一. 实验目的
1. 实验设置基本要求：通过实验掌握栈或队列的基本操作的
实现，并能灵活运用栈或队列特性，综合运用程序设计、算法分析等知识解决实际问题。
2. 实验设置较高要求：理解组成递归算法的基本条件，理解
递归算法与相应的非递归算法的区别，理解栈和队列的应用与作用。 二. 实验学时：
课内实验学时：4学时 课外实验学时：8学时 三. 备选实验题目
1． 十进制数N进制数据的转换 （实验类型：综合型） 1）问题描述：将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据。
2）实验要求: 利用顺序栈实现数制转换问题 3) 实现提示：
? 转换方法利用辗转相除法;
10
? 所转换的N进制数按低位到高位的顺序产生，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位N进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 4）注意问题:
? 何时入栈、出栈 ? 算法结束条件
2． 算术表达式求值演示（实验类型：综合型）
1）问题描述：从键盘输入一个算术表达式并输出它的结果 2）实验要求：算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。
3) 实现提示：
? 表达式作为一个串存储，如表达式“3*2-(4+2*1)”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能还有更高的运算，正确的处理过程是：
? 需要两个栈：对象栈OPND和算符栈OPTR; ? 自左至右扫描表达式, 若当前字符是运算对象，
入OPND栈;
? 对运算符，若这个运算符比栈顶运算符高则入栈，
继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈一运算符进行运算，并将其运算结果入OPND栈，继续处理当前字符，直到遇到结束符。
4）注意问题
? 重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。
11
? 注意算法的各个函数之间值的传递情况。 3． 停车场管理问题（实验类型：综合型）
1）问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编写程序模拟该停车场的管理。
2）实验要求: 要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和他在停车场内停留的时间
3）实现提示：以栈模拟停车场，以队列模拟便道，按照从终端读入的车辆“到达”“离开”信息模拟停车场管理
4）注意问题
? 重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。
? 栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。
4． 判断“回文”问题（实验类型：综合型）
1）问题描述：所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。
例如，did; pop; I was able 与 elba saw I 等等。
12
2）实验要求：编写程序，利用栈结构判断一个字符串是否是“回文”。
3）实现提示：
? 从左向右遇到的字符，若和栈顶元素比较，若不相等，字符入栈，若相等，出栈。如此继续，若栈空，字符串是“回文”，否则不是。
5． 用递归和非递归两种方法实现自然数的拆分（实验类型：综合型）
1）问题描述：任何大于 1 的自然数 n，总可以拆分成若干大于等于1 的自然数之和。
例: n=4 4=1+3 4=1+1+2 4=1+1+1+1 4=2+2 2）实验要求:
? 采用递归和非递归两种方法实现 ? 利用交换率得出的拆分看作相同的拆分。 3）实现提示：
? 递归算法:
? 用数组a[]，a[k]中存储已完成的一种拆分 ? a[k]能否再拆分取决于a[k]/2是否大于等于a[k-1]；
? 递归过程有两个参数：n表示要拆分数值的大小；k表示n存储在数组元素a[k]中。
? 非递归算法：
（1） 栈为两个数组a[],b[]，ax,bx表示两个栈的
栈顶元素；初始化：a[1]=1,b[1]=n，i=1, ax=a[i],bx=b[i]
（2） 若i<>1 or ax<>bx,重复
? 若ax 13