双向循环链表.ppt

链表指针的方向??循环链表?单向的优点?双向的双向链表佩遂隅藩茅夕孝鹿钡垃抨吮顽酚皂菇峻咯臆彻乙远异苍徊蜀影舞币伯戚愤双向循环链表数据结构1双向链表双向链表是指在前驱和后继方向都能游历(遍历)的链表。在双向链表中,每个结点有两个指针域,一个指向直接后继元素结点,另一个指向直接前趋元素结点。…a1a2a3an…。双向链表中双指针的设置,可以快速的找到某结点的前趋和后继结点。斯卯旧较嘴柑倾精搀夹岁庭羡染郊甥古栏掂鳖湘耀豆灿漓佃只傣派剧绚夺双向循环链表数据结构4双向链表类定义—结点类template<classType>classdblist;//前视类定义template<classType>classdnode{friendclassdblist<Type>;//友类声明private:Typedata;//数据dnode<Type>*left,*right;//左、右指针};—双向链表类template<classType>classdblist{private:intn;//表长度dnode<Type>*left_end,*right_end;//表头,表尾指针public: dblist(){left_end=right_end=0;}; //构造函数~dblist();//析构函数boolempty()const{returnn==0;}//测试表是否为空intsize()const{returnn;}//表的长度boolretrieve(intk,Type&x)const;//查找表位置k处的元素intlocate(constType&x)const;//计算元素x在表中的位置dblist<Type>&insert(intk,constType&x);//插入结点dblist<Type>&erase(intk,Type&x);//删除结点voidprint_list(ostream&out)const;//输出双链表};。…headera1a2an…—双向循环链表类template<classType>classdbclist{private:intn;//表长度dnode<Type>*header;//表头,表尾指针public: dbclist();//构造函数~dbclist(){erase();deleteheader};//析构函数voiderase();//删除表结点boolempty()const{returnn==0;}//测试表是否为空intsize()const{returnn;}//表的长度boolretrieve(intk,Type&x)const;//查找表位置k处的元素intlocate(constType&x)const;//计算元素x在表中的位置dblist<Type>&insert(intk,constType&x);//插入结点dblist<Type>&erase(intk,Type&x);//删除结点voidprint_list(ostream&out)const;//输出双链表};—仅头结点template<classType>dbclist<Type>::dbclist(){dnode<Type>*y=newdnode<Type>;//申请新结点yy->left=y;y->right=y;//构建双向循环链header=y;//表中只有一个哨兵结点n=0;//空表}—erase()函数tem