清华大学：《数据结构及其应用》课程教学资源（PPT课件讲稿）双向循环链表

调查结果 讲课进度 偏快 27人 适中 20人 偏慢 2人 课程难易 太简单 偏难 太繁 人人人 讲解方法: 多讲理论、原理、方法,少讲具体程序 7人 少讲理论,多讲程序和C++内容 6人 多讲具体应用的完整实例 4人 其他 规定交作业时间,促进学生做作业 作业太多,要少而精; 最好能现场编程、调试; 2021220

2021/2/20 1 调查结果： 讲课进度： 偏快 27 人 适中 20 人 偏慢 2 人 课程难易： 太简单 1 人 偏难 9 人 太繁 1 人 讲解方法： 多讲理论、原理、方法，少讲具体程序 7 人 少讲理论，多讲程序和C＋＋内容 6 人 多讲具体应用的完整实例 4 人 其他： 规定交作业时间，促进学生做作业； 作业太多，要少而精； 最好能现场编程、调试；

双向链表( Doubly Linked List) 如果在一个应用问题中经常要求检测指针向前驱和后继方向移动 为保证移动的时间复杂度达到最小,就必须采用双向链表表示。 双向链表的结点结构: 左链指针数据右链指针 前驱结点 ILink data rLink 后继结点 template class DbINode private pe data DbINode* ILink, *rLink, 2021220

2021/2/20 2 双向链表（Doubly Linked List） 如果在一个应用问题中经常要求检测指针向前驱和后继方向移动， 为保证移动的时间复杂度达到最小，就必须采用双向链表表示。 双向链表的结点结构： 前驱结点 后继结点 template class DblNode { private: Type data; DblNode * lLink, * rLink; } lLink data rLink 左链指针 数据 右链指针

带头结点的双向循环链表 first eo}er-…er current first 空表 游标结点:* current 游标结点的前驱结点:*( current-> ILink) 游标结点的后继结点:*( current-> rLink) 2021220

2021/2/20 3 带头结点的双向循环链表： 空表 游标结点：* current 游标结点的前驱结点：* ( current -> lLink ) 游标结点的后继结点：* ( current -> rLink ) e0 e1 en-1 … current first first

双向循环链表的类定义: template class dbIlist DbIlist( Type unique Val ) DblList() int Length(const int IsEmpty (i return first->rLink--first int Find( const Type target) Type getData()const void Firster(f current-first;) int First( int Next(; int Prior ( int operator!(i return current!=NULL, void Insert( const Type value void Remove() private DbINode * first, *current 2021220

2021/2/20 4 双向循环链表的类定义： template class DblList { public: DblList ( Type uniqueVal ); ~DblList ( ); int Length ( ) const; int IsEmpty ( ) { return first ->rLink==first ;} int Find ( const Type & target ); Type getData ( ) const; void Firster ( ) { current = first; } int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) { return current != NULL;} void Insert ( const Type & value ); void Remove ( ) ; private: DblNode * first, * current; }

2021220

2021/2/20 5