01.【实习一】线性表及应用(1).ppt

数据结构数据结构20122012年秋季年秋季授课教师：授课教师： 方方 芳芳授课班级：授课班级：115111-3115111-3班班【【实习一实习一】】 线性表应用线性表应用【【实习题目一实习题目一】】：：n n（（n>20n>20）的阶乘）的阶乘【【问题描述问题描述】】大数运算大数运算————计算计算n n的阶乘（的阶乘（n>=20n>=20）基本要求基本要求】】（（1 1）数据的表示和存储；）数据的表示和存储；（（1.11.1）） 累积运算的中间结果和最终的计算结果的数据类型要累积运算的中间结果和最终的计算结果的数据类型要 求是整型求是整型————这是问题本身的要求；这是问题本身的要求；（（1.21.2）） 试设计合适的存储结构，要求每个元素或节点最多存试设计合适的存储结构，要求每个元素或节点最多存 储数据的储数据的3 3位位数值 （（2 2）数据的操作及其实现：）数据的操作及其实现：基于设计的存储结构实现乘法操作，要求从键盘上输入基于设计的存储结构实现乘法操作，要求从键盘上输入n n值，在屏幕上显示最终计算结果值，在屏幕上显示最终计算结果测试数据测试数据】】（（1 1））n n＝＝2020，，n n！＝！＝24329020081766400002432902008176640000（（2 2））n n＝＝3030，，n n！＝！＝265252859812191058636308480000000265252859812191058636308480000000（（1 1）设计数据的）设计数据的存储结构存储结构：：介于阶乘运算的精确性以及实型数据表示的不精确性，本介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，题不能采用实型表示累积运算的中间结果和最终的计算结果， 而而只能用整型只能用整型。

然而由于普通整型和长整型所能表述数的范围然而由于普通整型和长整型所能表述数的范围 受其字长的限制受其字长的限制，不能表示大数阶乘的累积结果，故必须设计，不能表示大数阶乘的累积结果，故必须设计 一个合适的数据结构实现对数据的存储，例如可以让每个元素一个合适的数据结构实现对数据的存储，例如可以让每个元素 或节点存储数据的若干位数值或节点存储数据的若干位数值从问题描述不难看出从问题描述不难看出n n值为任意值，故为使程序尽量不受限值为任意值，故为使程序尽量不受限制，应采用动态存储结构制，应采用动态存储结构2 2）） 数据的操作及其实现：数据的操作及其实现：（（2.12.1）累积运算的特点是当前的计算结果是下次乘法运算的）累积运算的特点是当前的计算结果是下次乘法运算的乘数；乘数；【【实现提示实现提示】】（（2.22.2）实现两个数的乘法运算须考虑：）实现两个数的乘法运算须考虑：（（1 1）乘数的）乘数的各位数都要与被乘数进行乘法运算各位数都要与被乘数进行乘法运算；；（（2 2）乘法）乘法过程中的进位问题过程中的进位问题及其实现；及其实现；（（3 3）因每个元素或节点最多存储数据的）因每个元素或节点最多存储数据的3 3位数值，故当元位数值，故当元素或节点中的数值大于素或节点中的数值大于999999，需，需向前一个元素或节点进位向前一个元素或节点进位。

【【可采用的数据结构可采用的数据结构】】（（1 1）采用）采用链式存储结构链式存储结构实现（普通单链表，循环单链表，普通实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）双项链表和双向循环链表中任选一种结构）————本次实习要求本次实习要求（（2 2）采用动态数组实现采用动态数组实现3 3））STLSTL的的listlist————提高要求）提高要求）12 1234345656^ ^7878* 10* 101 1232345456767^ ^8080实现提示实现提示【【假设假设】】每个元素或节点最多存储数据的每个元素或节点最多存储数据的2 2位位数值• • 每个节点每个节点存储三位数据存储三位数据，， • • 进行运算时，从头节点开始乘，所得数据暂存在节点进行运算时，从头节点开始乘，所得数据暂存在节点datadata域域中，中， • • 如果它大于如果它大于999999，则向前进位，进位为，则向前进位，进位为data/1000data/1000，， • • 如果前位为空，则新建一个节点，新建节点的如果前位为空，则新建一个节点，新建节点的datadata为该为该 data/1000data/1000，， • • 只要某一位有进位，则从该点依次向检查，如果因加了进位只要某一位有进位，则从该点依次向检查，如果因加了进位 后使自己后使自己datadata大于大于999999，则继续向前进位，直到每位节点数据，则继续向前进位，直到每位节点数据 都小于都小于999999，，• •【【注意注意】】输出结果时：如果节点数据域的值不足三位，应注输出结果时：如果节点数据域的值不足三位，应注 意在前补意在前补0 0以补足三位。

以补足三位实现提示实现提示1 1、数据结构：不带表头节点的、数据结构：不带表头节点的双双 向链表向链表^1^firstfirstcurrentcurrent2 2、某一状态下的计算过程分析、某一状态下的计算过程分析^^currentcurrent…………current->data>999current->data>999头节点，插入新节点头节点，插入新节点非头节点，直接进位非头节点，直接进位当前节点当前节点前一节点前一节点。