算法与数据结构：第3章线性表

《算法与数据结构：第3章线性表》由会员分享，可在线阅读，更多相关《算法与数据结构：第3章线性表（104页珍藏版）》请在金锄头文库上搜索。

1、01 八月 2024第1页线性表线性表01 八月 2024第2页【学习目标学习目标】 1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。01 八月 2024第3页【重点和难点重点和难点】 链表是本章的重点和难点。扎实的指链表是本章

2、的重点和难点。扎实的指针操作和内存动态分配的编程技术是学针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针好本章的基本要求，分清链表中指针 p p 和结点和结点 * *p p 之间的对应关系，区分链表之间的对应关系，区分链表中的头结点、头指针和首元结点的不同中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。所指以及循环链表、双向链表的特点等。【知识点知识点】线性表、顺序表、链表、有序表线性表、顺序表、链表、有序表01 八月 2024第4页线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中

3、必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集线性表线性表是一种最简单的线性结构线性结构01 八月 2024第5页1 线性表的类型定义线性表的类型定义3 线性表类型的实现线性表类型的实现 链式映象链式映象4 一元多项式的表示一元多项式的表示2 线性表类型的实现线性表类型的实现 顺序映象顺序映象01 八月 2024第6页线性表的类型定义线性表的类型定义01 八月 20

4、24第7页l定义：一个线性表是具有相同类型的n（n0）个数据元素的有限序列，通常记为：例 英文字母表（A,B,C,.Z)例数据元素l特征：i为元素的序号元素个数n表长度，n=0空表1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继1 线性表的定义01 八月 2024第8页 数据对象数据对象：D ai | ai D0, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai

5、 在线性表中的位序位序。01 八月 2024线性表的基本运算置空表setnull(L)：将线性表L置为空表。求长度length(L)：计算线性表L中数据元素的个数。取元素get(L,i)：取出线性表L中第i个数据元素；要求ilength(L)。取前趋prior(L,x)：取出线性表L中值为x的元素的前趋元素；要求x的位序大于1。取后继next(L,x)：取出线性表L中值为x的元素的后继元素；要求x的位序小于length(L)。定位序locate(L,x)：确定元素x在线性表L中的位置，并给出位置序号；若L中无x返回0。01 八月 2024线性表的基本运算（续）插入insert(L,x,i)：在

6、线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1ilength(L)+1。删除delete(L,i)：删除线性表L中的第i个元素，使表长减1；要求1ilength(L)。01 八月 2024第11页利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-101 八月 2024第12页求两个集合的并，即A=AB例例 2-1 01 八月 2024第13页 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：01 八月 2024第14页

7、1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访; 3若不存在，则插入之。get (LB, i)e locate (LA, e) insert(LA, n+1, e)操作步骤：操作步骤：01 八月 2024第15页 e =get(Lb, i); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!locate (La, e) ) insert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(La, Lb) La_len = length(La); / 求线性表的长度求线性表的

8、长度 Lb_len = length(Lb); for (i = 1; i = Lb_len; i+) / union01 八月 2024第16页 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-201 八月 2024第17页集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同01 八月 2024第18页void union(List &L

9、a, List Lb) La_len=length(La); Lb_len=length(Lb); / union e=get(Lb, i); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!locate(La, e) ) insert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i last = 0;01 八月 2024第29页线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现Locate(L, x) / 查找查找01 八月 2024第30页例如：顺序表的查找操

10、作23 75 41 38 54 62 17L.dataL.lastMAXSIZEx =38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 x 相比较。01 八月 2024第31页 int locate (sequenlist L, elemtype x) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：int i = 1; / i i 的初值为第的初值为第

11、 1 1 元素的位序元素的位序while (i = L.last & (L.datai!=x) +i;if (i = L.last) return i;else return 0;01 八月 2024第32页线性表操作insert(L, i, x)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？01 八月 2024第33页 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, x, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai xan, 表的长度增加01 八月 2024第34页算法的思想进行合法性

12、检查（i）检查线性表是否已满讲第n个至第i个元素逐一后移一个单位在第i个位置上插入表的长度+101 八月 2024插入运算的算法描述 void void insert(sequenlistinsert(sequenlist *L; *L; elemtypeelemtype x; x; intint i) i) intint j; j; if(iif(i(L-last+1)(L-last+1) printfprintf( (“插入位置不正确插入位置不正确nn”);); else else if(Lif(L-last=MAXSIZE)-last=MAXSIZE) printfprintf( (“表

13、已满，发生上溢表已满，发生上溢nn”);); else else for(jfor(j=L-=L-last;jlast;j=i;ji;j-) -) L-dataj+1=L- L-dataj+1=L-datajdataj; L- L-dataidatai=x; =x; L-last=L-last+1; L-last=L-last+1; /*insert*/ /*insert*/01 八月 2024第36页考虑插入算法的时间复杂度考虑插入算法的时间复杂度: :01 八月 2024第37页线性表操作 delete(&L, i)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？01 八月 2

14、024第38页 (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 01 八月 2024第39页算法的思想进行合法性检查，i是否满足要求判定线性表是否为空将第i+1至第n个元素逐一往前移动一个位置将表的长度减少101 八月 2024删除运算的算法描述 void void delete(sequenlistdelete(sequenlist *L *L，intint i) i) intint j; j; if(iif(iL-last)L-la

15、st) printfprintf( (“删除位置不正确删除位置不正确nn”);); else else for(jfor(j=i+1;j=i+1;jlast;jlast;j+)+) L-dataj-1=L- L-dataj-1=L-datajdataj; L-last=L-last-1; L-last=L-last-1; /*delete*/ /*delete*/01 八月 2024第41页考虑删除算法的时间复杂度考虑删除算法的时间复杂度: :01 八月 2024举例删除顺序表中的重复元素 一个顺序表中可能含有一些值相同的重复元素，题目要求对于值相同的重复元素只保留位序最小的一个而删除其它多余

16、的元素。l如（5，2，2，3，5，2）经删除重复元素后变为 （5，2，3） 01 八月 2024删除顺序表中的重复元素的算法描述 void Purge(L) sequenlist *L; int i,j,k; i=1; while(ilast) j=i+1; while(jlast) if(L-dataj=L-datai) for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/01 八月 2024举例有序表的合并顺序表A和B的元素均按由小到大的升序排列，编写算法将它们合并成为顺序表C，要求C中

17、元素也是从小到大的升序排列。算法思路：依次扫描A和B中元素，比较当前两个元素值，将较小的元素赋给C，直到其中一个顺序表扫描完毕，然后将另一个顺序表中剩余元素赋给C即可。 01 八月 2024有序表的合并的算法描述 void merge(C,A,B) sequenlist *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast&jlast) if(A-dataidataj) C-datak+=A-datai+; else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-data

18、k+=B-dataj+; C-last=k-1; /*merge*/01 八月 2024第46页01 八月 2024第47页 用一组地址任意地址任意的存储单元存放存放线性表中的数据元素。一、单链表一、单链表以数据域数据域(数据元素的信息数据元素的信息) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点以“结点的序列结点的序列”表示线性表 称作链表链表01 八月 2024第48页 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 a1 a2 . an 头指针空指针01 八月 2024第49页 typedef struct node elemtype

19、 data; / 数据域 struct node *next; / 指针域 LinkList; 二、结点和单链表的二、结点和单链表的 C 语言描述语言描述LinkList *H,*P； / H,P为单链表的头指针为单链表的头指针01 八月 2024第50页头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 01 八月 2024第51页1.元素的查找按序号查找01 八月 2024第52页L 线性表的操作 GetLinkList(L,i)在单链表中的实现(找到第3个元素)

20、:211830754256pppj1 2 301 八月 2024第53页 因此，查找第因此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针，比较移动指针，比较 j 和和 i 。 单链表不是一种顺序存取的结构，为找第单链表不是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第个数据元素，必须先找到第 i-1 个数据元素。个数据元素。 令指针令指针 p p 始终始终指向指向线性表中第线性表中第 j j 个数据元素。个数据元素。01 八月 2024 LinkList * getLinkList(LinkList *L，int i) LinkList *P; int j=0

21、; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; 01 八月 2024第55页1.元素的查找按值查找L211830754256pLocateLinkList(L,x) 01 八月 2024LinkListLinkList * *LocateLinkList(LinkListLocateLinkList(LinkList *L *L， elemtypeelemtype x) x) LinkListLinkList *P; *P; P=L-next; P=L-next; while(Pwhile(

22、P!=NULL)&(P-data!=x) !=NULL)&(P-data!=x) P=P-next; P=P-next; return P; /* return P; /*返回找到的结点位置或返回找到的结点位置或NULL*/NULL*/ 如果要返回位序，程序怎么修改01 八月 2024第57页2.插入操作01 八月 2024第58页ai-1 线性表的操作 insertLinkList(L, x ,i)在单链表中的实现： 有序对有序对 改变为改变为 和和 xaiai-101 八月 2024第59页s-data = e; s-next = p-next; p-next = s; / 插入 eai-

23、1aiai-1sp01 八月 2024第60页 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指针。针。01 八月 2024插入算法描述 void insertLinkList(LinkList *L, elemtype x,

24、int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第 i-1个 元 素 不 存 在 ， 参 数 i有 错n”); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; 01 八月 2024第62页3.删除操作01 八月 2024第63页线性表的操作deleteLinkList (L, i)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-101 八月 2024第6

25、4页 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq01 八月 2024删除单链表L中的第i个结点算法 void deleteLinkList(LinkList *L, int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在，参数

26、i 有错n”); else S=P-next; P-next=S-next; free (S); 01 八月 2024第66页 int deleteLinkList (LinkList *L, int i, ElemType &e) LinkList *p = L; int j = 0;while (p-next!=NULL & j next; / 寻找第 i 个结点，并令 p 指向其前趋 +j; if (!(p-next) | j i-1) return 0; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q)

27、;return 1;01 八月 20244.求表长只要设一个移动指针扫描整个单链表，就可以统计出元素个数即表长。其算法描述如下： int LengthLinkList(LinkList *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长*/ 该算法扫描整个单链表，时间复杂度为O(n)。 01 八月 2024第68页5.建立单链表01 八月 2024第69页如何从得到单链表？如何从得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表

28、的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” 的过程。的过程。01 八月 2024第70页例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。( (头插法头插法) )操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。01 八月 2024第71页adcbi=0 i=1 i=2

29、i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后01 八月 2024第72页void CreateList (LinkList *&L

30、, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList*) malloc (sizeof (node);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList*) malloc (sizeof (node); scanf(“%d”,&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入01 八月 2024第73页正序插法01 八月 2024单链表建立过程示例线性表（25

31、，45，18，76，29）的单链表动态建立过程如下图：01 八月 2024第75页LinkList * CreateList(int n) /* 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表 */int i;LinkList *L;LinkList * p,*r;L=(LinkList *)malloc(sizeof(LinkList); /* 生成头结点 */L-next=NULL;r=L;printf(请输入%d个数据n,n);for(i=1;idata);p-next=NULL;r-next=p;r=p;return L 01 八月 2024第76页归并两个有序表Lb2

32、6891115 La35811 01 八月 2024第77页LinkList * MergeList ( LinkList *&La, LinkList *&Lb )pa=La-next; pb=Lb-next;Lc=pc=La;While( pa & pb ) if( pa-data data ) pc-next=pa; pc=pa; pa= pa -next; else pc-next=pb; pc=pb; pb=pb-next; if(pa) pc-next=pa;else pc-next=pb; free(Lb); return Lc 。01 八月 2024举例将单链表H逆置 所谓逆置

33、是指结点间的关系相反，即前趋变后继而后继变前趋。如图(a)的单链表逆置后成为图(b)的单链表。算法思路：依次从原链表中取出每个结点，每次都把它作为第一个结点插入到新链表中去。为此要借用两个指针变量P和q，P用来指向原链表中的当前第一个结点，q用来指向从原表取出的每一个结点并利用它插入到新链表中去，当P为空时完成逆置。 01 八月 2024将单链表H逆置的算法描述 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-next; q-next=H-next; H-ne

34、xt=q; *reverse*/该算法没有开辟新的存储空间，对链表顺序扫描一遍就完成了逆置，时间开销为O(n)。01 八月 2024第80页优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序存储结构的优缺点01 八月 2024第81页单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢01 八月 2024第82页循环链表是表中最后一个结点的指针指向头结点，使链表构成环状h空表循环链表(circular linked list)v特点：

35、从表中任一结点出发均可找到表中其他结点，提高查找效率v操作与单链表基本一致,循环条件不同l单链表p或p-next=NULLl循环链表p或p-next=Hh01 八月 2024第83页r空表设置尾指针的循环链表设置尾指针的循环链表，在对两个单循环链表进行连接使可以提高效率。r2b1bnr1a1anr1-next=r2-next-next;r2-next=p;rpp=r1-next;01 八月 2024第84页单链表具有单向性的缺点，找前驱不方便！结点定义typedef struct dupnode elemtype data; struct dupnode *prior,*next;duplin

36、klist;priordatanextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;双向链表（double linked list）01 八月 2024第85页双向链表的操作特点：双向链表的操作特点：“查询查询” 和单链表相同。和单链表相同。“插入插入” 和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。01 八月 2024第86页void ins_dlinklist(duplinklist * p,int x)duplinklist *s; s=(duplinklist *)malloc(size

37、of(duplinklist ); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法评价：T(n)=O(1)xSbaP插入p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;01 八月 2024第88页bcaaPPvoid del_dlinklist(duplinklist *p) p-prior-next=p-next; p-next-prior=p-prior; free(p);删除算法描述算法评价：T(n)=O(1)p-prior-next=p-nex

38、t;p-next-prior=p-prior;01 八月 2024第90页用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的存在的问题问题： 改进链表的设置改进链表的设置1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前当前位置的位置的 指针指针” 三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2

39、将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。01 八月 2024第91页一个带头结点的线性链表类型一个带头结点的线性链表类型typedef struct node / 结点类型结点类型 ElemType data; struct node *next; Link;typedef struct / 链表类型链表类型 Link * head, *tail; / 分别指向头结点和 /最后一个结点的指针 int len; / 指示链表长度 Link* current; / 指向当前被访问的结点 /的指针，初始位置指向头结点 LinkList;01 八月 2024第92

40、页01 八月 2024第93页在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？01 八月 2024第94页 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 expexp ,则p为结点C(x)的一项，移动p2. p-expq-exp,则q结点插入到p结点之

41、前，移动q3. p-exp=q-exp,则，系数相加，释放q结点01 八月 2024一元多项式的数据类型定义如果是多项式的运算问题如相加和相乘等，考虑到会产生新的项和系数为零项减少这两种情况，宜考虑采用链式存储结构即单链表实现。其数据类型可如下定义： typedef struct linknode float coef; int exp; struct linknode *next; polynomial;01 八月 2024多项式的链式存储表示示例假设使用头结点，前述的T(X)= 3+5x200+7x1000可表示为如下图所示的结构： 01 八月 2024多项式相加算法的思路不产生新结点而利

42、用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。若指数相等系数相加，和不为零修改*p的系数项并删除*q，和为零删除*p和*q；若指数不等，p-expexp时*p为和多项式中的一项，p-expq-exp时把*q插在*p之前（*q为和多项式中的一项）；所有操作之后要相应移动指针。直到其中一个链空，把另一个链剩下的结点插在*p之后。 01 八月 2024多项式相加算法的描述void polyadd(A,B)polynomial *A,*B; polynomial *p,*q,*s,*r; float x; p=A-next; q=B-n

43、ext; s=A; while(p!=NULL)&(q!=NULL) if(p-exp)(q-exp) r=q-next; q-next=p; /*把p接在q所指结点后*/ s-next=q; /*把q接入结果链*/ s=q; q=r; else if(p-expexp) s=p; p=p-next; 01 八月 2024多项式相加算法的描述（续）else x=p-coef+q-coef; if(x!=0) p-coef=x; s=p; else s-next=p-next; free(p); p=s-next; r=q; q=q-next; free(r); if(q!=NULL) s-ne

44、xt=q; /*把q链剩余结点链入结果链*/ free(B); /* polyadd*/该算法的比较次数与A、B两个多项式的长度m和n有关，算法的时间复杂度为O(m+n)。 01 八月 2024第102页 在这一章我们向大家介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现。 线性表是 n(n0) 个数据元素的序列，通常写成 (a1 ,a2 , an, ) 因此线性表中除了第一个和最后一个元素之外都只有一个前驱和一个后继。线性表中每个元素都有自己确定的位置，即位序，因此线性表也可以看成是由 n 个 (i,) 构成的集合。 n=0时的线性表称为空表，它是线性表的一种特殊状态，因此在写线性

45、表的操作算法时一定要考虑你的算法对空表的情况是否也正确。 顺顺序序表表是线性表的顺序存储结构的一种别称。它的特点是以存储位置相邻表示两个元素之间的前驱后继关系。因此，顺序表的优点是可以随随机机存存取取表中任意一个元素，其缺点是每作一次插入或删除操作时，平均来说必须移动表中一半元素。常应用于主要是为查查询询而而很很少少作作插插入入和和删删除除操操作作，表长变化不大的线性表表长变化不大的线性表。【本章小结本章小结】01 八月 2024第103页 链链表表是线性表的链式存储结构的别称。它的特点是以指针指示后继元素，因此线性表的元素可以存储在存储器中任意一组存储单元中。它的优优点点是是便便于于进进行行

46、插插入入和和删删除除操操作作，但不不能能进进行行随随机机存存取取，每个元素的存储位置都存放在其前驱元素的指针域中，为取得表中任意一个数据元素都必须从第一个数据元素起查询。由于它是一种动态分配的结构，结点的存储空间可以随用随取，并在删除结点时随时释放，以便系系统统资资源源更更有有效效地地被被利利用用。这这对对编编制制大大型型软软件件非非常常重重要要，作作为为一一个个程程序序员员在在编编制程序时必须养成这种习惯制程序时必须养成这种习惯。 由于线性表是一种应用很广的数据结构，链表的操作又很灵活，因此在C+等面向对象的程序设计语言中都已为程序员提供了链表类，读者在使用时应该首先充分了解它的操作接口。在自己实现链表类时，正如课程中所述，应该为链表结构设置合适的数据成员和恰当的操作接口，以便使每个基本操作的时间复杂度在尽可能低的级别上。 01 八月 2024第104页