数据结构与算法.ppt

文档介绍：数据结构与算法
-
链表的游标类(Iterator)
游标类主要用于单链表的搜索。
游标类的定义原则:
Iterator类是List类和ListNode类的友元类。
Iterator对象引用已有的List类对象。
Iterator类有一数据成员current,记录对单链表最近处理到哪一个结点。
Iterator类提供若干测试和搜索操作
表示链表的三个类的模板定义

enum Boolean { False True };
template <class Type> class List;
template <class Type> class ListIterator;
template <class Type> class ListNode {
friend class List <Type>;
friend class ListIterator <Type>;
public:
………
private:
Type data;
ListNode<Type> *link;
};
template <class Type> class List {
public:
………
private:
ListNode<Type> *first, *last;
};
template <class Type> class ListIterator {
public:
ListIterator ( const List<Type> & l )
: list (l), current () { }
//构造函数: 引用链表 l, 表头为当前结点
Boolean NotNull ( );
//检查链表中当前指针是否非空
Boolean NextNotNull ( );
//检查链表中下一结点是否非空
Type *First ( );
//返回链表表头指针
Type *Next ( );
//返回链表当前结点的下一个结点的地址
private:
const List<Type> & list; //引用已有链表
ListNode<Type> *current; //当前结点指针
}
链表的游标类成员函数的实现
template <class Type>
Boolean ListIterator<Type>::NotNull ( ) {
//检查链表中当前元素是否非空
if ( current != NULL ) return True;
else return False;
}
template <class Type>
Boolean ListIterator<Type>::NextNotNull ( ) {
//检查链表中下一元素是否非空
if ( current != NULL &&
current→link != NULL ) return True;
else return False;
}
template <class Type>
Type *ListIterator<Type>::First ( ) {
//返回链表中第一个结点的地址
if ( →link != NULL )
{ current = ; return current; }
else { current = NULL; return NULL; }
}
template <class Type>
Type *ListIterator<Type>::Next ( ) {
//返回链表中当前结点的下一个结点的地址
if ( current != NULL
&& current→link != NULL ) {
current = current→link;
return current;
}
else { current = NULL; return NULL; }
}
利用游标类(iterator)计算元素的和
int sum ( const List<int> &l ) {
ListIterator<int> li (l); //定义游标对象
if ( ! ( ) ) return 0;
int retvalue = * ( ); //第一个元素值
while ( ( ) ) //链表未扫描完
retvalue += * ( ); //累加
return retvalue;
}
静态链表结构利用数组定义,运算
过程中存储空间大小不变
分配节点: j = avil;