第2章 线性表(精品).ppt

数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构1近近3周周上课上课内容内容第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表线性结构线性结构若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a1,a2,an）线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）2线性结构的特点：线性结构的特点：只有一个首结点和尾结点；只有一个首结点和尾结点；除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a1,a2,an）线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是一对一一对一的的见见第第2章章3第第2章章线性表线性表2.1线性表的逻辑结构线性表的逻辑结构2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.4应用举例应用举例（一元多项式的表示及相加）（一元多项式的表示及相加）作业作业4（a1,a2,ai-1，ai,ai1，,an）2.1线性表的类型定义线性表的类型定义1.线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点5例例1分析分析26个英文字母组成的英文表个英文字母组成的英文表（A,B,C,D,Z）学号学号姓名姓名性性别别年年龄龄班级班级2001011810205于春梅于春梅女女 182006级计算机科学与技术级计算机科学与技术1班班2001011810260何仕鹏何仕鹏男男 182006级计算机科学与技术级计算机科学与技术1班班2001011810284王王爽爽女女 182006级计算机科学与技术级计算机科学与技术1班班2001011810360王亚武王亚武男男 182006级计算机科学与技术级计算机科学与技术1班班：例例2分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性6练：判断下列叙述的正误：练：判断下列叙述的正误：1.数数据据的的逻逻辑辑结结构构是是指指数数据据元元素素之之间间的的逻逻辑辑关关系系，是用户按使用需要建立的。是用户按使用需要建立的。2.线线性性表表的的逻逻辑辑结结构构定定义义是是唯唯一一的的，不不依依赖赖于于计计算机。算机。3.数数据据结结构构是是指指相相互互之之间间存存在在一一种种或或多多种种关关系系的的数据元素的全体。数据元素的全体。4.线性结构反映结点间的逻辑关系是一对一的。线性结构反映结点间的逻辑关系是一对一的。5.一维向量是线性表，但二维或一维向量是线性表，但二维或N维数组不是。维数组不是。6.“同同一一数数据据逻逻辑辑结结构构中中的的所所有有数数据据元元素素都都具具有有相相同同的的特特性性”是是指指数数据据元元素素所所包包含含的的数数据据项项的的个数都相等。个数都相等。72.线性表的类型定义（详见课本线性表的类型定义（详见课本P19）对线性表的有关操作举例请大家看课本对线性表的有关操作举例请大家看课本P20例例2-1，例，例2-2 82.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结作作 业业92.2.1顺序表的表示顺序表的表示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存储线性表的元素，可通过存储线性表的元素，可通过数组数组VnVn来实现来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻10线性表顺序存储特点：线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（素存放位置亦可求出（利用数组下标利用数组下标）。计算方法）。计算方法是（是（参见存储结构示意图参见存储结构示意图）：）：设首元素设首元素a1的存放地址的存放地址为为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度设每个元素占用存储空间（地址长度）为）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L注意：注意：C C语言中的数组的下标从语言中的数组的下标从0 0开始，开始，即：即：VnVn的有效范围是的有效范围是V0V0Vn-1Vn-111线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)+(n-1)L Lb+(max-1)+(max-1)L L12一个一维数组，下标的范围是一个一维数组，下标的范围是到，每个数组元素用相邻的到，每个数组元素用相邻的个字节个字节存储。存储器按字节编址，设存储数组存储。存储器按字节编址，设存储数组元素元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：LOC(M3)=98+5(3-0)=113解：解：地址计算通式为：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）13用数组用数组V来存放来存放26个英文字母组成个英文字母组成的线性的线性表（表（a，b，c，z），），写出在顺写出在顺序结构上序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。voidbuild()/*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;核心语句：核心语句：法法1Vi=Vi-1+1;法法2Vi=a+i;法法3Vi=97+i;例例214voidmain(void)/*主函数主函数，字母线性表的生成和输出，字母线性表的生成和输出*/n=26;/*n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V的的实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/inti;for(i=0;i=q;-p)for(p=&(L.elemn-1);p=q;-p)*(p+1)=*p;*(p+1)=*p;*p=e;*p=e;+n;+n;/元素后移一个位置元素后移一个位置/插入插入e e/表长加表长加1 1 核心语句：核心语句：17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入插入252518实现步骤：实现步骤：(n为表长）为表长）将第将第i至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除位置i是否合法是否合法?应当有应当有1in或或i=1,n3)3)删除删除 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for(+p;p=q;+p)for(+p;pdata=a;p-next=q;方式方式3：先让指针变量：先让指针变量p指向该结点的首地址，然后用：指向该结点的首地址，然后用：(*p).data=a；(*p).nextq38设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。至此应可看懂教材P28对于单链表的抽象描述，和教材教材P22关于顺序表的关于顺序表的抽象抽象定义。定义。练习：练习：p-dataai的值的值p-nextai+1的地址的地址39附2：教材教材P22关于顺序表的关于顺序表的抽象抽象定义：定义：Typedefstruct/若后面不再用，可省略结构名若后面不再用，可省略结构名ElemType*elem;/表基址表基址intlength;/表长（特指元素个数）表长（特指元素个数）intlistsize;/表当前存储容量（字节数）表当前存储容量（字节数）SqList;TypedefstructLnodeElemTypedata;/数据域structLnode*next;/指针域Lnode,*LinkList;/*LinkList为Lnode类型的指针附1：教材P28对于单链表的抽象描述:40补充：结构类型的补充：结构类型的C语言表示法语言表示法介绍三个有用的库函数（都在介绍三个有用的库函数（都在中）：中）：sizeof(x)计算变量计算变量x的长度；的长度；malloc(m)开辟开辟m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p)释放指针释放指针p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。问问1：自定义结构类型变量自定义结构类型变量test的长度的长度m是多少是多少？问问2：结构变量结构变量test的首地址的首地址(指针指针p）是多少是多少？问问3：怎样删除结构变量怎样删除结构变量test？只能借助其指针删除！只能借助其指针删除！*nextdatatest，长度为长度为m字节字节pmsizeof(test)p(test*)malloc(m)free(p)412.3.2链表的实现链表的实现1.1.单链表的建立和输出单链表的建立和输出2.2.单链表的修改单链表的修改3.3.单链表的插入单链表的插入4.4.单链表的删除单链表的删除5.5.应用举例应用举例6.6.其它链表形式其它链表形式421.1.单链表的建立和输出单链表的建立和输出实例实例：用单链表结构来存放用单链表结构来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z）,请写出请写出C语言程序语言程序。难点分析：难点分析：每个数据元素在内存中是每个数据元素在内存中是“零散零散”存放的，存放的，其首地址怎么找？又怎么一一链接？其首地址怎么找？又怎么一一链接？实现思路：实现思路：先开辟头指针，然后陆续为每个数据元先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的素开辟存储空间并赋值，并及时将地址送给前面的指针。指针。43将全局变量及函数提前说明：将全局变量及函数提前说明：#include#includetypedef struct liuchar data;struct liu*next;test;liu*p,*q,*head;/一般需要一般需要3个指针变量个指针变量int n;/数据元素的个数数据元素的个数int m=sizeof(test);/*结构类型定义好之后，每个变量结构类型定义好之后，每个变量的长度就固定了，的长度就固定了，m求一次即可求一次即可*/44void build()/字母链表的生成。字母链表的生成。要一个一个慢慢链入int i;head=(test*)malloc(m);/m=sizeof(test)前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符ap-next=(test*)malloc(m);/为后继结点开新空间为后继结点开新空间！p=p-next；/让指针变量P改为指向后继结点p-data=i+a-1;/最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！新手特别容易忘记！新手特别容易忘记！45voiddisplay()/*字母链表的输出字母链表的输出*/p=head;while(p-next!=NULL)/*只只要要没没到到最最后后一一个个元元素素，就就不不停停地地“顺顺藤藤摸摸瓜瓜”输输出出*/printf(%c,p-data);p=p-next;printf(“%cn”,p-data);/别忘记输出尾结点数据别忘记输出尾结点数据讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？sum+;462.2.单链表的修改单链表的修改(或读取）或读取）思路：思路：要修改第要修改第i个个数据元素，关键是要先找到该结数据元素，关键是要先找到该结点的指针点的指针p，然后用然后用p-data=new_value 即可。难点：难点：单链表中想取得第单链表中想取得第i个元素，必须从头指针出个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取发寻找（顺藤摸瓜），不能随机存取。核心语句：核心语句：见教材见教材P29的的GetElem_L函数说明函数说明Status Status GetElem_L(LinkListL,inti,ElemType&e)P=L-next;j=1;P=L-next;j=1;whilewhile(p(p&jjnext;+j;)p=p-next;+j;if(!p|ji)if(!p|ji)returnreturn ERROR;ERROR;e=p-data;e=p-data;returnreturn OK;OK;473.3.单链表的插入单链表的插入在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：插入步骤（即核心语句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s；p-nexts-next思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？元素x结点应预先生成：S=(test*)S=(test*)malloc(mmalloc(m);S-data=x;S-data=x;S-next=p-nextS-next=p-next484.4.单链表的删除单链表的删除在链表中删除某元素的示意图如下：在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：删除步骤（即核心语句）：q=p-next;/保存保存b的的指针，靠它才能指向指针，靠它才能指向cp-next=q-next;/a、c两结点相连两结点相连free(q)；/删除删除b结点，彻底释放结点，彻底释放p-next思考：思考：省略省略free(q)语句语句行不行行不行？(p-next)-next495.5.应用举例：两个链表的归并（教材应用举例：两个链表的归并（教材P31P31）算法要求：算法要求：已知：已知：线性表线性表A、B，分别由分别由单链表单链表LA,LB存储，存储，其中数据元素按值其中数据元素按值非递减有序非递减有序排列，排列，要求：要求：将将A，B归并归并为一个新的线性表为一个新的线性表C,C的数据的数据元素仍按值非递减排列元素仍按值非递减排列。设线性表。设线性表C由由单链表单链表LC存储。存储。假设：假设：A=（3，5，8，11），），B=（2，6，8，9，11）预测：预测：合并后合并后C=（2,3,5,6,8,8,9,11，11）50用链表可表示为：用链表可表示为：3 3 5 511 11/8 8 LaLa 2 2 6 611 11/8 8 LbLb 9 9 2 2 3 3 6 6 5 5 LcLc 8 8头头结点结点51算法分析：算法分析：算法主要包括：算法主要包括：搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要需要两个指针两个指针搜索两个链表；搜索两个链表；比较：比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中数据将两个结点中数据小的结点插入新链表。小的结点插入新链表。52La35811 Lb26811 9PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb，Pc指向新链表当前结点指向新链表当前结点LcPa3PcPa5Pc11 Pc2PbPcPa53算法实现：算法实现：VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/按值排序的单链表按值排序的单链表LA,LB，归并为归并为LC后也按值排序后也按值排序free(Lb);/释放释放Lb的头结点的头结点/MergeList_Lpc-next=pa?pa:pb;/插入剩余段插入剩余段while(pa&pb)/将将pa、pb结点按大小依次插入结点按大小依次插入C中中if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-nextpa=La-next;pb=Lb-next;Lc=pc=La；/初始化初始化54思考思考1、不用、不用Lc，直接把直接把La表插到表插到Lb表中；或者把表中；或者把Lb表表插到插到La表中表中，如何编程？，如何编程？2、要求不能有重复的数据元素，如何编程？、要求不能有重复的数据元素，如何编程？556.其它链表形式答：能。只要定义一个结构类型（含答：能。只要定义一个结构类型（含数据域数据域和和指指示域示域）数组，就可以完全描述链表，这种链表称）数组，就可以完全描述链表，这种链表称为为静态链表静态链表。注：数据域含义与前面相同，指示域相当于前面注：数据域含义与前面相同，指示域相当于前面的指针域。的指针域。讨论讨论1 1：用一维数组也能存放链表吗？怎样实现？用一维数组也能存放链表吗？怎样实现？静态链表的插入与删除操作与普通链表一样，静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。不需要移动元素，只需修改指示器就可以了。具体实现过程见具体实现过程见教材教材P31-34P31-34。56讨论讨论2 2：链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结答：能。只要将表中最后一个结点的指针域指向头结点即可点即可 (P-next=head;)(P-next=head;)。这种形成环路的链表称这种形成环路的链表称为为循环链表循环链表。特别：带头结点的特别：带头结点的空空循环链表样式循环链表样式参见教材参见教材P35P35特点：特点：1 1、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。2 2、操作仅有、操作仅有、操作仅有、操作仅有 一一一一 点与单链表不同：点与单链表不同：点与单链表不同：点与单链表不同：循环条件循环条件循环条件循环条件单链表单链表单链表单链表-p=NULL-p=NULL或或或或 p-next=NULLp-next=NULL循环链表循环链表循环链表循环链表-p=head-p=head或或或或 p-next=headp-next=headH57讨论讨论3 3：单链表只能查找结点的直接后继，能不单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可答：能。只要把单链表再多开一个指针域即可(例例如用如用*nextnext和和*prior;prior;)。双向链表在非线性结构（如树结构）中将大量使用。双向链表在非线性结构（如树结构）中将大量使用。prior datanext这种有两个指针的链表称为这种有两个指针的链表称为双向链表双向链表。其特点是。其特点是可以双向查找表中结点。参见教材可以双向查找表中结点。参见教材P3539P3539。特别：带头结点的特别：带头结点的空空双向链表样式：双向链表样式：582.3.3链表的运算效率分析链表的运算效率分析1.查找查找因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为O(n)。时间效率分析2.插入和删除插入和删除因线性链表不需要移动元素，只要修因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为改指针，一般情况下时间复杂度为O(1)。但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为O(n)。59练：练：空间效率分析链表中每个结点都要增加一个指针空间，相当于总链表中每个结点都要增加一个指针空间，相当于总共增加了共增加了n个整型变量，空间复杂度为个整型变量，空间复杂度为O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点*P P，需找到它需找到它的的，其时间复杂度为，其时间复杂度为。前驱结点的地址前驱结点的地址O O(n)(n)60上堂课要点回顾上堂课要点回顾1.1.链表的表示链表的表示(包括有关术语、包括有关术语、结构数据类型结构数据类型等）等）2.2.链表的实现链表的实现（建表、输出、修改、插入、删除）（建表、输出、修改、插入、删除）补充：其它链表形式静态链表静态链表循环链表循环链表双向链表双向链表同学提问：同学提问：testtest*p,*q*p,*q是否应改为是否应改为liuliu*p,*q?*p,*q?怎样读取头结点数据域中的信息？怎样读取头结点数据域中的信息？链表的操作要用指针，蛮链表的操作要用指针，蛮“裹人裹人”！是是用用L-dataL-data仅两个作用：找位置仅两个作用：找位置和改地址！和改地址！61第第2章章线性表线性表2.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.4应用举例应用举例（一元多项式的表示及相加）一元多项式的表示及相加）本章小结及作业讨论本章小结及作业讨论622.4应用举例应用举例1.一元多项式的数学通式？一元多项式的数学通式？2.用抽象数据类型如何描述它的定义？用抽象数据类型如何描述它的定义？3.用用C语言如何描述它的定义？语言如何描述它的定义？4.如何编程实现两个一元多项式相加？如何编程实现两个一元多项式相加？一元多项式的表示及相加一元多项式的表示及相加(参见教材参见教材P3943)讨论：讨论：631.一元多项式的数学通式？一元多项式的数学通式？一元多项式的通式可表示为：一元多项式的通式可表示为：分析：分析：一元多项式在计算机内存储时，既可用一元多项式在计算机内存储时，既可用顺序表顺序表存储，存储，又可用又可用链表链表存储。但当多项式的次数很高且零系数项很多时，存储。但当多项式的次数很高且零系数项很多时，则更适于用链表存储（则更适于用链表存储（通常设计两个数据域和一个指针域通常设计两个数据域和一个指针域）。）。a0a1a2am-2am-1顺序表顺序表链表链表am-1 em-1am-2 em-2a0e0或或0.0-1am-1 em-1a0e0642.2.用抽象数据类型如何用抽象数据类型如何定义定义一元多项式一元多项式？（参见（参见P P4040）ADT PolynomialPolynomial数据对象：D=ai|aiTermSet,i=1,2,m,m0TermSetTermSet中的每个元素包含一个表示系数的实数和表示指数的整数中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|ai-1,ai D,且且a ai-1i-1中的指数值中的指数值 expon=、Pb-expon等情况，等情况，再决定是再决定是将两系数域的数值相加（并判其和是否为将两系数域的数值相加（并判其和是否为0 0），还），还是将较高指数项的结点插入到新表是将较高指数项的结点插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+70具体编程（用具体编程（用C语言）语言）1.利用建表操作CreatPolyn(&P,mCreatPolyn(&P,m)分别建立链表a和链表b；详细内容参见教材P42下部描述。2.利用加操作AddPolyn(&AddPolyn(&P Pa a,&P,&Pb b)对对链表a和链表b进行相加；详细内容参见教材P43描述。编程时请注意，在前面定义中已规定：编程时请注意，在前面定义中已规定：初始条件：一元多项式初始条件：一元多项式P Pa a和和P Pb b已存在。已存在。操作结果：完成多项式相加运算，即：操作结果：完成多项式相加运算，即：P Pa aP Pa aP Pb b，并并销毁一元多项式销毁一元多项式P Pb b。从从教材程序中可教材程序中可“猜猜”出，例中的链表是按指数项升序出，例中的链表是按指数项升序排列的。排列的。71Void Void AddPolyn(polynomial&AddPolyn(polynomial&P Pa a,polynomialpolynomial&P Pb b)ha=GetHead(Pa);hb=GetHead(Pb);/取二表头指针取二表头指针(指向头结点）指向头结点）qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);/指向二表首元结点指向二表首元结点while(qa&qb)/若二表均未到末尾，若二表均未到末尾，a=GetCurElem(qa);/*/*则比较两结点的数据域（注意则比较两结点的数据域（注意a,ba,b含有含有 b=GetCurElem(qb);两个数据分量）两个数据分量）*/*/switch(*cmp(a,b)/cmp(a,bcmp(a,b)是用户自定义函数，见是用户自定义函数，见P42P42倒倒9 9行行case-1:/若若a a的指数值小于的指数值小于b b，此，此a a结点不动（升序）结点不动（升序）ha=qa;qa=NextPos(Pa,ha);break;case0:/若若a a的指数值等于的指数值等于b b，则系数相加，则系数相加sum=a.coef+b.coef;If(sum!=0.0)SetCurElem(qa,sum);ha=qa;72 elseDelFirst(ha,qa);FreeNode(qa);/若系数为若系数为0 0，则两结点都删，则两结点都删DelFirst(hb,qb);FreeNode(qb);qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);break;case1:/若若a a的指数值大于的指数值大于b b，应前插，应前插b b（保持升序）保持升序）DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;/a/a表大结点后移表大结点后移/switch/whileIf(!ListEmpty(Pb)Append(Pa,qb);/若若a a表空，则表空，则b b表剩余项全部表剩余项全部 /链接到链接到a a表中；而表中；而b b表空时无需动作，因为表空时无需动作，因为a a表本身就是求和结果。表本身就是求和结果。FreeNode(hb);/无论什么结局，最终无论什么结局，最终b b表都是要废掉的。表都是要废掉的。/AddPolynAddPolyn73运算效率分析运算效率分析:(1)系数相加系数相加0 加法次数加法次数 min(m,n)其中其中m和和n分别表示表分别表示表A和表和表B的结点数。的结点数。(2)指数比较指数比较极端情况是极端情况是表表A和表和表B没有一项指数相同，没有一项指数相同，比较次数最多为比较次数最多为m+n-1(3)新结点的创建新结点的创建极端情况是产生极端情况是产生m+n个新结点个新结点合计时间复杂度为合计时间复杂度为O(m+n)74本章小结（本章小结（讨论题形式讨论题形式）线线性性表表逻逻辑辑结结构构特特点点是是，只只有有一一个个首首结结点点和和尾尾结结点点；除除首首尾尾结结点点外外其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。简简言言之，线性结构反映结点间的逻辑关系是一对一（之，线性结构反映结点间的逻辑关系是一对一（1:11:1）的。）的。问问1：线性表的逻辑结构特点是什么？其顺序存储线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？结构和链式存储结构的特点是什么？答：答：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。理统一）；要求内存中可用存储单元的地址必须是连续的。链式存储时，相邻数据元素可随意存放，但所占存储空间链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。系的指针。75 顺序存储的优点是存储密度大顺序存储的优点是存储密度大(1)1)，存储空存储空间利用率高。缺点是插入或删除元素时不方便。间利用率高。缺点是插入或删除元素时不方便。链式存储的优点是插入或删除元素时很方便，链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（使用灵活。缺点是存储密度小（11），存储空间利），存储空间利用率低。用率低。答：答：问问2：顺序存储和链式存储各有哪些优缺点？顺序存储和链式存储各有哪些优缺点？事实上，链表插入、删除运算的快捷是以空间事实上，链表插入、删除运算的快捷是以空间代价来换取时间。代价来换取时间。76问问3：在什么情况下用顺序表比链表好？：在什么情况下用顺序表比链表好？顺序表适宜于做顺序表适宜于做查找查找这样的静态操作；链表宜这样的静态操作；链表宜于做于做插入、删除插入、删除这样的动态操作。这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。删除操作，则采用链表。答：答：77