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

数据结构:线性表的基本运算及多项式的算术运算一、实验目的和要求实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境（实验设备）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 (抽象类) istmpxyjLength。Findfint i,T& xSearchfT x)Insert(int ifT x) Delete(int i) Update(int irT x).cut)SeqListint maxLength;T *elements;int n;SeqList(int mSize);-SeqListQSingleListnode （结点类）node<T>* first; int n;友兀类一T element; node<T>* link;SingleList() -SingleListQ其实，抽象类LinearList规定了公共接口。分别派生了 SeqList类和SingleList。SingleList类与SingleList类分别实现了 LinearList类中的所有接口。程序代码以及分析：Linearlist 类：#include <iostream>using namespace std;template <class T>class LinearListprotected: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，否则返回falsevirtual int Search(T x) const=0; /寻找值是 x 的元素，找到 返回true，否则返回falsevirtual bool Insert(int i,T x)=0; 在下标为 i 的元素后面插virtual bool Delete(int i)=0;删除下标为 i 的元素virtual bool Update(int i,T x)=0;/将下标为 i 的元素更新为 xvirtual void Output(ostream& out)const=0; /将线性表送至输 出流;包含了一个保护数据成员n,和8种运算，具体说明见注释。实验报告Seqlist 类：template <class T>class SeqList:public LinearList<T>protected: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函数算去流程图算法分析：Search函数功能是查找值是x的元素，返回下标，不存在返回-1；本程序采用从第一个元素依次遍历的方法，时间复杂度为O（n）。代码：template <class T>int SeqList<T>:Search(T x) const(int i;for(i=0;i<n;i+)(if(elementsi=x)(break;if(i=n)没有找到(return -1;Else找到(return i;Insert ()函数:insert算法分析:对每一个i要先判断是否越界，然后判断是否有剩余空间可以插入；符合条 件之后依次后移元素，腾出空间将x插在i+1的位置。时间复杂度是O（n）。代码:template <class T>bool SeqList<T>:Insert(int i,T x)(if(i<-1|i>=n)判断越界(cout<<"out of bounds"<<endl;return false;if(n=maxLength) /判断剩余空间是否充足(cout<<"overflow"<<endl;return false;for(int j=n;j>i+1;j-) /移位操作(elementsj=elementsj-1;elementsi+1=x; /插入n+;元素总数+1return true;Delete ()函数:否返回ruedel eteQ函数浙睢图算法分析:首先判断链表是否是空链表，再判断下标是否越界。符合条件后，从i + 1的 位置依次向前移动一个位置，再将总数n减1.算法时间复杂度是O （n）代码:template <class T>bool SeqList<T>:Delete(int i)(if(n=0)(cout<<Underflow<<endl;return false;if(i<0|i>=n)(cout<<"out of bounds"<<endl;return false;for(int j=i;j<n-1;j+)(elementsj=elementsj+1;n-;return true;SingleList 类: template <class T>class SingleList; 提前声明singlelist类，结点类中用到 template <class T>class node /结点类protected:T element;node<T>* link;friend class SingleList<T>template <class T>class SingleList:public LinearList<T>private:node<T>* 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函数:是输出下标越界信息 返回 false<>find函数流程图算法分析：首先判断下标是不是越界，然后定义临时变量j用来计数，标记当前遍历位置的下标，到达下标i是停止，并赋值给x。时间复杂度是O(n)代码：template <class T>bool SingleList<T>:Find(int i,T& x) constif(i<0|i>=n)cout<<"out of bounds"<<endl;return false;node<T>* p=first;int j=0;while(j<i)p=p->link;j+;P是否为空否P对应的元素;否是XSearch 函数:p=firstj=O算法分析:首先定义指针p和标记位置下标的j。然后从first依次遍历，每次遍历j加定义II的指针p , I临时变 蜀，用来标记当前位置x= p->element;return true;j+ rP后移T位 置返回下桐)1，以此来标记当前位置的下标，一旦遍历到了 x，则返回下标。如果到尾节点还没有遍历到，则不存在x，返回-1 ；时间复杂度是O(n)T未找到返 回)代码:template <class T>int SingleList<T>:Search(T x) constnode<T>* p;p=first;int j=0;while(p)(if(p->element=x)(return j;j+;p=p->link;return -1;Insert 函数:下时界？输出提示r返回 false下时界？改动头曰点j 插入元素、o?,定义指针q遍历到 带插入位置修改link ,插入元素返回true算法分析：首先判断下标是否越界，然后分两种情况进行插入，第一种情况是插入到第 一个元素，需要修改first指针，第二种情况是插入到下标不是0的情况， 需要先遍历到插入下标的前一个位置，然后将这个位置的link指针赋值给新 申请的空间，然后修改这个结点link指针，使它指向新申请的空间。再对新 申请的空间的element赋值。因为要遍历到下标所在位置，所以时间复杂度 是 O (n)。代码：template <class T>bool SingleList<T>:Insert(int i,T x)(if(i<-1|i>=n)(cout<<"out of bounds"<<endl;return false;if(i=-1)(node<T>* p=new node<T>p->link=first;first=p;first->element=x;n+;return true;int j=0;node<T>* q=first;while(j<i)(q=q->link;j+;node<T>* p=new node<T>p->link=q->link;p->element=x;q->link=p;n+;return true;Delete 函数:定义指针q遍历到 待删除位置修改link ,删除元素算法分析：首先判断是否是空链表，在判断下边是否越界。然后分两种情况进行删除，第一种情况是删除第一个元素，需要修改first指针，第二种情况是删除下 标不是0的情况，需要先遍历到删除下标的前一个位置，然后将这个位置的 link指针指向下下个节点，然后删除下一个节点，期间需要先保存下个节点 的地址。因为要遍历到下标所在位置，所以时间复杂度是O（n）。代码：template <class T>bool SeqList<T>:Delete(int i)(if(n=0)(cout<<"Underflow"<<endl;return false;if(i<0|i>=n)(cout<<"out of bounds"<<endl;return false;for(int j=i;j<n-1;j+)(elementsj=elementsj+1;n-;return true;实验测试与调试：Main函数：int main()(SeqList<int> LObj(50);cout<<"LObj.IsEmpty(): "<<LObj.IsEmpty()<<endl;cout<<"LObj.Length(): "<<LObj.Length()<<endl;cout<<" Here end OK."<<endl;return 0;程序运行结果：LObj.IsEmpty():1LObj.Length():0Here end OK.分析：正确程序二：多项式的加法和乘法算术运算本程序包含三个文件main.cpp, Polynominal.h, Term.h。文件之间的关系图如下：main.cpp凋用Polynominal .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;out<<a.coef;if(a.exp=0)return out;if(a.exp=1)out<<"X"return out;out<<"XAn<<a.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<<(ostream& out,const Polynominal& r); 重载输出 运算符friend istream& operator>>(istream& in,Polynominal& r); /重载输入运算符friend Polynominal& operator+(Polynominal& a,Polynominal& b);/重载加号 运算符friend Polynominal& operator*(Polynominal& a,Polynominal& b); 重载乘号运算符private:Term* theList;多项式的头结点;核心算法：PolyAdd 函数:开始P指向对象的指数判断系数和是 不是。判断他们指教是否 相等结束相等在当前多项式中找到不太于p对 成指数的第一?点混撒十pqp指向参数r的第一T对象 q指向当前对盆的thelistp成f插入当前对象 结系数相加，保 存在当前对象 中删除当前项算法分析：整体思路为将传入参数的每一项一个一个的插入到当前对象中，插入时 要考虑指数相等的情况下系数相加，系数相加后为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->exp>p->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;心e顷；elseq->InsertAfter(p->coef,p->exp);k;Copy函数：算法分析: 首先清空当前对象的结点，保留表头结点。对参数r多项式中的每一项，用Insertafter函数插入到当前对象中。由于Term中的InsertAfter函数，并 且带返回值，所以插入变得很简单，最后当前对象尾节点赋值为thelist， 完成循环链表。删除和插入分别只要循环当前对象和参数对象，所以时间复 杂度是O（n） 代码: void Polynominal:Copy(Polynominal& r)PolyX函数:开始采用乘法配律,】湘乘两项拆 分,存至1NI朝多项式tmp中1用噂排序法捋tmp按指tT大到舛E序从前往后检查有没有指数相同的 项r有日赫合并，合并为0的话册 除将tmp用 copy函数篡 制到当前对象结束算法分析:整体思路：首先定义一个临时多项式对象tmp,用来存相乘之后的结果。根 据乘法分配律将两个多项式相乘的结果保存在tmp中，由于两层循环这步的 时间复杂度是O（m*n）。然后采用选择排序法对tmp中的项按照指数从大到小排序，排序 交换项的时候由于是链表结构，所以只交换系数和指数的值，链接和原来的 结构不变。之所以采用选择排序而不是冒泡排序，是因为冒泡排序需要双向 移动指针，而这个是单向链表，排序时间复杂度是O(矽2)。最后考虑拆分 项同类项的合并。如果指数相同，则将系数相加，如果相加得0，则删除这一 项，具体实现时候可以采用一个指针两两操作。这一步时间复杂度是O(n)。 最后将tmp用Copy函数复制到当前对象。因为tmp是个局部变量，所以函数 结束会自动析构，不需要担心内存泄漏问题。综上，整体时间复杂度是 max(O(m*n),O(nA2);代码：void Polynominal:PolyX(Polynominal& r)Polynominal tmp;Term *p,*q,*t;p=theList->link;q=r.theList->link;t=tmp.theList;while(p->exp>=0)q=r.theList->link;while(q->exp>=0)t=t->InsertAfter(p->coef*q->coef,p->exp+q->exp);q=q->link;测试与调试： 输入数据：3 14 -8 8 6 2 2 0 0 -1 输出：The polynominal is:3X"14-8X"8+6X”2+2输入：2 104 8-6 20 -1输出：The polynominal is:2X"10+4X"8-6X"2The polynominal is:3X"14+2X"10-4X"8+2输入： 1 2 0 -1输出：The polynominal is:1X"2The polynominal is:3X"16+2X"12-4X"10+2X"2 结果： 正确实验报告