带表头结点的单链表 表头结点位于表的最前端,本身不 带数据,仅标志表头。 设置表头结点的目的是统一空表与 非空表的操作,简化链表操作的实 现 非空表 空表
带表头结点的单链表 ◼ 表头结点位于表的最前端，本身不 带数据，仅标志表头。 ◼ 设置表头结点的目的是统一空表与 非空表的操作，简化链表操作的实 现。 非空表 空表 first a1 an 0 first 0
在带表头结点的单链表第一个结点前插入新结点 first- p newnode newnode first=0 first- 插入p newnode newnode newnode->link=p->link if(p->link- NULL last- newnode; p->link=newnode
在带表头结点的单链表第一个结点前插入新结点 newnode->link = p->link; if ( p->link == NULL ) last = newnode; p->link = newnode; first newnode first newnode 插入 first newnode 0 first newnode 0 插入 p p p p
从带表头结点的单链表中删除第一个结点 first 非空表 first p q q=p->link; first-+ p->link=q->link delete first if (p->link-- NULL last=p; q(空表)
q = p->link; p->link = q->link; delete q; if ( p->link == NULL ) last = p; 从带表头结点的单链表中删除第一个结点 first first (非空表） first first 0 (空表） 0 p q p q
单链表的模板类 类模板将类的数据成员和成员函数 设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中,增加了 表头结点
单链表的模板类 ◼ 类模板将类的数据成员和成员函数 设计得更完整、更灵活。 ◼ 类模板更易于复用。 ◼ 在单链表的类模板定义中，增加了 表头结点
用模板定义的单链表类 template <class Type> class List template <class Type> class ListNode i friend class List<Type>; Type data; ∥/结点数据 Listnode<Type>lik;∥结点链接指针 ublic. ListNode():link(NULL){}∥构造函数 ListNode( type& item data (item), link (NULLf
用模板定义的单链表类 template <class Type> class List; template <class Type> class ListNode { friend class List<Type>; Type data; //结点数据 ListNode<Type> *link; //结点链接指针 public: ListNode ( ) : link (NULL) { } //构造函数 ListNode ( Type& item ) : data (item), link (NULL) { }