实习报告_96.docVIP

实习报告 --------------链表实现多项式相加 计算机科学系A班 左银波 / 邝子民 23 / 25 2005年12月 9日 实习题目： 用链表实现两个多项式相加，每一项用指数ne和系数nf表示。编写程序实现以下功能： （1）在键盘上输入指数ne和系数nf，分别生成两个一元多项式HA和HB； （2） 输出多项式HA和HB； （3） 把多项式HA和HB相加，生成新的一元多项式HC； （4） 输出新的一元多项式HC（原HA,HB不变）； （5）询问”Continue(n)?”,当输入回答字符’n’时结束程序，否则转（1）执行。 注意多项式输出形式为：3X^8-2X^1+7X+7^0. 多项式存储方式如下图，最多不超过10项，但两式子相加后结果可能超过10项 Ne1 Nf1 Ne2 Nf2 Ne3 Nf3 … … 0 0 Ne=Nf=0表示输入结束。 主要算法： 题目中要求多项式用链表存储，所以关键在于建立链表和对链表中项按指数进行排序和合并，在主程序中只需要调用函数创建链表并对其进行链表操作即可。我们的思路是这样的：编写四个链表函数――LIST创建链表、ORDER――链表排序、SORT――相同指数项合并、SHOW――输出链表各项，下面给出各个函数的实现算法： 创建链表：首先保存调用现场、调用中断int21h修改要申请内存块大小，因为系统已预先规定了可申请新内存块的大小，若不修改则不能申请成功；然后调用中断申请一个新内存块，若申请失败则显示提示信息并结束程序；提示用户输入一项的指数和系数，这里规定指数不能为负数，为提高程序使用性，我们允许输入项的指数有重复，在后面的处理过程中会将它们合并为新的一项，保存该内存块的段首地址，同时置下一节点域为空；判断其是否为首节点，是则将其段地址赋予链表头指针，否则将其链入当前链表结尾（即把它的段首地址赋予当前链尾链域；判断输入的指数和系数是否均为零，是则结束，否则判断创建节点是否多于9个，是则创建链表结束，否则会到开始继续创建节点；最后，创建链表结束，恢复现场并返回主程序。 链表元素排序：根据题目输出要求，我们将链表每个节点元素按照指数由大到小进行排序。这里我们借鉴实验教程中的冒泡算法排序。1将临时链表指针指向所要排序链表首节点；2如果节点域是为空则排序结束，否则比较该节点和下一节点指数，若后者大则交换两节点值，包括指数和系数，否则转4；3若节点为首节点则改变头指针的值为第二节点段首地址，并将二节点原下一节点链域赋予原首节点的下一节点链域，把原头指针值赋予原第二节点下一节点链域，不是首节点则按类似方法改变对应节点的下一节点链域；4临时链表指针指向下一节点，转步骤2重复执行；5按上面1～4重复执行，直到冒泡排序完成。 合并相同项：注意此步是在排序的基础上完成的，所以其重用性受到限制，更好的做法是把此子程序和排序子程序合二为一，以使其重用性更强。 算法比较简单，由于排完序的链表其指数相同项一定是相邻的，利用此点，不断的把指数相同的项系数相加并合为一项就可以了。这里不再赘述，具体实现请看后面源程序代码。 链表输出的实现也较为简单，只需逐个访问链表元素打印结果即可，也不再重复描述。 测试数据及报告： 输入：HA:5X^2+3X^1-8X^0 HB:7X^5-10X^5+8X^2+7X^0 输出：HA:5X^2+3X^1-8X^0 HB:-3X^5+8X^2+7X^0 HC:-3X^5+13X^2+3X^1-1X^0 输入：HA:4X^2+3X^0 HB:-4X^2-3X^0 输出：HA:4X^2+3X^0 HB:-4X^2-3X^0 HC:0 输入：HA:3X^3-4X^7+7X^5 HB:6X^5-3X^1 输出：HA:-4X^7+7X^5+3X^3 HB:6X^5-3X^1 HC:-4X^7+13X^5+3X^3-3X^1 观察以上数据，结果符合要求，由于上述数据已基本包括了所有类型，可以保证程序的完整性。 主要流程图： LIST------创建链表 N Y N Y N Y 体会及教训： 链表是上学期已经接触过的数据类型，只是现在要改用汇编语言来实现，其本质是没有变化的，通过实习，使我们对链表这一重要的数据类型掌握和理解更深刻，它有着数组无法替代的点，可以随机确定存储长度，功能多样