∥不带头结点 bool nhl<em)*: insert(const 2.3.2双链表 dink Elem tatem, LL: (double linked list) ∥带头结点 单链表的主要不足之处是: anakselem>(item, head): ink字段仅仅指向后继结点,不能 有效地找到前驱 fence>next: 双链表弥补了上述不足之处 righten++i Link<Elem>(tem, curr) return true; ■增加一个指向前驱的指针 return true: 真太血张写 大血张體 新有食究 双链表示意图 双链表及其结点类型的说明 truct DblListNode 双向链表 elem data first- aoa*… DblListNode *rlink: DblListNode *llink: struct Double list DbIListNode *first, *last CK cK 真太张铭写 北盒大管血歌张写 新究 插入过程(注意顺序) 删除过程 在P所指结点后面插入一个新结点 删除p所指的结点 □= q->rlink=p->rlink p->rlink=NULL 如果马上 q>link=p(注意,教材p-> rlink-link) Mlink=NULL 则可以不 p->rlinK=q bac> link->nK=q 真大带酱张储 新有,种究 北大管息歌张帖习4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 back next // 带头结点 // 不带头结点 template<class Elem> bool NHList<Elem>::insert(const Elem& item) { if (head == NULL) head = curr = tail = new Link<Elem>(item, NULL); else { Link<Elem>* temp = head; if (temp == curr) { head = new Link<Elem>(item, head); curr = head; } else { while(temp->next != curr) temp = temp->next; temp->next = new Link<Elem>(item, curr); curr = temp->next; } } rightcnt++; return true; } template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence->next); if (tail == fence) tail = fence->next; rightcnt++; return true; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 back next 2.3.2 双链表 (double linked list) „ 单链表的主要不足之处是： „ link字段仅仅指向后继结点，不能 有效地找到前驱 „ 双链表弥补了上述不足之处 „ 增加一个指向前驱的指针 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 back next 双链表示意图 first last a0 a1 an-1 双向链表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 back next 双链表及其结点类型的说明 struct DblListNode { ELEM data; DblListNode *rlink; DblListNode *llink; }; struct DoubleList { DblListNode *first，*last; }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 back next 插入过程（注意顺序） 在p所指结点后面插入一个新结点 p q q->rlink=p->rlink q->llink=p (注意，教材p->rlink->llink) p->rlink=q q->rlink->llink=q new q; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 back next 删除过程 „ 如果马上删除p „ 则可以不赋空 删除p所指的结点 p p->llink->rlink=p->rlink p->rlink->llink=p->llink p->rlink=NULL p->llink=NULL