数据结构作业多项式计算.docxVIP

实习报告题目：一元稀疏多项式计算器编译环境：Microsoft Visual Studio 2010功能实现：输入并建立多项式输出多项式并按指数降序排列多项式的相加与相减选作内容（1）：计算多项式在x处的值选作内容（2）：多项式求导需求分析本程序中，多项式系数定义为double型，多项式指数定义为int型。本程序执行方式：程序在终端上显示提示信息后，用户在键盘上输入运算命令；根据运算命令提示，用户按照规定的格式输入多项式；输出最终的运算结果。程序的测试数据：概要设计本程序采用单链表来存储多项式，链表中的每个节点存储着多项式中某一项的系数和指数。单链表中结点的定义：定义每个结点的数据项，包括多项式的系数和指数。struct item{double coef;//多项式系数intexp;//多项式指数};定义链表结点，List类（即链表类）可以访问每个结点。class ListNode {public:item data;//多项式内容ListNode *link;//链表指针//构造函数ListNode(){link = NULL;}ListNode( item *it, ListNode *next=NULL ){data.coef = it-coef;data.exp = it-exp;link = next;}friend class List;};本程序的基本算法设计：多项式的相加或者相减运算：两个多项式中所有指数相同的项对应系数相加或者相减，若和不为零，则构成结果多项式的一项，而所有指数不相同的那些项均被复制到结果多项式中。多项式求导算法：按照求导规则，对原链表中的每一个结点进行求导，将新生成的结点存储在结果多项式中。多项式赋值算法：对链表中的存储的多项式按照数学运算法则，进行数学运算，并返回相应的结果。详细设计List类的详细定义：class List {public:ListNode *first;//指向表头的指针int length;//链表长度List() { first = NULL; length = 0; };ListNode * FindNode( int i);//查找函数：查找链表中第i个元素item * GetNode( int i);//取值函数：返回链表中第i个元素的内容int InsertNode( item *value, int i );//插入函数：在链表的第i个位置插入一个结点void CreatList( int );//创建函数：创建一个链表void Sort();//排序函数：按照指数大小对元素进行排序void Disp();//显示函数：输出多项式double Calcu( double );//赋值函数：对多项式赋值void Clear();//清空函数：对链表置空};List类中主要成员函数的实现：查找函数：返回链表中第i个元素的地址。ListNode *List::FindNode(int i){if(i==0) return first;else if(i0) return NULL;else{ListNode *p = first-link;int j = 1;while (p!=NULLji){p = p-link;j++;}return p;}}取值函数：返回链表中第i个元素的内容。item * List::GetNode(int i){ListNode *p = FindNode(i);if(p==NULL)return NULL;else return (p-data);}插入函数：在链表的第i个位置插入一个结点。int List::InsertNode(item *value,int i){ListNode *p = FindNode(i-1);//查找第i-1个结点ListNode *tmp = NULL;if(first==NULL)//若链表为空，则构造新链表{first = new ListNode(value, NULL);length++;return 1;}if(p==NULL)//新结点作为头结点插入{tmp = first;p = new ListNode(value, NULL);first = p;p-link = tmp;length++;}else{//将新结点插入到第i个位置tmp = FindNode(i);ListNode *newnode = new ListNode(value,NULL);p-link = newnode;newnode-link = tmp;length++;}return 1;}创建函数：创建一个链表。void List::CreatList(int n){item t;int err=0;cou