中国科学技术大学：《数据结构与数据库》课程教学资源（PPT课件讲稿）第二章 线性表

插入结点操作： 前插、后插 时间复杂度：前插0(n)、后插0(1) pre (a)插人到P之前(e必须知道p的前露pre) (b)梧入到P之后（不须知道P的前驱） ypb@ustc.edu.cn 16 中国科学技木大学

ypb@ustc.edu.cn 16 中国科学技术大学 时间复杂度：前插O(n)、后插O(1) 插入结点操作 ：前插、后插

删除结点操作时间复杂度On) suc 3 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 17 中国科学技术大学 删除结点操作 时间复杂度O(n)

单链表的其它操作举例 【例】逆序创建链表时间复杂度On) 化一b-c-应+奶 P ypb@ustc.edu.cn 18 中国科学技木大学

ypb@ustc.edu.cn 18 中国科学技术大学 【例】逆序创建链表 时间复杂度O(n) L ∧ e p d p c p b p b p ∧ 单链表的其它操作举例

逆置单链表时间复杂度0(n)* 逆置线性链表 a4 a2 L a1个 3 ypb@ustc.edu.cn 19 中国科学技术大学

ypb@ustc.edu.cn 19 中国科学技术大学 逆置单链表 时间复杂度O(n)* 逆置线性链表 s p L a1 a2 a3 a4 ∧ L ∧ p a1 ∧ s p a2 s p a3 s p a4

【例】以单链表表示线性表实现集合的并* void union L(LinkList &La,LinkList &Lb ) if (!La)(La Lb;return; 对比算法2.1 while Lb) s=Lb;Lb Lb->next: p=La; while(p&&p->data!=s>data){/查找 pre=p;p=p->next; //while if(p)delete s,/找到 else{pre->next=s;s>next=NULL;}/插入 /while /union L 时间复杂度OmXn) ypb@ustc.edu.cn 20 中国科学技术大学

ypb@ustc.edu.cn 20 中国科学技术大学 【例】以单链表表示线性表实现集合的并 * void union_L( LinkList &La, LinkList &Lb ) { if (!La) {La = Lb;return;} while ( Lb ) { s = Lb; Lb = Lb->next; p = La; while ( p && p->data != s ->data ) { //查找 pre = p; p = p->next; }//while if ( p ) delete s; //找到 else { pre->next = s; s->next = NULL;} //插入 }// while }// union_L 时间复杂度O(m×n) 对比算法2.1