大数阶乘数据结构算法课程设计 副本.doc

实习题目一 线性表及其应用 【问题描述】 大数运算——计算n的阶乘（n=20）。 【基本要求】 （1）数据的表示和存储； （1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求； （1.2） 试设计合适的存储结构，要求每个元素或节点最多存储数据的3位数值。 （2）数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。 【实现提示】 （1）设计数据的存储结构： 介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或节点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。 （2） 数据的操作及其实现： （2.1）累积运算的特点是当前的计算结果是下次乘法运算的乘数； （2.2）实现两个数的乘法运算须考虑： （1）乘数的各位数都要与被乘数进行乘法运算； （2）乘法过程中的进位问题及其实现； （3）因每个元素或节点最多存储数据的3位数值，故当元素或节点中的数值大于999，需向前一个元素或节点进位。 【实现结构】 （1）采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。 （2）采用动态数组实现。 【实现程序】 #include stdafx.h #include iostream using namespace std; templateclass T class Chain; templateclass T class ChainNode { friend ChainT; private: T data; ChainNodeT *link; }; templateclass T class Chain { public: Chain(){first=0;}; ~Chain(); bool IsEmpty()const{return first==0;} int Length()const; bool Find(int k,Tx) ; ChainTInsert(int k,const Tx); ChainT Change(int k,T x); ChainT Delete(int k, T x); ChainT Search(const Tx)const; int OutPut(); private: ChainNodeT*first; }; /**************析构函数（删除链表的所有节点）********************/ templateclass T ChainT::~Chain() { ChainNodeT*next; while(first) { next=first-link; delete first; first=next; } } /**********************确定链表的长度*****************************/ templateclass T int ChainT::Length()const { ChainNodeT*current=first; int len=0; while(current) { len++; current=current-link; } return len; } /*********************在链表中查找第K个元素*************************/ templateclass T bool ChainT::Find(int k,T x) { ChainNodeT*current=first; int index=0; while(indexkcurrent) { current=current-link; index++; } if(current) {x=current-data;return true;} return false; } /*********************向链表中插入元素*************************/ templateclass T ChainT ChainT::Insert(int k,const Tx) { Cha