双向循环链表精选.ppt

链表指针的方向？ 双向链表 双向链表 是指在前驱和后继方向都能游历(遍历)的链表。 在双向链表中，每个结点有两个指针域，一个指向直接后继元素结点,另一个指向直接前趋元素结点。 双向链表结点结构 双向链表结构 双向链表中有指向头结点和尾结点的两个指针left_end和right_end。 双向链表中双指针的设置，可以快速的找到某结点的前趋和后继结点。 双向链表类定义—结点类 template <class Type> class dblist; //前视类定义 template <class Type> class dnode { friend class dblist<Type>; //友类声明 private: Type data; //数据 dnode<Type> *left, *right; //左、右指针 }; 双向链表类定义—双向链表类 template <class Type> class dblist { private: int n; //表长度 dnode<Type> *left_end, *right_end; //表头,表尾指针 public: dblist ( ) {left_end=right_end = 0;}; //构造函数 ~dblist ( ); //析构函数 bool empty( ) const {return n==0;} //测试表是否为空 int size( ) const {return n;} //表的长度 bool retrieve(int k, Type& x) const; //查找表位置k处的元素 int locate(const Type& x) const; //计算元素x在表中的位置 dblist<Type>& insert(int k, const Type& x); //插入结点 dblist<Type>& erase(int k, Type& x); //删除结点 void print_list(ostream& out) const; //输出双链表 ｝； 双向循环链表 双向链表通常采用带表头结点的循环链表形式。 双向循环链表类定义—双向循环链表类 template <class Type> class dbclist { private: int n; //表长度 dnode<Type> *header; //表头,表尾指针 public: dbclist ( ); //构造函数 ~dbclist ( ) {erase();delete header}; //析构函数 void erase(); //删除表结点 bool empty( ) const {return n==0;} //测试表是否为空 int size( ) const {return n;} //表的长度 bool retrieve(int k, Type& x) const; //查找表位置k处的元素 int locate(const Type& x) const; //计算元素x在表中的位置 dblist<Type>& insert(int k, const Type& x); //插入结点 db