dnode.h

安全数组 普通链表 哈希表 二叉搜索树 AVL树 集合类 通用自动机 所有类均使用模板编写

/* 双向节点
 * 
 */

#ifndef DOUBLY_LINKED_NODE_CLASS
#define DOUBLY_LINKED_NODE_CLASS

#include <stdlib.h>

template <class T>
class DCLinkedList;

template <class T>
class DNode
{
private:
	// 指向左、右节点的指针
	DNode<T> *left;
	DNode<T> *right;

public: 
	// data 为公有成员 
	T data;
        
	// 构造函数
	DNode(void); 
	DNode (const T& item);
             
	// 改变表的方法
	void InsertRight(DNode<T> *p);
	void InsertLeft(DNode<T> *p);
	DNode<T> *DeleteNode(void);
        
	// 取得指向左、右方向节点的指针
	DNode<T> *NextNodeRight(void) const;
	DNode<T> *NextNodeLeft(void) const;
		
	friend class DCLinkedList<T>;
};

// 创建空表并保留数据成员未定义，用于 header，“哨位”节点
template <class T>
DNode<T>::DNode(void)
{
	// 初始化节点使其指向自身
    left = right = this;
}

// 创建空表并初始化数据
template <class T>
DNode<T>::DNode(const T& item)
{
	// 建立一个指向自身的节点并初始化 data 域
    left = right = this;
    data = item;
}
        
// 将节点 p 插入到双向链表中当前节点的右边
template <class T>
void DNode<T>::InsertRight(DNode<T> *p)
{
	// 将 p 和当前节点的右后继节点相连
    p->right = right;
	right->left = p;
	
 	// 将 p 的左边和当前节点相连
    p->left = this;
    right = p;
}

// 将节点 p 插入到当前节点左边
template <class T>
void DNode<T>::InsertLeft(DNode<T> *p)
{
	// 将 p 和当前节点的左后继节点相连
    p->left = left;
    left->right = p;
    
 	// 将 p 的右边和当前节点相连
    p->right = this;
    left = p;
}

// 从链表中删除当前节点并返回其地址
template <class T>
DNode<T> *DNode<T>::DeleteNode(void)
{
	// 左边的节点必须链接到当前节点的右边
    left->right = right;
    
	// 右边的节点必须链接到当前节点的左边
    right->left = left;
    
    // 返回当前节点的指针
    return this;
}

// 返回指向右边节点的指针
template <class T>
DNode<T> *DNode<T>::NextNodeRight(void) const
{
    return right;
}

// 返回指向左边节点的指针
template <class T>
DNode<T> *DNode<T>::NextNodeLeft(void) const
{
    return left;
}

#endif	// DOUBLY_LINKED_NODE_CLASS