数据结构上机报告-实现一元多项式抽象数据类型.doc

数据结构上机实习报告数据结构上机实习报告 第一次上机实习题目 实现一元多项式抽象数据类型 班级： 121141 姓名： 王庆涛 学号： 20141002513指导老师： 郭艳完成日期： 2016.04.211、 需求分析1.1问题描述和规格说明已知一元n次多项式：设计程序实现一元n次多项式的抽象数据类型，模拟一元n次多项式的操作行为。包括：数据元素：ai，存储结构，逻辑操作：1、构造一个空的多项式2、多项式插入新的一项3、多项式合并同类项4、多项式的加法Pn(x)+Qn(x)=Rt(x)5、多项式的乘法Pn(x)*Qn(x)=Rt(x)6、打印多项式7、计算多项式的值 1.2功能需求1)首先构造两三个多项式供用户使用；2)用户可以进行添加多项式或是添加多项式中的项；3)或是修改其中的项，或是对多项式进行删除，或仅仅删除其中的某项；4)或是查看当前的某项多项式5) 用户赋予多项式变量x值后可以计算多项式的值6)可以计算两个或是多个多项式的和；7)可以计算两个以上多项式的乘积8)可以对多项式中的同类项进行合并2、设计(目标：有效组织与处理数据)2.1抽象数据类型:因为每个多项式有n个项，每个项包含不同的系数和指数， 多项式的系数ai抽象为整数，变量x也是整数，x的次幂n也是整数，故多项式的每一项抽象为一个Nape类型的节点，包括：ai、x、n数据元素，最后整个一元n次多项式抽象为Polynomial数据类型。详细设计如下：Nope类型设计为：class Nopefriend class Polynomial; /设置Polynomial为Nope的友元类，方便Polynomial类访问Nope的私有数据成员private:int m_factor; /项系数int m_times; /次幂public:Nope(int factor=0,int times=0);/构造函数Nope();int GetFoctor()const; /获取项系数int GetTimes()const; /获取次幂void SetFactor(int factor); /设置项系数void SetTimes(int times); /设置次幂Nope & operator=(const Nope& item); /赋值=int operator=(const Nope& item); /比较=/比较次幂的大小friend ostream &operator(ostream& out, const Nope&item); /输出Nope(const Nope& item); /复制构造&;Polynoomial数据类型设计为：class Polynomialprivate:int m_x; /多项式中的变量xint m_size; /多项式的项数LinListWithRear m_list; /存储多项式的带尾指针的单向链表public:Polynomial(int size = 0,int factor= 1);/可以构造系数为factor，个数为size的多项式，次幂依次增长Polynomial();Polynomial(const Polynomial&poly);int GetM_size()const; /获取多项式的项数int GetM_x()const;int GetM_factor(const int& index)const; /获取第index项的系数/从第1项开始（而不是第0项）int GetM_times(const int& index)const; /获取第index项的次幂inline double GetM_Number(const int& index)const; /获取第index项的值,因为计算多项式的值时频繁调用，所以设计为内联函数int Getfactor(const int& times)const; /获取次幂为times的项的系数 /失败或没有，返回0int GetIndex(const int& times)const; /获取次幂为times的项的下标/从1开始double GetNumber(const int& times)const; /获取次幂为times的项的值 /失败或没有 返回0double GetTotalNumber()const; /获取整个多项式的值int SetM_factor(const int& index,const int& factor); /设置第index项的系数/从第1项开始（而不是第0项）int Setfactor(const int& times,const int& factor); /设置次幂为times的项的系数/失败返回0int SetM_times(const int& index, const int& times); /设置次幂为times的项的系数/失败返回0int SetM_x(const int & x); /给未知数m_x赋值bool DeleteIndex(const int & index); /删除第index项bool DeleteTimes(const int & times); /删除次幂为times的项bool DeleteFactor(const int& factor); /删除所有系数为factor的项inline int InsertEnd(const int& factor, const int& times); /从尾部插入新项，系数为factor，次数为times/失败返回0inline void InsertEnd(const Nope& item);Polynomial& operator=(const Polynomial&Poly); /赋值void Combine(); /合并同类项且按次幂排序void Print()const; /打印多项式void OrderPolynomial(); /按次幂排序多项式int OrderInsert(const int& factor, const int& times); /有序插入新项，系数为factor，次数为times/失败返回0Polynomial operator+(const Polynomial&polyb); /多项式的加法Polynomial operator*(const Polynomial&polyb); /多项式的乘法friend ostream &operator(ostream& out, const Polynomial& item); /输出;2.2存储结构设计： 1)存储结构的确定数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析一元n次多项式逻辑操作的特点和指针所占空间比例，然后确定最优的存储结构。a) 确定采用链式存储结构1. n次多项式在构造时频繁执行插入操作，在程序运行阶段频繁执行删除或修改操作，且多项式的项数n不能确定，用户对项数n的需求变化大。2. 如果采用链表，指针存储开销和整个结点内容所占空间相比，其比例较小综上所述，认为不采用顺序表，而采用链表。b) 选择哪种链式存储结构？1. 多项式在构造时可能经常在尾部插入或是在尾部修改数据，因此增设尾指针，尾指针始终指向链表的尾部结点。 通过增设尾指针，在表尾插入的算法时间复杂度为O（1）。综上所述，采用带尾指针的链表存储结构。2)设计带尾指针的单链表a) 结构描述b) 逻辑操作设带尾指针的循环单链表类型名为ListCWithRear，L 是ListCWithRear 型。通过分析n次多项式的抽象数据类型，进一步确定带尾指针的单链表的逻辑操作如下所示：1. LinListCWithRear(L)/初始化2. IsEmpty(L)/ 判断是否是空表。如果表为空，返回0，否则返回1。3. InsertEnd(L, x) /在表尾插入新结点x。插入成功返回1，失败返回0。5. LinListCWithRear(L)/ 撤销单链表6. void OrderInsert(const T& x);/单链表的有序插入7.int SetItem(const T& item,const int &pos); /修改第pos个节点的数据8.void OrderList();/单链表内元素按=符合排序2.3算法设计void LinListWithRear:OrderInsert(const T& x) /有序插入数据元素xListNode *curr, *pre; curr = head-next;/curr指向首元结点pre = head;/pre指向头结点while (curr != NULL & curr-data = x)/*next;ListNode *q = new ListNode(x, pre-next);/申请一个结点并赋值pre-next = q;/把新结点插入在pre所指结点后if (curr = NULL)rear = q;/尾指针始终指向链尾size+;/表长加1/*算法时间复杂度分析：很明显，这个函数基本语句的执行次数是f(n)=n，故时间复杂度T(n) = O(n);*/void LinListWithRear:OrderList()ListNode *curr= head;/curr指向头结点while (curr-next != NULL)/= 比较符ListNode*second = curr-next;/指向下一个节点while (second-next != NULL)/= 比较符ListNode*third = second-next;/指向下一个节点if (curr-next-data data) /继续往下搜索second = second-next;else /third掉链，接在curr后面second-next = second-next-next;third-next = curr-next;curr-next = third;curr = curr-next;rear = curr;/*算法时间复杂度分析：很明显，这个函数基本语句的执行次数是f()=n+n-1+n-2+.+2+1=(n-1)*n/2，故时间复杂度T(n) = O(n*n);*/Polynomial类：Polynomial Polynomial:operator+(const Polynomial&polyb) /多项式加法/Polynomial polyc; /局部变量，用于存储相加的结果if (m_size + polyb.m_size = 0)return polyc;ListNode *pa = m_list.head; /获取第一个节点/pa指向头指针ListNode *pb = polyb.m_list.head;while (pa-Next() != NULL) polyc.InsertEnd(pa-Next()-Data().m_factor, pa-Next()-Data().m_times); /从尾部插入pa = pa-Next(); /pa指向La的下一个元素while (pb-Next() != NULL)polyc.InsertEnd(pb-Next()-Data().m_factor, pb-Next()-Data().m_times);pb = pb-Next(); /pb指向Lb的下一个元素polyc.Combine(); /合并同类项return polyc; /返回相加结果/*算法时间复杂度分析：很明显，这个函数基本语句的执行次数是f()=n+n=2n，故时间复杂度T(n) = O(n);*/Polynomial Polynomial:operator*(const Polynomial&polyb) /多项式乘法if (m_size = 0|polyb.m_size=0)return *this;Combine(); /先将当前多项式合并同类项以减少乘法时间复杂度Polynomial polyc;ListNode *pa = m_list.head; /获取第一个节点/pa指向头指针ListNode *pb = polyb.m_list.head;while (pa-Next() != NULL ) Nope tempa(pa-Next()-Data();while (pb-Next() != NULL)Nope tempb(pb-Next()-Data();polyc.InsertEnd(tempa.m_factor*tempb.m_factor, tempa.m_times+tempb.m_times);pb = pb-Next(); /pb指向Lb的下一个元素pa = pa-Next(); /pa指向La的下一个元素polyc.Combine();/ 将相乘结果合并同类项再返回return polyc;/*算法时间复杂度分析：很明显，这个函数基本语句的执行次数是f()=n+n+n+n+.+n+n=n*n，故时间复杂度T(n) = O(n*n);如果考虑InsertEnd(i);函数的执行次数也为T(n)=O(1)，即时间复杂度仍然为T(n)=O(n*n);*/void Polynomial:Combine() /合并同类项且ListNode *pa = m_list.Index(1); /获取第一个数据节点int index1 = 0;while (pa-Next() != NULL) index1+;int index2 = 0;ListNode *pb = pa;Nope tempa(pa-Data(); while(pb-Next()!=NULL)index2+;Nope tempb(pb-Next()-Data();if (tempa.m_times = tempb.m_times)tempa.SetFactor(tempa.m_factor + tempb.m_factor);pa-SetData(tempa);/pb = pb-Next()-Next();m_list.Delete(index1 + index2);m_size-;index2-; /删除一个else pb = pb-Next(); /pb指向Lb的下一个元素pa = pa-Next(); /pa指向La的下一个元素/*算法时间复杂度分析：很明显，这个函数基本语句的执行次数是f(n)=n+n-1+n-2+.+1=(n+1)*n/2，故时间复杂度T(n) = O(n的2次方);*/2.4模块及调用关系文件包含关系调试类结构：多项式类结构：3、使用说明1 本程序运行在windows 系列的操作系统下，执行文件为：ADT Polynomial.exe。2. 用户需严格按照用户界面的输入提示说明输入数据进行测试使用。3 在 使用中输入的选择项数请从第一项开始算起，而不是第零项。除非界面提示可以输入；否则可能引起访问越界导致程序退出！4 输出结果表示多项式的当前结构，格式为Pn(x)= a*pow(x,y1 ) + b*pow(x,y2)+.Pow(x,y)表示x的y次方，a，b表示项的项数5.只有当给多项式的变量x赋值之后才可以求出多项式的总值，否则求值为0；4、调试分析1.在看课本时我一直以为链表的head指针是另外一个单独的指针，head-next是头节点，head-next-next才是首元节点，所以写代码时出现了很多的错误，调试过程中才发现head是头指针，head-next就是首元节点，才算深刻认识了链表啊2.在测试类中我是用一个vector来装需要测试的多项式的，但是编译器却报错说我没有写构造函数/error C2558