北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第二章 线性表、栈和队列

单链表结点类型以及变量说明 struct listnode eleM data ListNode x link; typedef listNode listPtr; Listptr first last back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 16

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 back next 单链表结点类型以及变量说明 struct ListNode { ELEM data； ListNode * link; }; typedef ListNode * ListPtr; ListPtr first, last;

单链表插入算法 ∥插入数据内容为 value的新结点,为第个结点 ListNode Insert(ELEM value, int i)t ListNode p,*q; p= FindIndex(i-1); if (p== null) return NULL; q= new ListNode;∥需要时才new q->link=p->link; I-data=value; p->link=q if( q->link NULL last=g: return gB back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 17

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 back next 单链表插入算法 // 插入数据内容为value的新结点, 为第i个结点。 ListNode * Insert(ELEM value, int i) { ListNode *p，*q; p = FindIndex(i-1); if (p == NULL ) return NULL; q = new ListNode; // 需要时才new q->link = p->link; q->data = value; p->link = q; if(q->link == NULL ) last=q; return q; }

不带头结点vs带头结点 nead curn tail 不 202311215 带 头 head curR tail 结 20 2310+12151 点 head fence tail 带 头 20 23 12 15 结 head fence taiN 点亡+2021+101216z back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 18

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 back next 20 23 10 12 15 15 不带头结点 head curr tail 20 23 12 15 head curr tail 20 23 12 带头结点 head fence tail 20 23 12 15 head fence tail 10 不带头结点 vs 带头结点

∥不带头结点 template <class Elem> bool NHList<Elem>::insert(const Elem& item)t if (head NULL head=cur〓tail=new Link<Elem>(item, NULL; else Link< Elem>* temp head ∥带头结点 if (temp = curr)t ea new template <class Elem> Link<Elem>(item, head); bool LList<Elem>::insert(const curr= head Elem& item)t fence->next= new Link<Elem>(item, fence->next); else t if (tail = fence) while(temp->next!= curr) temp temp->next; tail s fence->next temp->next= new righten++i Link<Elem>(item, curr)i return true: curr= temp->next righten++ return true back } exo 北京大学信息学院张铭编写 版权所有,转载或翻印必究 19

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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; }

2.3.2双链表 (double linked list) 单链表的主要不足之处是: link字段仅仅指向后继结点,不能 有效地找到前驱 双链表弥补了上述不足之处 增加一个指向前驱的指针 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 20

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 back next 2.3.2 双链表 (double linked list) „ 单链表的主要不足之处是： „ link字段仅仅指向后继结点，不能 有效地找到前驱 „ 双链表弥补了上述不足之处 „ 增加一个指向前驱的指针