wex9_32.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

template <class T>
class DNode
{
    private:
    	// circular links to the left and right
        DNode<T> *left;
        DNode<T> *right;
    public: 
    	// data is public 
        T data;
        
		// constructors
        DNode(void); 
        DNode (const T& item);
        
        
        // list modification methods
        void InsertRight(DNode<T> *p);
        void InsertLeft(DNode<T> *p);
        DNode<T> *DeleteNodeRight(void);
        DNode<T> *DeleteNodeLeft(void);
        DNode<T> *DeleteNode(void);
        
        
        // obtain address of the next node to the left or right
        DNode<T> *NextNodeRight(void) const;
        DNode<T> *NextNodeLeft(void) const;
};

// constructor that creates an empty list and
// leaves the data uninitialized. use for header
template <class T>
DNode<T>::DNode(void)
{
	// initialize the node so it points to itself
    left = right = this;
}

// constructor that creates an empty list and initializes data
template <class T>
DNode<T>::DNode(const T& item)
{
	// set node to point to itself and initialize data
    left = right = this;
    data = item;
}
        
// insert a node p to the right of current node
template <class T>
void DNode<T>::InsertRight(DNode<T> *p)
{
	// link p to its successor on the right
    p->right = right;
	right->left = p;
	
 	// link p to the current node on its left
    p->left = this;
    right = p;
}

// insert a node p to the left of current node
template <class T>
void DNode<T>::InsertLeft(DNode<T> *p)
{
	// link p to its successor on the left
    p->left = left;
    left->right = p;
    
 	// link p to the current node on its right
    p->right = this;
    left = p;
}

// unlink the current node from the list and return its address
template <class T>
DNode<T> *DNode<T>::DeleteNode(void)
{
	// node to the left must be linked to current node's right
    left->right = right;
    
	// node to the right must be linked to current node's left
    right->left = left;
    
    // return the address of the current node
    return this;
}

// return pointer to the next node on the right
template <class T>
DNode<T> *DNode<T>::NextNodeRight(void) const
{
    return right;
}

// return pointer to the next node on the left
template <class T>
DNode<T> *DNode<T>::NextNodeLeft(void) const
{
    return left;
}

template <class T>
DNode<T> *DNode<T>::DeleteNodeRight(void)
{
	// save address of node to be deleted
    DNode<T> *tempPtr = right;
    			
    if (right == this)
        return NULL;	// if we point to ourselves, return

	// current node points to successor of tempPtr.
    right = tempPtr->right;
 	// successor of tempPtr points back to curr node.
    tempPtr->right->left = this;
    return tempPtr; 
}

template <class T>
DNode<T> *DNode<T>::DeleteNodeLeft(void)
{
	// save address of node to be deleted
    DNode<T> *tempPtr = left;
    			
    if (left == this)
        return NULL;	// if we point to ourselves, return

	// current node points to successor of tempPtr.
    left = tempPtr->left;
 	// successor of tempPtr points back to curr node.
    tempPtr->left->right = this;
    return tempPtr; 
}

// Print list moving right.
template <class T>
void PrintList(DNode<T> *header)
{
	DNode<T> *p;
	
	p = header->NextNodeRight();
	do
	{
		cout << p->data << "  ";
		p = p->NextNodeRight();
	} while (p != header);
	cout << endl;
	
}

void main(void)
{
	DNode<int> dlist, *p, *q;
	int i;
	
	// create a circular doubly linked list with data values
	// 1, 2, 3, I, 9,10
	p = &dlist;
	for(i=1;i <= 10;i++)
	{
		q = new DNode<int>(i);
		p->InsertRight(q);
		p = q;
	}
	
	PrintList(&dlist);
	
	// move 7 positions into the list to the right
	for(p = &dlist, i=0;i < 7;i++)
		p = p->NextNodeRight();
	// delete the nodes to the left and right of p
	p->DeleteNodeLeft();
	p->DeleteNodeRight();

	PrintList(&dlist);
}

/*
<Run>

1  2  3  4  5  6  7  8  9  10  
1  2  3  4  5  7  9  10  
*/