第2章-数据结构(顺序表和线性链表)课件

第第2 2章章 常用数据结构及其运算常用数据结构及其运算1.1.内容内容:n基本数据结构及其运算基本数据结构及其运算n线性表线性表n树树n图图n查找与排序技术查找与排序技术2.2.特点和学习建议特点和学习建议n重视实践重视实践3.3.重点和难点重点和难点n数据结构形式和算法种类多数据结构形式和算法种类多,动态存储结构动态存储结构,递归技术递归技术.2024/7/1112.1 2.1 概述概述n数据结构是计算机应用方面的基础课程，为数据结构是计算机应用方面的基础课程，为学习学习操作系统操作系统、数据库数据库及及软件工程软件工程打基础打基础n计算机语言、数据结构和算法计算机语言、数据结构和算法n好的软件设计好的软件设计=好的数据结构好的数据结构+好的算法好的算法n概念概念(数值型和非数值型程序设计数值型和非数值型程序设计)n是一门研究非数值计算的程序设计问题中计算机是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间的关系和运算等的学科。的操作对象及其之间的关系和运算等的学科。2024/7/112n2.1.12.1.1数据结构数据结构n程序分类：程序分类：n数值型程序：数值计算；数值型程序：数值计算；n非数值型程序：数据处理；非数值型程序：数据处理；n在数据处理领域中，数据类型复杂，且数据在数据处理领域中，数据类型复杂，且数据元素之间具有各种特定的联系，数据集合中元素之间具有各种特定的联系，数据集合中元素之间的关系元素之间的关系以及如何以及如何组织和表达组织和表达这些数这些数据，以提高数据处理效率。据，以提高数据处理效率。n数据结构数据结构是研究非数值运算的程序设计问题。是研究非数值运算的程序设计问题。2024/7/1132.1.2 2.1.2 基本概念和术语基本概念和术语数据数据(data)(data)：对客观事物的符号表示，信息的载对客观事物的符号表示，信息的载体，可用计算机表示和处理。体，可用计算机表示和处理。数数(figure/number)(figure/number)、文本、文本(text)(text)、图形、图形(graph)(graph)、视频、视频(video)(video)、声音（、声音（audioaudio）和图像）和图像(image)(image)等。等。数据元素数据元素(data element/node/record):(data element/node/record):是数据集是数据集合中的一个个体，是数据的基本单位。合中的一个个体，是数据的基本单位。注意：不一定是单个的数字或字符，它本身也可能是若注意：不一定是单个的数字或字符，它本身也可能是若干个数据项的组合。如：学生成绩登记表，数据元素对干个数据项的组合。如：学生成绩登记表，数据元素对应记录，记录又包含字段应记录，记录又包含字段嵌套定义嵌套定义数据对象数据对象(data object):(data object):具有相同性质的数据元具有相同性质的数据元素的集合素的集合数据结构数据结构(data structure):(data structure):指同一数据对象中各指同一数据对象中各数据元素间存在的数据元素间存在的关系（关系（relationshiprelationship）。2024/7/114n集合论方法定义集合论方法定义：S=(D,R)S=(D,R)S S是一个二元组；是一个二元组；D D是一个数据元素的非空有限集合；是一个数据元素的非空有限集合；R R是定义在是定义在D D上的关系的非空有限集合。上的关系的非空有限集合。n一个一个n n维向量维向量x=(xx=(x1 1,x,x2 2,x,xn n)nD=xD=x1 1,x,x2 2,x,xn n nR=xR=,x,线性表。线性表。n家庭成员数据结构家庭成员数据结构B=(D,R)B=(D,R)nD=D=双亲双亲,儿子儿子,女儿女儿 nR=(R=(双亲双亲,儿子儿子),(),(双亲双亲,女儿女儿)n复杂的数据结构复杂的数据结构,其数据元素可以是另一种数据结构其数据元素可以是另一种数据结构nA Am mnAiaijn嵌套定义嵌套定义n优点：采用集合论抽象定义法可描述广泛的数据结构优点：采用集合论抽象定义法可描述广泛的数据结构n线性结构线性结构n非线性结构非线性结构2024/7/115nrelationshipstructuren数据结构分类：数据结构分类：1.集合：元素之间除了集合：元素之间除了“同属于一个集合同属于一个集合”的关系的关系外，再无其它关系。外，再无其它关系。南京路步行街上熙熙攘攘的人群南京路步行街上熙熙攘攘的人群2.线性结构：线性结构：1：1。班长和班级班长和班级n图书信息查询系统图书信息查询系统3.树形结构：树形结构：1：n。父母和孩子父母和孩子n计算机和人对弈问题计算机和人对弈问题4.图状结构图状结构/网状结构：网状结构：n:m。老师和学生老师和学生n多叉路口交通灯的管理问题多叉路口交通灯的管理问题n数据逻辑结构的两要素数据逻辑结构的两要素:n表示数据元素的信息表示数据元素的信息n表示各数据元素之间的表示各数据元素之间的前后件前后件关系关系2024/7/116n数据结构包括数据结构包括:n逻辑结构与物理结构：逻辑结构与物理结构：n逻辑结构（逻辑结构（数据结构数据结构）：研究数据元素及其关系的）：研究数据元素及其关系的数学特性；数学特性；n物理结构（物理结构（存储结构存储结构）：是逻辑结构在计算机中的）：是逻辑结构在计算机中的映象，即具体实现，用高级语言中各种数据类型来映象，即具体实现，用高级语言中各种数据类型来描述这种实现。数据在物理空间中的存储方式描述这种实现。数据在物理空间中的存储方式.n同一种逻辑结构同一种逻辑结构,可对应不同物理结构可对应不同物理结构,物理结构不物理结构不同同,则算法不同则算法不同.n对于计算机存储空间对于计算机存储空间,前后件元素不一定相邻前后件元素不一定相邻,且前且前件元素不一定在前件元素不一定在前,后件元素不一定在后后件元素不一定在后.n例例:C:C中线性表的数组和动态链表实现中线性表的数组和动态链表实现2024/7/117数据类型数据类型(data type):(data type):是指程序设计语言中允许的是指程序设计语言中允许的变量类型。变量类型。注意：每一个变量必须与一个且仅与一个数据类型相联系，注意：每一个变量必须与一个且仅与一个数据类型相联系，规定了该变量可以设定的值的集合，及这个集合上的一组规定了该变量可以设定的值的集合，及这个集合上的一组运算。（语言不同而不同）运算。（语言不同而不同）分类：分类：基本数据类型：变量值不可再分。整型、实型、布尔型。基本数据类型：变量值不可再分。整型、实型、布尔型。结构数据类型：值可再分。数组、结构。结构数据类型：值可再分。数组、结构。数据结构与算法：数据结构与算法：算法是解决某一特定类型问题的算法是解决某一特定类型问题的有限运算序列有限运算序列，它的实现必须借助程序设计语言中，它的实现必须借助程序设计语言中提供的数据类型及其运算。提供的数据类型及其运算。效率：与数据的表示形式有关，数据结构的选择至效率：与数据的表示形式有关，数据结构的选择至关重要。它是算法和程序设计的基本部分，对程序关重要。它是算法和程序设计的基本部分，对程序的质量影响很大，（的质量影响很大，（三好三好）。）。数据结构数据结构存储结构存储结构相应算法。相应算法。2024/7/118n2.2 2.2 线性表线性表(1:1)(1:1)n线性表：在数据处理中，大量数据均以线性表：在数据处理中，大量数据均以表格表格形式出现，称为线性表。形式出现，称为线性表。n最简单、最基本最简单、最基本、最常见、最常见。n存储结构：顺序存储结构：顺序(向量向量)、链表、链表n主要运算：主要运算：n插入插入(建表建表)、删除、查找和排序。、删除、查找和排序。n内容包括内容包括:n线性表的定义和运算种类线性表的定义和运算种类n顺序顺序(向量向量)存储存储(顺序表顺序表)n链式存储链式存储(线性链表线性链表)n向量向量(顺序顺序)和链表两种存储方式的比较和链表两种存储方式的比较2024/7/1192.2.1 2.2.1 线性表的定义和运算种类线性表的定义和运算种类n线性表（线性数据结构）线性表（线性数据结构）是数据元素的有限序列。是数据元素的有限序列。n例：人民币面值例：人民币面值 一年四季一年四季n现实中客观存在的实体经过现实中客观存在的实体经过数学抽象数学抽象后都可用线性表后都可用线性表的一般形式表示：的一般形式表示：L=(aL=(a1 1,a,a2 2,a,an n)L:L:线性表，线性表，a ai i元素元素(属于某数据对象属于某数据对象)，n n表长，表长，n=0n=0时时为空表。为空表。n结构特点：前趋后继结构特点：前趋后继(前件后件前件后件)关系关系n数据元素之间是线性关系，即两唯一数据元素之间是线性关系，即两唯一(首结点和终结点首结点和终结点)、一、一前趋一后继。前趋一后继。n定义：定义：L=(D,R)L=(D,R)D=aD=a1 1,a,a2 2,a,an n,R=a,R=|a|ai-1i-1,a,ai i D,2inD,2in2024/7/1110n非线性表（非线性数据结构）：如果一个非线性表（非线性数据结构）：如果一个数据结构不是线性结构，则称之为非线性数据结构不是线性结构，则称之为非线性结构。结构。n如辈分关系。如辈分关系。n线性表的基本运算：线性表的基本运算：插入、删除、插入、删除、查找和排序查找和排序n建表建表、修改修改n存储结构不同，运算方法不同。存储结构不同，运算方法不同。n教学步骤教学步骤:n结构特点及基本运算结构特点及基本运算2024/7/1111n注意：注意：n空表既可以是线性表，也可以是非线性表；空表既可以是线性表，也可以是非线性表；取决于具体问题。如其运算按线性表的规则取决于具体问题。如其运算按线性表的规则处理，则属于线性表，否则为非线性表。处理，则属于线性表，否则为非线性表。n思考思考:n为什么引入空表为什么引入空表?2024/7/11122.2.2 2.2.2 顺序存储线性表顺序存储线性表(顺序表顺序表)1 1、顺序存储结构（向量式存储结构）、顺序存储结构（向量式存储结构）用一组连续地址的存储单元存放线性表的数据元素。用一组连续地址的存储单元存放线性表的数据元素。高级语言中一维数组类型表示。高级语言中一维数组类型表示。如如A1:nA1:n来存储线性表（来存储线性表（a a1 1,a,a2 2,a,an n），在内存中的），在内存中的存放形式为：存放形式为：b+(i-1)mb+mbanan-1aia2a1adr(aadr(ai i)=adr(a)=adr(a1 1)+(i-1)m)+(i-1)m只要知道元素序号就很容易找只要知道元素序号就很容易找到第到第i i个数据元素，且无论个数据元素，且无论i i为为何值，找到第何值，找到第i i个元素所需时个元素所需时间相同。间相同。2024/7/1113n基本特点：基本特点：n连续性连续性n物理顺序物理顺序=逻辑顺序逻辑顺序n随机访问、随机访问、顺序存储顺序存储2024/7/1114n2 2、顺序表的插入、删除运算、顺序表的插入、删除运算n(1)(1)插入：在第插入：在第i i个元素前插入一个新元素个元素前插入一个新元素x x。n设在长度为设在长度为n n的线性表中第的线性表中第i i个元素前插入一个元素个元素前插入一个元素x x，存放线性表的，存放线性表的向量为：向量为：V1:m(mn)V1:m(mn)INSERTLIST(V,INSERTLIST(V,m m,n,i,x),n,i,x)1.if(in+1)then1.if(in+1)then参数错参数错 returnreturnn1.if(i1)then i=11.if(in)then i=n+1 1.else if(in)then i=n+1 异常输入容错处理异常输入容错处理2.for j=n to i step(-1)2.for j=n to i step(-1)3.Vj+13.Vj+1VjVj4.end(j)4.end(j)5.Vi 5.Vi x x6.n 6.n n+1 n+17.return7.return2024/7/1115n(2)(2)删除：删除第删除：删除第i i个元素。个元素。nDELETELIST(VDELETELIST(V，n n，i i）n1.if(in)then1.if(in)then参数错参数错returnreturn2.for j=i to n-1 2.for j=i to n-1 step(1)step(1)n3.Vj3.VjVj+1Vj+14.end(j)4.end(j)5 5.n.n n-1 n-17.return7.return2024/7/1116nQuestions:n如删除最后一个元素，作何操作？如删除最后一个元素，作何操作？(最好情最好情形形)n删除第一个元素，又如何？删除第一个元素，又如何？(最坏情形最坏情形)2024/7/1117n3 3、算法的时间复杂度分析、算法的时间复杂度分析n主要消耗在移动元素上，与主要消耗在移动元素上，与n(n(问题尺度问题尺度)、i i(输输入入)有关有关 ，用，用平均移动次数平均移动次数来分析平均性能。来分析平均性能。n设设p pi i是在第是在第i i个元素前插入一个元素的概率，则个元素前插入一个元素的概率，则在长为在长为n n的表中插入一个元素所需的平均移动次的表中插入一个元素所需的平均移动次数为：数为：n设等概率，设等概率，p pi i=1/(n+1)=1/(n+1)，则有：，则有：2024/7/1118n设等概率，设等概率，q qi i=1/n=1/n，则有：，则有：n结论：结论：n一半元素；一半元素；n当当n n较大时是相当可观的；较大时是相当可观的；n适用于不频繁进行插入、删除运算，表中元素相对稳定的问适用于不频繁进行插入、删除运算，表中元素相对稳定的问题。题。(顺序表的缺点顺序表的缺点)nq qi i为删除第为删除第i i个元素的概率，则删除一个元素所个元素的概率，则删除一个元素所需移动次数的平均值为：需移动次数的平均值为：2024/7/1119n顺序存储的缺点顺序存储的缺点n作插入、删除运算时要移动大量元素；作插入、删除运算时要移动大量元素；n因要求一组连续的存储单元，当表长可变时，会发生因要求一组连续的存储单元，当表长可变时，会发生浪费或溢出。建表为静态分配浪费或溢出。建表为静态分配.n课后思考课后思考-设计算法求解皇后问题（设计算法求解皇后问题（案例之一案例之一）:n由由n2个方块排成个方块排成n行行n列的正方形称为列的正方形称为“n元棋盘元棋盘”。如果两个皇后位于棋盘上的同一行或同一列或同。如果两个皇后位于棋盘上的同一行或同一列或同一对角线上一对角线上,则称她们为互相攻击则称她们为互相攻击.现要求找出使现要求找出使n元元棋盘上的棋盘上的n个皇后互不攻击的所有布局个皇后互不攻击的所有布局.2024/7/11202.2.3 2.2.3 线性链表线性链表 1 1、链式存储结构（、链式存储结构（克服顺序存储结构不足克服顺序存储结构不足）n不需要一组连续的存储单元，其数据元素可分散存放。为了在逻不需要一组连续的存储单元，其数据元素可分散存放。为了在逻辑上保持连续，需在每个元素中存放其后继元素辑上保持连续，需在每个元素中存放其后继元素(后件后件)的地址。的地址。如下图：如下图：head地址地址内内 存存10091007a31008nila4100710061002a11005100410031008a2100210011000heada1a2a3 a4图图2.5 2.5 线性表的链式结构线性表的链式结构物理上分散、逻辑上有序物理上分散、逻辑上有序2024/7/1121n结点结构结点结构:n数据域数据域（存放元素值（存放元素值)、指针域、指针域(后继元素的地址后继元素的地址)、头指针、头指针(head)(head)、空指针空指针(nil(nil或或)。n算法描述语言中，指针类型结构表示为：算法描述语言中，指针类型结构表示为：a data next数据域和指针域的访问数据域和指针域的访问:data(a):data(a)、next(a)next(a)。对应对应C C中的指针数据类型中的指针数据类型。2 2、线性链表的基本算法、线性链表的基本算法特点特点:不移动元素、修改指针、动态分配不移动元素、修改指针、动态分配(动态生动态生成或回收链表的结点成或回收链表的结点)。2024/7/1122（1 1）基本操作：）基本操作：指针赋值、指针移动、插入某结点前和插入某结点后。指针赋值、指针移动、插入某结点前和插入某结点后。符号含义：符号含义：p,q,sp,q,s为指针类型变量，其数据域为为指针类型变量，其数据域为datadata，指针域为，指针域为nextnext；下页图下页图(完善前插完善前插)注意注意：前插需从前插需从headhead开始，寻找插点，而后插不需要，因直开始，寻找插点，而后插不需要，因直接可用接可用next(p)next(p)。随机存储、顺序访问；逻辑有序、物理无序。随机存储、顺序访问；逻辑有序、物理无序。难点：难点：修改指针的顺序修改指针的顺序2024/7/11232024/7/1124（2 2）结点的动态生成及回收：）结点的动态生成及回收：n动态分配动态分配:线性链表的存储空间是在程序执线性链表的存储空间是在程序执行过程中动态分配的，因此，插入时，提供行过程中动态分配的，因此，插入时，提供一个存储空间；删除时，回收该存储空间。一个存储空间；删除时，回收该存储空间。n动态分配的实现动态分配的实现:使用空白链表。空白链表使用空白链表。空白链表供所有具有相同数据类型的链表共享，以便供所有具有相同数据类型的链表共享，以便充分利用存储空间。充分利用存储空间。n设具有数据域设具有数据域datadata，指针域，指针域nextnext的空白链表，其的空白链表，其头指针为头指针为avav。2024/7/1125n从空白链表中获取一个结点，由指针从空白链表中获取一个结点，由指针p p指向。指向。GETNODE(P)GETNODE(P)1.p1.pavav2.av 2.av next(av)next(av)3.return3.returnn回收一个由回收一个由p p指针指向的结点，放回空白链表。指针指向的结点，放回空白链表。RET(P)RET(P)1.next(p)1.next(p)avav2.av 2.av p p3.return3.return(3)(3)插入运算插入运算问题描述：问题描述：在头指针为在头指针为headhead的链表中，在的链表中，在值值为为a a的结点前的结点前插入一个插入一个值值为为b b的结点。如为空表，则的结点。如为空表，则b b为第一个结点，为第一个结点，如表中无如表中无a a元素，则将元素，则将b b插入链表的末尾。插入链表的末尾。注意：分配后注意：分配后av后移一个结点。后移一个结点。注意：回收后，注意：回收后，p指向的结点指向的结点变为第一个结点。变为第一个结点。从头开始从头开始2024/7/11262024/7/1127nINLINKSTINLINKST（head,a,bhead,a,b）1.GETNODE(p);data(p)1.GETNODE(p);data(p)b;b;/取得一个新结点取得一个新结点p/p/2.if(head=nil)thenhead 2.if(head=nil)thenhead p;next(p)p;next(p)nil;returnnil;return /空表情况空表情况/3.if(data(head)=a)thennext(p)3.if(data(head)=a)thennext(p)head;head;head headp;returnp;return/a/a为第一个结为第一个结点点,改进待叙改进待叙,不同不同:head:head指向第一个结点指向第一个结点.第一个结点变第一个结点变了了,所以要修改所以要修改head/head/4.4.LOOKFOR(head,a,q)LOOKFOR(head,a,q)/寻找元素寻找元素a a的前趋结点的前趋结点q/q/5.next(p)5.next(p)next(q);next(q)next(q);next(q)p p 6.return 6.returnLOOKFOR(head,a,q)LOOKFOR(head,a,q)/a/a在中间或不存在在中间或不存在/1.q 1.q headhead2.while(next(q)2.while(next(q)nil)and(data(next(q)nil)and(data(next(q)a)doa)do3.q3.qnext(q)next(q)/如表中无如表中无a a结点，则结点，则q q指向最后一个结点，指向最后一个结点，b b结点作为尾结点结点作为尾结点/4.return4.return2024/7/1128(4)(4)删除运算删除运算n问题描述问题描述:在头指针为在头指针为head的线性链表中删除元素的线性链表中删除元素a.2024/7/1129pq2024/7/1130nDELINKST(head,a)DELINKST(head,a)1.if(head=nil)then1.if(head=nil)then空表空表returnreturn2.if(data(head)=a)thens2.if(data(head)=a)thensnext(head);next(head);RET(head);RET(head);head head s;returns;return /a/a为第一个结点，为第一个结点，s s为中间变量为中间变量,改进改进/3.3.LOOKFOR(head,a,q)LOOKFOR(head,a,q)4.if(next(q)=nil)then4.if(next(q)=nil)then无此结点无此结点returnreturn5.5.p p next(q);next(q)next(q);next(q)next(p)next(p)6.RET(6.RET(p p)/p/p为待删除节点，为待删除节点，q q为其前趋为其前趋/7.return7.return2024/7/1131n3 3、线性链表的其它形式、线性链表的其它形式n(2)(2)具有头结点的线性链表具有头结点的线性链表(简化算法简化算法,减少分支减少分支)：n头结点：结构相同、数据域空、指针域指向第一个结点。头结点：结构相同、数据域空、指针域指向第一个结点。n优点优点:使算法在使算法在形式上得以简化形式上得以简化。如插入，。如插入，表空表空相当于相当于a a元元素不存在；当素不存在；当a a为为第一个元素第一个元素时，不必修改时，不必修改headhead。n（3 3）循环链表）循环链表：表中最后一个结点的指针域指向表头，整个：表中最后一个结点的指针域指向表头，整个链表形成一个环。链表形成一个环。2024/7/1132nn优点：优点：只要给定循环链表中的任一结点的地址，就可以只要给定循环链表中的任一结点的地址，就可以遍历遍历整个链表，整个链表，而不必从头指针开始。方便某些运算而不必从头指针开始。方便某些运算,克服克服“顺序访问顺序访问”缺点。缺点。（4 4）双向链表：）双向链表：结点有两个指针域，一个指向前趋结点，一个结点有两个指针域，一个指向前趋结点，一个指向后继结点。指向后继结点。n优缺点：优缺点：n单向链表：单向搜索，表长为单向链表：单向搜索，表长为n n时，执行时间为时，执行时间为O(n)O(n)。n双向链表：双向搜索，但插入或删除时需修改两个指针。双向链表：双向搜索，但插入或删除时需修改两个指针。2024/7/11332024/7/1134习题习题(线性表的两种存储结构线性表的两种存储结构)n问题描述问题描述:n将表长为将表长为n的顺序表和不带头结点的单向链表的顺序表和不带头结点的单向链表(a1，a2，an)中的元素逆置中的元素逆置.2024/7/1135算法实现算法实现:nInvert1(A,n)1.for i=1 to n div 22.AiAn-i+13.end(i)4.Return5.div为向下取整为向下取整nInvert2(head)1.phead;q nil2.while(p nil)do3.r next(p)/保持联系保持联系4.next(p)q/转换方向转换方向5.q p;p r/处理下一个结点处理下一个结点6.end(while)7.head q/此时此时q指向指向an8.Return9.抓住抓住:前趋后继关系前趋后继关系;10.P正在处理的结点正在处理的结点;11.q其前趋结点其前趋结点;12.r其后继结点其后继结点.2024/7/1136a1ai-1aiai+1an a1 ai-1aiai+1an qpr2024/7/11374 4、线性表应用实例、线性表应用实例一元多项式相加一元多项式相加n一元多项式一元多项式p pn n(x)(x)的表示法：的表示法：p pn n(x)=p(x)=p0 0+p+p1 1x+px+p2 2x x2 2+p+pi ix xi i+p+pn nx xn n若按升幂排列，则它由若按升幂排列，则它由n+1n+1个系数唯一确定，可用一个个系数唯一确定，可用一个线性表表示：线性表表示：p=(pp=(p0 0,p,p1 1,p,pi i,p,pn n)其指数其指数i i隐含在系数隐含在系数p pi i的序号内。的序号内。np pn n(x)(x)的存储结构的存储结构:顺序存储结构：求值，不需修改系数和指数。顺序存储结构：求值，不需修改系数和指数。链式存储结构：相加、或多项式的次数很高但又存在大链式存储结构：相加、或多项式的次数很高但又存在大量的零系数项。量的零系数项。n多项式多项式线性表线性表;n不同运算、不同情形，采用不同存储结构不同运算、不同情形，采用不同存储结构.2024/7/1138一元多项式的链式结构一元多项式的链式结构:n多项式中的每一项对应链表中的一个结点多项式中的每一项对应链表中的一个结点.n指数、系数和指针域指数、系数和指针域2024/7/1139多项式相加多项式相加:C(x)=A(x)+B(x)C(x)=A(x)+B(x)n运算规则：运算规则：n指数相同的项对应系数相加，若和不为零，则构成指数相同的项对应系数相加，若和不为零，则构成C C（x x）中的一项；若和为零，则）中的一项；若和为零，则c(x)c(x)中没有该指数中没有该指数项。项。A(x)A(x)和和B(x)B(x)中所有指数不相同的项均中所有指数不相同的项均复抄复抄到到C(x)C(x)中。中。n A(x)A(x)和和B(x)B(x)均带有头结点，均带有头结点，h hA A和和h hB B分别为其头指针，分别为其头指针，p p和和q q的初值分别指向它们的第一项（的初值分别指向它们的第一项（指数不一定相指数不一定相同同）。）。2024/7/1140n运算过程运算过程(算法思想算法思想)：n比较比较p,qp,q所指结点的指数项，分如下三种情形：所指结点的指数项，分如下三种情形：n若若EXP(p)EXP(q),EXP(p)EXP(q),EXP(p)EXP(q),则则q q所指的结点为所指的结点为C(x)C(x)的一项，将的一项，将q q结点结点插入插入p p结点之前，结点之前，q q后移一个结点。后移一个结点。n若若EXP(p)=EXP(q),EXP(p)=EXP(q),则系数相加，如和不为则系数相加，如和不为0 0，修改，修改p p结点的结点的系数，回收系数，回收q q结点。否则删去结点。否则删去p p结点结点(因为实质是在因为实质是在A(x)A(x)的基的基础上通过修改系数础上通过修改系数、删除和插入结点而形成、删除和插入结点而形成C(x)的的)，同时，同时回收回收p p和和q q结点。结点。n实质实质：n链式存储的特点决定可以：链式存储的特点决定可以：n将将B(x)B(x)加到加到A(x)A(x)中，最后形成中，最后形成C(x)C(x)。C(x)C(x)的结点的结点不需要重新生成。不需要重新生成。2024/7/1141算法阅读算法阅读:n分块说明功能划分分块说明功能划分.n使用典型案例执行法使用典型案例执行法:2024/7/1142ADDPOLY(hA,hB)n1.p1.pnext(next(h hA A););q qnext(next(h hB B)n2.p2.prere h hA A;h;hC C h hA A/pre/pre指向指向p p的前趋，的前趋，h hC C为为c(x)c(x)的头指针。的头指针。/n3.3.while(pwhile(p nil)AND(q nil)AND(q nil)donil)don4.4.casecasen5.5.EXP(p)EXP(q):EXP(p)EXP(q):EXP(p)EXP(q):n13u13u next(q);next(q)next(q);next(q)p;next(pp;next(prere)q;pq;prere q;q q;q uun14.14.end(case)end(case)n15.end(while)15.end(while)n16.if(q 16.if(q nil)then next(pnil)then next(prere)q q/B(x)/B(x)的次数高于的次数高于A(x)/A(x)/n17.RET(h17.RET(hB B)/)/回收头结点回收头结点n18.return18.return2024/7/1143注意：图中错误,释图.2024/7/11442.2.4 2.2.4 向量和链表的比较向量和链表的比较n1 1、线性表的长度是否固定？、线性表的长度是否固定？表长固定表长固定向量向量静态分配；静态分配；表长不固定表长不固定链表链表动态分配。动态分配。n2 2、线性表的主要操作是什么？线性表的主要操作是什么？向量向量连续存放连续存放随机存取随机存取适用频繁适用频繁查找查找不适用不适用插入、删除插入、删除平均移动一半元素。平均移动一半元素。链表链表随机存放随机存放顺序存取顺序存取查找要从头指针开始查找要从头指针开始查找的时间复杂度为查找的时间复杂度为O(n)O(n)适用插入、删除适用插入、删除但但“前前插插”时，要查找前趋结点时，要查找前趋结点查找的时间复杂度为查找的时间复杂度为O(n)O(n)增加指针域增加指针域以空间换取时间。以空间换取时间。n3 3、采用的算法语言、采用的算法语言线性链表要求所使用的语言工具提供指针类型变量。线性链表要求所使用的语言工具提供指针类型变量。n4 4、线性表的大小、线性表的大小,多个表共享计算机存储空间多个表共享计算机存储空间 导致运算的失败或中断导致运算的失败或中断2024/7/1145问题问题:伪码翻译为伪码翻译为C/Pascal1.定义链表结点定义链表结点2.GETNODE(p)3.RET(p)2024/7/1146n#include“stdlib.h”nstruct noden int data;n struct node*next;nnmain()nnstruct node*P;nnp=(struct node*)malloc(sizeof(struct node);nnfree(p);n2024/7/1147p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日