数据基础及教程 23

2.5线性表的应用—两个多项式相加2.5.1问题描述多项式求两个多项式相加的程序例如，p(x)=2x3+3.2x5-6x+10，q(x)=6x+1.8x5-2x3+x2-2.5x4-5r(x)=5x5-2.5x4+x2+5r(x)=p(x)+q(x)1/39

两个多项式的数据分别存放在abc1.in和abc2.in文本文件中，要求相加的结果多项式的数据存放在abc.out文本文件中。4233.25-61100abc1.in文件p(x)=2x3+3.2x5-6x+106611.85-2312-2.54abc2.in文件q(x)=6x+1.8x5-2x3+x2-2.5x4-5第1个多项式: [[2.0,3],[3.2,5],[-6.0,1],[10.0,0]]排序后结果: [[3.2,5],[2.0,3],[-6.0,1],[10.0,0]]第2个多项式: [[6.0,1],[1.8,5],[-2.0,3],[1.0,2],[-2.5,4],[-5.0,0]]排序后结果: [[1.8,5],[-2.5,4],[-2.0,3],[1.0,2],[6.0,1],[-5.0,0]]相加多项式: [[5.0,5],[-2.5,4],[1.0,2],[5.0,0]]abc.out文件2/39(c1,e1)(c2,e2)…(cm,em)多项式项多项式线性表3/39ADTPolyClass{}

//多项式抽象数据类型

数据对象：PolyElem={(ci，ei)|1≤i≤n，ci∈float，ei∈int};

数据关系：r={<xi，yi>|xi，yi∈PolyElem，i=1，…，n-1}

基本运算：

初始化和销毁：分别用于建立空存储结构和释放其空间。

CreateList(fname)：从fname文件中读取数据建立多项式。

Sort()：对多项式按指数递减排序。

DispPoly()：输出多项式存储结构。}//ADTPolyClass4/392.5.2问题求解1.设计链式存储结构一个多项式用一个带头结点的单链表存储，每个结点存储一个每个多项式项[ci，ei]（其中ci为系数，ei为指数）5/39多项式结点类型PolyNodestructPolyNode{}

//多项式单链表结点类型doublecoef; //系数intexp; //指数PolyNode*next; //指向下一个结点的指针PolyNode():next(NULL){} //构造函数PolyNode(doublec,inte){} //重载构造函数coef=c;exp=e;next=NULL;}};6/39classPolyList { //多项式单链表类public:PolyNode*head; //多项式单链表的头结点指针

PolyList(){

//构造函数head=newPolyNode(); //建立头结点}~PolyList() {

//析构函数PolyNode*pre=head,*p=pre->next;while(p!=NULL){deletepre; pre=p;p=p->next; //pre、p指针同步后移}deletepre;}voidCreateList(char*fname);//读文件采用尾插法建立多项式单链表voidSort(); //对多项式单链表按exp域递减排序voidDispPoly(); //输出多项式单链表};设计多项式单链表类为PolyList，其中构造函数和析构函数的设计思路与2.3.2节单链表的完全相同。PolyList类的定义如下：7/39多项式p(x)=2x3+3.2x5-6x+10对应的单链表：2.0head33.25-6.0110.00∧8/39（1）创建多项式单链表CreateList(fname)voidCreateList(char*fname){//读文件采用尾插法建立多项式单链表freopen(fname,"r",stdin); //输入重定向到fname文件PolyNode*s,*r;doublec;intn,e;scanf("%d",&n);r=head; //r始终指向尾结点,开始时指向头结点for(inti=0;i<n;i++){scanf("%lf%d",&c,&e);s=newPolyNode(c,e); //创建新结点sr->next=s; //将结点s插入结点r之后r=s;}r->next=NULL; //尾结点next域置为NULL}2.设计PolyList的基本运算算法读文件+尾插法建表9/39（2）多项式单链表排序Sort()将结点p有序插入到有序子表2.0head33.25-6.0110.00∧p有序子表10/39voidSort(){ //对多项式单链表按exp域递减排序PolyNode*p,*pre,*q;q=head->next; //q指向开始结点if(q==NULL)return; //原单链表空时返回p=head->next->next; //p指向结点q的后继结点if(p==NULL)return; //原单链表只有一个数据结点时返回q->next=NULL; //构造只含一个数据结点的有序单链表while(p!=NULL){q=p->next; //q用于临时保存结点p后继结点pre=head; //从有序表开头比较while(pre->next!=NULL&&pre->next->exp>p->exp)

pre=pre->next;

//在有序表中查找插入结点p的前驱结点prep->next=pre->next; //在结点pre之后插入结点ppre->next=p;p=q; //继续处理原单链表余下的结点}}查找到第一个≤p->exp的位置的前驱结点pre11/39（3）输出多项式单链表DispPoly()voidDispPoly(){ //输出多项式单链表boolfirst=true; //first为true表示是第一项PolyNode*p=head->next; //p指向开始结点while(p!=NULL){ if(first){printf("[%.1lf,%d]",p->coef,p->exp);first=false;}elseprintf(",[%.1lf,%d]",p->coef,p->exp); p=p->next;}printf("\n");}12/39两个按指数递减排序的多项式单链表相加的结果多项式单链表二路归并+尾插法建表3.设计两个多项式单链表相加运算算法PolyAdd()13/39

用pa、pb分别遍历A和B的结点，先建立一个空多项式单链表C，在pa、pb都没有遍历完时循环：若pa结点的指数较大，复制pa结点并添加到C的末尾，同时pa后移一个结点。若pb结点的指数较大，复制pb结点并添加到C的末尾，同时pb后移一个结点。若pa和pb结点的指数相同，求出它们的系数和c（c=pa->coef+pb->coef），如果c≠0，由c和pa->exp新建一个结点并添加到C的末尾，否则不新建结点，pa、pb均后移一个结点。上述循环过程结束后，若有一个多项式单链表没有遍历完，说明余下的多项式项都是指数较小的多项式项，将它们均复制并添加到C末尾。14/39voidPolyAdd(PolyList&A,PolyList&B,PolyList&C){//A+B->CPolyNode*pa=A.head->next; //pa指向A的开始结点PolyNode*pb=B.head->next; //pb指向B的开始结点PolyNode*s,*r;doublec;r=C.head; //r指向尾结点while(pa!=NULL&&pb!=NULL){if(pa->exp>pb->exp){ //归并指数较大的结点pas=newPolyNode(pa->coef,pa->exp); //复制产生结点sr->next=s;r=s; //将结点s链到C末尾pa=pa->next;}15/39elseif(pa->exp<pb->exp){ //归并指数较大的结点pbs=newPolyNode(pb->coef,pb->exp);//复制产生结点sr->next=s;r=s; //将结点s链到C末尾pb=pb->next;}else{ //两结点指数相等的情况

c=pa->coef+pb->coef; //求两指数相等结点的系数和cif(c!=0) { //系数和不为0的情况s=newPolyNode(c,pa->exp); //新建结点sr->next=s;r=s; //将结点s链到C末尾

}pa=pa->next;pb=pb->next;}}16/39if(pb!=NULL)pa=pb; //复制余下的结点while(pa!=NULL){s=newPolyNode(pa->coef,pa->exp); //复制产生结点sr->next=s;r=s; //将结点s链到C末尾pa=pa->next;}r->next=NULL; //尾结点的next域置为NULL}17/394.设计主程序intmain(){freopen("abc.out","w",stdout); //输出重定向到abc.out文件PolyListA,B,C; //建立3个多项式单链表对象A.CreateList("abc1.in");cout<<"第1个多项式:";A.DispPoly();A.Sort();cout<<"排序后结果:";A.DispPoly();B.CreateList("abc2.in");cout<<"第2个多项式:";B.DispPoly();B.Sort();cout<<"排序后结果:";B.DispPoly();

PolyAdd(A,B,C);cout<<"相加多项式:";C.DispPoly();return0;}18/39执行程序后打开abc.out文件19/392.6STL中的线性表STL中有一类容量称为顺序容器，顺序容器按照线性次序的位置存储数据，即第1个元素，第2个元素，依此类推，简单地说，可以采用这些容量存放线性表。STL中的顺序容器有vector、string、deque和list。这里主要介绍vector和list。20/392.6.1vector向量容器1.vector向量的基本应用vector向量容器是一个可变长的动态数组。根据下标（索引）随机访问某个元素的时间是常数。在尾部添加一个元素的时间大多数情况下也是常数。在中间插入或删除元素时，因为要移动多个元素，因此速度较慢，平均花费的时间和容器中的元素个数成正比。v[0]v[1]v[2]…v[n-1]未用空间表头表尾Myfirstsize已用空间capacityMylastMyend21/39定义vector容器的几种方式如下：vector<int>v1; //定义元素为int的向量v1vector<int>v2(10); //指定向量v2的初始大小为10个int元素vector<double>v3(10，1.23); //指定v3的10个初始元素的初值为1.23vector<int>v4(a，a+5); //用数组a[0..4]共5个元素初始化v422/39vector的主要成员函数及其说明成员函数说明empty()判断当前向量容器是否为空size()返回当前向量容器的中的实际元素个数[]返回指定下标的元素reserve(n)为当前向量容器预分配n个元素的存储空间capacity()返回当前向量容器在重新进行内存分配以前所能容纳的元素个数resize(n)调整当前向量容器的大小，使其能容纳n个元素front()获取当前向量容器的第一个元素back()获取当前向量容器的最后一个元素push_back(e)在当前向量容器尾部添加了一个元素einsert(p，e)在p位置插入元素e，即将元素e插入到迭代器p指定元素之前pop_back()删除向量中最后一个元素erase()删除当前向量容器中某个迭代器或者迭代器区间指定的元素clear()删除当前向量容器中所有元素23/39成员函数说明begin()返回容器中第一个元素的迭代器end()返回容器中尾元素后面一个位置的迭代器rbegin()返回容器中尾元素的反向迭代器rend()返回容器中首元素前面一个位置的反向迭代器迭代器成员函数24/39#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>myv; //定义vector容器myvvector<int>::iteratorit; //定义myv的正向迭代器itmyv.push_back(1); //在myv末尾添加元素1it=myv.begin(); //it迭代器指向开头元素1myv.insert(it,2); //在it指向的元素之前插入元素2myv.push_back(3); //在myv末尾添加元素3myv.push_back(4); //在myv末尾添加元素4it=myv.end(); //it迭代器指向尾元素4的后面it--; //it迭代器指向尾元素4myv.erase(it); //删除元素4for(it=myv.begin();it!=myv.end();++it)printf("%d",*it);printf("\n");return0;}以下程序说明vector容器的应用21325/392.vector向量的排序STL的算法库提供了丰富的函数，许多函数可以用于vector向量以实现复杂的功能。例如STL的排序算法sort()（用于数组、vector向量等具有随机存取特性的容器）。有关排序算法的原理在第10章介绍，这里仅仅讨论sort()算法的应用。26/391）内置数据类型的排序对于内置数据类型的数据，sort()默认是以less<T>（小于函数）作为比较函数实现递增排序。为了实现递减排序，需要调用greater<T>函数。27/39#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;voidDisp(vector<int>&myv){ //输出vector的元素vector<int>::iteratorit;for(it=myv.begin();it!=myv.end();it++)cout<<*it<<"";cout<<endl;}intmain(){inta[]={2,1,5,4,3};intn=sizeof(a)/sizeof(a[0]);vector<int>myv(a,a+n);cout<<"初始myv:";Disp(myv); //输出：21543sort(myv.begin(),myv.end(),less<int>());cout<<"递增排序:";Disp(myv); //输出：12345sort(myv.begin(),myv.end(),greater<int>());cout<<"递减排序:";Disp(myv); //输出：54321return0;}28/392）自定义数据类型的排序

同样默认的比较函数是less<T>（即小于比较函数），但需要重载该函数。另外还可以重载函数调用运算符()。通过这些重载函数来设置元素比较方式。实现排序时主要有两种方式：

方式1：在定义类或者结构体类型中重载<运算符，以实现按指定成员的递增或者递减排序。如sort(myv.begin(),myv.end())调用默认<运算符对myv容器的所有元素实现排序。

方式2：在单独定义的类或者结构体中重载函数调用运算符()（operator()），以实现按指定成员的递增或者递减排序。如sort(myv.begin(),myv.end(),Cmp())调用Cmp的()运算符对myv容器的所有元素实现排序。29/39#include<iostream>#include<algorithm>#include<vector>#include<string>usingnamespacestd;structStud{

//Stud结构体类型intno;stringname;Stud(intno1,stringname1):no(no1),name(name1){}//构造函数booloperator<(constStud&s)const{//方式1：重载<运算符returnno>s.no; //用于按no递减排序，改为<按no递增排序}};structCmp{

//方式2：重载函数调用运算符()booloperator()(constStud&s,constStud&t)const{return<;//用于按name递增排序，改为>按name递减排序}};30/39voidDisp(vector<Stud>&myv){ //输出vector的元素vector<Stud>::iteratorit;for(it=myv.begin();it!=myv.end();it++)cout<<it->no<<","<<it->name<<"\t";cout<<endl;}31/39intmain(){Studa[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};intn=sizeof(a)/sizeof(a[0]);vector<Stud>myv(a,a+n);cout<<"初始myv:";Disp(myv);//输出：2,Mary1,John5,Smithsort(myv.begin(),myv.end()); //默认使用<运算符排序cout<<"按no递减排序:";Disp(myv);//输出：5,Smith2,Mary1,Johnsort(myv.begin(),myv.end(),Cmp());//使用Cmp中的()运算符进行排序cout<<"按name递增排序:";Disp(myv);//输出：1,John2,Mary5,Smithreturn0;}32/392.6.2list链表容器list链表容器是一个循环双链表。可以从任何地方快速插入与删除。它的每个结点之间通过指针链接，不能随机访问元素，为了访问表容器中特定的元素，必须从表头开始顺序遍历直到找到匹配的结点。list容器插入比vector快，由于对每个结点单独分配空间，所以不存在空间不够而需要重新分配的情况。begin()头结点尾结点…nodeend()33/39定义list容器的几种方式如下：list<int>l1; //定义元素为int的链表l1list<int>l2(10); //指定链表l2的初始大小为10个int元素list<double>l3(10，1.23); //指定l3的10个初始元素的初值为1.23list<int>l4(a，a+5); //用数组a[0..4]共5个元素初始化l434/39list的主要成员函数及其说明成员函数说明empty()判断链表容器是否为空size()返回链表容器中实际元素个数back()返回链表容器中尾元素front()返回链表容器中头元素push_back()在链表尾部插入元素pop_back()删除链表容器的尾元素push_front()在链表头部插入元素pop_front()删除链表容器的头元素remove()删除链表容器中所有指定值的元素remove_if(cmp)删除链表容器中满足条件的元素erase()从链表容器中删除一个或