双向循环链表.ppt

《双向循环链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、链表指针的方向？2.7双向链表单链表？循环链表？单向的优点？双向的双向链表1双向链表双向链表是指在前驱和后继方向都能游历(遍历)的链表。在双向链表中，每个结点有两个指针域，一个指向直接后继元素结点,另一个指向直接前趋元素结点。2.7双向链表2双向链表结点结构结点图示存储数据元素存储后继结点地址存储前驱结点地址数据域data左指针left右指针right2.7双向链表3双向链表结构…a1a2a3an…2.7双向链表left_endright_end双向链表中有指向头结点和尾结点的两个指针left_end和right_end。双向链表中双指针的设置，可以快速的找

2、到某结点的前趋和后继结点。4双向链表类定义—结点类templateclassdblist;//前视类定义templateclassdnode{friendclassdblist;//友类声明private:Typedata;//数据dnode*left,*right;//左、右指针};2.7双向链表5双向链表类定义—双向链表类templateclassdblist{private:intn;//表长度dnode*left_end,*right_end;//表

3、头,表尾指针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&insert(intk,constType&x);//插入结点dblist&erase(

4、intk,Type&x);//删除结点voidprint_list(ostream&out)const;//输出双链表｝；2.7双向链表6双向循环链表双向链表通常采用带表头结点的循环链表形式。…headera1a2an…非空表2.7双向链表空表header7双向循环链表类定义—双向循环链表类templateclassdbclist{private:intn;//表长度dnode*header;//表头,表尾指针public:dbclist();//构造函数~dbclist(){erase();deleteheader};//

5、析构函数voiderase();//删除表结点boolempty()const{returnn==0;}//测试表是否为空intsize()const{returnn;}//表的长度boolretrieve(intk,Type&x)const;//查找表位置k处的元素intlocate(constType&x)const;//计算元素x在表中的位置dblist&insert(intk,constType&x);//插入结点dblist&erase(intk,Type&x);//删除结点voidprint_list(ostream&ou

6、t)const;//输出双链表};2.7双向链表8构造函数—仅头结点templatedbclist::dbclist(){dnode*y=newdnode;//申请新结点yy->left=y;y->right=y;//构建双向循环链header=y;//表中只有一个哨兵结点n=0;//空表}空表headery2.7双向链表9析构函数—erase()函数templatevoiddbclist::erase(){dnode*current;//当前结点dnod

7、e*next;//下一结点if(header==0)return;//已是空表current=header->right;//current初始化while(!empty()){//若表非空则依次删除表中结点next=current->right;deletecurrent;n--;//n实际控制循环次数current=next;}}2.7双向链表headera1a2an……currentnextcurrentnextcurrentnextcurrent10基本思想:从第1个结点开始依次向后扫描，直到找到位置k上的元素，并存于x中，且返回ture

8、，位置k无效返回false。查找位置k元素并存于x中