第2章 线性表（三） 1/.

Presentation on theme: "第2章 线性表（三） 1/."— Presentation transcript:

1 第2章 线性表（三） 1/

2 2.7 线性表的应用 线性表的合并 有序表的合并 1 2

3 2.7.1 线性表的合并 问题描述： 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合 A=AB
2.7.1 　线性表的合并 问题描述： 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合 A=AB La=(7, 5, 3, 11) Lb=(2, 6, 3) La=(7, 5, 3, 11, 2, 6) .

4 【算法步骤】 依次取出Lb 中的每个元素，执行以下操作： 在La中查找该元素 如果找不到，则将其插入La的最后
.

5 【算法描述】 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)) ListInsert(&La,++La_len,e); }

6 2.7.2 　有序表的合并 问题描述： 已知线性表La 和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列. La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) .

7 【算法步骤】－有序的顺序表合并 (1) 创建一个空表Lc
(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) .

8 【算法描述】－有序的顺序表合并 else *pc++=*pb++; } T(n)=
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素 LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和 LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间 pc=LC.elem; //指针pc指向新表的第一个元素 pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素 pb_last=LB.elem+LB.length-1; //指针pb_last指向LB表的最后一个元素 while(pa<=pa_last && pb<=pb_last){ //两个表都非空 if(*pa<=*pb) *pc++=*pa++; //依次“摘取”两表中值较小的结点 else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; //LB表已到达表尾 while(pb<=pb_last) *pc++=*pb++; //LA表已到达表尾 }//MergeList_Sq T(n)= S(n)= O(ListLength(LA)+ ListLength(LB))

9 有序链表合并－－重点掌握 将这两个有序链表合并成一个有序的单链表。 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。 表中允许有重复的数据。

10 有序链表合并－－重点掌握 La 1 7 8 Lb 2 4 6 8 10 11 La 1 2 4 6 7 8 10 11 合并后

11 【算法步骤】－有序的链表合并 (1)Lc指向La
(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 (4) 释放 Lb 表的表头结点

12 有序链表合并（初始化） La 1 7 8 Lc = pc pa Lb 2 4 6 8 10 11 pb

13 有序链表合并( pa->data < ＝pb->data )
La(Lc ,pc) 1 7 8 pa Lb 2 4 6 8 10 11 pb pc->next = pa; 16:15

14 有序链表合并( pa->data < ＝pb->data )
La(Lc) 1 1 7 8 Pc Pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa; 16:15

15 有序链表合并( pa->data < ＝pb->data )
La(Lc) 1 1 7 8 Pc pa = pa->next; Pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa; 16:15

16 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 Pc pa Lb 2 4 6 8 10 11 pb pc->next = pb; 16:15

17 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 Pc pc= pb; pb pc->next = pb; 16:15

18 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 Pc pc= pb; pb =pb->next; pb pc->next = pb; 16:15

19 pc-> next=pa?pa:pb;
有序链表合并 La(Lc) 1 7 8 pa(NULL) 2 4 6 8 10 11 pc pb pc-> next=pa?pa:pb; 16:15

20 有序链表合并 合并后 La(Lc) 1 7 8 delete Lb; 2 4 6 8 10 11 16:15

21 【算法描述】－有序的链表合并 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; pc=Lc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb; pc=pb; pb=pb->next;} pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点} T(n)= S(n)= O(1) 16:15

22 思考：要求合并后的表无重复数据，如何实现？
La(Lc) 1 7 8 2 4 6 8 10 11 提示：要单独考虑 pa->data = =pb->data

23 2.8 案例分析与实现 案例2.1 ：一元多项式的运算 P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 10 5 -4
数组表示 （每一项的指数i隐含在其系数pi的序号中） P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 指数 （下标i） 1 2 3 4 系数p[i] 10 5 -4 Rn(x) = Pn(x) + Qm(x) 线性表R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn)

24 线性表P =((p1, e1), (p2, e2),…,(pm, em))
案例2.2 ：稀疏多项式的运算 多项式非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x （b）B(x) = 8x + 22x7 − 9x8 下标i 1 2 3 系数a[i] 7 9 5 系数 b[i] 8 22 -9 指数 17 线性表P =((p1, e1), (p2, e2),…,(pm, em)) 创建一个新数组c 分别从头遍历比较a和b的每一项 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项 指数不相同，则将指数较小的项复制到c中 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

25 链式存储结构 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 顺序存储结构存在问题 存储空间分配不灵活
运算的空间复杂度高 链式存储结构 typedef struct PNode { float coef;//系数 int expn; //指数 struct PNode *next; //指针域 }PNode,*Polynomial;   A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 -1 7 3 1 9 8 5 17 22 -9 A B

26 多项式创建---【算法步骤】 ① 创建一个只有头结点的空链表。 ② 根据多项式的项的个数n，循环n次执行以下操作： 生成一个新结点*s；
设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点； 指针q初始化，指向首元结点； 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q； 将输入项结点*s插入到结点*q之前。

27 多项式创建---【算法描述】 void CreatePolyn(Polynomial &P,int n)
{//输入m项的系数和指数，建立表示多项式的有序链表P P=new PNode; P->next=NULL; //先建立一个带头结点的单链表 for(i=1;i<=n;++i) //依次输入n个非零项 { s=new PNode; //生成新结点 cin>>s->coef>>s->expn; //输入系数和指数 pre=P; //pre用于保存q的前驱，初值为头结点 q=P->next; //q初始化，指向首元结点 while(q&&q->expn<s->expn) //找到第一个大于输入项指数的项*q pre=q; q=q->next; } //while s->next=q; //将输入项s插入到q和其前驱结点pre之间 pre->next=s; } //for }

28 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 pa pb -1 7 3 1 9 8 5 17 22 -9 A
3 1 9 8 5 17 22 -9 A B pa pb

29 多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 pa pb A -1 7 3 1 9 8 5 17
3 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb

30 多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 pa pb A -1 7 11 1 9 8 5
11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb

31 多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 pa pb A -1 7 11 1 9 8 5
11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb

32 A17(x) = 7 + 3x + 9x8 + 5x17 B8(x) = 8x + 22x7 − 9x8

33 多项式相加---【算法步骤】 ① 指针p1和p2初始化，分别指向Pa和Pb的首元结点。 ② p3指向和多项式的当前结点，初值为Pa的头结点。
③ 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1->expn与p2->expn），有下列3种情况： 当p1->expn等于p2->expn时，则将两个结点中的系数相加，若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点，若和为零，则删除p1和p2所指结点； 当p1->expn小于p2->expn时，则应摘取p1所指结点插入到“和多项式”链表中去； 当p1->expn大于p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去。 ④ 将非空多项式的剩余段插入到p3所指结点之后。 ⑤ 释放Pb的头结点。

34 polynomial AddPolyn(polynomial &pa, polynomial &pb) {
polynomial qc; /* 用来指向新链表的尾结点的　*/ polynomial qa; /* 指向第一个链表的当前结点 */ polynomial qb; /* 指向第二个链表的当前结点*/ polynomial temp; /* 删除结点时做临时变量用 */ ElemType a, b; /* 分别存放两个链表当前结点的数据 */ float sum; /* 存放两个链表中当前结点的系数和 */ qc = pa; qa = pa->next; qb = pb->next; while( qa && qb ) a = qa->data.expn; b = qb->data.expn; switch( cmp(a,b) ) 34/

35 qa->data.coef=sum;
case -1: /* 第一个链表中当前结点的指数值小 */ qc->next=qa; qc=qa; qa=qa->next; break; case 0: /* 指数值相等 */ sum = a.coef + b.coef; if( sum != 0.0) { qa->data.coef=sum; } else temp=qa; free(temp); 35/

36 case 1: /* 第一个链表中当前结点的指数值大 */ qc->next = qb; qc = qb;
temp = qb; qb = qb->next; free(temp); break; case 1: /* 第一个链表中当前结点的指数值大 */ qc->next = qb; qc = qb; } /* End of Switch */ } /* End of while(!qa && !qb) */ qc->next = qa?qa:qb; /* qa?qa:qb三目运算 */ free(pb); return (pa); } 36/

37 案例2.3 ：图书信息管理系统 实验1---基于线性表的图书信息管理系统

38 图书顺序表 图书链表

39 typedef struct {//顺序表 Book *elem; int length; } SqList; struct Book { char id[20];//ISBN char name[50];//书名 int price;//定价 }; typedef struct LNode {//链表 Book data; struct LNode *next; }LNode,*LinkList;

40 小结 1、掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。 2、熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。 16:15

41 小结 3、熟练掌握顺序表的查找、插入和删除算法 4、熟练掌握链表的查找、插入和删除算法
5、能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合 16:15

42 16:15 顺 序 表 链 表 空间 存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现闲置或溢出现象 存储密度
顺 序 表 链 表 空间 存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现闲置或溢出现象 存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1 需要借助指针来体现元素间的逻辑关系，存储密度小于1 时间 存取元素 随机存取，时间复杂度为O(1) 顺序存取，时间复杂度为O(n) 插入、删除 平均移动约表中一半元素，时间复杂度为O(n) 不需移动元素，确定插入、删除位置后，时间复杂度为O(1) 适用情况 ① 表长变化不大，且能事先确定变化的范围 ② 很少进行插入或删除操作，经常按元素序号访问数据元素 ① 长度变化较大 ② 频繁进行插入或删除操作 16:15

43 算法设计题 1. 设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转，且仍利用原表的存储空间。
1. 设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转，且仍利用原表的存储空间。　 【算法步骤】从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部 16:15

44 p q p q p q p L L  标志后继结点q 修改指针（将p插入在头结点之后） 重置结点p（p重新指向原表中后继） a1 a2
16:15

45 算法设计题 2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。 16:15

46 (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止
【算法步骤】 (1)Lc指向La (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后 (4) 释放 Lb 表的表头结点 16:15

47 第2题实现过程动态演示 q q pa pa pa La 12 23 34 45 56 q q pb pb Lb 11 32 43 48 54
∧ 32 43 48 54 Lc ∧ 16:15

48 算法设计题 3.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 【算法步骤】类似于求n个数中的最大数
可假设第一个结点最大，用指针pmax指向。 然后用pmax依次和后面的结点进行比较，发现大者则用pmax指向该结点。 这样将链表从头到尾遍历一遍时，pmax所指向的结点就是最大者。 其中的比较语句形式如下： if(p->data > pmax->data) pmax=p; 16:15

49 作业 使用C语言实现多项式加法运算。 实验一：线性表的操作及应用 49/