数据结构--线性表的基本运算及多项式的算术运算

数据结构:线性表的基本运算及多项式的算术运算一、 实验目的和要求实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境(实验设备)X64架构计算机一台，Windows 7操作系统，IDE: Dev C+ 5.11编译器: gcc 4.9.2 64bit二、 实验原理及内容程序一：实现顺序表和单链表的实现本程序包含了四个文件，分别是LinearListMain.cpp，linearlist.h，seqlist.h，singlelist.h。分别是主程序，线性表抽象类，顺序储存线性表的实现，链表储存顺序表的实现。文件之间的关系图：本程序一共包含了三个类：分别是LinearList（线性表抽象类），SeqList（顺序储存的线性表），SingleList（链表储存的线性表）。 类与类之间的关系图如下：其实，抽象类LinearList规定了公共接口。分别派生了SeqList类和SingleList。SingleList类与SingleList类分别实现了LinearList类中的所有接口。程序代码以及分析：Linearlist类：#include using namespace std;template class LinearList protected: int n; /线性表的长度 public: virtual bool IsEmpty() const=0; /判读是否是空线性表 virtual int Length() const=0; /返回长度 virtual bool Find(int i,T& x) const=0; /将下标为i的元素储存在x中，成功返回true，否则返回false virtual int Search(T x) const=0; /寻找值是x的元素，找到返回true，否则返回false virtual bool Insert(int i,T x)=0; /在下标为i的元素后面插入x virtual bool Delete(int i)=0; /删除下标为i的元素 virtual bool Update(int i,T x)=0;/将下标为i的元素更新为x virtual void Output(ostream& out)const=0; /将线性表送至输出流;包含了一个保护数据成员n，和8种运算，具体说明见注释。实 验 报 告Seqlist类：template class SeqList:public LinearListprotected: int maxLength; /顺序表的最大长度 T *elements; /动态一维数组的指针 int n;public:SeqList(int mSize); /构造函数 SeqList() delete elements; /析构函数 bool IsEmpty() const; int Length() const; bool Find(int i,T& x) const; int Search(T x) const; bool Insert(int i,T x); bool Delete(int i); bool Update(int i,T x); void Output(ostream& out)const ; ;实 验 报 告核心算法：Search函数：算法分析：Search函数功能是查找值是x的元素，返回下标，不存在返回-1；本程序采用从第一个元素依次遍历的方法，时间复杂度为O（n）。代码：template int SeqList:Search(T x) constint i;for(i=0;in;i+)if(elementsi=x)break;if(i=n) /没有找到return -1;Else /找到return i;Insert（）函数：算法分析：对每一个i要先判断是否越界，然后判断是否有剩余空间可以插入；符合条件之后依次后移元素，腾出空间将x插在i+1的位置。时间复杂度是O（n）。代码：template bool SeqList:Insert(int i,T x)if(i=n) /判断越界coutout of boundsendl;return false;if(n=maxLength) /判断剩余空间是否充足coutoverflowi+1;j-) /移位操作elementsj=elementsj-1;elementsi+1=x; /插入n+; /元素总数+1return true;Delete（）函数：算法分析：首先判断链表是否是空链表，再判断下标是否越界。符合条件后，从i+1的位置依次向前移动一个位置，再将总数n减1.算法时间复杂度是O （n）代码：template bool SeqList:Delete(int i)if(n=0)coutUnderflowendl;return false;if(i=n)coutout of boundsendl;return false;for(int j=i;jn-1;j+)elementsj=elementsj+1;n-;return true;SingleList 类：template class SingleList; /提前声明singlelist类，结点类中用到template class node /结点类protected:T element;node* link;friend class SingleList;template class SingleList:public LinearListprivate:node* first; /头指针int n;public: SingleList() first=NULL; n=0; /构造函数 SingleList(); bool IsEmpty() const; int Length() const; bool Find(int i,T& x) const; int Search(T x) const; bool Insert(int i,T x); bool Delete(int i); bool Update(int i,T x); void Output(ostream& out)const; ;核心算法：Find函数：算法分析：首先判断下标是不是越界，然后定义临时变量j用来计数，标记当前遍历位置的下标，到达下标i是停止，并赋值给x。时间复杂度是O（n）代码：template bool SingleList:Find(int i,T& x) constif(i=n)coutout of boundsendl;return false;node* p=first;int j=0;while(jlink;j+;x= p-element;return true;Search函数：算法分析：首先定义指针p和标记位置下标的j。然后从first依次遍历，每次遍历j加1，以此来标记当前位置的下标，一旦遍历到了x，则返回下标。如果到尾节点还没有遍历到，则不存在x，返回-1；时间复杂度是O（n）代码：template int SingleList:Search(T x) constnode* p;p=first;int j=0;while(p)if(p-element=x)return j;j+;p=p-link;return -1;Insert函数：算法分析：首先判断下标是否越界，然后分两种情况进行插入，第一种情况是插入到第一个元素，需要修改first指针，第二种情况是插入到下标不是0的情况，需要先遍历到插入下标的前一个位置，然后将这个位置的link指针赋值给新申请的空间，然后修改这个结点link指针，使它指向新申请的空间。再对新申请的空间的element赋值。因为要遍历到下标所在位置，所以时间复杂度是O（n）。代码：template bool SingleList:Insert(int i,T x)if(i=n)coutout of boundsendl;return false;if(i=-1)node* p=new node;p-link=first;first=p;first-element=x;n+;return true;int j=0;node* q=first;while(jlink;j+;node* p=new node;p-link=q-link;p-element=x;q-link=p;n+;return true;Delete函数：算法分析：首先判断是否是空链表，在判断下边是否越界。然后分两种情况进行删除，第一种情况是删除第一个元素，需要修改first指针，第二种情况是删除下标不是0的情况，需要先遍历到删除下标的前一个位置，然后将这个位置的link指针指向下下个节点，然后删除下一个节点，期间需要先保存下个节点的地址。因为要遍历到下标所在位置，所以时间复杂度是O（n）。代码：template bool SeqList:Delete(int i)if(n=0)coutUnderflowendl;return false;if(i=n)coutout of boundsendl;return false;for(int j=i;jn-1;j+)elementsj=elementsj+1;n-;return true;实验测试与调试：Main 函数：int main()SeqList LObj(50);coutLObj.IsEmpty(): LObj.IsEmpty()endl;coutLObj.Length(): LObj.Length()endl;cout Here end OK.endl;return 0;程序运行结果：LObj.IsEmpty():1LObj.Length():0Here end OK.分析：正确程序二：多项式的加法和乘法算术运算本程序包含三个文件main.cpp, Polynominal.h, Term.h。文件之间的关系图如下:程序包含两个类，项结点类和多项式类，二者为组合关系。其中，多项式由项结点组成。Polynominal是Term类的友元类。程序代码以及分析：Term 类：class Termpublic:Term(int c,int e);Term(int c,int e,Term* next);Term* InsertAfter(int c,int e);private:int coef; /每一项的系数int exp; /每一项的指数Term* link; /指向下一个结点的指针friend ostream& operator(ostream &out,const Term &a); /重载输出运算符号friend class Polynominal; /友元声明; 核心算法：InsertAfter函数InsertAfter的功能是在当前对象后面插入一个对象。首先以系数，指数和当前对象的link为参数动态申请一个新的空间，然后将返回的新空间地址赋值给当前对象的link。完成插入。代码：Term* Term:InsertAfter(int c,int e)link=new Term(c,e,link);return link;输出运算符重载：输出时，要判断系数和指数，具体如下：代码：ostream& operator(ostream &out,const Term& a)if(a.coef=0)return out;outa.coef;if(a.exp=0)return out;if(a.exp=1)outX;return out;outXa.exp;return out;多项式Polynominal类：class Polynominalpublic:Polynominal(); /构造函数Polynominal(); /析构函数void AddTerms(istream& in); /输入多项式void OutPut(ostream& out)const; /输出多项式void PolyAdd(Polynominal& r); /多项式相加void PolyX(Polynominal& r); /多项式相乘void Copy(Polynominal& r); /多项式赋值拷贝friend ostream& operator(istream& in,Polynominal& r); /重载输入运算符friend Polynominal& operator+(Polynominal& a,Polynominal& b);/重载加号运算符friend Polynominal& operator*(Polynominal& a,Polynominal& b); /重载乘号运算符private:Term* theList; /多项式的头结点;核心算法：PolyAdd函数：算法分析：整体思路为将传入参数的每一项一个一个的插入到当前对象中，插入时要考虑指数相等的情况下系数相加，系数相加后为0要删除这个项，指数不相等直接插入。通过一个指向参数r的项的指针p的移动来实现每一项的插入，q的移动来判断指数。由于输入时是按照指数从大到小，所以q可以接着上次的移动继续移动，不需要复位，也由此降低了时间复杂度。p和q 指针只需要分别遍历一遍，所以整体时间复杂度是O（n）。代码：void Polynominal:PolyAdd(Polynominal& r)Term *p,*q,*q1;p=r.theList-link;q=theList;while(p-exp=0)while(q-link-expp-exp)q=q-link;if(q-link-exp=p-exp)q-link-coef=q-link-coef+p-coef;if(q-link-coef=0)Term *tmp=q-link;q-link=q-link-link;delete tmp;elseq-InsertAfter(p-coef,p-exp);p=p-link;Copy函数：算法分析：首先清空当前对象的结点，保留表头结点。对参数r多项式中的每一项，用Insertafter函数插入到当前对象中。由于Term中的InsertAfter函数，并且带返回值，所以插入变得很简单，最后当前对象 尾节点赋值为thelist，完成循环链表。删除和插入分别只要循环当前对象和参数对象，所以时间复杂度是O（n）代码：void Polynominal:Copy(Polynominal& r)Term* p=theList-link;while(p!=theList)theList-link=p-link;delete p;p=theList-link;p=theList;Term *q=r.theList-link;while(q-exp=0)p=p-InsertAfter(q-coef,q-exp);q=q-link;p-link=theList;PolyX函数：算法分析： 整体思路：首先定义一个临时多项式对象tmp，用来存相乘之后的结果。根据乘法分配律将两个多项式相乘的结果保存在tmp中，由于两层循环这步的时间复杂度是O（m*n）。然后采用选择排序法对tmp中的项按照指数从大到小排序，排序交换项的时候由于是链表结构，所以只交换系数和指数的值，链接和原来的结构不变。之所以采用选择排序而不是冒泡排序，是因为冒泡排序需要双向移动指针，而这个是单向链表，排序时间复杂度是O（n2）。最后考虑拆分项同类项的合并。如果指数相同，则将系数相加，如果相加得0，则删除这一项，具体实现时候可以采用一个指针两两操作。这一步时间复杂度是O（n）。最后将tmp用Copy函数复制到当前对象。因为tmp是个局部变量，所以函数结束会自动析构，不需要担心内存泄漏问题。综上，整体时间复杂度是max(O(m*n),O(n2);代码：void Polynominal:PolyX(Polynominal& r)Polynominal tmp;Term *p,*q,*t