《数据结构--线性表的基本运算及多项式的算术运算.docx》由会员分享,可在线阅读,更多相关《数据结构--线性表的基本运算及多项式的算术运算.docx(35页珍藏版)》请在三一办公上搜索。
1、数据结构:线性表的基本运算及多项式的算术运算一、实验目的和要求实现顺序表和单链表的基本运算,多项式的加法和乘法算术运算。要求:能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境(实验设备)X64架构计算机一台,Windows 7操作系统,IDE: Dev C+ 5.11编译器:gcc 4.9.2 64bit二、实验原理及内容程序一:实现顺序表和单链表的实现本程序包含了四个文件,分别是 LinearListMain.cpp,linearlist.h, seqlist.h,singlelist.h。分别是主程序,线性表抽象类,顺序储存线性表的实现,链表储 存顺序
2、表的实现。文件之间的关系图:本程序一共包含了三个类:分别是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 (结点
3、类)node* first; int n;友兀类一T element; node* link;SingleList() -SingleListQ其实,抽象类LinearList规定了公共接口。分别派生了 SeqList类和SingleList。SingleList类与SingleList类分别实现了 LinearList类中的所有接口。程序代码以及分析:Linearlist 类:#include using namespace std;template class LinearListprotected:int n; /线性表的长度public:virtual bool IsEmpty() c
4、onst=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
5、i,T x)=0;/将下标为 i 的元素更新为 xvirtual 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() con
6、st;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 int SeqList:Search(
7、T x) const(int i;for(i=0;in;i+)(if(elementsi=x)(break;if(i=n)没有找到(return -1;Else找到(return i;Insert ()函数: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) /判断剩余空间是否
8、充足(coutoverflowi+1;j-) /移位操作(elementsj=elementsj-1;elementsi+1=x; /插入n+;元素总数+1return true;Delete ()函数:否返回ruedel eteQ函数浙睢图算法分析:首先判断链表是否是空链表,再判断下标是否越界。符合条件后,从i + 1的 位置依次向前移动一个位置,再将总数n减1.算法时间复杂度是O (n)代码:template bool SeqList:Delete(int i)(if(n=0)(coutUnderflowendl;return false;if(i=n)(coutout of bounds
9、endl;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:
10、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函数:是输出下标越界信息 返回 falsefind函数流程图算法分析:首先判断下标是不是越界,然后定义临时变量j用来
11、计数,标记当前遍历位置的下标,到达下标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+;P是否为空否P对应的元素;否是XSearch 函数:p=firstj=O算法分析:首先定义指针p和标记位置下标的j。然后从first依次遍历,每次遍历j加定义II的指针p , I临时变 蜀,用来标记当前位置x= p-element;return true;j+
12、rP后移T位 置返回下桐)1,以此来标记当前位置的下标,一旦遍历到了 x,则返回下标。如果到尾节点还没有遍历到,则不存在x,返回-1 ;时间复杂度是O(n)T未找到返 回)代码: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 函数:下时界?输出提示r返回 false下时界?改动头曰点j 插入元素、o?,定义指针q遍历到 带插入位置修改link ,插入元素返回true算法分析:首先判断下标是
13、否越界,然后分两种情况进行插入,第一种情况是插入到第 一个元素,需要修改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-lin
14、k=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 函数:定义指针q遍历到 待删除位置修改link ,删除元素算法分析:首先判断是否是空链表,在判断下边是否越界。然后分两种情况进行删除,第一种情况是删除第一个元素,需要修改first指针,第二种情况是删除下 标不是0的情况,需要先遍历到删除下标的前一个位置,然后将这个位置的 link指
15、针指向下下个节点,然后删除下一个节点,期间需要先保存下个节点 的地址。因为要遍历到下标所在位置,所以时间复杂度是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(
16、): 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。文件之间的关系图如下:main.cpp凋用Polynominal .h程序包含两个类,项结点类和多项式类,二者为组合关系。其中,多项 式由项结点组成。Polynominal是Term类的友元类。
17、程序代码以及分析: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的功能是在当前对
18、象后面插入一个对象。首先以系数,指数和当前 对象的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
19、 out;outXAna.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(is
20、tream& 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指向当
21、前对盆的thelistp成f插入当前对象 结系数相加,保 存在当前对象 中删除当前项算法分析:整体思路为将传入参数的每一项一个一个的插入到当前对象中,插入时 要考虑指数相等的情况下系数相加,系数相加后为0要删除这个项,指 数不相等直接插入。通过一个指向参数r的项的指针p的移动来实现每 一项的插入,q的移动来判断指数。由于输入时是按照指数从大到小, 所以q可以接着上次的移动继续移动,不需要复位,也由此降低了时间 复杂度。p和q指针只需要分别遍历一遍,所以整体时间复杂度是O(n)。 代码:void Polynominal:PolyAdd(Polynominal& r)Term *p,*q,*q1;
22、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;心e顷;elseq-InsertAfter(p-coef,p-exp);k;Copy函数:算法分析: 首先清空当前对象的结点,保留表头结点。对参数r多项式中的每一项,用Insertafter函数插入到当前对象中。由于Term中的InsertAfte
23、r函数,并 且带返回值,所以插入变得很简单,最后当前对象尾节点赋值为thelist, 完成循环链表。删除和插入分别只要循环当前对象和参数对象,所以时间复 杂度是O(n) 代码: void Polynominal:Copy(Polynominal& r)PolyX函数:开始采用乘法配律,】湘乘两项拆 分,存至1NI朝多项式tmp中1用噂排序法捋tmp按指tT大到舛E序从前往后检查有没有指数相同的 项r有日赫合并,合并为0的话册 除将tmp用 copy函数篡 制到当前对象结束算法分析:整体思路:首先定义一个临时多项式对象tmp,用来存相乘之后的结果。根 据乘法分配律将两个多项式相乘的结果保存在tm
24、p中,由于两层循环这步的 时间复杂度是O(m*n)。然后采用选择排序法对tmp中的项按照指数从大到小排序,排序 交换项的时候由于是链表结构,所以只交换系数和指数的值,链接和原来的 结构不变。之所以采用选择排序而不是冒泡排序,是因为冒泡排序需要双向 移动指针,而这个是单向链表,排序时间复杂度是O(矽2)。最后考虑拆分 项同类项的合并。如果指数相同,则将系数相加,如果相加得0,则删除这一 项,具体实现时候可以采用一个指针两两操作。这一步时间复杂度是O(n)。 最后将tmp用Copy函数复制到当前对象。因为tmp是个局部变量,所以函数 结束会自动析构,不需要担心内存泄漏问题。综上,整体时间复杂度是
25、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:3X14-8X8+6X”2+2输入:2 104 8-6 20 -1输出:The polynominal is:2X10+4X8-6X2The polynominal is:3X14+2X10-4X8+2输入: 1 2 0 -1输出:The polynominal is:1X2The polynominal is:3X16+2X12-4X10+2X2 结果: 正确实验报告