（知识点三） 2.3 线性表的链式表示和实现 本节将介绍线性表的另一存储结构—— 链式存储及其对应的操作。

Presentation on theme: "（知识点三） 2.3 线性表的链式表示和实现 本节将介绍线性表的另一存储结构—— 链式存储及其对应的操作。"— Presentation transcript:

1 （知识点三） 2.3 线性表的链式表示和实现 本节将介绍线性表的另一存储结构—— 链式存储及其对应的操作。

2 链式存储结构的特点：存储结构可以不是连续的。可以用一个指针域来指出下一个数据元素所在内存的位置。一般，用结点来表示某数据元素及其对应的下一个结点的位置。 由于每个 只包含一个指针域,所以既叫做线性表，也叫做单链表. 数据域 指针域 结点

3 单链表 1、单链表的逻辑结构 h 不带头节点的链表 h 带头节点的链表 (思考:头节点的作用)

4 线性表的单链表的存储表示 用C语言中的指针数据类型描述的单链表： q p typedef struct LNode {
ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针 若设 LNode *p,*q; 则p,q都是指针变量, p->data 表示p结点的数据域 p->next 表示p结点的后继指针域 p data next q p

5 单链表操作的实现 GetElem(L, i, e) // 取第i个数据元素 ListInsert(&L, i, e) // 插入数据元素
ListDelete(&L, i, e) // 删除数据元素 ClearList(&L) // 重置线性表为空表 CreateList(&L, n) // 生成含 n 个数据元素的链表

6 1、单链表操作 GetElem(L, i, &e)在单链表中的实现
21 18 30 75 42 56 ∧ j p p

7 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。
单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 令指针 p 始终指向线性表中第 j 个数据元素。

8 while (p && j<i) { p = p->next; ++j; }
Status GetElem_L(LinkList L, int i, ElemType &e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L 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; 算法时间复杂度为: O(ListLength(L))

9 2、单链表的插入 ListInsert(&L, i, e)
在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。基本操作：找到线性表中第a的结点，修改其指向后继的指针 data next a b p 有序对 <a, b> 改变为 <a, x> 和<x,b> x s

10 s = (LNode *)malloc(sizeof(LNode)); s->data = x;

11 步骤2 ：将数据元素x插在a和b元素之间。 data next a b p x s

12 s->next = p->next; p->next = s;
用C语言描述为： s->next = p->next; p->next = s; data next a b p x s

13 在带头结点单链表L中第i个位置之前插入元素e：
… L a1 ai-1 p ai … an ^ j = 0

14 在带头结点单链表L中第i个位置之前插入元素e：
… L a1 ai-1 p ai … an ^ j = 1

15 在带头结点单链表L中第i个位置之前插入元素e：
… L a1 ai-1 ai p … an ^ j = …

16 在带头结点单链表L中第i个位置之前插入元素e：
… L a1 ai-1 p ai … an ^ j = i-1 GetElem(L,i-1)

17 s … L p … ^ 关键语句： s=(LNode *)malloc(sizeof(LNode)); s->data = e;
ai-1 p ai … an ^ 关键语句： s=(LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s;

18 while (p && j<i-1 ){ p=p->next; ++j ； } //寻找i-1个结点
typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针 算法2.9 p29 status ListInsert_L( LinkList &L,　int I, ElemType e ) { // 在带头结点的单链线性表Ｌ中第i个位置之前插入元素e p=L;j=0; while (p && j<i-1 ){ p=p->next; ++j ； } //寻找i-1个结点 if (!p||j>i-1) return ERROR s=(LinkLIst) malloc( sizeof(LNode) ); s->data = e; s->next = p->next; p->next = s; return OK; } // ListInsert_L 时间复杂度：O(ListLength(L))

19 3、单链表的删除-1 在线性表的两个数据元素a和c之间删除一个数据元素b，已知p为其单链表存储结构中指向结点a的指针。基本操作：找到线性表中第b个结点，修改其指向后继的指针 删除元素b： data next … … a b b c p

20 3、单链表的删除-2 删除元素b： data next … … a b b c p

21 … … 3、单链表的删除 ListDelete (&L, i, &e) -3 删除元素b： 用C语言语句描述为：
data next … … a b b c p 用C语言语句描述为： p->next=p->next->next;

22 删除元素b并释放之： q data next … … a b b c p 步骤1：将b的地址记录下来 即：q=p->next;

23 … … 删除元素b并释放之： 步骤2：让p->next指向b后第一个结点 即：p->next=q->next; q a b
data next … … a b b c p 步骤2：让p->next指向b后第一个结点 即：p->next=q->next;

24 删除元素b并释放之： q data next … … a b b c p 步骤3：释放b结点 即：free(q)

25 删除元素b并释放之： b q data next … … a c p 步骤3：释放b结点 即：free(q)

26 status ListDelete_L( LinkList &L, int i, ElemType e ) {
p=L;j=0; while (p->next && j<i-1) { //寻找第i个结点，并令p指向其前驱 p=p->next;++j； } 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))

27 4、如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是对每个建立好的结点进行“逐个插入” 的过程。
主要方法：从单链表的尾部进行插入。

28 操作步骤： 一、建立一个“空表”； 四、依次类推，直至输入a1为止。 二、输入数据元素an， 建立结点并插入； an
建立带头结点的单链表。 操作步骤： 一、建立一个“空表”； 二、输入数据元素an， 建立结点并插入； an 三、输入数据元素an-1， 建立结点并插入； an an-1 四、依次类推，直至输入a1为止。

29 an void CreateList_L(LinkList &L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表
算法2.11 p30 void CreateList_L(LinkList &L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表 } // CreateList_L 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; // 插入 } //for L->next p->next L p an 算法的时间复杂度为: O(Listlength(L))

30 5、当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度如何估算？

31 控制结构： 基本操作： 算法时间复杂度 for 循环 LocateElem void union(List &La, List Lb) {
La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (!LocateElem(La, e, equal( )) ListInsert(La, ++La_len, e); }//for } // union 控制结构： 基本操作： 算法时间复杂度 for 循环 LocateElem 当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) ) 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) )

32 控制结构： 基本操作： for 循环 ListInsert 算法时间复杂度 当以顺序映像实现抽象数据类型线性表时为:
void purge(List &La, List Lb) { InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } }//for } // purge 控制结构： 基本操作： for 循环 ListInsert 算法时间复杂度 区别在于顺序存储时该问题的插入位置是末尾可以直接定位； 链式存储时该问题的插入位置是末尾但必须从头指针找起：在单链表的最后一个元素之后插入元素时， 需遍历整个链表 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength2(Lb) )

33 算法时间复杂度 void MergeList(List La, List Lb, List &Lc) {
InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } } … … 算法时间复杂度 控制结构： 基本操作： 三个并列的while循环 ListInsert 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)+ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength 2(La)+ListLength 2(Lb) )

34 在线性表中实现单链表的操作时，存在的问题：
１．单链表的表长是一个隐含值． ２．在单链表的最后一个元素最后插入元素时，需遍历整个链表． ３．在链表中，元素的”位序”概念淡化，结点的”位置”概念强化． 改进链表的设置： １．增加“表长”，“表尾指针”和“当前位置的指针”三个数据域； ２．基本操作由位序改为指针(使得有的操作的时间复杂度尽量降低)

35 6、一个带头结点的线性链表类型 Typedef struct LNode{ //结点类型 ElemType data;
Struct LNode *next } *Link , *Position Status MakeNode(Link &p,ElemType e)//分配结点空间 //分配由 p指向的值e的结点，并返回OK； //若分配失败，则返回ERROR void FreeNode(Link &p); //释放p所指的结点

36 typedef struct {//链表类型
link head ,tail; //指向头结点和最后一个结点 int len; //指示链表的长度 Link current //指向当前访问的结点的指针 //初始位置指向头结点 }LinkList;

37 链表的基本操作： ｛结构初始化和销毁结构｝ Status InitList(LinkList &L); //构造一个空的链表Ｌ，
//头指针，尾指针和当前指针均指ElemType e向头结点 //表长为零 Status DestroyList(LinkList &L); //销毁线性表Ｌ，Ｌ不再存在 ｛引用型操作｝ Status　ListEmpty(LinkList &L);//判表空 int ListLength(LinList L);//求表长 Status Prior(LinkList L);//改变当前指针指向其前驱　

38 Status Next(LinkList L);//改变当前指针指向其后继
ElemType GetCurElem(LinkList L);//返回当前指针所指的数据元素 Status LocatePos(LinkList L ,int i); //改变当前指针指向第i个元素 Status LocateElem(LinkList L ,ElemType e, Status (*compare )(ElemType e, ElemType e); //若存在与e满足函数compare()判定关系的元素，则移动当前指针 //指向第１个满足条件的元素，并返回OK，否则返回ERROR Status　ListTraverse(LinkList L, Status(*visit()); //依次对Ｌ的每一个元素调用函数visit()

39 ｛加工型操作｝ Status　ClearList(LinkList &L); //重置为空表 Status SetCurElem(LinkList &L, ElemType e); //更新当前指针所指数据元素 Status Append(LinkList &L, Link s); //一串结点链接在最后一个结点之后 Status InsAfter(LinkList &L, ElemType e); // 将元素e插入在当前指针之后 Status DelAfter(LinkList &L, ElemType *e); // 删除当前指针之后的结点

40 Status InsAfter( LinkList& L, ElemType e ) {
// 表L中当前指针所指结点之后,并返回OK; 否则返回ERROR。 } // InsAfter if ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s->next = L.current->next; L.current->next = s; return OK; 带头结点的线性表类型定义： typedef struct LNode{//结点类型 Elemtype data ; struct LNode *Next; } *Link ,*Position; typedef struct {//链表类型 Link head ,tail; //指向头结点和最后一个结点 int len; //指示链表的长度 Link current //指向当前访问的结点的指针,初始位置指向头结点 }LinkList; LinkList L； // L 为单链表的头指针

41 // 若当前指针及其后继在链表中，则删除线性链表L中当前
Status DelAfter( LinkList& L, ElemType& e ) { // 若当前指针及其后继在链表中，则删除线性链表L中当前 // 指针所指结点之后的结点，并返回OK; 否则返回ERROR。 } //DelAfter if ( !(L.current && L.current->next ) ) return ERROR; q = L.current->next; L.current->next = q->next; e=q->data; FreeNode(q); return OK; 带头结点的线性表类型定义： typedef struct LNode{//结点类型 Elemtype data ; struct LNode *Next; } *Link ,*Position; typedef struct {//链表类型 Link head ,tail; //指向头结点和最后一个结点 int len; //指示链表的长度 Link current //指向当前访问的结点的指针,初始位置指向头结点 }LinkList; LinkList L； // L 为单链表的头指针

42 利用上述定义的线性链表如何完成线性表的其它操作 ？
例1： Status ListInsert_L(LinkList L, int i, ElemType e) { // 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e } // ListInsert_L if (!LocatePos (L, i-1)) return ERROR; // i 值不合法，第 i-1 个结点不存在 if (InsAfter (L, e)) return OK; //插入在 i-1 个结点之后 else return ERROR;

43 // 已知单线性表La 和 Lb 的元素按照值非减排序
例2：算法2.20 P39 Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ，LinkList &Lbc int (*compare) (ElemType,ElemType))) { // 已知单线性表La 和 Lb 的元素按照值非减排序 //归并有序表 La 和 Lb ,得到新的（非减排序）线性表 Lc, 归并之后销毁La 和 Lb, // If （! InitList(Lc)) return ERROR; // 存储空间分配失败 ha=GetHead(La); hb=GetHead(Lb); //ha、hb分别指向La和Lb的头指针 Pa=Nextpos(La,ha); Pb=Nextpos(Lb,hb); While (pa && pb) { //La和Lb均非空 a=GetcurElem(pa); b=GetcurElem(pb); //ha、hb 分别为当前表的比较元素 If ((*compare )(a,b) <=0 ) ) { //a<=b DelFirst(ha,q) ; Append(Lc,q); Pa=Nextpos(La,ha) ; } else { //a>b DelFirst(hb,q) ; Append(Lc,q); Pb=Nextpos(Lb,hb) ; } } //while If (pa) Append (Lc,pa); //链接La中剩余的结点 else Append (Lc,pb); //链接Lb中剩余的结点 FreeNode (ha); FreeNode (hb); //释放La和Lb头结点 Return OK； } // MergeList_L

44 小结 1、在单链表上插入、删除一个结点，必须知道其前驱结点。 2、单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。 3、链式存储的优点：插入删除效率高 4、链式存储的缺点：访问某个数据效率低、存储密度低

45 循环链表是一种头尾相接的链表。其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
其它形式的链表 循环链表 循环链表是一种头尾相接的链表。其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表：在单链表中，将终端结点的指针域NULL改为指向第一个结点，就得到了单链形式的循环链表，并简称为单循环链表。 循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：

46 …. a1 an head ⑴ 非空表 ⑵ 空表

47 （2）单循环链表最后结点的指针域不为空，而是指向 “头结点”。
a1 a2 an-1 an head 单循环链表 …… 单循环链表与单链表的差别仅在于： （1）单链表最后结点的指针域为空； （2）单循环链表最后结点的指针域不为空，而是指向 “头结点”。

48 双向循环链表 空表 非空表 a a2 … an

49 双向链表 双向链表:有时侯为了方便找出当前结点的前驱，在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。

50 1、 双向链表结点定义 双向链表结点定义为： typedef struct DuLNode{ ElemType data; //数据域
struct DuLNode *prior; //指向前驱元素的指针 struct DuLNode *next;//指向后继元素的指针 } DuLNode ,*DuLinkList;

51 …. a1 an head 设指针p指向某一结点，则有： ⑴ 非空表 双向链表 ⑵ 空表
2、双向链表相邻结点指针域之间的关系 设指针p指向某一结点，则有： (p—>prior)—>next = p (p—>next)—>prior = p 即结点*p的存储位置既存放在其前趋结点 *(p—>prior)的直接后继指针域中，也存放 在它的后继结点*(p—>next)的直接前趋指针域中。 p …. ^ a1 an ^ head ⑴ 非空表 双向链表 ^ ^ ⑵ 空表

52 3、双向链表的操作-1 1）插入操作前的状态步骤 当前要插入的s结点 P ai-1 ai ai+1 s e p —>prior
next prior ai next prior ai+1 next p —>prior —>next =p p —>prior —>next =p s prior e next 当前要插入的s结点

53 3、双向链表的操作-2 2）插入操作步骤-(1) ① s->prior = p->prior; 当前要插入的s结点 P ai-1
next prior ai next prior ai+1 next p —>prior —>next =p p —>prior —>next =p s->prior ① s prior e next 当前要插入的s结点 ① s->prior = p->prior;

54 3、双向链表的操作-3 2）插入操作步骤-(2) ② p-> prior -> next = s; 当前要插入的s结点 P
ai-1 next prior ai next prior ai+1 next p —>prior —>next =p p —>prior —>next =p ② s->prior ① s prior e next 当前要插入的s结点 ② p-> prior -> next = s;

55 3、双向链表的操作-4 2）插入操作步骤-(3) ③ s->next = p; 当前要插入的s结点 P ai-1 ai ai+1 ③
p —>prior P prior ai-1 next prior ai next prior ai+1 next p —>prior —>Next =p ③ p —>prior —>next =p ② ① s prior e next s->prior s->prior 当前要插入的s结点 ③ s->next = p;

56 3、双向链表的操作-5 2）插入操作步骤-(4) ④ p->prior = s; P ai-1 ai ④ ③ ② ① s e
s->prior prior ai-1 next prior ai next ④ ③ ② ① s prior e next s->prior s->prior ④ p->prior = s;

57 小结：1)在双向链表P结点前，插入一个s结点操作共需以下四个步骤——
① s->prior = p->prior; ② p-> prior -> next = s; ③ s->next = p; ④ p->prior = s; 2) 除了考虑上述的基本操作外，其它操作与（循环）单链表相同。

58 2） 删除操作 ① p->prior->next = p->next; ② p->next->prior = p->prior; ③ free(p);

59 2.4 一元多项式的表示及相加 一元多项式的表示

60 一元多项式的表示： 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 但是对于形如
S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？

61 （（p1, e1）, (p2, e2), …, (pm,em) ） Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem
一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 < e2 < ┄ < em = n 可以下列线性表表示： （（p1, e1）, (p2, e2), …, (pm,em) ）

62 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数，
一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 < e2 < ┄ < em = n 可以下列线性表表示： （（p1, e1）, (p2, e2), ┄, (pm,em) ）

63 例如 P866(x) = 7x2 - 3x11 +5x866 可用线性表 ( (7, 2), (-3, 11), (5, 866) ) 表示

64 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象： 数据关系：
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 }

65 基本操作(1) （2）DestroyPolyn ( &P ) （3）PrintPolyn ( &P )
（1）CreatPolyn ( &P, m ) 操作结果：输入 m 项的系数和指数，建立一元多项式 P。 （2）DestroyPolyn ( &P ) 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 （3）PrintPolyn ( &P ) 操作结果：打印输出一元多项式 P。

66 基本操作(2) (5) AddPolyn ( &Pa, &Pb ) (4) PolynLength( P )
操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。

67 基本操作(3) (6) SubtractPolyn ( &Pa, &Pb )// 初始条件：一元多项式 P 已存在。
操作结果：完成一元多项式 相减运算，即 pa=pa-pb， 并销毁一元多项式pb。 (7) MultiplyPolyn ( &Pa, &Pb )// 初始条件：一元多项式 pa和pb已存在。 操作结果：完成一元多项式 相乘运算，即 pa=pa*pb， } ADT Polynomial

68 结点的数据元素类型定义为: 一元多项式的实现： typedef struct { // 项的表示 float coef; // 系数
typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType;

69 Status CreatPolyn ( polynomail &P, int m ) {
// 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项 } return OK; scanf (e.coef, e.expn); if (!LocateElem ( P, e, (*cmp)()) ) if ( !InsAfter ( P, e ) ) return ERROR; 注意: 1.输入次序不限; 2.指数相同的项只能输入一次。

70 参考教材算法2.2 P43 // 多项式加法:Pa=Pa+Pb,并销毁一元多项式Pb void AddPolyn(polynomial *Pa,polynomial *Pb) { Position ha,hb,qa,qb; term a,b; ha=GetHead(*Pa); hb=GetHead(*Pb); // ha和hb分别指向Pa和Pb的头结点 qa=NextPos(ha); qb=NextPos(hb); // qa和qb分别指向Pa和Pb中当前结点（现为第一个结 点） while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa) { // Pa和Pb均非空且ha没指向尾结点(qa!=0) a=GetCurElem(qa); b=GetCurElem(qb); // a和b为两表中当前比较元素 switch(cmp(a,b)) case -1: ha=qa; // 多项式Pa中当前结点的指数值小 qa=NextPos(ha); // ha和qa均向后移一个结点 break;

71 case 0: qa->data.coef += qb->data.coef; // 两者的指数值相等,修改Pa当前结点的系数值 if (qa->data.coef==0) // 系数和为0，删除多项式Pa中当前结点 { DelFirst(Pa,ha,&qa); FreeNode(&qa); } else { ha=qa; DelFirst(Pb,hb,&qb); FreeNode(&qb);} qb=NextPos(hb); qa=NextPos(ha); break;

72 case 1: DelFirst(Pb,hb,&qb); // 多项式Pb中当前结点的指数值小 InsFirst(Pa,ha,qb); ha=ha->next; qb=NextPos(hb); } if(!ListEmpty(*Pb)) { (*Pb).tail=hb; Append(Pa,qb); // 链接Pb中剩余结点 DestroyPolyn(Pb); // 销毁Pb

73 算法示意图如下： qb -1 pa 7 0 3 1 9 8 5 17 ^ pb 8 1 22 7 -9 8 ^ qa ha hb ha qa
^ pb 22 7 ^ qa ha hb ha qa qb -1 pa ^ pb 22 7 ^ hb

74 最后： qb=NULL -1 pa 7 0 11 1 9 8 5 17 ^ pb 8 1 22 7 -9 8 ^ qa ha hb
^ pb 22 7 ^ qa ha hb qb=NULL -1 pa ^ pb 22 7 ^ qa ha 最后： -1 pa 22 7 ^

75 第二章 小结 2、在熟练掌握这两类存储结构的形式化定义与描述方法的基础上，掌握抽象数据类型定义方法；掌握线性表的各种基本操作的实现。
第二章 小结 1、了解线性表的逻辑结构特性即线性表中数据元素之间存在着线性关系；并掌握在计算机中表示线性表中数据元素之间关系的两类不同存储结构——顺序存储结构和链式存储结构；顺序存储结构表示的线性表简称为顺序表，链式存储结构表示的线性表简称为链表。 2、在熟练掌握这两类存储结构的形式化定义与描述方法的基础上，掌握抽象数据类型定义方法；掌握线性表的各种基本操作的实现。 3、并掌握如何判断一个好的算法的估算方法；从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；

76 第二章 内 容 结 束