数据结构课件C++版线性表

1、Data Structure-Ch2 Linear List 2022-6-15mayan 第二章 线性表线性表线性表顺序表顺序表单链表单链表循环链表循环链表和和双向链表双向链表多项式及其运算多项式及其运算静态链表静态链表Data Structure-Ch2 Linear List 2022-6-15mayan 2.1 线性表（Linear List）2.1.1概念线性表的概念线性表（线性表（linear list）是 n (0) 个数据元素的有限序列，记作 其中，),(11niiaaaaL空表空表数据类型数据类型问题问题值与位置值与位置的关系的关系Data Structure-Ch2 Lin

2、ear List 2022-6-15mayan 2.1线性表（Linear List）2.1.2线性结构的特点 线性结构的特点 存在一个唯一被称作“第一个”的数据元素；存在一个唯一被称作“最后一个”的数据元素；除第一个数据元素外，其他元素均有且仅有一个直接前驱，第一个元素没有前驱；除最后一个数据元素外，其他元素均有且仅有一个直接后继，最后一个元素没有后继。Data Structure-Ch2 Linear List 2022-6-15mayan 2.1线性表（Linear List）2.1.3线性表的抽象基类 线性表的抽象基类template class LinearList public:

3、LinearList();/构造函数 LinearList();/析构函数 virtual int Size() const = 0;/求表中最大可容纳的表项个数 virtual int Length() const = 0;/求表长度 virtual int Search(T& x) const = 0; /搜索 virtual int Locate(int i) const = 0;/定位Data Structure-Ch2 Linear List 2022-6-15mayan 2.1线性表（Linear List）2.1.3线性表的抽象基类virtual bool getData

4、(int i, T &x) const = 0; /取值virtual void setData(int i, T& x) = 0; /赋值 virtual bool Insert(int i, T& x) = 0; /插入virtual bool Remove(int i, T& x) = 0;/删除virtual bool IsEmpty() const = 0;/判表空 virtual bool IsFull() const = 0;/判表满virtual void Sort() = 0;/排序virtual void input() = 0;/输入vir

5、tual void output() = 0;/输出virtual LinearListoperator= (LinearList& L) = 0; /复制;Data Structure-Ch2 Linear List 2022-6-15mayan 2.1 线性表（Linear List）2.1.4线性表的存储表示线性表的存储表示顺序存储方式链表存储方式Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.1 定义及特点定义线性表的顺序存储方式（顺序表）指的是用一组地址连续的存储单元依次存储线

6、性表的数据元素。即它利用元素在物理位置上的邻接关系来表示表中元素间的逻辑关系。通常用数组来实现。 Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.1 定义及特点优点：无须为表示表中元素之间的逻辑关系而增加额额外的存储空间外的存储空间；只要确定了线性表的起始地址，就可以对表中的元素进行随机存取随机存取随机存取的存储结构；缺点：插入和删除元素的运算不方便，除最后一个元素外，做插入、删除操作时均须移动大量元素，其效率较低；分配存储空间的问题。 Data Structure-Ch2 Linear Lis

7、t 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -类定义#include /定义在“seqList.h”中#include #include linearList.hconst int defaultSize = 100;template class SeqList: public LinearList protected: T*data; /存放数组存放数组 int maxSize; /最大可容纳表项的项数最大可容纳表项的项数 int last; /当前已存表项数（从当前已存表项数（从0开始）开始） void reSize(int

8、 newSize);/改变数组空间大小改变数组空间大小Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -类定义public: SeqList(int sz = defaultSize); /构造函数 SeqList(SeqList& L); /复制构造函数 SeqList() delete data; /析构函数 int Size() const return maxSize; /求表最大容量 int Length() const return last+1; /计算

9、表长度 int Search(T& x) const;/搜索x在表中位置，函数返回表项序号 int Locate(int i) const;/定位第 i 个表项，函数返回表项序号bool getData(int I, T& x)const /取第i个表项的值if (i0&i0&i=last+1)datai-1=x;bool Insert(int i, T& x);/插入bool Remove(int i, T& x);/删除bool IsEmpty()return (last= -1)?true:false; /判表空否bool IsFull()

10、return(last=maxSize-1)?true:false; /判表满否 void input(); /输入 void output(); /输出SeqList operator=(SeqList& L); /表整体赋值;Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -构造函数#include /操作“exit”存放在此#include “seqList.h” /操作实现放在“seqList.cpp”template SeqList:SeqList(int

11、sz) /sz定义数组长度 if (sz 0) maxSize = sz; last = -1; data = new TmaxSize; /创建表存储数组 if (data = NULL) /动态分配失败 cerr 存储分配错误！ endl; exit(1); Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -复制构造函数template SeqList:SeqList ( SeqList& L ) maxSize = L.Size(); last = L.Leng

12、th()-1; data = new TmaxSize;/创建存储数组 T value; if (data = NULL)/动态分配失败 cerr 存储分配错误！ endl; exit(1); for (int i = 1; i = last+1; i+) /传送各个表项 L.getData(i, value); datai-1 = value; Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -搜索算法template int SeqList:Search(T& x

13、) const for (int i = 0; i = last; i+)/顺序搜索 if ( datai = x ) return i+1; /表项序号和表项位置差1 return 0; /搜索失败; 在表中顺序搜索与给定值 x 匹配的表项，找到则函数返回该表项是第几个元素，否则函数返回0Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -表项的插入算法template bool SeqList:Insert (int i, T& x) if (last = maxS

14、ize-1) return false; /表满 if (i last+1) return false; /参数i不合理 for (int j = last; j = i; j-) /依次后移 dataj+1 = dataj; datai = x; /插入(第 i 表项在datai-1处) last+; return true; /插入成功将新元素x插入到表中第i (0ilast+1) 个表项之后Data Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.2 类定义及其操作 -表项的删除算法template

15、 bool SeqList:Remove (int i, T& x) if (last = -1) return false; /表空 if (i last+1) return false; /参数i不合理 x = datai-1; for (int j = i; j = last; j+) /依次前移，填补 dataj-1 = dataj; last-; return true; 从表中删除第 i (1ilast+1) 个表项，通过引用型参数 x 返回被删元素。函数返回删除成功信息。顺序表顺序表vs.vs.一维数组一维数组Data Structure-Ch2 Linear List

16、2022-6-15mayan 2.2 顺序表（Sequential List）2.2.3顺序表性能分析 -搜索算法性能分析搜索算法的时间代价用数据比较次数数据比较次数来衡量。搜索成功的平均比较次数 pi 是搜索第 i 项的概率 ci 是找到时的比较次数若搜索概率相等，则搜索不成功 数据比较 n 次iniicp1=ACN212)(11)2(111=1nnnnnninni ACNData Structure-Ch2 Linear List 2022-6-15mayan 2.2 顺序表（Sequential List）2.2.3顺序表性能分析 -插入、删除算法性能分析顺序表的插入和删除的时间代价主要

17、看循环内的数据移动次数数据移动次数。考虑所有插入位置，相等插入概率时，平均移动元素个数为:考虑表中所有可能删除位置（1in）,相等删除概率时，平均移动元素个数为：221)(1)(10)1(11)(11=0nnnnnninnniAMNninnnnninn12121)(11)(1=)01) 1(AMNnData Structure-Ch2 Linear List 2022-6-15mayan 2.2顺序表（Sequential List）2.2.4顺序表的应用 -集合的“并”运算void Union ( SeqList& LA, SeqList& LB ) int n = LA.L

18、ength ( ), n2 = LB.Length ( ); int i, k, x; for ( i = 0; i n2; i+ ) LB.getData(i,x); /在LB中取一元素k = LA.Search(x); /在LA中搜索它if (k = 0) /若在LA中未找到插入它 LA.Insert(n, x); n+; /插入到第n个表项位置 Data Structure-Ch2 Linear List 2022-6-15mayan void Intersection ( SeqList & LA, SeqList & LB ) int n = LA.Length (

19、); int x, k, i = 0; while ( i link = first; first = newNode; else /否则，寻找插入位置 LinkNode *current = first;将新元素 x 插入到第 i 个结点之后。i从1开始，i = 0 表示插入到首元结点之前。Data Structure-Ch2 Linear List 2022-6-15mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 -插入算法for(int k=1; klink;if (current = NULL) /链短cerr link = curr

20、ent-link; current-link = newNode;return true; Data Structure-Ch2 Linear List 2022-6-15mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 -删除Data Structure-Ch2 Linear List 2022-6-15mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 -删除Data Structure-Ch2 Linear List 2022-6-15mayan 2.3单链表（singly linked l

21、ist）2.3.3单链表中结点的插入和删除 -删除算法bool List:Remove (int i, int& x) LinkNode *del;/暂存删除结点指针if (i link; else LinkNode *current = first; /找i-1号结点 for (int k=1; klink;将链表中的第 i 个元素删去, i 从1开始。Data Structure-Ch2 Linear List 2022-6-15mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 -删除算法 if (current = NULL |

22、current-link = NULL) cout link; /删中间/尾结点current-link = del-link; x = del-data; delete del; /取出被删结点数据 return true;Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.4 带附加头结点的单链表附加头结点即表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。Data Structure-Ch2 Linear List 2022

23、-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类#include#include#include linearList.htemplate /定义在“LinkedList.h”struct LinkNode /链表结点类的定义 T data; /数据域 LinkNode *link; /链指针域 LinkNode(LinkNode *ptr=NULL) link = ptr; LinkNode(const T& item, LinkNode *ptr = NULL) data = item; link = ptr; ;初始化数据与指

24、针的构造函数初始化指针成员的构造函数Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类template class List:public LinearList protected: LinkNode *first; /表头指针public: List() first = new LinkNode; /构造函数 List(T& x) first = new LinkNode(x); List( List& L);/复制构造函数 List()makeEmpty

25、();/析构函数 void makeEmpty();/将链表置为空表Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类int Length() const;/计算链表的长度LinkNode *getHead()constreturn first;void setHead(LinkNode *p)first=p;/LinkNode *Search(T x);/搜索含x元素LinkNode *Locate(int i)const;/定位第i个元素bool getData(int

26、 i, T &x)const;/取出第i元素值void setData(int i, T& x);/更新第i元素值bool Insert (int i, T& x); /在第i元素后插入bool Remove(int i, T& x); /删除第i个元素bool IsEmpty() const/判表空否返回附加头结点地址设置附加头结点地址Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 return first-link=NULL?true

27、:false; bool IsFull() const /判表满否 return false; void input(T); void output(); List& operator=(List& L);Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -复制构造函数templateList:List(List& L)T value;LinkNode *srcptr=L.getHead();LinkNode *destptr=first=new

28、LinkNode;while(srcptr-link!=NULL)value=srcptr-link-data;destptr-link=new LinkNode(value);destptr=destptr-link;srcptr=srcptr-link;Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -置空template void List:makeEmpty() LinkNode *q; while (first-link != NULL) q = first-

29、link; /保存被删结点 first-link = q-link; /从链上摘下该结点 delete q; /删除 qData Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -求表长templateint List:Length() constLinkNode *p=first-link;/检测指针 p 指示第一号结点int count=0;while(p!=NULL) /逐个结点检测p=p-link;count+;return count; Data Structure-C

30、h2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -搜索/在表中搜索含数据x的结点, 搜索成功时函数返/该结点地址; 否则返回NULL。template LinkNode *List:Search(T x) LinkNode *current = first-link; while ( current != NULL & current-data != x ) current = current-link; /沿着链找含x结点 return current;Data Structure-Ch2

31、Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -定位/函数返回表中第 i 个元素的地址。若i 0或 i 超/出表中结点个数，则返回NULL。template LinkNode *List:Locate ( int i ) const if (i 0) return NULL;/i不合理 LinkNode *current = first; int k = 0; while ( current != NULL & k link; k+; return current; /返回第 i 号结点地址或NU

32、LLData Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -插入/将新元素 x 插入在链表中第 i 个结点之后。template bool List:Insert (int i, T& x) LinkNode *current = Locate(i);if (current = NULL) return false; /无插入位置LinkNode *newNode = new LinkNode(x); newNode-link = current-link; /链入

33、current-link = newNode;return true; /插入成功Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -删除/删除链表第i个元素, 通过引用参数x返回元素值template bool List:Remove (int i, T& x ) LinkNode *current = Locate(i-1);if ( current = NULL | current-link = NULL) return false; /删除不成功 Link

34、Node *del = current-link; current-link = del-link;x = del-data;delete del; return true;Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -赋值templateList& List:operator =(List& L) T value;LinkNode *srcptr=L.getHead();LinkNode *destptr=first=new LinkNode;wh

35、ile(srcptr-link!=NULL)value=srcptr-link-data;destptr-link=new LinkNode(value);destptr=destptr-link;srcptr=srcptr-link;destptr-link=NULL;return *this;Data Structure-Ch2 Linear List 2022-6-15mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 -前插法建立单链表template void List:input(T endTag) LinkNode *newNode; T

36、 val; first=new LinkNode; if(first=NULL)cerr存储分配错误！val; while(val!=endTag)newNode=new LinkNode(val);if(newNode=NULL)cerr存储分配错误！link=first-link;first-link=newNode;cinval;Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表（circular list） -定义与特点 定义：循环链表（circular list）是另一种形式的表示线性表的链表，它的结

37、点结构与单链表相同，与单链表不同的是链表中表尾结点的link域中不是NULL，而是存放了一个指向开始结点的指针。Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表（circular list） -定义与特点特点：从任意一个结点出发可以找到表中其他结点；在循环链表上实现各种运算与单链表类似，它们仅在判断是否到达表尾的条件上有所不同，前者是判断current-link=first，而后者是判断current-link=NULL。Data Structure-Ch2 Linear List 2022-6-15maya

38、n 2.4循环链表和双向链表2.4.1循环链表（circular list）带尾指针的循环链表的操作在表尾插入，时间复杂性O(1)在表尾删除，时间复杂性O(n)在表头插入，相当于在表尾插入在表头删除，时间复杂性O(1)Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表（circular list） -类定义template struct CircLinkNode /链表结点类定义 T data; CircLinkNode *link; CircLinkNode ( CircLinkNode *next =NUL

39、L):link(next) CircLinkNode (T d, CircLinkNode *next = NULL):data(d),link(next);Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表（circular list） -类定义template /链表类定义class CircList : public LinearList private: CircLinkNode *first, *last; /头指针, 尾指针public: CircList(const T& x); /构造函

40、数CircList(CircList& L); /复制构造函数CircList(); /析构函数 int Length() const; /计算链表长度Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表（circular list） -类定义bool IsEmpty() return first-link = first; /判表空否CircLinkNode *getHead() const; /返回表头结点地址void setHead ( CircLinkNode *p ); /设置表头结点地址Cir

41、cLinkNode *Search ( T x );/搜索CircLinkNode *Locate ( int i );/定位T *getData ( int i ); /提取void setData ( int i, T& x ); /修改bool Insert ( int i, T& x ); /插入bool Remove ( int i, T& x); /删除;Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表-用循环链表解决约瑟夫问题约瑟夫问题的提法:n 个人围成一个圆圈，首先第

42、 1 个人从 1 开始，一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后再从下一个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。用不带表头结点的循环链表来组织。Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表-用循环链表解决约瑟夫问题例如： n = 8，m = 3Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表-用循环链表解决约瑟夫问题void ma

43、in() CircList clist; int i, n m; cout n m; for (i = 1; i = n; i+ ) clist.insert(i, i); /约瑟夫环 Josephus(clist, n, m); /解决约瑟夫问题Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.1循环链表-用循环链表解决约瑟夫问题void Josephus(CircList& Js, int n, int m) CircLinkNode *p = Js.getHead(),*pre = NULL; int i,

44、 j; for ( i = 0; i n-1; i+ ) /执行n-1次 for ( j = 1; j link; cout “出列的人是” data link = p-link; delete p; /删去 p = pre-link; ;ppreppprepData Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） -双向链表的概念使用双向链表（double linked list）的目的目的是为了解决在链表中访问直接前驱和直接后继问题。双向链表的每个结点至少由三个域组成：带头

45、结点的双向循环链表：特性：p=p-lLink-rLink=p-rLink-lLink;Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） 带附加头结点的双向循环链表的类定义template struct DblNode /链表结点类定义T data;/链表结点数据DblNode *lLink, *rLink; /前驱、后继指针DblNode ( DblNode *left = NULL, DblNode *right = NULL ):lLink(left),rLink(

46、right) DblNode ( T value, DblNode *left = NULL, DblNode *right = NULL):data(value), lLink(left),rLink(right) ; Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list）-类定义template class DblList /链表类定义public:DblList ( T uniqueVal ) /构造函数，建立附加头结点 first = new DblNode (uni

47、queVal); if(first=NULL)cerr”存储分配出错”rLink = first-lLink = first; DblList ();int length() const;Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） -类定义bool IsEmpty() return first-rlink = first; DblNode *getHead () const return first; void setHead ( DblNode *ptr ) f

48、irst = ptr; DblNode *Search ( T& x, int d); /在链表中按d指示方向寻找等于给定值x的结点, /d=0按前驱方向,d0按后继方向DblNode *Locate ( int i, int d ); /在链表中定位序号为i(0)的结点, d=0按前驱方 /向,d0按后继方向Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） -类定义bool Insert ( int i, const T& x, int d ); /在

49、第i个结点后插入一个包含有值x的新结点,d=0 /按前驱方向,d0按后继方向bool Remove ( int i, T& x, int d ); /删除第i个结点private: DblNode *first; /表头指针;Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） -双向链表的插入向前插入Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked l

50、ist） -双向链表的插入template bool DblList:Insert ( int i, const T& x, int d ) /建立一个包含有值x的新结点, 并将其按 d 指定的/方向插入到第i个结点之后。 DblNode *current = Locate(i, d); if ( current = NULL ) return false; DblNode *newNode = new DblNode(x);if(newNode=NULL)cerr”存储分配出错”lLink = current-lLink; current-lLink = newNode;newNod

51、e-lLink-rLink = newNode; newNode-rLink = current; Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表（double linked list） -双向链表的插入else /后继方向:插在第i个结点后面 newNode-rLink = current-rLink; current-rLink = newNode; newNode-rLink-lLink = newNode; newNode-lLink = current;return true; /插入成功Data

52、 Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表 -双向链表的删除算法Data Structure-Ch2 Linear List 2022-6-15mayan 2.4循环链表和双向链表2.4.2双向链表 -双向链表的删除算法template bool DblList:Remove( int i, T& x, int d ) /在双向循环链表中按d所指方向删除第i个结点。 DblNode *current = Locate (i, d); if (current = NULL) return false; /

53、删除失败current-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; x = current-data; delete current; /删除 return true; /删除成功Data Structure-Ch2 Linear List 2022-6-15mayan 2.5 多项式及其运算n阶多项式 Pn(x) 有 n+1 项。 系数 a0, a1, a2, , an 指数 0, 1, 2, , n。按升幂排列iniinnnxaxaxaxaaxP02210 )(Data Structure-Ch2 Li

54、near List 2022-6-15mayan 2.5多项式及其运算多项式的顺序存储表示插入和删除时项数可能有较大变化，因此要移动大量数据。不利于多个多项式的同时处理。多项式的链表存储表示多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。Data Structure-Ch2 Linear List 2022-6-15mayan 2.5多项式及其运算-多项式类的链表定义struct Term /多项式结点定义 float coef; /系数 int exp; /指数 Term *link; /链接指针 Term (float c, int e, Term *next

55、= NULL) coef = c; exp = e; link = next;Term *InsertAfter ( float c, int e); friend ostream& operator (ostream&,const Term& ); Data Structure-Ch2 Linear List 2022-6-15mayan 2.5多项式及其运算-多项式类的链表定义class Polynomial /多项式类的定义public:Polynomal() first = new Term(0, -1); /构造函数Polynomal ( Polynomal&

56、amp; R); /复制构造函数int maxOrder(); /计算最大阶数Term *getHead()const return first;private:Term *first; Data Structure-Ch2 Linear List 2022-6-15mayan 2.5多项式及其运算-多项式类的链表定义friend ostream& operator ( istream&,Polynomal& );friend void Add ( Polynomial& A, Polynomial& B, Polynomial& C );fri

57、end void Mul ( Polynomial& A, Polynomial& B, Polynomial& C );Data Structure-Ch2 Linear List 2022-6-15mayan 2.5多项式及其运算-多项式相加AH = 1 - 3x6 + 7x12BH = - x4 + 3x6 - 9x10 + 8x14CH = 1 - x4 - 9x10 + 7x12 + 8x14AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14Data Structu

58、re-Ch2 Linear List 2022-6-15mayan AH.firstBH.first CH.first1 0-1 4-3 63 6-9 107 128 14papcpb 2.5多项式及其运算-多项式相加Data Structure-Ch2 Linear List 2022-6-15mayan AH.first CH.first 1 01 0-1 4-3 63 6-9 107 128 14papbpcBH.first2.5多项式及其运算-多项式相加Data Structure-Ch2 Linear List 2022-6-15mayan AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.first2.5多项式及其运算-多项式相加Data Structure-Ch2 Linear List 2022-6-15mayan AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14p