数据结构第二章线性表.docx

第二章线性表本章基本知识点：线性表的逻辑结构及其基本操作顺序存储结构和链式存储结构，以及基本操作的算法设计 静态链表的存储结构、循环链表、双向链表元素的插入、删除 线性表的应用1线性表的类型定义(线性表的逻辑结构)下面给出两个二维表的实例：线性表：简称表，是n (n30)个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L= (% a2 , ，气,ai , ，a, 其中，ai (IWiWn) 称为数据元素；下角标i表示该元素在线性表中的位置或序号。线性结构的基本特征是：线性结构是一个数据元素的有序(次序)集1. 集合中必存在唯一的一个“第一元素”；2. 集合中必存在唯一的一个“最后元素”；3. 除最后元素在外，均有唯一的后继；4. 除第一元素之外，均有唯一的前驱。线性表的抽象数据类型定义如下：Linear_list=(D, S, P)D = ail ai ElemSet,i=0,1,2,. .,n-1S = <ai 1,ai>| ai 1,aiD, i=1,2,.,n-1<ai 1,ai>为序偶，表示前后关系基本操作P：插入、删除、修改，存取、遍历、查找。void ListAppend(List L, Elem e);void ListDelete(List L, int i);int SetElem(List L, int i, Elem e);int GetElem(List L, int i, Elem &e);int ListLength(List L);void ListPrint(List L);int LocateElem(List L, Elem e);合并、分解、排序例：利用线性表LA和LB分别表示集合A和B,求A=AUB0void union(List &La, List Lb) ( int La_ len, Lb_ len;La_ len=ListLength(La);Lb_ len=ListLength(Lb);for(i=1; i<=Lb_len; i+) GetElem(Lb, i, e);if(!LocateElem(La, e)ListAppend(La, e);/计算表长/取Lb的第i个元素/在La中查找e/在La中插入e2线性表的顺序表示和实现线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表中的数据元素一段连续的存储空间存储线性uI下标： 01i2 i-1n-141 | | 务-i | 务 | 云用一维数组来实现线性表由上图可以看出线性表第i个数据元素存储在数组下标为i-1的位置，即数据元 素的序号和存放它的数组下标之间存在着对应关系。一般情况下，(a，a，.,a.i，a.，,a )的顺序存储：121-1i n01-2i-1n-1Max-1气%气a空闲长度*Loc(a )Loc(a)1i下际：01i-2 i-ln-1 划 13&12用-1空区去的坦度所以，L。C0J = SG Wi) + 0 1，其中c为每个元素所占用的存储单元。线性表的动态分配的顺序存储结构#define LIST_INIT_SIZE 100#define LIST_INCREMENT 10/存储空间的分配增量typedef struct( ElemType *elem; /存储空间的基址int length;当前表长int listsize;当前已分配的存储空间SqList;Status InitList_Sq( SqList& L ) /构造一个空的线性表L.elem = (ElemType*)malloc (LIST_INIT_SIZE sizeof (ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK; / InitList_Sq算法时间复杂度O(1)补充知识点：C中的动态分配与释放函数 void *malloc(unsigned int size)生成一大小为size的结点空间，将该空间的起始地址赋给p； free(void *p)回收p所指向的结点空间； void *realloc(void *p, unsigned int size)将p所指向的已分配内存区的大小改为size，size可以比原分配的空 间大或小。/*函数结果状态代码*/#defineTRUE1#defineFALSE0#define OK 1#defineERROR0#define INFEASIBLE -1#define OVERFLOW-2/*函数结果状态类型，其值为上述的状态代码*/typedef int Status;顺序表的基本操作：LocateElem(L, e, compare() II 查找ListInsert(&L, i, e) 插入元素ListDelete(&L, i) 删除元素顺序表基本操作的实现：插入操作:(a, ., a , a,., a)改变为11-1 n(a , ,a , e, a, ,a )1111<a , a> 1-1' 1<M，e>, <e, ai>a a aa a1 2i-1inaa ae a a12i-1i表的长度增加插入操作的分析：e,则原来第iL.length个数据元素必须先后移，第i个位置放以腾出第i个位置；后移的顺序是从最后一个元素开始（为什么？），逐个往后移q = &（L.elemi-1）;/ q 指示插入位置for （p = &（L.elemL.length-1）; p >= q; -p）*（p+1） = *p;/插入位置及之后的元素右移*q = e; / 插入 e+L.length; / 表长增 1或者，不用指针操作for （ j = L.length; j >= i; j-）L.elemj = L.elemj-1; / 后移L.elemi -1 = e; /第 i 个元素存放在 L.elemi-1中L.length = L.length+1;i的合法范围为 1WiWL.length+1当L.lengthNL.listsize时，先申请一个有一定增量的空间：申请成功则原空间的元素复制到新空间，修改L.listsize，再进行插入工作; 否则报错退出。插入操作的算法分析：闾题拧膜是表的长度length （设为月），基本i吾句是for循环白兀 素后移语句。-最好情况 E+1 （在表尾插» 不需要移劫元素，时TH复 杂度为。（1虞"" -最坏情况：>1 （在表普插，需要移动全部元素，后移语 句执行M被，时间复杂度为n+1w-/+.!）= -=O（Yl）!-12,也就是说,在顺序表上实现插五操作，等概率情况下，平均要移动表中一半的元素，算法的平均时间复杂度为。（痂-平均惜况4令.瑶网表示元素移动次数的平均值设乩表示插 .入第£ （1名寻+1】环位置的概率，假设以=1位+1）,由 于在第£个位苜上插氐元素后移语句的执行没数为vi+i,故：M+l1删除操作(a , a , a., a, ., a )改变为11-111+1 n(a1,，a1-1, a1+1,-<a1-1, a1>, <a1, a1+1><a 1-1a 1+1删除操作的分析：去掉第i个元素，则原来第i+1L.length个数据元素必须前移以覆盖第i个位置；前移的顺序是从第i+1元素开始，逐个往前移p = &(L.elemi-1);e = *p;q = L.elem+L.length-1; for (+p; p <= q; +p)/ p为被删除元素的位置/被删除元素的值赋给e/表尾元素的位置*(p-1) = *p;/被删除元素之后的元素左移-L.length;或者，不用指针for ( j = i; j < L.length ; j+) L.elemj-1 = L.elemj; L.length = L.length-1删除操作的算法分析：/表长减1间题规模是表的长度length (设为心，基本i吾句是for循环中元 素前移语句。最好1情况：删除表尾元素(即Ml),无需移动元素，时间复 杂度为0 (1) -最坏情况：删除表头元素(即，需移动除第T元素以 外的所有元素，时间复杂度为平均情况：令 y 表示元素移动次数的平的值*设川表示删 除第？ £：1买遂办卞元素的概率，假设P 1=2-=/'= 1,由于删除 第/个元素需要移动n-i个元素，故Eg = 或=-f 侦一快=萱1 =。(n)2-1咨 2-12也就是说，在I底序表上实现删朝作，等概率情况下，平均要移动表 中一半的元素，算法的平均时间复杂度为削唯总结顺序表的优缺点：顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：插入和删除操作需要移动大量元素；表的容量难以确定，表的容量难以扩充； 造成存储空间的碎片。例题解析：例1：增序顺序表的合并，设其中无相同元素Status SqList_Merge(SqList La,SqList Lb,SqList &Lc)( ElemType *pa,*pb,*pc,*pa_last,*pb_last;Lc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem) return ERROR;pa=La.elem; pb=Lb.elem; pc=Lc.elem;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1; while(pa<=pa_last && pb<=pb_last) if(*pa<=*pb) *pc=*pa; pc+; pa+; else *pc=*pb; pc+; pb+; while(pa<=pa_last) *pc=*pa; pc+; pa+; while(pb<=pb_last) *pc=*pb; pc+; pb+; return OK; 算法的时间复杂度为(Lb.length+La.length) )例3 :设有一个顺序表L，其元素为整型数据，设计一个算法将L中所有小于0的整数 放在前半部分，大于等于0的元素放在后半部分。例4 :用顺序表表示集合，设计一个算法实现集合的交集运算。例5：用顺序表表示集合，设计一个算法实现集合的并集运算。2线性动态链表单链表：用一组任意的存储单元存放线性表的元素。例：(a, a ,a, a)的存储示意图 1234存储特点：逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；a 2 - 0325a 1 0200单链表是由若干结点构成的；0200单链表的结点只有一个指针域。0208 单链表的结点结构：数据域指针域data nextdata：存储数据元素03000325-结点Ia30300数据域 气指针域next：存储指向后继结点的地址单链表的结构typedef struct LNode( ElemType data;struct LNode *next;LNODE, *LinkList;单链表的头接点：无头结点：（空表时，L为NULL），第一个结点无前驱结点，只能通过某指针变量来指向，如L；其余结点均有前驱结点，故可通过其直接前驱结点的next域来指向。有头结点：（空表时，L指向一结点（称为头结点），第一个结点和其余结点均可统一表示为其直接前驱结点的next域所指向。单链表的基本操作取第i个元素GetElem_L(LinkList L, int i, ElemType &e)插入操作ListInsert_L(LinkList &L, int i, ElemType删除操作ListDelete_L(LinkList &L, int i, ElemType创建单链表CreateList_L(LinkList &L)e)&e)头插法尾插法单链表基本操作的实现：查找第 i 个数据元素 GetElem_L（LinkList L, inti,ElemType&e)在单薄表中，因为元素序号和该元素的存储位宣之间没有对应关 系，因此，不能像顺序表那样直接按序号访问。单链表的故只能从头指针出发，设置一个工作才薛十顺收 域旗个结点往下搜索当p指向某结削判断是否为第1个结点，若 是，则查找成功；否则，将工作指针p后移。对每个结点依次执行上 述操作，直到p为NULL时查找关败。其查找过程如图219所示。pp p=NULL提出四个问题？如何实现工作指针的初始化？；如何实现累加器初始化？；如何判断p指向第i个接点？；如何实现工作指针的后移？(P+？)GetElem_L(LinkList L, int i, ElemType &e) II 1是带头结点的链表的头指针，以e返回第i个元素P = L->next; j = 1; p指向第一个结点，j为计数器while (p && j<i) p = p->next; +j; /顺指针向后查找，直到p指向第i个元素/或p为空if (!p | j>i )return ERROR; 第i个元素不存在e = p->data;取得第i个元素return ok；算法时间复杂度为: / GetElem_L O(ListLength(L)注意：p+不能保证工作指针移到下一个结点，如下图所示：血 轮!p p+p->next单链表查找算法的性能分析：在单蒲表的查找舞法中，问题规模是表的长度(设为刊，基奉语 句是while ；盾环中M作指针云移语句。最好情祝：查找第f元素结点，无需移动工作指针；最坏情况：查找最后W个元素结点，移动n-1；欠工作指针；平均情况：设查找位置为？"玲5,工作指针需要移动M 而等概率情况下，:时间性能为因此，单链表是顺序存厩结构。 在第 i 个位置插入数据元素 ListInsert_L(LinkList &L, int i, ElemType e) 首先，分析一般情况：要将接点插入到结点气和气1之间，修改和两个指 针为此，需要知道气1的地址。其次，分析表头和表尾的特殊情况，结果：表头，表中间，表尾插入操作语句一致，不要特殊处理。提出三个问题？工作指针的初始化应该指向何处？；如何查找第i-1个位置？；修改指针和的顺序能否替换？(注：示意图中的指针first和算法中的指针L是一回事。)ListInsert_L(LinkList L, int i, ElemType e) /L为带头结点的单链表的头指针，本算法/在链表中第i个结点之前插入新的元素ep = L; j = 0;while (p && j < i-1) p = p->next; +j; / 寻找第 i-1 个结点if (!p II j > i-1)return ERROR; / i大于表长或者小于1s->next = p->next;p->next = s; / 插入return OK;单链表插入算法的时间主要消耗在查找正确的的位置上，所以，时间复杂度也为O(n) 下面分析不带头结点的插入，则需要在表头的情况作特殊的处理，如下图所示：那么，在带头结点的语句上增加下列语句Status ListInsert_L(LinkList L, int i, ElemType e) ( if (i=1)/处理在表头插入的情况。s = (LinkList) malloc (sizeof (LNode);s->data = e;s->next = L; L = s;return OK;else 与带头结点的单链表插入操作相同单链表的第 i 个位置删除操作 ListDelete_L(LinkList &L, int i, ElemType &e) 首先，分析一般情况-要实现结点免1和命1之间逻辑关系的变化-令结点免1的指计 域指向结点叫+1修改指督需要知道结点务一1的地址-查找元素 妇的地址(将工潟旨针口移结点筮1)o-释放被删结点务的存储单元2指针q指向结点的-要求返回被删元素值f在辉放结点以之前将元素取出。q = p->next; p->next = q->next;e = q->data;free(q);其次，分析表头，表尾的情况需要注意在表尾的特殊情况，此时虽然被删除的结点不存在，但其前驱结点 却存在，因此仅当被删除结点的前驱结点p存在且p不是终端结点时，才能确定 被删除的结点存在。上述思想的伪语言描述如下：i.工作J薛十p初始化；累加器演零；2查找第1-1个结点并使工作p指向该结点F菌若查找失败勃脂!1的段端结点*:则抛出位置异常；否则，生1暂存被删结点和被删元素值；摘链，将结点p的后继结点昆龄上摘下； 释放被删结点 ：3 4返回被删元素值；ListDelete_L(LinkList L, int i, ElemType &e) /删除以L为头指针(带头结点)的单链表中第i个结点p = L; j = 0；while (p->next && j < i-1) p = p->next; +j; /寻找第i个结点，并令p指向其前趋if (!(p->next) | j > i-1)return ERROR; /删除位置不合理q = p->next； p->next = q->next； / 删除并释放结点e = q->data; free(q);return OK; / ListDelete_L算法的时间复杂度为：O(ListLength(L)单链表删除操作的时间复杂度的分析：删除算法的时间主要消耗在查找正确的删除位置上，故时间复杂度为O(n) 小结：在单链表上进行插入和删除无须移动元素，在将工作指针指向合适的位置 后，仅需要修改结点之间链接的指针。思考：如何建立单链表，？想法：逆位序输入n个数据元素的值，建立带头结点的单链表。链表是一个动态的 结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。单链表的创建(头插法)first.如何用语旬firsliiewNodiT密实现初端机 口 血卜诲xt=NULL0初始化项迎卜i /%,S 如何用语句 ,© s->5iext=first->iuext;"一实现横仄的匚二1 first->nerf=s;(b)桶六元旗ai如果我们逆序输入n个数据元素的值，就可以建立一个从a0an的表 下面是该算法的C语言描述。CreateList_L(LinkList &L, int n) /逆序输入n个数据元素，建立带头结点的单链表L = (LinkList) malloc (sizeof (LNode);L->next = NULL; 先建立一个带头结点的单链表for (i = n; i > 0; -i) p = (LinkList) malloc (sizeof (LNode);scanf(&p->data); / 输入元素值p->next = L->next; L->next = p; / 插入 / CreateList_L算法的时间复杂度为:O(Listlength(L)单链表的创建(尾插法：将待插入结点插在终端结点的后面。)插入第一个元素结点算法描述:first35 srearrears=new Node<T>s->data=a0;first->next=s;rear=first;依次插入每一个结点算法描述:first3512rearrearrears=new Node<T>s->data=a1;first->next=s;rear=first;CreateList_L(LinkList &L, int n) L = (LinkList) malloc (sizeof (LNode);L->next = NULL; /先建立一个带头结点的单链表 rear=L;for (i = n; i > 0; -i) s = (LinkList) malloc (sizeof (LNode);scanf(&s->data); / 输入元素值 rear->next =s; rear=s; / 插入rear->next=NULL;算法的时间复杂度为：O(Listlength(L) / CreateList_L例题解析例1、增序线性链表的合并，设其中无相同元素。/破坏La和Lb,用La和Lb的结点组合LcLNODE *LinkList_Merge(LNODE *La,LNODE *Lb) ( LNode *pa,*pb,*pctail,*Lc;Lc=pctail=La; / Lc的头结点是原La的头结点 pa=La->next; pb=Lb->next; free(Lb); while(pa!=NULL && pb!=NULL) if(pa->data <= pb->data)( pctail->next=pa; pctail=pa; pa=pa->next; else pctail->next=pb; pctail=pb; pb=pb->next; if(pa!=NULL) pctail->next=pa;else pctail->next=pb; return(Lc);例2无序线性链表的交集AHB ? ?例3线性链表的逆序例4复制线性链表的结点3静态链表用数组来表示单链表，用数组元素的下标来模拟单链表的指针。例：线性表(张，王，李，赵，吴)的静态链表存储first：静态链表头指针，为了方 便插入和删除操作，通常静态链 表带头结点；avail：空闲链表头指针，空闲链 表由于只在表头操作，所以不带 头结点；静态链表的存储结构typedef struct ElemType data;int next;/后继的下标Component;typedef struct Component SpaceMAXSIZE;或 *Space;int avil; /第一个空闲单元的下标SlinkList;静态链表的插入操作在线性表（张，王，李，赵，吴）中“王”之后插入“孙”1 2 6 4 5 4 O - 面 长E ML头是 8 nn- 3 uk- - - N0 1 2 3 4 5孙 入 推后 之 王静态链表的删除操作在线性表（张，王，李，赵，吴）中删除“赵” data nextdata next除«2 3 4 5 张王李赵吴 1 2 3 4 50101张王李赵吴2 3 5 5 -1676778788-18-11张2王3李56吴-178-1data nextdata next0101张212王323李4删除赵34赵5:45吴-1归还空间56767 878 -18思考：相对于顺序表而言，静态链表有什么特点？优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素， 从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要 维护一个空闲链；静态链表不能随机存取。4循环链表将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。（在单链表中结点p出发无法找到其前驱=循环链表）=绥一气 Lf % 一 < first为了使空表和非空表的处理一致，通常也附设一个头结点。循环链表的存储示意图 如下：空表和非空表的处理一致附设头结点 空循环链表first非空循环链表first循环链表的插入操作：（一般情况）循环链表的插入操作：（表头和表尾的情况）注意：循环链表基本操作的实现与单链表的不同之处仅在于循环条件，循环条件 p!=first 或 p->next!=first在用头指针指示的循环链表中，开始结点由first next指示，查找开始 结点的时间为0（1）;查找终端结点需要将单链表扫描一遍，时间为O（n） 假如用指向终端结点的尾指针来指示循环链表，则查找开始结点和终端结点 的时间复杂度均为0（1）（开始结点由rear->next->next指示）rear循环链表的应用（约瑟夫环） 问题的描述：设有端号为1，2，巧的n （n0）个人围成一个圈，每个人 持有一个密码他.从第1 .个人开始报数,才建!I用时停止才收，报皿 的又出圈，再从他的下一个久起重新报数，报到血时停止才收，报m 的出圈，七如此下去"直到所有人全部出圈为止当任意给定h 和血后，设计算法求凹个人出圈的波序分析问题:（运行一个示例，是n=6,m=3时的求解过程。）如就2.出圈<d>.4出圈由上述求解的过程，可以把问题的输入（即n个人的编号）看成是一个线性序列， 因此问题抽象出的模型是线性表。设计存储结构（实质上要考虑的问题一 如何表示某人已经出圈使之不参与下一轮 报数；-当报数到表尾时如何再回到表头使计数循环进行）（1） 顺序存储结构实现约瑟夫环问题a将出圈的人从顺序表中删除，需要移动元素降低了效率。I下标：口 1*3 3下标:D 1 2 3 4 31 传 45|1 檀 |4|5 伯一初始化,：b 5.3出圈b将出圈的人所占的存储单元存储一个标志，（如赋值为0），表示该单元的 的人已经出圈。（2）链式存储结构实现约瑟夫环问题由于约瑟夫环问题本身具有循环性质，为了统一对表中任意结点的操作，循环链表不带头结点。.二 1一> W 3一._A 4字6first一eE一一-" 一、 '"Tlx:ount=2prepE初始化1 -* 33 一- 4 一卜 5- 6firstTV"' 一其基本思想如下：设工作指针p指向当前计数结点，为实现删除结点p的操作再设辅助工作指针pre指向结点p的前驱结点，为了便于工作指针的初始化，将指针pre初试化为开始结点，将指针p初试化为开始结点的后继，计数从2开始。伪代码描述如下：1.工作指针pre和p初蜘尤，计数器count初始化； prerst p=fii'st-<-next; count=2;Y为瘦于研蛛圈饵 M2开始计数2循环直到p=pt巳2.1 如果 count=m% 贝 U输出结点队2.1.2删除结点队遇1,3计数器counts零，重新开始计数；2:2否则，执行2. 2.1 T作牒十pre和p后移；2.2.2计数器增虹3.斑表中只剩下一个结点p,输出结点口后将结点口删除;参考代码：struct node( int code;struct node *next;；typedef struct node NODE;main()( NODE *head=create(6); josph(head,3); NODE *create(int count) /无特殊头结点NODE *head,*p,*last; int i;for(i=1; i<=count; i+) p=(NODE *)malloc(sizeof(NODE);p->code=i;if(i=1) head=last=p;else last->next=p; last=p; last->next=head;return(head);void josph(NODE *head,int k)int i; NODE *p,*pre;p=head;while(head->next!=head)for(i=1; i<k; i+) pre=p; p=p->next; printf("%d,”,p->code); /准备删除 *p if(p=head) head=p->next;pre->next=p->next; free(p); p=pre->next;printf("%dn",head->code);5双向链表在单链表的每个结点中再设置一个指向其前驱结点的指针域。结点结构：prior data nextdata：数据域，存储数据元素；prior:指针域，存储该结点的前趋结点地址;next:指针域，存储该结点的后继结点地址。如果将头结点和尾结点连接起来，就构成了双循环链表。双链表的插入操作:在结点P的后面插入一个新结点S,需要修改四个指针，如图 所示。 s->priot; s->next=p->nezt; p->next->prior=s, p->nexb=s;注意修改指针的相对 赎序。在修改第和步 指针时，要用到p->next 以找到结点p的后继，所 以第步的指针修改要在第和步的指针修改完成后才能进行。双链表的删除操作设指针p指向待删缝点,删除操作需要唆改两条语句，如图 所示。 (p->prior) ->net=p->hext;麹链表删!除揉作示毒图 (p-> nesi) -.prior=p- > prior;虽然执行上述语句后结点p的两个指针域仍指向其前驱结点和 后继结点，但在双链表中已经找不到结点p 了，而且，执行完删除 操作之后，还要将结点p所占的存储空间7包括两个指针域)蹴。6 一元多项式的表示及相加一元多项式p (X) = p + p X + p x2 + . + p xn012n在计算机中，可以用一个线性表来表示:P = (p” p,，p)01n但是对于形如S(x) = 1 + 3x10000 -2x20000的多项式，上述表示方法是否合适？一元稀疏多项式可写成Pn(x) = P1xe1 + p2Xe2 + + pXem其中：P.是指数为的项的非零系数，0 V ei < e2 < < em = n可以下列线性表表示：(pi，%),(改公，唱)例如：(x) = 7x3 - 2x12 - 8x999999、'可用线性表(7, 3), (-2, 12), (-8, 999)表示一元多项式单链表的存储结构typedef struct polynode( int coef;int index;struct node *next;PolyNode;一元多项式加法的实现：为了运算方便，采用带头结点的单链表，先分析两个多项式求和的过程。设两个 工作指针P和q，分别指向两个单链表的开始结点。两个多项式求和实质上是对结点P 的指数域和结点q的指数域进行比较，这会出现下列三种情况：若p->exp< q->exp，则结点p应为结果中的一个结点，将指针p后移；? p电匚MiabiHE卜却不5J"IU -M雨 U1M 冒钉对Mil蒸h第一种暗况示意图 若p->exp>q->exp,则结点q应为结果中的一个结点，将q插入到第一个单链表中结点 p之前，再将指针q后移；LE 口 "丰4药口/>| 5 |1外 5 / /第二种情况示意囹（3）若p->exp=q->exp，则p与q所指为同类项，将q的系数加到p的系数上。若相加 结果不为0，则将指针p后移，删除结点q；若相加结果为0，则表明结果中无此项，删除 结点p和结点q，并将指针p和指针q分别后移；上述思想用伪代码描述如下:1. 工作针仪q初始化；2. 以p存在且q存在)执行下列三种®之一2.1 如p->exp<q7>exp)则指针-后;2 2 如果 p->exp>q7exP!则2.2.1将结点q插_A_到结点p文_刖=2.2.2指针q指向原点的下一个结点；2 .3 如果 p->exp=q>exp!则2.3.1 y->coeF=p->coef4-q-> coef；2.3.2如果尸光如则执行下列操作，否则，指针F后移;2.3.2.1删除结点p2.3.2.2使指针p指向它原指结点的下一个结焉2.3.3删除结点塞23.4使指针