《数据结构(C++版)》第2章 线性表

1、第第2章章 线性表线性表2.1 线性表的类型定义线性表的类型定义2.1.2 线性表的定义线性表的定义线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个地排列”。在一个线性表中，数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表是由n（n0）个类型相同的数据元素组成的有限序列，通常表示为L=(a1, a2, ,ai1, ai, ai+1, , an)。其中，L为线性表名称，ai为组成该线性表的数据元素，ai1领先于ai，ai领先于ai+1，称ai1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1, 2, , n1时，a

2、i有且仅有一个直接后继元素；当i=2, 3, , n时，ai有且仅有一个直接前驱元素。线性表的长度就是线性表中元素的个数n（n0）。当n=0时，称为空表。在非空表中，每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。i称为数据元素ai在线性表中的位序。2.1.2 线性表的线性表的抽象数据类型抽象数据类型抽象数据类型描述抽象数据类型描述线性表的抽象数据类型描述见如下ADT。ADT List 数据集合： 数据关系： 数据操作：Init_List(&L) /初始化线性表输入：空。返回结果：构造一个空的线性表L。Destroy_List(&a

3、mp;L) /撤销线性表输入：线性表L。返回结果：撤销线性表L。线性表的线性表的抽象数据类型抽象数据类型Clear_List(&L) /清空线性表输入：线性表L。返回结果：将线性表L重置为空表。List_Empty(&L) /判断线性表是否为空输入：线性表L。返回结果：若线性表L为空表，则返回TRUE，否则返回FALSE。List_Length(&L) /求线性表的长度输入：线性表L。返回结果：线性表L中的数据元素个数。线性表的线性表的抽象数据类型抽象数据类型Get_Elem(&L，i，&e) /取线性表中第i个数据元素的值输入：线性表L，1 i Lis

4、t_Length(L)。返回结果：用e返回线性线L中第i个数据元素的值。Locate_Elem(&L，e，compare( ) /返回给定值在线性表中的位置输入：线性表L，compare( )是数据元素相等判定函数。返回结果：线性表L中第1个与e满足相等关系的数据元素的位序。若这样的数据元素不存在，则返回值为0。Prev_Elem(&L，cur_e，&pre_e) /返回当前元素的前一个元素值 输入：线性表L。返回结果：若cur_e是线性表L中的数据元素，且不是第1个，则pre_e返回它的直接前驱元素；否则操作失败，pre_e无定义。Next_Elem(& L，

5、cur_e，&next_e) /返回当前元素的后一个元素值输入：线性表L。返回结果：若cur_e是线性表L中的数据元素，且不是最后一个，则用next_e返回它的直接后继元素；否则操作失败，next_e无定义。List_Insert(&L，i，e) /在线性表的第i个位置之前插入数据元素e输入：线性表L，1 i List_Length(L)+1。返回结果：在线性表L中的第i个位置之前插入新的数据元素e，线性表L的长度加1。List_Delete(&L，i，&e) /删除线性表中的第i个数据元素输入：非空线性表L，1 i List_Length(L)。返回结果：删除

6、L中的第i个数据元素，用e返回其值，线性表L的长度减1。List_Traverse(&L，visit( ) /遍历线性表输入：线性表L。返回结果：依次对线性表L的每个数据元素调用visit( )函数进行访问。一旦visit( )访问失败，则操作失败。ADT List例例21 假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素为集合中的成员。试编写一个算法求一个新的集合C=AB，即将两个集合的并集放在线性表LC中。算法如下：void List_Merge(List LA，List LB，List &LC) int lena， lenb， le

7、nc，i； ElemType e； Init_List(LC)； for (i=1；i=List_Length(LA)；i+) /*将LA的所有元素插入到LC中*/ Get_Elem(LA，i，e)； List_Insert(LC，i，e)； lena=List_Length(LA)；/*求线性表的长度*/lenb=List_Length(LB)；for (i=1；i=lenb；i+) /*取LB中的第i个数据元素并将其赋给e*/ Get_Elem(LB，i，e)；/*LA中不存在和e相同者，则插入到LC中*/if (!Locate_Elem(LA，e，compare() List_Inser

8、t(LC，+lena，e)；时间复杂度为：O(List_Length(LA)*List_Length(LB)2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 顺序表顺序表线性表的顺序存储：是指用一组地址连续的存储单元依次存储线性表中的数据元素。设a1的存储地址为Loc(a1)，每个数据元素占用d个字节，则第i个数据元素的地址为Loc(ai)=Loc(ai)+(i1)d，1in，如图2.1所示。 a1 1 Loc (a1) 0 a a2 2 Loc (a1)+sizeof(ElemType) 1 线性表存储空间线性表存储空间 存储地址存储地址 下标位置下标位置 a ai i Loc (

9、a1)+(i-1)*sizeof(ElemType) i-1 a an n Loc (a1)+(n-1)*sizeof(ElemType) n - 1 Loc (a1)+(MaxSize-1)*sizeof(ElemType) MaxSize -1 图2.1 线性表的顺序存储 Loc(a1)通常称作线性表的起始位置或基地址。只要确定了存储线性表的起始位置，线性表中的任意一个数据元素都可以随机存取。因此，线性表的顺序存储结构是一种随机存取的存储结构。线性表的这种机内表示称为线性表的顺序存储结构或顺序映射。通常，称这种存储结构的线性表为顺序表。其特点是以数据元素在计算机内“物理位置相邻”来表示线性

10、表中数据元素之间的逻辑关系。例22 设一维数组A的下标的取值范围是0 - - 99，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素A0的第一个字节的地址是100，则A5的第一个字节的地址是 。解：第i个元素的存储地址的计算公式为Loc(ai) = Loc(a1) + (i1) d，1 i n。因此，Loc(A5)=100+ (50)5=125。数组A的第1个元素的下标是0，即A0。线性表的动态分配顺序存储结构的描述（了解）线性表的长度可变，而且最大存储空间随问题的不同而不同，因此需要动态地分配线性表的空间。在C+语言中，可用动态分配的一维数组来表示，描述见如下程序：/文件L

11、ine_ListSqu.h，类Line_ListSqu#include#includetemplateclass Line_ListSqu public：Line_ListSqu(int MaxListSize=10)；/构造函数Line_ListSqu( ) if (element) delete element； /析构函数bool IsEmpty( ) const return length=0； int Length( ) const return length； bool Find(int i，T& x) const；/将第i个元素的值用x返回Line_List& D

12、elete(int i，T& x)；/删除第i个元素的值，并且用x返回int Search(const T& x) const；/返回x中元素所处的位置Line_List& Insert(int i，const T& x)；/在第i个元素前面插入x void Output(ostream& out) const；protected： long length； long MaxSize； T *elem；/一维动态数组，其元素类型为可变类型T2.2.2 顺序存储结构顺序存储结构基本操作的实现基本操作的实现初始化：初始化：顺序表的初始化即构造一个空表，操作比

13、较简单，代码（算法21）如下所示：Template Line_ListSqu : Line_ListSqu(int MaxListSize) /线性表的构造函数 MaxSize=MaxListSize； elem=new TMaxSize； length=0；顺序存储结构顺序存储结构基本操作的实现基本操作的实现按序号查找按序号查找：顺序表是一种随机存取的数据结构，因此很容易在顺序表中实现按序号查找元素。代码（算法22）如下所示： template bool Line_ListSqu:Find(int i，T& x) const /在线性表中查找第i个元素并用x返回 if (ilengt

14、h) return false； x=elemi1； return true； 按序号查找元素的主要目的是返回待查元素，其时间复杂度为O(1) 。顺序存储结构顺序存储结构基本操作的实现基本操作的实现按值查找按值查找是指在线性表中查找与给定值x相等的数据元素，具体实现代码（算法23）如下： template int Line_ListSqu: Search(const T& x) const int i = 0； if (IsEmpty( ) return 0；/线性表为空时返回0 while(ilength &!(x= =elemi) i+； if (elemi= =x) re

15、turn +i； else return 0； 上述算法的主要操作是比较，平均比较次数为(n+1)/2，算法的时间复杂度为O(n)。 顺序存储结构顺序存储结构基本操作的实现基本操作的实现输出函数输出函数的实现代码（算法24）如下：Template void Line_ListSqu：Output(ostream& out)const for(int i=0；ilength；i+) outelemi“”；顺序存储结构顺序存储结构基本操作的实现基本操作的实现为了在所有情形下都能引发一个异常，本节定义一个异常类NoMem，非法操作将会简单地引发一个类型为NoMem的异常。 #includec

16、lass NoMem public： NoMem( ) cout“memory is not enough”；顺序存储结构顺序存储结构基本操作的实现基本操作的实现如果表中不存在第m个元素，则应出现一个越界异常，定义为OutOfBounds，每当正在执行的函数中的参数超出所期望的范围时，就会引发这种类型的异常。class OutOfBounds public： OutOfBounds( ) cout”out of bounds”； ；顺序存储结构顺序存储结构基本操作的实现基本操作的实现线性表的插入操作线性表的插入操作是指在线性表的第m1个数据元素和第m个数据元素之间插入一个新的数据元素x，其结果

17、是使长度为n的线性表(a1, a2 , am1, am, an)变成长度为n+1的线性表(a1, a2 , am1, x, am, an)，并且数据元素am1和am之间的逻辑关系发生了变化。 实现步骤如下：(1)合法性判断：插入位置i是否合法?表是否已满?(2)将第i至第n位的元素向后移动一个位置；(3)将要插入的元素写到第i个数据元素的位置；(4)表长加1。顺序存储结构顺序存储结构基本操作的实现基本操作的实现具体算法（算法25）描述如下：templateLine_ListSqu& Line_ListSqu:Insert(int i，T& x) if (ilength+1) t

18、hrow OutOfBounds( )； if (length=MaxSize) throw NoMem( )； for(int j=length1；j=i1；j ) elemj+1=elemj； elemi1=x； length+； return *this；l 顺序表上的插入运算，时间主要消耗在数据的移动上，在第m个位置上插入x，从am到an都要向下移动一个位置，共需移动n m+1个元素，而m的取值范围为：1 m n+1，即有n+1个位置可以插入。在顺序表上做插入操作平均需要移动表中的一半数据元素，时间复杂度为O(n) 。顺序存储结构顺序存储结构基本操作的实现基本操作的实现线性表的删除操作

19、线性表的删除操作是使长度为n的线性表(a1, a2, am1, am,an)变为长度为n1的线性表(a1, a2, am1, am+1,an)，并且数据元素am1、am和am+1之间的逻辑关系也会发生变化，需要把第m+1n个元素（共nm个元素）依次向前移动一个位置来反映这种变化。具体实现步骤如下：判断删除位置i是否合法，合法则将该位置元素放入x中，否则抛出异常；将第i+1至第n位的元素向前移动一个位置；表长减1。顺序存储结构顺序存储结构基本操作的实现基本操作的实现具体算法（算法26）描述如下：template Line_ListSqu& Line_ListSqu：Delete(int

20、i，T& x) if (Find(i，x) for(int j=i；jlength；j+) elemj1=elemj； length ； return *thiselse throw OutOfBounds( )； 与插入操作相同，删除操作的时间也主要消耗在移动表中的元素上，删除第m个元素时，其后面的元素am+1到an都要向前移动一个位置，共移动了nm个元素，该算法的时间复杂度也为O(n)。 顺序存储结构顺序存储结构应用举例应用举例例23 应用举例：已知一个线性表中的元素按元素值非递减有序排列，试设计算法删除表中值相同的多余元素。 解：算法一： void purgelist(Line_

21、ListSqu A) int i=0；/i是扫描指示器，赋初值0 while(i=A.length2) if (A.elemi!=A.elemi+1) i+；/继续往后扫描 else for(int j=i+2；j=A.length1；j+) A.elemj1=A.elemj；/删除重复元素 A.length； /修改表长 顺序存储结构顺序存储结构应用举例应用举例算法二： void purgelist(Line_ListSqu A) int j=0，i=1； while(i=A.length1) if (A.elemi!=A.elemj) /将元素移至正确的位置上 A.elemj+1=A.el

22、emi；j+； i+；/继续往后扫描 A.length=j+1；/修改表长 算法一的时间复杂度为O(n2)，算法二的时间复杂度为O(n)。由此可见，算法一的时间效率比算法二的时间效率要低。2.3 线性表的链式存储结构线性表的链式存储结构2.3.1 线性链表线性链表线性链表的定义 链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素ai，除了存放数据元素自身的信息ai之外，还需要和ai一起存放其后继元素ai+1所在的存储单元的地址，这两部分信息组成一个“结点”。存放数据元素信息的称为数据域，存放其后继元素地址的称为指针域，指针域中存储的信息称为指针或链。结点结构如书上图2.2所

23、示。n个结点ai (1 i n)链接成一个链表，即为线性表（a1，a2，an）的链式存储结构。由于此链表中的每个结点只包含一个指针域，故又称线性链表或单链表。例如， 图2.3所示为学生信息线性表（张跃，朱炳，李雪，张方，赵欣，宋亮，董琴，李辉）的单链表存储结构。整个链表的存取由头指针H开始进行，它指向链表中第一个结点的存储位置，线性链表中最后一个结点的指针为“空”（NULL）。 存储地址数据域指针域3张方169朱炳6016赵欣4826董琴4233张跃942李辉NULL48宋亮2660李雪333头指针H图2.3 学生信息线性表通常我们把链表画成用箭头相链接的结点序列，结点之间的箭头表示链域中的指

24、针。图2.3的线性表可画成如图2.4所示的形式。为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个头结点。这样可以免去对链表第一个结点的特殊处理。将图2.4加上头结点如图2.5所示。张跃 朱炳 李雪 张方 赵欣 宋亮 董琴 李辉 Header 8 张跃 朱炳 李雪 赵欣 宋亮 董琴 李辉 图2.5 带头结点的单链表张方 图2.4 线性表的指针表示线性表的单链表存储结构的类定义单链表的类定义通常使用两个类：一个结点类Line_ListNode和一个单向链表类Line_ListLink。一个链表包含了0、一个或多个结点，一个类型为Line_ListLink的对象包含0、一个或多个类型为L

25、ine_ListNode的对象。Line_ListLink定义为Line_ListNode的一个友类，所以Line_List Link可访问Line_ListNode的所有成员，也包括私有成员。 以下给出链表结点类和单链表类的类定义描述：#include template class Line_ListLink；/Line_ListNode类的友元 template class Line_ListNode friend class Line_ListLink； private： Line_ListNode *link； T data； public： Line_ListNode(Line_Li

26、stNode *ptrlink=NULL) link=ptrlink； Line_ListNode(const T& item，Line_ListNode *ptrlink=NULL) data=item；link=ptrlink； Line_ListNode(void) /析构函数 templateclass Line_ListLinkpublic：Line_ListLink( ) first=0；Line_ListLink( )；bool IsEmpty( ) const return first= =0；int Length( ) const；bool Find(int i，T&

27、amp; x) const；/将第i个结点的值用x返回Line_ListLink& Delete(int i，T& x)；/删除第i个结点的值，并用x返回int Search(const T& x) const；Line_ListLink& Insert(int i，const T& x)；/在第i个结点的前面插入x void Output(ostream& out) const；Line_ListNode *GetFirst( ) return first；private： Line_ListNode *first；2.3.2 线性表线性表基本

28、操作的实现基本操作的实现求表长求表长运算从头指针开始，将其赋值给指针变量cur。当cur不为NULL时，计数器变量length的值加1，逐步后移cur指针，每后移一个结点，长度值加1，直到cur指向NULL结束，返回length值即为表的长度值。代码（算法27）如下所示：templateint Line_ListLink：length( ) const Line_ListNode *cur=first； int length=0； while(cur) length+； cur=curlink； return length；查找第查找第i个结点个结点，也是从头指针开始，依次后移到第i个结点，代

29、码（算法28）如下所示：templatebool Line_ListLink：Find(int i，T& x) const if (i1) return false； Line_ListNode *cur=first； int j=1； while(jlink；j+ if (cur) x=curdata；return true； else return false； 查找给定值查找给定值所在所在的结点的序号的结点的序号，即定位操作。具体代码（算法29）如下： templateint Line_ListLink：Search(const T& x) const Line_List

30、Node *cur=first； int j=1； while(curdata!=x & cur!=NULL) cur=curlink；j+ if (cur) return j； else return 0； 上述算法的主要操作是比较并后移指针，两个查找算法的平均比较次数为(n+1)/2，求表长算法的移动次数为n，故3个算法的时间复杂度均为O(n)。输出函数的实现代码如下：templatevoid Line_ListLink：Output(ostream& out)const Line_ListNode *cur； for(cur=first；cur；cur=curlink)

31、outdatanext=pnext；pnext=s；abpbapxs（a)插入前（b)插入后图2.6 在单链表中插入结点snext=pnext；pnext=s； 插入运算是将值为x的新结点插入到单链表的第i个结点之前的位置上。先在单链表中找到第i1个结点，再在其后插入新结点。具体算法代码（算法210）如下所示： templateLine_ListLink& Line_ListLink：Insert(int i，const T& x) if (i0) throw OutOfBounds( )；/插入位置不合法 Line_ListNode *p=first； int j=1； wh

32、ile(p & jlink；+j； /查找第i1个结点 if (i0 & !p) throw OutOfBounds( )；/没有第i1个结点 Line_ListNode *s=new Line_ListNode； sdata=x； if (i1) slink=plink；plink=s； else /插入结点为第一个元素 slink=first；first=s； return *this；在线性表中删除元素在线性表中删除元素b时时，为了实现3个元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为其单链表存储结构中指向结点a的指针，删除过程如图2.7所示。指

33、针修改核心语句描述为：pnext=pnextnext；等价语句为：q = pnext；pnext = qnext；abpcabpc图2.7 在单链表中删除结点(a)删除前(b)删除后指针修改核心语句描述为：pnext=pnextnext；等价语句为：q = pnext；pnext = qnext；删除运算是将单链表的第删除运算是将单链表的第i个结点删去个结点删去。先在单链表中找到第i1个结点，再删除其后的结点。具体算法代码（算法211）如下所示：templateLine_ListLink& Line_ListLink：Delete(int i，T& x) if (i1 | !f

34、irst) throw OutOfBounds( )；/删除位置不合法 Line_ListNode *p=first； if (i=1) first=firstlink； else Line_ListNode *q=first； int j=1； /查找第i个结点 while(q & jlink；+j； if (!q | !qlink) throw OutOfBounds( )；/没有第i个结点 p=qlink；qlink=plink； x=pdata；delete p； return *this；2.3.3 静态链表静态链表为了便于在不设“指针”类型的高级程序设计语言中使用链表结构，

35、有时也可借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标（指示器cur即为伪指针）代替指针以指示结点在数组中的相对位置。数组中的第0个分量可以看成头结点，其指针域指示链表的第一个结点。为了和“指针”类型描述的线性链表相区别，我们称这种用数组描述的链表为静态链表。见教材P40图2.8静态链表2.3.4 循环链表循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再为空，而是指向表头结点，整个链表形成一个环。由此，从表中的任意一个结点出发均可找到链表中的其他结点。如图2.8所示为单循环链表。循环链表的操作和线性链表基本一致，差别在于，判别链表中最后

36、一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。Headera1anHeader图2.8 单循环链表(a) 非空表(b) 空表2.3.5 双向链表双向链表在需要频繁地同时访问前驱结点和后继结点时，可采用另一种链表结构，即双向链表。所谓双向链表，就是每个结点都有两个指针域，一个指向直接后继结点，另一个指针域指向直接前驱结点。图2.9给出了双向链表的结点结构。指向前驱结点的指针域数据域指向后继结点的指针域plinkdatanlink图2.9 给出了双向链表的结点结构双向链表的类定义：双向链表的类定义通常也使用两个类：一个结点类DLine_ListNode和一个双向链表类DLine_

37、ListLink。以下给出双向链表结点类和双向链表类的类定义描述：#include template class DLine_ListLink；/作为DLine_ListNode类的友元，需要提前声明 template class DLine_ListNode friend class DLine_ListLink； private： DLine_ListNode *plink，*nlink； T data；线性表的链式存储结构线性表的链式存储结构 public： DLine_ListNode(DLine_ListNode*prior=NULL， DLine_ListNode*next=NUL

38、L) plink=prior；nlink=next；DLine_ListNode(const T& item，DLine_ListNode*prior=NULL，DLine_ListNode *next=NULL) data=item；plink=prior；nlink=next； DLine_ListNode(void) /析构函数 线性表的链式存储结构线性表的链式存储结构templateclass DLine_ListLinkpublic：DLine_ListLink( ) first=last=0；DLine_ListLink( )； int Length( ) const； b

39、ool Find(int i，T& x) const；/将第i个结点的值用x返回DLine_ListLink& Delete(int i，T& x)；/删除第i个结点的值，用x返回int Search(const T& x) const；/在第i个结点的前面插入x DLine_ListLink& Insert(int i，const T& x)；void Output(ostream& out) const； private： DLine_ListNode *first，*last；在双向链表中，结点的插入和删除操作涉及前后结点的两个指针

40、域的变化。图2.10和图2.11分别显示了插入和删除结点时指针的修改情况，它们的算法分别如算法2-12和2-13所示，两者的时间复杂度均为O(n) 。xab1243pqabcp图2.10 插入操作图2.11 删除操作 设p指向双向链表中的第i个结点，q指向待插入的值为x的结点，则插入的主要操作如下： qplink=pplink； pplinknlink=q； qnlink=p； pplink=q；设p指向双向链表中的第i个结点，则删除操作的主要步骤如下：pplinknlink=pnlink；pnlinkplink=pplink；delete p；插入算法插入算法(算法2-12)： templa

41、teDLine_ListLink& DLine_ListLink：Insert(int i，const T& x) if (i0) throw OutOfBounds( )；/插入位置不合法 DLine_ListNode *p=first； int j=1； while(p & jnlink；+j； /查找第i个结点 if (i0 & !p) throw OutOfBounds( )；/没有第i个结点 DLine_ListNode *q=new DLine_ListNode； qdata=x； if (i1) qplink=pplink；pplinknlink=

42、q； qnlink=p；pplink=q； else /插入结点为第一个元素 qnlink=q；qplink=q；first=q； return *this；删除算法删除算法(算法2-13)：templateDLine_ListLink& DLine_ListLink：Delete(int i，T& x) if (i1 | !first) throw OutOfBounds( )；/删除位置不合法 DLine_ListNode *p； if (!p=Get_Elem(k) return false； x=pdata； pplinknlink=pnlink； pnlinkplin

43、k=pplink； delete p； return *this； 2.4 线性表的应用线性表的应用例例25 试比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，表长分别为m和n。Aq和Bq分别为 A 和 B 中除去最大共同前缀后的子表。例如，A=(x，y，x，z，x，z)，B=(x，y，x，z，y，x，x，z)，两个表的最大共同前缀为 (x，y，x，z) 。则Aq=(x，z)，Bq=(y，x，x，z)。若Aq=Bq=空表，则A=B；若Aq=空表且Bq空表，或两者均不空且Aq的首元素小于Bq的首元素，则AB。算法思路：首先找出A、B的最大共同前缀；然后求出Aq和Bq，之

44、后再按比较规则进行比较，AB 则返回1；A=B则返回0；AB则返回1。选用顺序存储结构，具体算法如下：templateint compare(Line_ListSqu A，Line_ListSqu B，int m，int n) Line_ListSqu Aq，Bq； int i=0，j=0，ml=0，nl=0； while (A.elemi= =B.elemi) i+； /找最大共同前缀 for (j=i；jm；j+) Aq.elemji=A.elemj；ml+； /求Aq，ml为Aq的长度 for (j=i；j0 | m10 & n10 & Aq.elem0Bq.elem0)

45、 return 1； else return 1；例26 已知单链表H为一个用带头结点的链表表示的线性表，写一算法将其倒置。算法描述如下：templatevoid Line_ListLink：Reverse ( ) Line_ListNode *p，*head=new Line_ListNode( )； while(first!=NULL) p=first；first=firstlink； plink=headlink；headlink=p； first=headlink； delete head；例题2.7 一元多项式相加/多项式类定义class Node public： float ef；int exp；class Polynomial public： Polynomial(Line_ListLink *list