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

《数据结构--线性表的基本运算及多项式的算术运算.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构:线性表的基本运算及多项式的算术运算一、实验目的和要求实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境(实验设备)X64架构计算机一台，Windows7操作系统，IDE:DevC++5.11编译器:gcc4.9.264bit二、实验原理及内容程序一：实现顺序表和单链表的实现本程序包含了四个文件，分别是LinearListMain.cpp，linearlist.h，seqlist.h，singlelist.h。分别是主程序，线性表抽象类，顺序储存线性表的实现，链表储存顺序表的实现。文件之

2、间的关系图：本程序一共包含了三个类：分别是LinearList（线性表抽象类），SeqList（顺序储存的线性表），SingleList（链表储存的线性表）。类与类之间的关系图如下：其实，抽象类LinearList规定了公共接口。分别派生了SeqList类和SingleList。SingleList类与SingleList类分别实现了LinearList类中的所有接口。程序代码以及分析：Linearlist类：#includeusingnamespacestd;templateclassLinearList{protected:intn;//线性表的长度pu

3、blic:virtualboolIsEmpty()const=0;//判读是否是空线性表virtualintLength()const=0;//返回长度virtualboolFind(inti,T&x)const=0;//将下标为i的元素储存在x中，成功返回true，否则返回falsevirtualintSearch(Tx)const=0;//寻找值是x的元素，找到返回true，否则返回falsevirtualboolInsert(inti,Tx)=0;//在下标为i的元素后面插入xvirtualboolDelete(inti)=0;//删除下标为i的元素virtualboolUpdate(i

4、nti,Tx)=0;//将下标为i的元素更新为xvirtualvoidOutput(ostream&out)const=0;//将线性表送至输出流};包含了一个保护数据成员n，和8种运算，具体说明见注释。实验报告Seqlist类：templateclassSeqList:publicLinearList{protected:intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针intn;public:SeqList(intmSize);//构造函数~SeqList(){delete[]elements;}//析构函数boolIsEmpt

5、y()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;};29实验报告核心算法：Search函数：算法分析：Search函数功能是查找值是x的元素，返回下标，不存在返回-1；本程序采用从第一个元素依次遍历的方法，时间复杂度为O（n）。代码：templateintSeqList::Search(Tx)const29{int

6、i;for(i=0;iboolSeqList::Insert(inti,Tx){if(i<-1

7、

8、i>=n)//判断越界{cout<<"outofbounds"<

9、gth)//判断剩余空间是否充足29{cout<<"overflow"<i+1;j--)//移位操作{elements[j]=elements[j-1];}elements[i+1]=x;//插入n++;//元素总数+1returntrue;}29Delete（）函数：算法分析：首先判断链表是否是空链表，再判断下标是否越界。符合条件后