23链表( inked list 令单链表 first指向特殊的头结点 双链表 ■引入头结点有利于特殊情况的处理 ①循环链表 空链表 链表头 i按照c/C++数组下标编号的规则 从0到n-1 链表的第0个结点为frst>link 真太血张写 大血张體 新有食究 单链表的存储结构 单链表结点类型以及变量说明 单链表 struct ListNode f{a{aa-…tamz eleM data 空的单链衰 istNode link data字段 link字段 typedef ListNode listPtr; ListPtr first, las 中ack bacK 真太张铭写 北盒大管血歌张写 新究 单链表插入算法 不带头结点vs带头结点 插入数据内容为 value的新结点,为第个结 istNode* Insert(ELEM value, int i)i 2四212sz p= FindIndex(i-l) 0位121 if (p- NULL )return NULL q· new List 口圆回 q->link- NULL) 不带头结点带头结点 return q: 120231012i Back 真大带酱张储 新有,种究 北大管息歌张帖习3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 back next 2.3 链表(linked list) „ 单链表 „ 双链表 „ 循环链表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 back next „ first指向特殊的头结点 „ 引入头结点有利于特殊情况的处理 „ 空链表 „ 链表头 „ i按照C/C++数组下标编号的规则 „ 从0到n-1 „ 链表的第0个结点为first->link 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 back next 单链表的存储结构 first a0 a1 a2 an-1 last 单链表 空的单链表 first last data字段 link字段 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 back next 单链表结点类型以及变量说明 struct ListNode { ELEM data； ListNode * link; }; typedef ListNode * ListPtr; ListPtr first, last; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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 带头结点