[数据结构课件] 第2章 线性表.pdf

从第2章至第4章将讨论 线性结构。线性结构的特点是:在数据元素的非空有限集中，/(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元 素；(3)除第一个之外，集合中的每个数据元素均只有 一个前驱；(4)除最后一个之外，集合中每个数据元素均只有 一个后继。第2章线性表第2.1线性表的类型定义 2.2线性表的顺序表示和实现、2.3线性表的链式表示和实现目2.4 一元多项式的表示及相加21线性表的类型定义a学时)V/乂性(Linear_List)是最常地目晨简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个 数据元素的具体含义，在不同的情况下各不相同，它可以 是一个数、或一个符号，也可以是一页书，甚至其它更复 杂的信息。例如，26个英文字母的字母表：(A,B,C,，Z)是一个线性表，表中的数据元素是单个字母字符。又如，某校从1978 年到1983年各种型号的计算机拥有量的变化情况，可以用线性表的形 式给出：(6,17,28,50,92,188)表中的数据元素是整数。在稍复杂的线性表中，一个 可以由若干个(Item)组成。在这种情况下，常把数据元素称为(Record),含有大量记录的线性表又称(File)。例如，一个学校的学生健康情况登记表如图2.1所示，表中每个学 生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况 等六个数据项组成。图2.1学生健康情况登记表姓名学号性别年龄班级健康状况王小林790631男18计98健康陈红790631女20计98一般刘键平790633男21计98健康张立立790634男17计98神经衰弱 综合上述三个例子可见，线性表中的数据元素可 以是各种各样的，但同一线性表中的元素必定具有相 同特性，即属同一数据对象，相邻数据元素之间存在 春序偶关系。若将线性表记为，、/(a，冏一1，a1+i，(2 1)线性表中元素的个数n(nNO)定义为线性表的长度,n=0时称为空表。在非空表中的每个数据元素都有一个 确定的位置，如为是第一个数据元素。位是最后一个 数据元素，码是第i个数据元素，称i为数据元素马在线 性表中的位序。线性表是一个相当灵活的数据结构，它的长度可根据 需要增长或缩短，即对线性表的数据元素不仅可以进行访 问，还可进行插入和删除等。/抽象数据类型线性表的定义如下：ADT List数据对象：D=aj|a,eElemSet,i=1,2,3,n,n0数据关系：R1=|如-eD,i=2,.,n基本操作：/lnitList(&L)I 操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表。ClearList(&L)初痛条件：线性表L已存在。/I操作结果：将L重置为空表。ListEmpty(L)初法条件：线性表L已存在操作结果：若L为空表，贝U返回TRUE,否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在，iWKListLength(L)。操作结果：用e返回L中第i数据个元素的值。ILocateElem(L,e,compare()初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回1_中第1个与e满足关系compare()的数据元素的位序。不存在，则返 值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在、/I操作结果：若cur_e是L的数据元素，且不是 第一个，则用pre_e返回它的前驱,否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作作失败，next_e 无定义。Listlnsert(&L,i,e)初始条件：线性表L已存在，1iListLengWL)+1o/操作结果：在L中第i个立置之前插入新的数据元素e,L的长廖加1。/IListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1i ListLength(L)o操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L,visit()初始条件：线性表L已存在。I操作结果：依次对L的每个数据元素调用函数visit()oADT List例2-1假设利用两个线性表LA和LB分别表示两个集合A 和B(即：线性表中的数据元素即为集合中的成员)，现要求一 个新的集合A二AUB。V/void union(List&La,List Lb)I 将所有在线性表Lb中但不在La中的数据元素插入到La中 HLa_len=ListLength(La)；Lb_len=ListLength(Lb)；for(i=1；i=Lb_len；i+)GetElem(Lb,i,e)；/La中不存在和e相同的数据元素，则插入 if(!LocateElem(La,e,equal)Listinsert(La,+La_len,e)；/union-算法？1-例2-2已知线性表LA和LB中的数据元素按值非递减有 序排列，现要求将LA和LB归并为一个新的线性表LC,且LC 中的数据元素仍按值非递减有序排列。例如，设 ILA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,8,9,11,11,15,20)void MergeList(List La,List Lb,List&Lc)已知线性表La和Lb中的数据元素按值非递减排列。归并La/I 和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。/InitList(Lc)；i=j=1；k=0；La_len=ListLength(La)；Lb_len=ListLehgth(Lb)；while(i=La_len)&(j=Lb_len)Get曰em(La,i,&ai)；GetElem(Lb,j,&bj)；if(ai=bj)Listlnsert(Lc,+k,ai)；+i；else Listinsert(Lc,+k,bj)；+j；)算法2.2上述两个算法的时间复杂度分析：假如GetElem和Listinsert这两个操作的执行时间 和表长无关，LocateElem的执行时间和表长成正比，邛 /H/算法2的时间复杂度y ，.O(ListLength(LA)*ListLength(LB),算法2.2的时间复杂/则 O(ListLength(LA)+ListLength(LB)o虽然算法2.2中含三个(while)循环语句，但只有当i和j均指向 表中实际存在的数据元素时，才能取得数据元素的值并进行相互 比较；并且当其中一个线性表的数据元素均已插入到线性表LC中 后，只要将另外一个线性表中的剩余元素依次插入即可。因此，对于每一组具体的输入(LA和LB),后两个(while)循环语句只执行 一个循环体。2.2线性表的顺序表示和实现(1学时)线性表的顺序表示指的是用一组地址连续的存储单元依 次存储线性表的数据元素。假设线性表的每个元素需占用L个存储单元，并以所占 的第一个单元的存储地址作为数据元素的存储位置。则线性 表中第i+1个数据元素的存储位置LOC(aj+i)和第i个数据元素 的存储位置LOC(aJ之间满足下列关系：LOC(ai+1)=LOC(aj)+L一般来说，线性表的第i个数据元素司的存储位置为 ILOC(aJ=L0C(ai)+(i-1)*L式中LOC(ai)是线性表的第一个数据元素的存储位置，通 常称做线性表的起始位置或基地址。线性表的这种机内表示称做线佳表的小同雷结构或顺(Sequential Mapping),反之，称这种存储结构的线性存储地址 表为顺序表。它的特点是，为表中相邻 b 的元素马和ai+1赋以相邻的存 b+i、储位置 LOC(a)和 LOC(aj+i)。换句话说，以元素在计算机内内存状态a2数据元素在线 性表中的位序12“物理位置相邻”来表示线性 表中数据元素之间的逻辑关系o(见图2.2)。由此，只要确定 了存储线性表的起始位置，线 性表中任一数据元素都可随机 存取，所以线性表的顺序存储b+(i-1)*Laib+(n-1)*L结构是一种 的存储结构。由于高级程序设计语言中的数组类型也有随机存取的 特性，因此，瞰都用数组来描述数据结构中的顺年存储 结核。在此，由于线性表的长度可变，且所需最存储空间 随问题不同而不同，则在C语言中可用动态分配的一维数 组，如下描述。/-线性表的动态分配顺序存储结晶一 仙efine LIST_INIT_SIZE 100 线性表存储空间的初始分配量#define LISTINCREMENT 10 线性表存储空间的分配增量 Mtypedef struct ElemType*elem/存储空间基址int length;当前长度int listsize；/当前分配的存储容量(以sizeof(ElemType)为单位)JSqList；Status lnitList_Sq(SqList&L)构造-个空的线咐L。V/L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(E1emType)if(!L.elem)exit(OVERFLOW)；/存储分配失败L.length=0；/空表长度为0L.listsize=LIST_INIT_SIZE；/初始存储容量return OK；/lnitList_Sq算法2.3在这种存储结构中，容易实现线性表的某些操作，如随机存取第i个数据 元素等。只是要特别注意的是，C语言中数组的下标从“0”开始，因此,若L是SqList类型的顺序表，则表中第i个数据元素是L.EIemi-1。下面重 点讨论线性表的插入和删除两种操作在顺序存储表示时的实现方法。图2.3线性表插入前后的状况(a)插入前n=8;(b)插入后n=9;序号序号数据儿余儿乐112112213213321321插入4 _A2442425 5285256306287427308778429977(a)(b)例如，图2.3表示一个 线性表在进行插入操作的前、后4其数据元素在存储空间 中的位置变化。为了在线性 表的第4和第5个元素之间插 入一个值为25的数据元素，则需将第5个至第8个数据元 素依次往后移动一个位置。|一般情况下，在第 1 i(14Wn)个元素之前插入一个 元素时，需将第n至第i(共n-i+1)个元素向后移动一个位 置，如算法2.4所示。Status Listlnsert_Sq(SqList&L,int i,ElemType e)/在顺序线性表L中第i末位置之前插入新的元素e,/./i的合法值为 14iVListLength_Sq(L)+1if(iL.length+1)return ERROR；i值不合法/if(Length 二Listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.1istsize+LISTINCREMENT)*sizeof(ElemType)if(!newbase)exit(OVERFLOW)；存储分配失败L.elem=newbase；新基址L.listsize+=LISTINCREMENT；/增加存储容量q=&(L.EIemi-1)；/q 为插入位置for(p=&(L.elemL.length-1)；p=q；-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e；/插入 e+L.length；/表长增 1return OK；/Listinsert _Sq算法2.4反之，线性表的删除操作是使长度为n的线性表变成长度为n-1的线性表。/一般情况下，删除第i(14in)个元素时需将从第 i+1至第n(共n-i)个元素依次向前移动一个位置，如算法 2.5所示。Status ListDelete_Sq(SqList&L,int i,ElemType&e)/在顺序线性表I中删除第i个元素，并用e返回/其值，i的合法值为10iListLength_Sq(L)if(iL.length)return ERROR；p=&(L.elemi-1)；/p为被删除元素的位置/e=*p；/被删除元素的值赋给e q=L.elem+L.1ength-1；表尾元素的位置 for(+p；pnext；7 j=i；初始化，p指向第一个元素结点，j为计数器 while(p&jnext；+j；)if(!p|ji)return ERROR；第i个元素不存在 e=p-data；/取第i个元素return OK；/GetElem_L算法2.8“插入r和”在单链表中,何实现r操作呢?(a)插入前;为插入数据兀素X,首先要 生成一个数据域为X的结点，然 后插入在单链表中。根据插入操 作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x,而结点x中的指针域应指向结点 b,从而实现三个元素a,b和x 之间逻辑关系的变化。插入后的 单链表如图2.8(b)所示。假设s 为指向结点x的指针，则上述指 针修改用语句描述即为：s-next=p-next；p-next=s；a(b)插入后。图2.8在单链表中插入 结点时指针变化状况反之，如图2.9所不在 线性表中删除元素b时，为 在单链表中实现元素a、b和 c之间逻辑关系的变化，仅 需修改结点a中的指针域即 可。假设p为指向结点a的指 针，则修改指针的语句为：p-n ext=p-n ext-next；可见，在已知链表中元 素插入或删除的确切位置的 情况下，在单链表中插入或 删除一个结点时，仅需修改 指针而木需要移动兀素。J j一 a；b 1c图2.9在单链表中删除结 点时指针变化状况算法2.9和算法2.10分别为Listinsert和ListDelete在单链浮中的实现。A/Status Listlnsert_L(LinkList&L,int i,ElemType e)/在带头结点的单链线性表L中第i个.I/位置之前插入元素e/.p=L；j=0；while(p&jnext；+j；/寻找第i-1 个结点if(!p|ji-1)return ERROR；s=(LinkList)malloc(sixeof(LNode)；s-data=e；s-n ext=p-next；p-next=s；return OK;/Listlnsert_L算法2.9Status ListDelete_L(LinkList&L,int i,ElemType e)/在带头结点的单链线性表L，删/除第i个元素，并由e返回其(/p=L；j=0；while(p-next&j next；+j；)if(!(p-next)|j-1)return ERROR；q=p-next；，p-next=q-next；册！I除并释放结点 e=q-data；free(q)；return OK；/ListDelete_L删除位置不合理算法2.10单链表和顺序存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表 占用的空间不需预先分配划定，而是可以由系统应需 求即时生成。因此，建出性表的链式上储结构的过 程就是一个动态生成链表的过程。即从“空表”的初 始状态，依次建立各元素结点，并逐个插入链表。void CreateList_L(LinkList&L,int n)逆位序输入n个元素的值，建立带表头结点的单链线性表L。L=(LinkList)malloc(sizeof(LNode)；/L-next=NULL；先建立一带头结点的单链表 Ifor(i=n；i0；-i)p=(LinkList)malloc(sizeof(LNode)；scanf(&p-data)；输入元素值7 Hp-next=L-next；L-next=p；/插入至表头)算法2.11(其时间复杂度为0(n)。)下面讨W如何够两个有序 链表则一个有序冷？假设头指针为La和Lb的单 链表分别为线性表LA和LB的存 储结构，现要归并La和Lb得到 单链表Lc,按照2.1节中算法 MergeList的思想，需设立三个 指针pa、pb和pc,其中pa和pb 分别指向La表和Lb表中当前待 比较插入的结点，而pc指向Lc 表中当前最后一个结点，若pa-data data,则将pa所指 结点链接到pc所指结点之后，否则将pb所指结点链接到pc所 指结点之后。/paLa|十void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc,/Lc的元素也按值非递减排列o pa=La-next；pb=Lb-next；Lc=pc=La；用La的头结点作为Lc的头结点while(pa&pb)if(pa-data data)pc-next=pa；pc=pa；pa=pa-next；)else pc-next=pb；pc=pb；pb=pb-next)pc-next=pa?pa:pb/插入乘U余段free(Lb)；释放Lb的头结点/MerqeList_L算法2.12有时，也可借用一维数组来描述线性链表，其类型说 明，如下所示：线性表的静态单链表存储结构Y/#define MAXSIZE 1000 链表的最大长度typedef structElemTyPe data；int Cur；component,SLinkList MAXSIZE；这种描述方法便于在不设“指针”类型的高级程序设 计语言中使用链表结构。在如上描述的链表中，数组的一 个分量表示一个结点，同时用游标（指示器cur 代替指针 指示结点在数组中的相对位置。数组的第零分量可看成头 结点，其指针域指示链表的第一个结点。1ZHAO2QIA.3SU4LI/5ZHOU6WU7ZHENG8WANG011ZHAO22QIAN33SUN44LI95ZHOU66WU87ZHENG88WANG09SHI510(a)修改前的状态；(b)修改后的状态 图2.10静态链表示例例如，图2.10(b)展 示了图2.10(a)所示线 性表在插入数据元素“SHF和删除数据元 素“ZHENG”之后的状 况。为了和指针型描 述的线性链表相区别,我们给这种用数组描 述的链表起名叫静态 链表假设S为SLinkList型变量，则SOCur指示第一个结 点在数组中的位置，若设i=S.cur,贝恰rdata存储 线性表的第一个数据元素，且si.cur指示第二个结点 在数组中的位置。一般情况，若第i个分量表示链表的 第k个结点，则Si.cur指示第k+1个结点的位置。因此 在静态链表中实现线性表的操作和动态链表相似，以 整型游标i代替动态指针p,i=SiCur的操作实为指针 后移（类似于P=p-next。例如，在静态链表中实现的定位函数Locate日em 如算法2.13所示、/Iint LocateElem_SL(SLinkList S,ElemType e)/在静态单链线性表L中查找第1个值为e的元素。/若找到，则返回它在L中的位序，否则返回0。i=S0.cur；i指示表中第一个结点 Iwhile(i&Si.data!=e)i=Si.cur；在表中顺链查找return i；/LocateElem_SL算法2.13类似地可写出在静态链表中实现插入和删除操作的 算法。从图2.10的例子可见，指针修改的操作和前面描 述的单链表中的插入和删除的算法2.9,2.10类似，所 不同的是，需由用户自己实malloc和free这两个函数。为了辨明数组中哪些分量未被使用，解决的办法是将所 有未被使用过以及被删除的分量用游标链成一个备用的 链表，每当进行插入时便可从备用链表上取得第一个结 点作为待插入的新结点；反之，在删除时将从链表中删 除下来的结点链接到备用链表上。2.3.2 循环链表循环链表(Circularinked List)是另一种形式的 链式存储结构。它的特是点表中最后一个结点的指针 域指向头结点，整个链表形成一个环。由此从表中任 一结点出发均可找到表中其它结点，如图2.12所示为 单链的循环链表。(a)非空表(b)空表图2.12单循环链表循环链表的操作和线 性表基本一致，差别仅在 于算法中的循环条件不是P 或者pnext是否为空，而是它们是否等于头指针。但有的时候，若在循 环链表中设置尾指针而不 设头指针(如图(a)所示)可使某些操作简化。例如 将两个线性表合并成一个 表日寸，仅需将一个表的表 尾和另一个表的表头相接。仅需改变两个指针即可，运算时间为0(1)。合并后 的表如图(b)所示。_ _(b)2.3.3 双向链表以上讨论的链式存储结构的结点中只有一个指示直 接后继的指针域，因此从某个结点出发只能顺时针往 后寻查其它结点。若要寻查结点的直接前趋，则须从 表头指针出发。/在单链表中，NextElem的执行时间为0(1),而 PriorElem的执行时间为0(n)。为了克服单链表这种单 向性的缺点,可利用双向链表(Double Linked List)。/-线性表的双向链表存储结构一 typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;L(b)空的双向循环链表L(c)非空的双向循环链表若P为指向表中某结点的指针，则 p-next-prior=p-prior-next=p在双向链表中，有些操作如：ListLength、GetElem 和LocateElem等仅需涉及一个方向的指针，则它们的算 法描述和线性表的操作相同，但在插入、删除时有很大的 不同，在双向链表中需同时修改两个方向的指针。图2.15在双向链表中删 除结点时指针变化状况图2.16在双向链表中插入 一个结点时指针变化状况Status Listlnsert_DuL(DuLinkList&L,int i,ElemType e)/在带头结点的双链循环线性表中第i个位置之前插入元素e,./i的合法值为1 v=i v二表长+1/.if(!(p=GetElemP_DuL(L,i)/在L中确定第i个元素的位置指针preturn ERROR;/p=NULL,即第i个元素不存在 if(!(s=(DuLinkList)malloc(sizeof(DuLNode)return ERROR;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return OK;/Listlnsert_DuL;算法2.18Status ListDelete_DuL(DuLinkList&L,int i,ElemType&e)/删除带头结点的双链循环线性表L的第i个元素，/./i的合法值为1室表长/.if(!(p=GetElemP_DuL(L,i)/在L中确定第i个元素的位置指针preturn ERROR；/p=NULL,即第i个元素不存在 e=p-data；p-prior-next=p-next;p-next-prior=p-prior;free(p)；return OK/ListDelete_DuL算法2.19从本节(2.3)的讨论中可见，由于链表在空间的合 理利用上和插入、删除时不需要移动等的优点，因此 在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作如求线性表的长度时不 如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系用指针来表示，则数据元素在线性表 中的“位序”的概念已淡化，而被数据元素在线性链 表中的“位置”所代替。为此，从实际应用角度出发 重新定义线性链表及其基本操作。一个带头结点的线性链表类型定义如下:typedef struct LNode 结点类型ElemType data;struct Lnode*next;*Link,*position;typedef struct 链表类型Link head,tail;/分别指向线性链表中的头结点和最后一个结点 int len；指示线性链表中数据元素的个数JLinkList；Status MakeNode(Link&p,ElemType e)；分配由p指向的值为e的结点，并返回OK；/若分配失败，则返回ERROR；/void FreeNode(Link&p)；/释放P所指结点/Status InitList(LinkList&L)；构造-个空的线性链表LStatus DestroyList(LinkList&L)；销毁线性链表L,L不再存在Status ClearList(LinkList&L)；/将线性链表L重置为空表，并释放原链表的结点空间Status InsFirst(Link h,Link s)；/已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前Status DelFirst(Link h,Link&q)；/已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回Status Append(LinkList&L,Link s)将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的/最后一个结点之后，并改变链表L的尾指针指向新的尾结点Status Remove(LinkList&L,Link&q)；删除线性链表L中的尾结点并以q返回，.改变链表L的尾指针指向新的尾结点.Status lnsBefore(LinkList&L,Link&p,Link s)；/已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，并修改指针P指向新插入的结点Status InsAfter(LinkList&L,Link&p,Link s)；/已知p指向线性链表、的一个结点，将S所指结点插入在/p所指结点之后并修改指针P指向新插入的结点Status SetCurElem(Link&p,ElemType e)；/已知p指向线性链表中的一个名品，用e更新p所指结点中数据元素的值ElemType GetCurElem(Link p)；已知p指向线性链表中的一个结点，/返回P所指结点中数据元素的值Status ListEmpty(LinkList L)；/若线性链表L为空表，则返回TRUE,否则返回FALSEint ListLength(LinkList L)；/返回线性链表L中元素个数Position GetHead(LinkList L)；/返回线性链表L中头结点的位置Position GetLast(LinkList L)；返回线性链表L中最后一个结点的位置Position PriorPos(LinkList L,Link p)；/已知p指向线性链表L中的一个结点，返回p所指结点的,直接前驱的位置，若无前驱，则返回NULL、Position NextPos(LinkList L,Link p)；/已知p指向线性链表L中的一个结点，/返回p所指结点的直接后继的位置，若无后继，则返回NULLStatus LocatePos(LinkList L,int i,Link&p)；返回p指示线性链表L中第i个结点的位置并返回OK,/呼不合法时返回E,OR/Position LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)/返回线性链表L中第1个与e满足.I函数compare。判定关系的元素的 I/位置，若不存在这样的元素，则返回NULL Status ListTraverse(LinkList L,Status(*visit)()；依次对L的每个元素调用函数vis*),一旦vis让()失败，则操作失败。在上述定义的线性链表的基本操作中，除了 DestroyList,ClearList,Remove,InsBefore,PriorPos,LocatePos,LocateElem和ListTraverse的时间复杂度和表 长成正比之外，其它操作的时间复杂度都和表长无关，Append操作的时间复杂度则和插入的结点数成正比。利用 这些基本操作，容易实现诸如在第i个元素之前插入元素或 删除第i个元素或合并两个线性表等操作。Status Listlnsert_L(LinkList&L,int i,ElemType e)，在带头结点的单链线性表L的第i个元素之前插入元素eif(!LocatePos(L,i-1,h)return ERROR；I H仅值不合法/Iif(!MakeNode(s,e)return ERROR；T/结点存储分配失败 lnsFirst(h,s)；return OK；/Listlnsert_L算法2.202.4 一元多项式的表示及相加(1 学时)/./V/符号多项式的操作，已圭成为表处理的典型用例。在数学上，一个一元多项式Pn(x)可按升塞写成：Pn(x)=Po+P1X+p2x2+.V pnxn,它由n+1 个系数唯一定。因此，在计算机里，它可用一个线性表P来表示：P=(P0，Pl，P2,Pn)每一项的指数i隐含在其系数Pi的序号里。I假设Qm(x)是一元m次多项式，同样可用线性表Q 来表示Q=(q0 q 虫qm)不失一般性，设mvn,则两个项式相加的结果Rn(x)=Pn(x)+Qm(x)可.线性表R表示：/R=(Po+q0，Pl+q1，P2+q2，Pm+qm，Pm+1，Pn)显然，我们可以对P、Q和R采用顺序存储结构，使得多 项式相加的算法定义十分简洁。然而在通常的应用中，多项式的次数可能很高且变 化很大，使得顺序存储结构的最大长度很难决定。特别是 在处理形如S(x)=1+3x10000+2x20000的多项式时，就要用一长度为20001的线性表来表示，表 中仅有三个非零元素，这种对内存空间的浪费是应当避免 的，但是如果只存储非零系数项则显然必须同时存储相应 的指数。一般情况下的一元n次多项式可写成Pn(X)=pxe+p2xe2+.+pmXem(2-7)其中Pi，是指数为ei的项的非零系数，且满足0 e1 e2 .=0，TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|3,_|,a,e D,且冏中的指数值司中的指数值，i=2,3,.,n基本操作：/CreatPolyn(&P,m)操作结果：输入m项的系数和指数,建立一元多项式PDestroyPolyn(&P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PolynLength(P)初始条件：-元多项式P已存在。/.操作结臬：返回-元多项RP中的项数/AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb,并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa-Pb,并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)/初始条件：-元多项式Pa和Pb已存在。/操作结果：完成多项式相乘运算，即：W Pa=Pa*Pb,并销毁-元多项式Pb。ADT Polynomial如何实现用这种线性链表表示的多相式的加法运算?根据一元多项式相加的运算规则：对于两个一 元多项式中所有指数相同的项，对应指数相加，若 其和不为零，则构成“和多项式”中的一项；对于 两个一元多项式中所有指数不相同的项，则分别复 抄到“和多项式”中去。在此，按照上述抽象数据类型Polynomial中基 本操作的定义，“和多项式”链表中的结点无需另 生成，而应该从两个多项式的链表中摘取。例如，图2.17中的两个线性链表分别表示一元多项式 A(x)=7+3x+9x8+5x17 和一元多项式 B(x)=8x+22x7-9x8o 从图中可见，每个结点表示多项式中的一项。B图2.17多项式的单链表存储结构图2.18相加得到的和多项式上述多项式的相加过程和上一节讨论的归并两个有 序表的过程极其类似，不同之处仅在于，后者在比较数 据元素时只出现两种情况。因此，多项式相加的过程亦 完全可以利用线性链表的基本操作来完成。在2.3节末 定义的线性链表类型适用于一般的线性表，而表示一元 多项式的应该是有序链表。有序链表的基本操作定义与线性链表有两处不同，一 是LocateElem的职能不同，二是需增加按有序关系进行插 入的操作Orderinsert,现说明如下：Status LocateElem(LinkList L,ElemType e,Position&q,int(*compare)(ElemType,ElemType)；若有序链表L中存在与e满足判定函薮compare。取值为0的元素，贝Uq指示L中第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数compare。取值 0的元素的前驱的位置，并返回 FALSEStatus Orderlnsert(LinkList&L,ElemType e,int(*compare)(ElemType,ElemType)；I 按有序判定函数compare。的约定,将值为e的结点插入到有序链表L的适当位置例2-4抽象数据类型Polynomial的实现。typedef struct/项的表示，多项式的/B作为LinkList的数劈元素/Mfloat coef；/系数int expn；/指数term,ElemType；两个类型名：term用于本ADT,ElemType为LinkList的数据对象名typedef structElemType e；Lnode*next；Lnode,LinkList；typedef LinkList polynomial；用带表头结点的有序链表表示多项式/基本操作的函数原型说明-void CreatPolyn(polynomail&P,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid DestroyPolyn(polynomail&P)；/销毁-元多项式P/void PrintPolyn(polynomail P)；打印输出一元多项式pint PolynLength(polymomail P)；返回一元多项式P中的项数void AddPolyn(polynomail&Pa,polynomail&Pb)；完成多项式相加运算，即：Pa=Pa+Pb,并销毁一元多项式Pbfvoid SubtractPolyn(polynomail&Pa,polynomail&Pb)；完成多项式相减运算，即：Pa=Pa-Pb,并销毁一元多项式Pbvoid MultiplyPolyn(polynomail&Pa,polynomail&Pb)；完成多项式相乘运算，即：Pa=Pa*Pb,并销毁一元多项式Pb/-基本操作的算法描述（部分）-int cmp term a,term b；依a的指数值v（或=）（或 b的指数值,分别返回-1,0和1；算法2.22void CreatPolyn(polynomail&P,int m)输入m项的系数和指数，建立表示一元多项式的有序链表夕InitList(P)；h=GetHead(P)；e.coef=0.0；e.expn=-1；/SetCurElem(h,e)；设置头结点的数据元素for(i=1；inext;2)L=P-next;3)R-data=P-data;4)R-data=P-next-data5)P-next-next-next-data=P-data;6)T=Pwhile(T!=NULL)T-data=T-data*2;T=T-next7)T=Pwhile(T-next!=NULL)T-data=T-data*2;T=T-next2.3简述以下算法的功能。1)Status A(LinlList L)yL是无表头结点的单链表/if(L&L-next)Q=