数据结构与算法--线性表3.ppt

* 1 Pa!=ha or pa-exp!=-1 2 Pa-exp==0 3 Q-next=pa-next 4 Q-next 5 =pa-coef*pa-exp 6 -- 7 Pa 8 Pa-next 华中农业大学理学院 章 英 zy@ 数据结构与算法 第四讲 循环链表 本讲知识点： (1)了解循环链表的创建方法 (2)掌握双向链表的删除、插入操作 (3)了解链表的相关应用 重点：双向链表的操作 难点：链表的应用 重温约瑟夫环问题，是否可以用链表实现？ 提出问题 la.head 数据成员需要变化吗? 单链表和循环链表的区别 SimpleLinkListint la; la.head ^ la.head SimpleCircLinkListint la; 一、循环链表之初始化 template class ElemType void SimpleLinkListElemType::Init() // 操作结果：初始化循环链表 { head = new NodeElemType; head-next = head; } 约瑟夫环已经形成，如何报数离队？ 分析问题 假设：n=6 m=4 1 2 3 4 5 6 la.head 分析问题 第一轮 第二轮 4离队 2离队 1 2 3 5 6 la.head 1 3 5 6 la.head 分析问题 第三轮 第四轮 1离队 3离队 3 5 6 la.head 5 6 la.head 解决问题 // … … for (int i = 1; i n; i++) { for (int j = 1; j = m; j++) // 从1报数到m { position++; if (position la.Length()) position = 1; } la.Delete(position--, out); cout out ; } la.GetElem(1, winer); cout winer endl; 参见文件夹S2_5里的文件alg.h 判断指针是否指向最后一个结点的方法？ 思考： 单链表： 循环链表： tmpPtr-next == NULL ; tmpPtr-next == head ; 二、双向链表 定义：单链表的每个结点再增加一个指向其前趋的指针域 back，这样形成的链表有两条不同方向的链，称之为双（向）链表。 结点：DblNode 类：SimpleDblLinkList 双向链表结点结构 struct DblNode { ElemType data; DblNodeElemType * back; DblNodeElemType * next; //…… }; ?前驱方向 后继方向? back data next p == p-back-next == p-next-back 双向链表举例 p 双向链表结点的插入 5 9 7 p q ① ③ ④ ② newPtr-back = nextPtr-back newPtr-next=nexPtr 一条语句即： newPtr=new DblNodeElemType(e,tmpPtr,nextPtr); nextPtr-back-next = newPtr nextPtr-back=newPtr nextPtr tmpPtr newPtr 双向链表结点的删除 5 9 7 tmpPtr-back-next = tmpPtr-next tmpPtr-next-back = tmpPtr-back tmpPtr × × 归纳: 双向链表和单向链表相比，其优势何在？ 双向链表可以实现前驱遍历。 学会链表，为后续课程打下基础。 线段树、平衡树等，在区间统计上有很大的优势。 但是对大数据量的修改维护、删除操作，他们也力不从心。要快速的定位元素，最快速的实现方法是数组；要快速的移动大量连续的元素，最快速的实现方法是链表。 二者可以统一协调起来，即：块状链表。 课堂实战 1、假设一个单循环链表，其结点含有三个域back、data、next。其中data为数据域；back为指针域，它的值为空指针（NULL）；next为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999软考 五（10分）】 ∧ a ∧ b ∧ z ∧ …… 分析问题 la.head a