循环链表
1 |
|
和单链表区别:
主要是构造的时候进行尾部连接头部:
1、构造函数中 添加head->next=head;
2、复制构造函数和重载=号函数中增加Lhead=L.getHead();用while(p1!=Lhead)来判别循环表结束 最后增加p2->next=head; 为末尾添加head连接;
3、 前插法构造不需要变化,后插法需要在最后增加p2->next=head; 为末尾添加head连接;
其他函数有需要遍历的,判断结束条件改变为!=head即可:
4、置空函数makeEmpty()获取表长函数getLength()查询数据函数Search(T x)获取第i个元素的地址函数Locate(int i)删除元素函数Remove(int i,T &x)判空函数isEmpyty()
输出函数output()只需要变化判断结束条件head->next!=head
5、 返回指针类若遍历后找不到,则返回NULL,因为循环链表最后元素的下一个指向为head而不是NULL 不能用最后的指向代替 。若不修改,会影响调用的判断
双向链表(带附加头结点的循环链表形式 )
1 |
|
双向循环链表和单链表的区别:
1、结点中有前驱和后驱两个连接指针
2、构造函数中需要对前指针后指针赋头节点值 head->right=head->left=head;
3、前插法创建和后插法:均需要四步。注意分析。
4、 置空函数需要添加左指向为head
5、按顺序查找并返回地址进行判断添加。之后其他函数如获取数据等直接调用即可
6、插入函数Insert需要多一种第0个元素后插入的条件,即空表插入的条件。
7、删除函数Remove由于是双向链表,所以不用再找第i-1个了 判断也不需要考虑第i-1个是最后一个了。
8、复制构造函数和重载=号,需要清空链表,构造使用后插法则4步即可